Условия оптимальности Куна и Таккера

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

Итак, рассмотрим задачу минимизации функции f ( x ) при условиях

.

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

.

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

.

Введем в рассмотрение два множества

.

Рассмотрим функцию Лагранжа следующего вида

.

Тогда необходимое условие для искомого оптимального вектора x ^* можно представить в виде

,
.

Согласно интерпретации множителей Лагранжа

.

Так как по определению оптимальности

,

получаем

для

для .

Введём в рассмотрение функцию Лагранжа в привычном для классических задач виде

.

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

(случай ).
(случай ).

Полученные условия оптимальности называются условиями Куна-Таккера. Смысл этих условий заключается в том, что для оптимального решения рассматриваемой задачи существуют такие множители Лагранжа l _i ^*, которые удовлетворяют соотношениям

,

(4.21)

или в развёрнутом виде

.

(4.22)

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

 

Упражнение 1. Показать, что в задаче минимизации функции f( x) при ограничении g_i( x) £ 0, x_j ³ 0,  необходимые условия оптимальности принимают вид

.

(4.23)

Упражнение 2. Показать, что множество допустимых x, задаваемое системой неравенств g_i( x) £ 0  выпукло, если функции g_i( x) – выпуклы.

Упражнение 3. Показать, что наличие седловой точки у функции Лагранжа F(x, l)=f(x) + l ^T g(x), т.е. выполнение соотношений F(x*, l) £ F(x*, l*) £ F(x, l*) для всех x ³ 0, l ³ 0, или, что то же самое, , является, как и в задачах на условный экстремум, достаточным условием достижения функцией f(x) в точке x* минимального значения при условии g(x) £ 0, x ³ 0.

Упражнение 4. Показать, что в общем случае при любых x Î X, l Î L имеет место неравенство .

Упражнение 5. Показать, что для задачи минимизации функции f( x) при условиях g( x) £ 0, x ³ 0 прямая задача состоит в отыскании , где .

Упражнение 6. Показать, что решение двойственной задачи, заключающейся в отыскании , где , в общем случае дает лишь оценку снизу для решения задачи минимизации f( x) при условии g( x) £ 0, x ³ 0, т.е.

.

Упражнение 7. Показать, что в случае выпуклых функций f(x) и g _i(x) решения прямой и двойственной задач (если они существуют) совпадают.

ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Анализ возможных численных методов оптимизации целесообразно начать с методов, предназначенных для решения однокритериальных детерминированных задач оптимизации при отсутствии ограничений. Такие задачи часто называют задачами безусловной оптимизации. Следует сразу подчеркнуть, что владение этими методами имеет принципиальное значение, ибо методы решения более сложных задач при наличии ограничений в большинстве случаев либо базируются на этих методах, либо практически сводятся к ним с использованием специальных приемов. Прежде всего отметим, что сущность всех численных методов оптимизации состоит в построении такой последовательности векторов {х ^k}, k = l, 2,..., которая, по крайней мере, удовлетворяет условию

Все методы могут быть разделены на классы в зависимости от максимального порядка производных функции f(x), вычисление которых предполагается в процессе поиска. Так, методы, использующие только значения самой функции, называют методами нулевого порядка. Если, кроме того, в процессе поиска требуется вычисление первых производных, то мы имеем дело с методами первого порядка. Методы второго порядка требуют для своей реализации вычисление вторых производных.

Методы первого порядка

С методической точки зрения анализ методов целесообразно начать с методов первого порядка. Основу этих методов составляют так называемые градиентные методы, сущность, которых заключается в том, что каждое новое приближение х ^k+1 к минимуму функции f( x) формируется на основе текущего приближения x^k  по схеме

(5.1)

где через h ^k обозначена величина шага поиска в направлении антиградиента  -Ñ f(x^k) на k-й итерации. По существу, данная схема основана на линейной аппроксимации функции f(x) в окрестности точки x^k. Обоснованием схемы может служить тот факт, что направление антиградиента -Ñ f(x^k)  в точке  x^k определяет (задает) локально наилучшее направление спуска, так как оно совпадает с направлением наискорейшего уменьшения значения функции f(x).

В зависимости от способа задания шага поиска различают различные градиентные методы. Некоторые из них рассматриваются ниже.

 

Метод градиентного спуска

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

(5.2)

Метод является локально-оптимальным, так как в каждой точке траектории поиска используется наилучшее направление спуска, определяемое антиградиентом (см. рис.5.1). Реализовать такую траекторию можно лишь приближённо, полагая шаг поиска достаточно малым, но конечным.

Рис.	5.1	Метод градиентного спуска

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

 

⇐ Предыдущая1234567Следующая ⇒

Поделиться: