Бронов С.А. Методы оптимизации в САПР

Подождите немного. Документ загружается.

Пояснения.

Последнее утверждение говорит о том, что, если имеются экстремумы,

то в функции Лагранжа учитывается соответствующая им целевая функция, а

не одни только ограничения.

Точки



называются условно-стационарными (так как рассматривается

условная оптимизация, в отличие от случая безусловной оптимизации, когда

они называются просто стационарными).

Далее вводится понятие индекса ограничений

J , активных в точке



(номера ограничений-неравенств, которые стали равенствами в точке



Достаточные условия экстремума первого порядка в задаче услов-

ной оптимизации с ограничениями-неравенствами

Пусть имеется точка ),(





x , удовлетворяющая необходимым условиям

экстремума первого порядка (рассмотренным выше) при 0







, число ак-

тивных ограничений в точке



совпадает с числом

переменных (при этом

условие регулярности выполняется). Если 0





для всех



, то точка



— условный локальный минимум. Если 0





для всех



, то точка



— условный локальный максимум.

Необходимые условия экстремума второго порядка в задаче услов-

ной оптимизации с ограничениями-неравенствами

Пусть



— регулярная точка экстремума в задаче условной оптимиза-

ции и имеется решение ),(





x , удовлетворяющее необходимым условиям

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

функции Лагранжа в точке ),(





x неотрицателен для минимума:

0),(







xLd

и неположителен для максимума:

0),(







xLd

для всех первых дифференциалов



таких, что

0)( 



xdq



при 0





для минимума и 0





для максимума,

0)( 



xdq



при 0





Достаточные условия экстремума второго порядка в задаче услов-

ной оптимизации с ограничениями-неравенствами

Пусть имеется точка ),(





x , удовлетворяющая необходимым условиям

экстремума первого порядка (рассмотренным выше) при 0







. Если в этой

точке 0),(







xLd , то для всех ненулевых



таких, что

0)( 



xdq



при 0





для минимума и 0





для максимума,

0)( 



xdq



при 0





то точка



— локальный минимум (максимум).

Алгоритм решения задачи условной оптимизации при ограничени-

ях-неравенствах

Исходные данные: вектор искомых переменных

размерности

, целе-

вая функция

)

(

и функции-ограничения в форме неравенств 0)(







Шаг 1. Составляется обобщённая функция Лагранжа







xqxIxL

)()(),,(



Шаг 2. Записываются необходимые условия экстремума первого поряд-

ка:





















.,,1,0)(

;,,1(max),0(min),0

;,,1,0)(

;,,1,0

),,(

mjxq





Шаг 3. Решается полученная система уравнений для двух случаев:

1) 0





;

2) 0





, для чего первое условие шага 2 делится на



и производится

замена переменных



на новые



В результате находятся значения



, соответствующие условно-

стационарным точкам



, которых в общем случае может быть несколько.

Из них выделяются те, что найдены при условии 0





— эти точки могут

быть регулярными точками экстремума, что необходимо проверить с помо-

щью достаточных условий.

Шаг 4. Для выделенных на шаге 3 точек проверяются достаточные

условия экстремума следующим образом:

а) определяют число

активных в точке



ограничений;

б) если



(т. е. число активных ограничений, превратившихся в урав-

нения, равно числу переменных



) и для всех



(т. е. для всех актив-

ных ограничений) 0





, то в точке



— локальный минимум, а если

0





, то в точке



— локальный максимум; если



или соответствую-

щие множители Лагранжа не удовлетворяют достаточным условиям первого

порядка, следует проверить достаточные условия второго порядка.

Для проверки достаточных условий второго порядка выполняются сле-

дующие действия:

а) записывается выражение для второго дифференциала классической

функции Лагранжа в точке ),(





x :

dxdx

xLd



 









1 1

),(



;

б) записывается система уравнений для первого дифференциала функ-

ций ограничений:

)(













xdq ,



при 0





для минимума и 0





для максимума,

)(













xdq ,



, 0





в) осуществляется проверка знака второго дифференциала: если

0),(







xLd при ненулевых

dx , то в точке



— условный локальный

минимум; если 0),(







xLd при ненулевых

dx , то в точке



— услов-

ный локальный максимум.

Если достаточные условия экстремума первого и второго порядков не

выполняются, то следует проверить выполнение необходимых условий вто-

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

ются дополнительные исследования, если не выполняются — в точке



нет

условного экстремума.

Шаг 5. Если точки условного экстремума найдены, в них вычисляются

значения целевой функции.

Пример 4.7. Пусть задана целевая функция

)( xxxI  на множестве





 xxxX , т. е. задано одно ограничение-неравенство

02)(

211









xxxq , причём здесь



Решение.

1. Составляется обобщённая функция Лагранжа:

)2()()()(),,(

211







xxxxxqxIxL



2. Выписываются необходимые условия экстремума первого порядка:

а)

 





 

 

