Раздел 2. Задачи безусловной оптимизации

Замкнутое и одновременно ограниченное множество в метрическом пространстве (в пространстве Rⁿ с заданным на нем понятием расстояния) называется компактным. Компактное множество называется выпуклым, если для любых , 0 ≤ a ≤ 1. То есть выпуклое множество В кроме всех своих точек содержит и все их выпуклые комбинации. Это означает, что вместе с допустимыми x¹ и x² допустимы и их смеси. Гладкой называется функция, которая в области своего определения имеет производные, то есть является дифференцируемой.

Функция f дважды дифференцируема, если для всех i,j=1,…,n существуют частные производные от частных производных, то есть

Симметричная относительно диагонали nxn- матрица называется матрицей Гессе. Задача нахождения максимального или минимального значения заданной функции на заданном множестве называется экстремальной. Имеется два вида экстремальных задач - задача на максимум и задача на минимум. Символически они записываются так:

(2.1)

Оптимальным решением задач (2.1) называется пара (x*,f (x*)), где x* - точка максимума (минимума), а f(x^*)- значение функции f в этой точке, то есть ее максимальное (минимальное) значение на множестве Х.

Решение задачи (2.1) требует разрешения трех проблем: 1) проблему существования оптимального решения; 2) проблему установления необходимых и достаточных признаков оптимальности (то есть характерных свойств, присущих точкам максимума и минимума); 3) проблему численного вычисления оптимальных решений. В задачах (2.1) применяются экстремальные точки двух видов: локальный максимум (минимум) и глобальный максимум (минимум). Точка называется точкой локального максимума (минимума), если

f(x⁰) ≥ f(x) (f(x⁰) ≤f(x)) для всех , где - ε-окрестность точки x⁰. Точка называется точкой глобального максимума (минимума), если эти неравенства выполняются для всех . Достаточное условие существования оптимальных решений задач (2.1) содержится в следующем утверждении.

Теорема (Вейерштрасса). Для того, чтобы в задаче (2.1) существовала точка глобального максимума (минимума), достаточно, чтобы допустимое множество X было компактно в R_n, а целевая функция f непрерывна на X.
Ввиду сложности проверки ограниченности множества X, применяется следствие из этой теоремы.

Следствие (теоремы Вейерштрасса). Если функция f непрерывна на R_n и

то f достигает своего глобального минимума в любом замкнутом подмножестве X пространства R_n.

Признаки оптимальности приведем в случае, когда в (2.1)X

. В этом случае задачи (2.1) принимают вид:

(2.2)

и называются задачами безусловной оптимизации.

Чтобы точка была точкой локального экстремума в задачах (2.2) необходимо, чтобы

(2.3)

Все точки x⁰, удовлетворяющие условию (2.3) , называются стационарными точками (точки подозрительные на экстремум).

Чтобы x⁰ была точкой локального максимума (минимума) в задаче (2.2) необходимо и достаточно, чтобы

и (2.4)

для всех . Здесь матрица Гессе функции f в точке x⁰ , а - скалярное произведение.

Известно, что дважды дифференцируемая на выпуклом множестве Х функция f вогнута (выпукла) тогда и только тогда, когда для любых векторов и справедливо условие (2.4) . Матрица будет отрицательно (положительно) полуопределенной в точке x⁰ , если

(2.5)

для всех k =1,…,n. Здесь символом обозначен минор k-го порядка матрицы :

где - определитель порядка k * k, вычисляемый в точке x⁰ .

Если в (2.5) неравенства строгие, то получаем необходимое и достаточное условие отрицательной (положительной) определенности матрицы Гессе в точке x⁰ . Условие (2.5) называется критерием Сильвестра для знакоопределенных матриц.

Поскольку условия (2.4) труднопроверяемы, то при проверке необходимых условий оптимальности в задачах (2.2) применяют критерий Сильвестра.

Следовательно, при помощи условий (2.3) - (2.5) можно предложить следующий алгоритм решения задач (2.2) :

вычислить все стационарные точки (найти все решения уравнения (2.3) );

выяснить характер экстремума стационарных точек (с использованием условий (2.4) - (2.5) ), для чего применить критерий Сильвестра;

среди всех точек локального максимума (минимума) найти точки глобального максимума (минимума), сравнивая значение функции f в этих точках.

Пример решения

Определить максимальное значение функции двух переменных и оптимальные значения переменных

f(x,y) = x³ + y² – 6xy - 39x + 18y +100

Берём производные по переменным, приравниваем их значения нулю и решаем систему

f_x' = 3x² - 6y - 39 = 0;

f_y^' = 2y - 6x + 18 = 0;

x² - 2y - 13 = x² - (3x - 18) - 13 = x² - 3x + 5 = 0

x₁ = 1, y₁ = -6; x₂ = 5, y₂ = 6;

A = f_xx^'' = 6x; B = f_yy^” = 2; C = f_xy^” = -6;

Если A*B – C² < 0 , то анализируемая точка - точка перегиба.

Если A*B – C² > 0 и А > 0, то в анализируемой точке функция минимальна.

Если A*B – C² > 0 и А < 0, а B > 0, то в анализируемой точке функция максимальна.

В примере точка М = (1, -6) - точка перегиба, так как A*B - C² = 6*1*2 - 36 < 0;

а точка М = (5, 6) - точка минимума, так как A*B – C² = 6*5*2 - 36 > 0;

Варианты заданий

1 2x³ + 2y² – 9xy - 27x + 12y +100

2 x³ + 3y² – 6xy - 28x + 21y +150

3 2 x³ + 4y² – 9xy - 21x + 18y +100

4 x³ + 5y² – 6xy - 39x + 21y +150

5 x³ + 2y² – 9xy - 27x + 12y +100

6 2x³ + y² – 9xy - 29x + 21y +150

7 x³ + 2y² – 6xy - 21x + 18y +100

8 2x³ + y² – 6xy - 39x + 12y +100

9 x³ + y² – 9xy - 27x + 18y +150

10 2x³ + y² – 6xy - 21x + 21y +100

11 x³ +2 y² – 9xy - 39x + 18y +100

12 2x³ + y² – 9xy - 27x + 21y +150

13 x³ + y² – 6xy - 21x + 18y +100

14 2x³ + 2y² – 9xy - 27x + 21y +100

15 x³ + 2y² – 6xy - 39x + 18y +100

16 2x³ + y² – 9xy - 21x + 21y +150

17 x³ + 2y² – 6xy - 27x + 18y +100

18 x³ + 2y² – 9xy - 27x + 18y +100

19 2x³ + y² – 6xy - 39x + 21y +150

20 x³ + 2y² – 9xy - 39x + 18y +100

21 x³ + 2y² – 6xy - 27x + 21y +150

22 2x³ + y² – 9xy - 27x + 18y +100

23 x³ + 2y² – 6xy - 39x + 21y +100

24 2x³ + 3y² – 6xy - 39x + 21y +150

25 x³ + 4y² – 7xy - 39x + 21y +200

26 x³ + 2y² – 8xy - 39x + 21y +100

27 2x³ + 2y² – 9xy - 39x + 21y +150

28 x³ + 3y² – 7xy - 39x + 21y +200

29 2x³ + 2y² – 9xy - 39x + 21y +100

30 x³ + 2y² – 6xy - 39x + 21y +150

31 x³ + 2y² – 6xy - 39x + 21y +200

32 x³ + 2y² – 6xy - 39x + 21y +100

33 x³ + 2y² – 6xy - 39x + 21y +150

34 x³ + 4y² – 8xy - 39x + 21y +200

35 2x³ + y² – 6xy - 39x + 21y +100

36 x³ + 2y² – 6xy - 39x + 21y +150

37 x³ + 3y² – 9xy - 39x + 21y +200

38 2x³ + 4y² – 6xy - 39x + 21y +100

39 x³ + 5y² – 6xy - 39x + 21y +150

40 x³ + 6y² – 6xy - 39x + 21y +200

41 x³ + 5y² – 9xy - 39x + 21y +100

42 2x³ + 4y² – 6xy - 39x + 21y +150

43 x³ + 6y² – 9xy - 39x + 21y +200

44 2x³ + 6y² – 6xy - 39x + 21y +100

45 x³ + 6y² – 9xy - 39x + 21y +150

46 x³ + 4y² – 6xy - 39x + 21y +200

47 x³ + 3y² – 6xy - 39x + 21y +100

48 2x³ + 6y² – 9xy - 39x + 21y +150

49 x³ + 6y² – 6xy - 39x + 21y +200

50 2x³ + 5y² – 9xy - 39x + 21y +100

51 x³ + 6y² – 6xy - 39x + 21y +150

52 x³ + 4y² – 9xy - 39x + 21y +200

Поиск по сайту: