Постановка задачи оптимизации

Глава 4. Математические модели оптимизации

Замечания 3.1.

1.Функцию f(x) называют выпуклой, если она целиком лежит не выше отрезка, соединяющего две ее произвольные точки. Функцию называют строго выпуклой, если она целиком лежит ниже отрезка, соединяющего две ее произвольные, но не совпадающие точки.

2.Если функция сильно выпуклая, то она одновременно строго выпуклая и выпуклая. Если функция строго выпуклая, то она одновременно выпуклая.

3.Выпуклость функции можно определить по матрице Гессе:

· Если H(x) ³ 0 "x Î Rⁿ, то функция выпуклая;

· Если H(x) > 0 "x Î Rⁿ, то функция строго выпуклая;

· Если H(x) ³ lE "x Î Rⁿ, где Е- единичная матрица, то функция сильно выпуклая.

Отметим важное свойство выпуклой функции. Если функция f выпукла на множестве X, то для любых точек x₁, x₂,..., x_mÎX и произвольных неотрицательных чисел l₁+l₂+...l_m=1 имеет место неравенство Иен Сена

f(l₁x₁ + l₂x₂ +...+ l_mx_m) £ l₁f(x₁) + l₂f(x₂) +...+ l_mf(x_m).

При m=2 это неравенство совпадает с неравенством (3.1) из определения выпуклой функции.

Сама по себе постановка задачи оптимизации проста и естественна: заданы множество Х и функция ¦(x),определённая на х, требуется найти точки минимума или максимума функции ¦ на х. Задачу на минимум запишем в виде:

(4.1)

При этом ¦ будем называть целевой функцией, х - допустимым множеством, любой элемент хÎХ – допустимой точкой задачи (4.1). Если х совпадает со всем пространством , задача 4.1 называется задачей безусловной минимизации (без ограничений), в противном случае - задачейусловной минимизации (с ограничениями).

Ограничения подразделения:

а) на линейные (I, II) и нелинейные (III, IV) (рис.4.1);

б) детерменированные (А, В) и стахостатические (группы кривых С_j) (рис.4.2).

Стохастические ограничения являются всевозможными, вероятными, случайными.

Необходимо подчеркнуть, что само понятие точки минимума, т.е. решения задачи (4.1), неоднозначно и требует уточнения.

Точка х*ÎХ называется:

1) точкойглобального минимума функции ¦ на множестве Х или глобальным решением задачи (4.1), если

(х), при "хÎХ; (4.2)

2) точкой локального минимума ¦ на Х или локальным решением задачи (4.1), если существует числотакое, что

(х), при всех ; (4.3)

где - замкнутый шар радиусас центром в х*.

¦(x) ¦(x) ¦(x)

1

0 x0 x0 х₂ х

а) б)

х

Рис. 4.3 Произвольная кривая с двумя локаль- Рис.4.4 Одномерные унимодальные функции нымии одним глобальным минимумами.

Таким образом, глобальный минимум - это наименьший из всех локальных минимумов. На рис. 4.3 показаны точки локальныхи глобального минимумов для произвольной кривой ¦(x).

Задача оптимизации, в которой критерий оптимальности ¦(x) имеет в области Х единственный локальный минимум, называется одноэкстремальной (унимодальной) задачей оптимизации. Простейшими из унимодальных функций являются выпуклые функции (рис. 4.4.а).

На рис.4.4 приведены примеры унимодальных одномерных функций.

Задача оптимизации, в которой критерий оптимальности ¦(х) имеет несколько локальных минимумов, называется многоэкстремальной задачей оптимизации.

Обычные методы решений много экстремальных задач обеспечивают нахождение лишь отдельной особой точки, в которой частная производная . Такой точкой в зависимости от случайных обстоятельств (выбор начального приближения) может быть любой из локальных минимумов или точка перегиба. В связи с этим существенное значение имеет исследование условий, при которых решение обеспечивает нахождение глобального минимума.

Если неравенство в (4.2) или (4.3) выполняется как строгое при х¹х*, то говорят, что х* -точка строгого минимума (строгое решение) в глобальном или локальном смысле. Ясно, что глобальное решение является и локальным; обратное неверно.

Для отражения того факта, что точка х*ÎХ является точкой глобального минимума функции ¦ на Х, будем использовать запись:

или эквивалентная ей запись

При этом говорят, что точка х* реализует величину ,т.е. минимальное значение функции ¦ на Х. Множество всех точек глобального минимума ¦ на Х обозначим через

.

Таким образом, Argmin¦(x)-это просто произвольная точка из множества .

При необходимости задачу минимизации можно заменить задачей максимизации или наоборот. Это объясняется тем, что минимум функции ¦ равен максимуму функции –¦, взятому с противоположным знаком, и достигаются оба эти экстремума при одних и тех же значениях переменных (рис.4.5). В точке х* min¦(x*)= -max(-¦(x*)) .

y=¦(x)

} min¦(x)

0 max¦(x){ x*. х

y= -¦(x)

Рис.4.5 К постановке задачи оптимизации.

Таким образом, если, например, задачу минимизации функции при каких-либо ограничениях требуется заменить задачей максимизации, то достаточно вместо взять в качестве целевой функцию -, найти максимум этой функции и заменить его знак на противоположный. Полученное значение будет оптимумом исходной задачи. По анологии с (4.1) будем записывать задачу максимизации функции ¦ на множестве Х в виде:

, хÎХ (4.4)

Решения задач (4.1) и (4.4), т.е. точки минимума и максимума функции ¦ на Х называют также точками экстремума, а сами задачи (4.1) и (4.4)-экстремальными задачами.