;022)(

),,(

;022)(

),,(

120211

110211

























xxxxx

б) 02)(









xxxq .

Таким образом, получена система уравнений и неравенств:





















,0)2(

(max);0

(min);0

;02

211

120

110





для которой ищется решение.

3. Решение системы может быть получено для двух случаев: для 0





и 0





В первом случае принимается 0





. тогда из первого условия системы

следует, что:

002









x , 0





что противоречит необходимому условию условного экстремума первого по-

рядка о существовании ненулевого вектора, состоящего из



, поэтому

допущение о 0





неверное.

Во втором случае 0





. Тогда можно перейти от обобщённой к клас-

сической функции Лагранжа, поделив её на



и заменив



на новые



 





 

 

;022)(

),(

;022)(

),(

12211

11211

























xxxxx

Тогда новая система уравнений и неравенств будет иметь вид:





















.0)2(

(max);0

(min);0

;02

211



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



Из условия дополняющей нежёсткости

0)2()(

21111









xxxq



следует:

1) если 0





(т. е. фактически ищется безусловный экстремум, так как

единственный коэффициент Лагранжа



обнуляет единственное ограниче-

ние), тогда решение: 0022

111











, 0





x , 0022

212















x , 0







;

2) если 0





, то должно выполняться условие 0)2()(

211









xxxq ,

поэтому система уравнений принимает вид:















,02

;02



откуда находится решение: 1





x , 1





x , 2







По знаку коэффициента





можно определить вид возможного экстре-

мума (точнее, исключить какой-либо вид): поскольку знак отрицательный,

это не может быть минимум, но, возможно, максимум. Окончательное суж-

дение связано с проверкой достаточных условий.

4. Проверяются достаточные условия экстремума.

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

условий является активность ограничений в точке предполагаемого экстре-

мума.

Рассматривается условие 0





. В соответствующей этому условию

точке 0





x , 0





x ограничение имеет вид: 022002

















xx ,

т. е. не является активным (не превращается в равенство). Поэтому в соответ-

ствии с достаточными условиями первого порядка нельзя утверждать, что

точка

x )0,0(



является экстремумом. Следует проверить её по достаточ-

ным условиям второго порядка, в соответствии с которыми анализируется

знак второго дифференциала функции Лагранжа. В точке

x )0,0(



второй

дифференциал имеет вид:

022

),(









 

 



dxdxdxdx

xLd

i j



его положительность обусловлена тем, что он равен сумме квадратов диф-

ференциалов, а квадраты, как и любые чётные степени — всегда неотрица-

тельны, причём с учётом ненулевых первых дифференциалах 0



dx , 0



он оказывается не только неотрицательным, но строго положительным.

В соответствии с достаточными условиями второго порядка положи-

тельность второго дифференциала означает, что в точке

x )0,0(



имеется

локальный минимум (отрицательность означала бы максимум). Но эта точка

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

что связано с принятым условием 0





(в соответствии с которым ограни-

чение в функции Лагранжа обнуляется).

Далее рассматривается случай с 0





. В соответствующей этому усло-

вию точке 1





x , 1





x , 2







ограничение имеет вид:

02112













xx , т. е. является активным (превращается в равенство),

но при этом число активных ограничений



меньше числа переменных



, а поэтому достаточные условия первого порядка не выполняются. Это

означает, что невозможно подтвердить или опровергнуть гипотезу о том, что

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

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

точке знака второго дифференциала:

),(

),( dxdxdxdx

xLd

i j









 

 





с учётом выражений для первого дифференциала ограничений (в данном

случае — одного ограничения):











































xdq

)()(

)(





























xx

)2()2(





011

2121







dxdxdxdx

откуда получается:

dxdx





Далее полученные значения подставляются во второй дифференциал

функции Лагранжа для определения его знака:

042)(222),(





dxdxdxdxdxxLd



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

x )0,0(



Так как в рассматриваемой точке 02







, то достаточное условие

максимума второго порядка не выполняется, поэтому сказать что-то опреде-

лённое о рассматриваемой точке невозможно. Остаётся проверить необходи-

мые условия второго порядка, которое сводится к анализу знака второго

дифференциала функции Лагранжа:

044),(





dxdxxLd



при любых

dx и

dx , т. е. необходимое условие второго порядка для макси-

мума не выполняется, следовательно, максимума точно нет.

Таким образом, получены следующие результаты:

1) в точке

