Исследование методов штрафных функций

      (1.11) 

     В силу регулярности (f ¢i(x*),h) = 0 и (g¢j(x),h) < 0, а по теореме 7.2 mj**³ 0 при j Î J(x*). Поэтому (1.11) влечет равенство m** = Q. Но тогда (1.5) означает, что 

       

     что вместе с линейной независимостью f ¢i(x*)дает равенство l** = Q. Противоречие.

     Таким образом l0**¹ 0. Положим теперь l*i= li**/l0**(i = 1, ..., k),  

       

     Очевидно  теперь, (1.10) выполняется автоматически, а (1.9) тривиально получается из (1.5).

 

     1.5 Достаточные условия,  существование, единственность 

     Ситуация  с задачей (1.1)–(1.3) несколько отличается от изучавшихся ранее, поскольку минимумы здесь могут быть двух типов. В случае, когда в точке минимума x* нет активных ограничений, т. е. J(x*) = Æ, ситуация полностью аналогична описанной в предыдущем параграфе, поскольку ограничения-неравенства в окрестности точки x* можно опустить (смотри рисунок 3а). В случае же, когда J(x*) ¹ Æ минимум может достигаться на границе множества W и точка x* может не быть стационарной точкой (смотри рисунок 3б).

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

     Теорема (достаточные  условия минимума). Пусть f0, f, g Î C2, а x* — допустимая точка такая, что для некоторых l* Î Rk и m* Î Rl, одновременно не равных нулю, выполнены условия (9)–(10) и при любых h Î Rm, h ¹ Q таких, что

     нелинейный  программирование алгоритм последовательность

     (f ¢i(x*),h) = 0 при i = 1, ..., k;

     (g¢j(x*),h) = 0 при j Î J(x*), m*j> 0;

     (g¢j(x*),h) ³ 0 при j Î J(x*), m*j= 0 

     выполнено неравенство (L¢¢xx(x*,l*, m*)h, h) > 0. Тогда x* — локальное решение задачи (1)–(3). 

     1.6 Об ограничениях-равенствах 

     С целью упрощения изложения, начиная  с этого момента, мы будем рассматривать  задачу условной оптимизации, содержащую только ограничения-неравенства. Это, с одной стороны, не снижает общности изложения, поскольку ограничения-равенства сводятся к ограничениям-неравенствам: ограничение  

     f(x) = Q 

     эквивалентно  ограничениям  

     f(x) £ Q, -f(x) £ Q. 

     С другой стороны, задачи с ограничениями-равенствами  мы уже достаточно подробно рассматривали выше.

     Здесь, правда, следует помнить об одном  важном обстоятельстве. При решении  задач с ограничениями-неравенствами  часто бывает важна (существенно используется) выпуклость функций, фигурирующих в задаче, вернее, выпуклость минимизируемой функции f0 и выпуклость множества W допустимых точек. Последнее гарантируется выпуклостью функций gj в ограничениях-неравенствах. Множества же, выделяемые ограничениями-равенствами, не бывают выпуклыми, за исключением случая аффинных функций fi. Поэтому методы решения задач условной оптимизации, существенно использующие "выпуклость задачи" могут применяться к задачам с ограничениями-равенствами с большой осторожностью.

     Напомним, что множество W Ì Rm называется выпуклым, если "(x, y Î W, l Î [0, 1])[lx + (1 - l)y Î W].  

     1.7 Еще один достаточный признак условного минимума 

     Напомним, что точка (x*, l*) называется седловой точкой функции L: W1×W2 ® R (W1 Ì Rm, W2 Ì Rl), если при всех (x, l) Ì W1×W2 выполнены неравенства

     L(x*, l) £ L(x*, l*) £ L(x, l*) 

     Теорема. Пусть (x*, l*) — седловая точка функции Лагранжа L: Rm×Rl+® R задачи (1), (3) (здесь Rl+= {l Î Rl: l і Q}), l* і Q, x* — допустимая точка. Тогда x* — глобальное решение этой задачи.

     Доказательство. Пусть x — произвольная допустимая точка, т. е. gi(x) £ 0 (i = 1, ..., l). Тогда  

     f0(x*) + (l*, g(x*)) = L(x*, l*) £ L(x, l*) = f0(x) +(l*, g(x)).(1.12) 

     Покажем, что  

     (l*, g(x*)) = 0.(1.13) 

     Тогда из (12), поскольку l* і Q, а g(x) £ Q, будет следовать нужное неравенство f0(x*) £ f0(x). Для доказательства (1.13) заметим, что по условию теоремы L(x*, Q) £ L(x*, l*), т. е.  

     (l*, g(x*)) ³ 0.(1.14) 

     Равенство (1.13) вытекает теперь из (14), т.к. l* і Q, а g(x*) £ Q.

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

     Однако, если функции f0 и gi (i = 1, ..., l) выпуклы, а множество W содержит хотя бы одну внутреннюю точку, то условия доказанной теоремы являются необходимыми и достаточными (это утверждение называется теоремой Куна — Таккера; оно является центральным фактом теории выпуклого программирования).

 

      2. МЕТОДЫ ШТРАФНЫХ ФУНКЦИЙ

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

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

     К параметрическим методам относятся: метод последовательной безусловной оптимизации, предложенный Фиакко и Маккормиком, метод Зангвилла и др.

     В непараметрических методах целевая  функция рассматривается как  функция, задающая дополнительное искусственное  ограничение, постепенно уплотняемое по мере получения новой информации о ходе решения задачи.

     Параметрические методы подразделяются на: 1) методы внутренней точки; 2) методы внешней точки; 3) комбинированные  методы.

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

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

     минимизировать 

      ,

       (2.1) 

     при ограничениях  

      ,

      , .  

     В основу штрафных функций положено преобразование задачи (2.1)-(2.3) в задачу минимизации без ограничений вида  

      (2.4)  

     где - штрафная функция;

       - весовые коэффициенты;

      , - некоторые функционалы.

     Выбирая вид функционала  , руководствуются следующими вариантами: 

       при . 

     Для чего необходимо, чтобы точка x всегда была внутренней точкой, т.е. чтобы выполнялось условие ,  

       при . 

     При таком выборе функционала  оперируют только с внешними точками, для которых выполняется условие  

       при и при . 

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

     При выборе функционала для ограничений-равенств вводится требование при . При этом обычно полагают . Наконец, при любом выборе функционалов , требуется, чтобы  

      ,

      ,

       .   

     2.1 Метод барьерных  поверхностей 

     Метод барьерных поверхностей относится  к группе методов внутренней точки и основан на использовании барьерной поверхности вида 

      ,(2.7) 

     где   - параметр, значения которого убывают с каждой итерацией при ;

       - положительные весовые коэффициенты.

     При этом барьерная функция (поверхность) неограниченно возрастает при .

     Примерами барьерных функций являются:

     а) обратная функция  

      (2.8) 

     б) логарифмическая функция  

      . 

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

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

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