5.3 Классические способы отыскания решения экстремальных задач

Вспомним, какие алгоритмы поиска экстремума функции нам известны.

Рассмотрим простейшую задачу о поиске минимума дифференцируемой функции на отрезке. Пусть — скалярная функция скалярного аргумента , заданная на отрезке . Требуется найти минимальное значение на . Алгоритм, который дает для решения этой задачи классический математический анализ заключается в следующем:

1. вычислить производную ;

2. найти все решения , ,..., уравнения =0 (стационарные точки);

3. вычислить значения , ,..., , , ;

4. выбрать среди этих значений минимальное.

Уже в простейшем случае возникает ряд вопросов. Как решать уравнение =0: не будет ли эта задача столь же сложна, как и основная проблема поиска экстремума? Что делать, если стационарных точек , ,..., очень много, или даже бесконечное многожество? Как организовать перебор и сравнение значений?

Еще сложнее обстоит дело с функциями нескольких переменных. Пусть — замкнутое подмножество , — функция переменных, заданная на множестве . Для того чтобы найти минимальное значение на множестве , классический математический анализ рекомендует

1. найти все решения , ,..., уравнения =0;

2. вычислить значения функции в этих точках;

3. вычислить все значения в границе множества ;

4. выбрать из указанных значений максимальное.

Очевидно, что даже если удается легко выполнить пп. 1, 2, то выполнить п. 3 практически невозможно. Таким образом, классический математический анализ не дает общего рецепта — для каждой задачи необходимо искать собственный метод решения. В задачах о поиске экстремума функции на некотором множестве , заданном системой равенств, наиболее распространенный метод исследования — метод множителей Лагранжа — состоит в отыскании стационарных точек функции Лагранжа.

Как поступают в классическом случае, например для следующей задачи: найти максимальное значение функции

=

на множестве ={ }?

Для решения задачи строят функцию Лагранжа

= + .

Затем отыскивают точки безусловного экстремума как стационарные точки функции Лагранжа:

= ; = ; = .

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

5.4Условие регулярности

Будем предполагать, что для задачи выпуклого программирования справедливо следующее условие: для каждого существует такая точка  , что ( ). Это условие эквивалентно следующему, которое принято называть условие регулярности Слейтера: существует такая точка  , что > .

53. Доказать эквивалентность двух условий регулярности.

5.5Функция Лагранжа. Условия оптимальности

Рассмотрим -мерный вектор = .

32. Функцию = +< , >, где , вектор  , называют функцией Лагранжа основной задачи выпуклого программирования.

33. Седловой точкой функции на множестве ,  , называется пара ( , ) , что для всех ,  выполнено

105. .

(105) можно записать в виде:

106. .

Последнее соотношение часто используется в теории матричных игр и характеризует седловую точку рассматриваемой игры: минимакс равен максимину.

31. (о достаточных условиях оптимальности задачи выпуклого программирования). Если пара ( , ) является седловой точкой функции Лагранжа на множестве ,  , то — оптимальная точка основной задачи выпуклого программирования (102).

ДОКАЗАТЕЛЬСТВО. Из определения функции Лагранжа и (105) получим:

107. = +< , > +< , > +< , >.

Из левого неравенства следует, что для любого 

108. < , >< , >,

а поскольку  и это неравенство справедливо для любого  ,то 0.

В частности, при =0 имеем: < , >=0. Если  , то по определению 0, поэтому для всех  будет

109. < , >0.

Поскольку (107) справедливо и для всякого , то получаем для всех  :

> +< , > .

Так как  (ибо  и 0), то получаем, что допустимый план является оптимальным.