Локализация и необходимые условия оптимальности

Задачу вида (1.4) будем называть исходной. Здесь 1(у), критерий оптимальности, определен на любом элементе множества допустимых решений D, у* — оптимальное решение, если оно существует, Г = = Ну*) — значение исходной задачи.

Один из подходов к получению решения сводится к использованию необходимого условия: «Если х* — лучший элемент D, то он заведомо не хуже любого из элементов подмножества L (x*) с D».

L (x*) включает в себя х* и еще некоторые элементы D. Его называют множеством сравнения. Множество сравнения выбирают так, чтобы из неравенства.

вытекали расчетные соотношения, позволяющие найти на D все элементы х-, которые им удовлетворяют. Таких элементов, претендующих на оптимальность, меньше, чем элементов D, а иногда «претендент» вообще единственный.

Переход к множеству сравнения L (x*) от множества D называют локализацией исходной задачи (1.4), а соотношения, вытекающие из (1.8), —условиями локальной неулучшаемости. Чем «шире» множество сравнения, тем меньше «претендентов» выделяют необходимые условия (они «сильнее»), но тем труднее как правило найти из этих условий X*.

Пример 1.1.x — скаляр, D — отрезок [0, 1], 1(х) — непрерывная и гладкая функция. Множество сравнения — все значения х, отличающиеся от х* не более чем на сколь угодно малое е.

Условие локальной неулучшаемости.

Из (1.9) следует, что если 8х имеет любой знак, то [ — | =0; если х* = 0,.

а значит, 8х> 0, то (— | <0; еслих* = 1, то 5×0. Когдах —.

vd*A*= о вектор, то из тех же условий следует требования к градиенту / в точке х'.

Множество сравнения в этом примере было выбрано столь малым, что на нем Дх) сколь угодно точно можно было приблизить линейной функцией. Но при этом необходимо было ограничить класс функций Дх) непрерывными и непрерывно дифференцируемыми.

В ряде случаев по всем или по некоторым переменным множество L (x*) можно расширить и выделить на нем х* условиями типа максимума. О таких задачах речь пойдет ниже. Соответствующие условия оптимальности называют условиями в форме «принципа максимума».

Любые необходимые условия формулируют так: «Если х* — оптимальное решение, то … (выполнены те или иные условия)». В ряде случаев нельзя заранее утверждать, что решение существует. Тогда оговаривают его существование «Если оптимальное решение х* существует, то …».

Достаточные условия имеют обратную формулировку: «Если по отношению к х* выполнены некоторые условия, то это оптимальное решение» (т. е. х* может быть оптимальным решением и в том случае, когда достаточные условия не выполнены).

Схема Лагранжа

В задаче условной оптимизации об экстремуме функции многих переменных/о (у) с наложенными на них ограничениями вида/(у) = 0 наличие связей между переменными существенно осложняет решение.

Лагранж предложил для этой задачи способ трансформации к задаче без ограничений с критерием L (y, X) =f₀(y) + А/(у). Он писал: «Если ищется максимум или минимум некоторой функции многих переменных при условии, что между этими переменными имеется связь, задаваемая одной или несколькими функциями, то нужно прибавить к функции, экстремум которой ищется, функции, задающие уравнения связи, умноженные на неопределенные множители, и затем искать максимум или минимум построенной суммы [ее называют функцией Лагранжа], как если бы переменные были независимы. Полученные уравнения, присоединенные к уравнениям связи, послужат для определения всех неизвестных».

Таким образом, Лагранж предлагал сначала найти максимум у* (X) функции L, потом подставить эту зависимость в уравнение/(у* (Я)) = О и найти значение неопределенного множителя. К сожалению, далеко не всегда получившееся уравнение имеет действительный корень. Ниже будет показано, что «принцип максимума Лагранжа» не всегда справедлив, максимуму/минимуму исходной задачи может соответствовать вовсе не максимум/минимум функции Лагранжа, а ее точка стационарности или, если решение лежит на границе, локально-неулучшаемая точка.