Задачи выпуклого программирования

Задача математического программирования

Выпуклая задача оптимизации

Задача (1.1) называется выпуклой, если X – выпуклое множество, f – выпуклая функция на X.

Теорема 1.8. Если задача (1.1) выпукла, то любое ее локаль­ное решение является также глобальным.

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

Второе свойство выпуклых задач можно высказать в виде сле­дующего общего принципа: необходимые условия при соответствующих предположениях выпуклости оказываются и достаточными.

Теорема 1.9. Пусть функция f выпукла на Rⁿ и дифференци­руема в точке х* Î Rⁿ. Если f'(х*) = 0, то х* – точка минимума f на X, т. е. решение задачи (1.5).

Полученные свойства выпуклых задач имеют важное значение не только в теории, но и в численных методах оптимизации. Дело в том, что большинство существующих численных методов позво­ляет, вообще говоря, находить лишь локальные решения, а точнее, стационарные точки задачи. Теоремы 1.8, 1.9 говорят о том, что для выпуклой задачи отыскание стационарной точки автоматически означает отыскание решения, причем глобального.

Укажем еще одно полезное свойство выпуклых задач.

Теорема 1.10. Пусть задача (1.1) выпукла и имеет решение. Тогда множество ее решений выпукло (рис. 1.7, а). Если при этом f строго выпукла на X, то решение задачи единст­венно, т. е. X* состоит из одной точки (рис. 1.7, б).

Рис.1.7. Выпуклость множества решений выпуклой задачи оптимизации

Задача (1.1) называется задачей математического программирования, если ее допустимое множество имеет вид

,

т.е. задается системой конечного числа неравенств и уравнений, рассматриваемых, вообще говоря, на некотором множестве Р Ì Rⁿ. Иными словами, задачу математического программирования можно записать в виде

f(x) ® min,

g_i(x) £ 0, i = 1, …, k, (1.21)

g_i(x)= 0, i = k+1, …, т, x Î P.

При этом условия типа g_i(x) £ 0 называются ограничениями-нера­венствами, типа g_i(x)= 0 – ограничениями-равенствами, оба этих типа условий — функциональными ограничениями; условие x Î P носит название прямого ограничения.

Классическая задача на условный экстремум является частным случаем задачи математического программирова­ния, когда ограничения-неравенства и прямое ограничение отсут­ствуют.

Деление ограничений задачи математического про­граммирования на функциональные и прямые условно. Например, в задаче (1.21) можно исключить ограничения-равенства путем вве­дения их в прямое ограничение, т.е. перейти к задаче вида

f(x) ® min,

g_i(x) £ 0, i = 1, …, k, x Î P',

где . Исключение всех функциональных ограничений лишь возвращает нас к задаче вида (1.1). То или иное представление задачи определяется целями исследова­ния. Однако, как правило, чем подробнее описаны функциональные ограничения задачи, тем детальнее удается изучить ее свойства. Обычно в качестве Р берется множество «простой» структуры, напри­мер координатный параллелепипед

,

причем здесь не исключается, что a_j = -¥ или b_j = +¥ (координаты могут уходить в бесконечность) при тех или иных j.

При геометрической интерпретации задач математического про­граммирования используются те же приемы, о которых шла речь выше. В дополнение к этому следует лишь отметить, что при изобра­жении области, определяемой ограничением-неравенством g_i(x) £ 0,указывается линия уровня g_i(x) = 0 и может ставиться знак «–» с той ее стороны, где g_i(x) £ 0, и знак «+» - с противоположной.

Пример 1.5. Пусть дана задача

f(x) = x₂ ® min,

, , .

Ее геометрической интерпретацией служит рис.1.8. Отсюда видно, что решением задачи является «нижняя» точка пересечения окруж­ности g₁(x) = 0 и прямой g₃(x) = 0, т.е. .

Укажем важный под­класс задач математического программирования. Задача (1.21) назы­вается задачей выпуклого программирования, если множество Р выпукло, функции f, g₁, ..., g_k выпуклы на Р, функции g_k+1, ..., g_m линейны (см. (1.19)).

Легко проверить, что задача из примера 1.5 является задачей выпуклого программирования. Приведем два содержательных при­мера задач этого типа.

Пример 1.6 (задача поиска). Объект, подлежащий обнаруже­нию, находится в одном из п районов с вероятностями р₁, ..., р_п соответственно. Для поиска объекта имеется общий ресурс вре­мени Т. Известно, что при поиске в i-м районе в течение времени t_i, вероятность обнаружения объекта (при условии, что он там нахо­дится) равна , где a_i > 0 – заданное число. Требуется так распределить время наблюде­ния по районам, чтобы максимизировать вероятность обнаружения объекта. Соответствующая задача оптимизации имеет вид

,

,

t_i ³ 0, i = 1, …, n.

Нетрудно проверить, что целевая функция задачи вогнута по t = (t₁, …, t_n). Переходя к минимизации этой функции, взятой с обратным знаком, получаем задачу выпуклого программирования.