x )0,0(



возможен условный минимум;

2) в точке

x )1,1(



нет ни минимума, ни максимума.

5. Далее в найденной точке экстремума следует найти значение целевой

функции:

000)(

 xxxI .

Таким образом, решаются задачи нахождения условного экстремума с

ограничениями-неравенствами.

2.3.4 Задача условной оптимизации со смешанными ограничениями

(равенствами и неравенствами)

Постановка задачи условной оптимизации со смешанными ограни-

чениями

Задача условной оптимизации со смешанными ограничениями фор-

мулируется следующим образом: даны дважды непрерывно дифференциру-

емые целевая функция

)

(

и функции ограничений

)

(

, определённые на

множестве

RX  , требуется исследовать целевую функцию

)

(

на экс-

тремумы, т. е. определить точки





её минимумов и максимумов на

множестве

)(min)( xIxI

Xx



 , )(max)( xIxI

Xx





с учётом условий, заданных равенствами и неравенствами:



























,,),1(,0)(

;;,,1,0)(

pmjxq

nmmjxq



где

— целые числа.

Необходимые условия экстремума первого порядка в задаче со сме-

шанными ограничениями

Пусть



есть точка локального экстремума в задаче условной оптими-

зации

)(min)( xIxI

Xx



 , )(max)( xIxI

Xx





с учётом условий, заданных равенствами и неравенствами:



























,,),1(,0)(

;;,,1,0)(

pmjxq

nmmjxq



Тогда найдется число 0







и вектор





, не равные одновременно нулю

и такие, что выполняются следующие условия:

 условие стационарности обобщённой функции Лагранжа по

),,(













или в векторной форме (через градиент) 0),,(







;

 условие допустимости решения:

0)( 







;

0)( 









;

 условие неотрицательности для условного минимума:

pmj

,...,1,0 





или условие неположительности для условного максимума:

pmj

,...,1,0 





;

 условие дополняющей нежёсткости:

pmjxq

,...,1,0)( 





Если при этом градиенты активных в точке



ограничений-равенств и

ограничений-неравенств )(



 xq

, )(



 xq

, …, )(



 xq

, )(





 xq

, …,

)(



 xq

линейно независимы (выполняется условие регулярности), то







Пояснения.

Условия знаокопределённости (неотрицательности и неположительно-

сти), а также условие дополняющей нежёсткости записывается только для

тех множителей Лагранжа, которые относятся к ограничениям-неравенствам.

Условие дополняющей нежёсткости понимается следующим образом:

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

из сомножителей. Это означает, что если какое-то условие-неравенство пас-

сивное [ 0)( 



, т. е. не равно нулю], то соответствующий коэффициент

Лагранжа равен нулю 0





. Если же это условие-неравенство активное

[ 0)( 



, т. е. равно нулю], то соответствующий коэффициент Лагранжа

может и не быть равным нулю (а может и быть равным). При этом в случае

максимума записывают условие 0





, а случае минимума 0





Достаточные условия экстремума первого порядка в задаче услов-

ной оптимизации со смешанными ограничениями

Пусть имеется точка ),(





x , удовлетворяющая необходимым условиям

экстремума первого порядка (рассмотренным выше) при 0







, суммарное

число ограничений-равенств и активных ограничений-неравенств в точке



совпадает с числом

переменных (при этом условие регулярности выполня-

ется). Если 0





для всех



, то точка



— условный локальный ми-

нимум. Если 0





для всех



, то точка



— условный локальный

максимум.

Необходимые условия экстремума второго порядка в задаче услов-

ной оптимизации со смешанными ограничениями

Пусть



— регулярная точка экстремума в задаче условной оптимиза-

ции и имеется решение ),(





x , удовлетворяющее необходимым условиям

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

функции Лагранжа в точке ),(





x неотрицателен для минимума:

0),(







xLd

и неположителен для максимума:

0),(







xLd

для всех первых дифференциалов



таких, что

0)( 



xdq







при 0





для минимума и 0





для максимума,

0)( 



xdq



при 0





Достаточные условия экстремума второго порядка в задаче услов-

ной оптимизации со смешанными ограничениями

Пусть имеется точка ),(





x , удовлетворяющая необходимым условиям

экстремума первого порядка (рассмотренным выше) при 0







. Если в этой

точке второй дифференциал классической функции Лагранжа неотрицателен

для минимума:

0),(







xLd

и неположителен для максимума: