Выпуклая функция нелинейного программирования

§1. Общий подход к решению задач нелинейного программирования.

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

Задача нелинейного программирования (задача НП) в общем виде формулируется следующим образом :

где хотя бы одна из функций f, ₁, ₂. _m нелинейна.

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

1) в определении внутри допустимого множества всех стационарных точек функции f, удовлетворяющих условию =0; j=1,2,…, n;

2) определении той стационарной точки, которая доставляет наибольшее значение функции f внутри области;

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

4) нахождении наибольшего значении функции f в вершинах области;

5) нахождении глобального максимума функции f.

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

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

Определение I. Множество называется выпуклым, если отрезок, соединяющий любые две точки множества, также принадлежит этому множеству. Ниже приводятся графические примеры выпуклых (a) и невыпуклых (b) множеств. ( рис. 1)

сякая точка Р отрезка, соединяющего точки Р₁, Р₂, выражается через эти точки следующим образом:

Каждой точке отрезка соответствует определенное значение λ. Равенство называется выпуклой комбинацией точек Р₁ и Р₂. Поэтому можно дать другое определение выпуклого множества: множество называется выпуклым, если оно содержит любую выпуклую комбинацию любых двух точек Р₁ и Р₂, из этого множества.

Определение II. Функция f называется выпуклой на заданном выпуклом множестве, если выполняется следующее неравенство:

Ниже изображена выпуклая функция Z= f (x₁, x₂) (рис. 2).

ричем M₁ = f (P₁), M₂ = f (P₂), M = f (P). Согласно определению выпуклой функции можно записать

Неравенство означает, что все точки поверхности функции, соответствующие отрезку Р₁, Р₂, лежат не ниже отрезка М₁М₂. Если функция выпуклая, то такое свойство будет выполняться обязательно.

Определение III. Функция f называется вогнутой на заданном выпуклом множестве, если выполняется следующее неравенство:

На рис. 2 изображена вогнутая функция Z= f (x₁, x₂). Причем M₁ = f (P₁), M₂ = f (P₂),

= f (P). Согласно определению вогнутой функции можно записать

Неравенство означает, что все точки поверхности функции, соответствующие отрезку Р₁Р₂, лежат не выше отрезка М₁М₂. Для вогнутых функций такое условие выполняется всегда.

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

1.Сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая) функция.

2.Локальный максимум строго выпуклой функции является ее глобальным максимумом и достигается в единственной точке выпуклого множества, в котором задана функция (рис. 3)

3. Локальный минимум строго вогнутой функции является ее глобальный минимум и достигается в единственной точке выпуклого множества, в котором задана функция (рис. 3)

4. Если выпуклая ( вогнутая) функция не имеет экстремума, то она достигает наименьшего и наибольшего значения на границе выпуклой области ( рис. 4)

5.Если функции _i (x₁, x₂,…, x_n); i=1,2,…,m — выпуклые (вогнутые), то множество, образуемое условиями

Источник

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

,

где Ф(Х) – выпуклая функция,D – выпуклое не пустое ограниченное и замкнутое множество. Напомним, что по определению выпуклая функция является непрерывной.

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

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

Теорема 1. ЕсливнутренняяточкамножестваD является точкой локального минимума в задаче выпуклого программирования, то в этой точке функцияФ(Х) достигает свой глобальный минимум.

Доказательство.Положим, что в точкефункцияФ(Х) не достигает наименьшего во множествеD значения. Тогда существует точка, для которой. Рассмотрим сечение,. Функциядостигает в точкенаибольшее значение. Действительно, поскольку.

Это значит, что существует окрестность точкии некотороетакие, что

. Но тогда , что противоречит условию теоремы●

Из теоремы следует, что во всех точках локального минимума выпуклая функция имеете одинаковые значения.

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

.

Рисунок 1 — К примеру 1

Теорема 2. ФункцияФ(Х), строго выпуклая на выпуклом множестве, имеет в этом множестве одну точку минимума (глобального)●

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

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

. (1)

Необходимость. Рассмотрим сечениефункцииФ(Х). Функцияопределена на отрезке [0,1], имеет в точкелокальный минимум и дифференцируема в этой точке. Следовательно(равенство нулю имеет место в том случае, когда точкаявляется внутренней точкой множестваD). По правилу дифференцирования сложной функции

.

Достаточность. Пусть в точкевыполнено неравенство (1). Рассмотрим сечениефункцииФ(Х), гдеX– произвольная точка из множестваD. ПосколькуФ(Х) выпукла во множествеD, то функциятакже выпукла на отрезке [0,1]. Кроме того, из неравенства (1) следует, что. Это означает, что— неубывающая отрезке [0,1] функция, т.е.. Последнее неравенство означает, чтои в точкефункцияФ(Х) принимает наименьшее в областиD значение●

Теорему 3 иллюстрирует рисунок 2.

Рисунок 2 — К теореме 2

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

Линии уровня на рисунке 2 получены с помощью следующей MATLAB-программы:

Заметим, что если точка является внутренней точкой множестваD, то условие (1) эквивалентно условию. Таким образом, условие (1) можно рассматривать как обобщение необходимого условия минимума.

Источник

REVIZED / 11_Выпуклое_программирование!

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

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

(1)

, (2)

. (3)

Нам понадобятся некоторые вспомогательные построения в пространстве векторов . Вектор из первых компонент точки будем обозначать через . Итак, .

Для задачи (1) – (3) определим множество

,

где .

Лемма. Для задачи выпуклого программирования (1) – (3) множество выпукло.

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

,

.

Из полученных неравенств и вытекает выпуклость множества .

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

Доказательство. Поскольку достаточность этого условия уже доказана для произвольной задачи нелинейного программирования (см. теорему 2.6 введения), осталось доказать только необходимость.

Необходимость. Пусть – решение задачи (1) – (3). Положим . Очевидно, что , так как , и .

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

Итак, . Согласно лемме множество выпукло. Следовательно, выполняются все требования теоремы 8.2. Поэтому существует ненулевой

вектор опорный в точке ко множеству :

. (4)

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

Легко увидеть, что при любом векторы включаются во множество . Тогда из (4) имеем:

. (5)

Покажем, что . Пусть это не так. Тогда . Следовательно, . По условию Слейтера существует вектор такой, что . Поэтому . Полученное противоречие и означает, что .

Обозначим . Покажем, что построенный вектор представляет собой искомый вектор множителей Лагранжа. Очевидно, что и из (5) получаем

. (6)

Отсюда при следует

. (7)

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

. Отсюда и из (7) следует, что в точке выполняется условие дополняющей нежесткости:

. (8)

,

(9)

Далее, пусть . Тогда . Отсюда и из (8) получаем неравенство

.

. (10)

Неравенства (9), (10) и означают, что – седловая точка функции Лагранжа задачи выпук-

лого программирования. Что и требовалось.

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

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

. (11)

Доказательство следует непосредственно из теоремы 6.5 и определения конуса опорных векторов в точке ко множеству .

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

, (12)

.

Доказательство. Покажем, что условия (12) и (13) эквивалентны включению (11). Пусть точка такова, что . Тогда и .

Пусть теперь . Тогда из теорем 2 и 10.5 следует, что необходимым и достаточным условием экстремума является существование таких множителей , , для которых . Положим для всех и получим из последнего равенства условия (12) и (13). Что и требовалось.

В заключение параграфа приведем формулировки двух теорем Куна-Таккера для задачи вы-

пуклого программирования с линейными ограничениями.

Теорема 4. Пусть в задаче выпуклого программирования (1) – (3) система ограничений (2) имеет вид , где A – матрица размерности , b – вектор размерности . Тогда для того, чтобы неотрицательный вектор был решением задачи, необходимо и достаточно, чтобы

существовал неотрицательный вектор такой, что – седловая точка функции Лагранжа данной задачи.

Отметим, что в этом случае функция Лагранжа имеет вид .

Теорема 5. Пусть в задаче выпуклого программирования (1), (2) целевая функция непрерывно дифференцируема, система ограничений (2) имеет вид , где A – матрица размерности , b – вектор размерности . Тогда для того, чтобы вектор был решением задачи, необходимо и достаточно, чтобы существовал неотрицательный вектор такой, что выполняются условия , .

Заметим, что в теоремах 4 и 5 не требуется выполнения условия Слейтера, поэтому они не являются частными случаями теорем 1 и 3 и требуют самостоятельного доказательства.

Источник