Тема 2. Задача нелинейного программирования (продолжение) (стр. 4 )

В силу выпуклости множества X имеем В силу вогнутости f(х) имеем при

Поэтому в силу f(x1) > f(x0) имеем f(x(α)) > f(x0) при α > 0, . Поскольку в любой окрестности x0 имеется точка x(α) с α > 0, то получили противоречие с утверждением о том, что в x0 имеется локальный максимум f(х).

Теорема доказана.

Теорема 3.7. Если при выполнении условий теоремы 3.6 функция f(х) строго вогнута, то глобальный максимум является единственным.

Доказательство. Пусть глобальный максимум не является единственным, то есть имеются две несовпадающие точки глобального максимума f(х) на множестве X, которые мы обозначим через x(1) и x(2). В силу теоремы 3.5 весь отрезок [x(1), x(2)] принадлежит множеству X* глобальных максимумов. Но это противоречит строго выпуклости функции f(х), состоящей в том, что

при любом .

2.4.  Необходимые и достаточные признаки существования решения

2.4.1.  Необходимый признак условного локального максимума для задач с выпуклыми функциями ограничений. Как мы видели, условие Якоби носит локальный характер: его выполнение зависит от рассматриваемой точки. При некотором сужении класса допустимых множеств (когда все функции, описывающие функциональные ограничения, выпуклы) локальное условие Якоби удается заменить на глобальное условие (не зависящее от рассматриваемых точек) – условие Слейтера, которое состоит в следующем.

Условие Слейтера

Существует такая допустимая точка , в которой все нелинейные (функциональные) ограничения выполняются как строгие неравенства .

В этом случае необходимые условия наличия локального максимума в точке выглядят следующим образом.

Теорема (необходимые условия Куна-Таккера для выпуклого случая)

Пусть в задаче нелинейного программирования

1) функции непрерывно дифференцируемы в некоторой окрестности точки ;

2) функции , выпуклы (в частности, линейны);

3) выполнено условие Слейтера.

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

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

Пример 4

В данном случае все функции непрерывно дифференцируемы, допустимое множество выпукло (рис. 1), но функция выпуклой не является. Условие Слейтера выполняется – взять, хотя бы, точку (0;0). Однако в точке максимума М(1;0) условие Куна-Таккера не выполняется: , т. е. разложение не возможно.

Рис. 1. Пример невыполнения условия Куна-Таккера в задаче, в которой допустимое множество выпукло и выполняется условие Слейтера

Замечание 2. Требование выполнения условия Слейтера в теореме существенно.

Пример 5

Все условия теоремы, за исключением выполнения условия Слейтера, выполняются. Допустимое множество в этой задаче состоит из одной точки (1;1), в которой, естественно, и будет максимум целевой функции. Однако и разложение не возможно.

Пример 6

Все условия теоремы, за исключением выполнения условия Слейтера, выполняются. Допустимое множество в этой задаче состоит из одной точки (2;1), в которой, естественно, и будет максимум целевой функции (рис. 2). Однако , и разложение не возможно.

Рис. 2. Пример существенности требования выполнения условия Слейтера

Тем не менее, нельзя утверждать, что если условие Слейтера не выполняется, то в точке максимума не будет выполняться условие Куна-Таккера (в этом случае оно может не выполняться, но может и выполняться). Так, если в примере 4 заменить целевую функцию на , получим в точке максимума (1;0), как и во всех точках максимума разложение .

Замечание 3. Условие Слейтера не равносильно наличию в допустимом множестве внутренней точки: наличие внутренней точки еще не говорит о выполнении условия Слейтера. Более того, условие Слейтера в теореме нельзя заменить на наличие внутренней точки в допустимом множестве.

Пример 7

В данной задаче все условия теоремы, за исключением выполнения условия Слейтера, соблюдаются (функция выпукла, правда, не строго). Более того, допустимое множество представляет собой треугольник, изображенный на рис. 1. Но так же, как и в примере 4, в точке максимума (1;0) условие Куна-Таккера не выполняется, поскольку .

2.4.2. Достаточный признак для задач выпуклого программирования

Теорема 3 (достаточное условие глобального максимума для задач выпуклого программирования)

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

Замечание. Выпуклость функций в данном случае можно заменить на более слабое условие (следствие) – выпуклость допустимого множества.

Поясним смысл сформулированного утверждения иллюстрацией для случая одного активного ограничения.

 

Иллюстрация достаточности условий Куна-Таккера в задаче выпуклого программирования для случая

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