Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Еслижеограничениенеактивно (т.е. выражениевскобкахнеравнонулю), то
соответствующий коэффициент Лагранжа должен быть равен нулю, т.е. это
ограничениенедефицитно, ононеоказываетвлияниянадальнейшееулучшение
целевойфункции.
Для точки условного максимума коэффициенты Лагранжа меняют знак на
противоположный (т.к. оптимальноезначениецелевойфункциивточкеусловного
максимумадолжновозрастать).
Приведенныеусловияэквивалентны теоремеКуна-Такера ичастоназываютсятак
же.
Достаточным условием для минимума (максимума) является выпуклость
(вогнутость) целевойфункциивстационарнойточке. Этозначит, чтогессиандолжен
бытьположительно (отрицательно) определен.
Таккакискатьусловныеэкстремумыизнеобходимыхидостаточныхусловийв
реальнойоптимизациипрактическиневозможно, тоглавныминструментомусловной
оптимизацииявляютсяитерационныеалгоритмы, строящиепоследовательностьточек,
сходящуюсякрешению.
Внастоящеевремянетметода, гарантирующегосуществованиерешениялюбой
общейзадачиматематическогопрограммирования.
Всеметодыусловнойоптимизациивтомилииномвидесводятеекоднойилик
последовательностизадачбезусловнойоптимизации.
Идеяметодасостоитвследующем.
ЕслинамбылибыизвестныкоэффициентыЛагранжавточкеусловного
минимума, томожнобылобыискатьседловуюточкуфункцииЛагранжа, выполняя
безусловную минимизацию пообъектнымпеременным, зафиксировав (оптимальные)
коэффициентыЛагранжа.
Еслибынамбылиизвестныобъектныепеременныевточкеусловногоминимума,
томожнобылобыискатьседловуюточкуфункцииЛагранжа, выполняябезусловную
максимизацию этой функции по коэффициентам Лагранжа, зафиксировав
(оптимальные) объектныепеременные.
Таккакнасамомделенамнеизвестныкакобъектныепеременные, таки
коэффициентыЛагранжа, томожнопоступитьследующимобразом. Зафиксировать
некоторыекоэффициентыЛагранжаирешитьзадачу минимизации функцииЛагранжа
пообъектнымпеременным. Затемзафиксироватьнайденныеобъектныепеременныеи
решить задачу максимизации функции Лагранжа по коэффициентам Лагранжа.
Повторять процесс до тех пор, пока изменения в объектных переменных,
коэффициентахЛагранжаизначенияхфункциинестанутпренебрежимомалыми.
Задачибезусловнойоптимизацииможнорешатьлюбымиизвестнымиметодами,
которыемогутбытьразнымидляобъектныхпеременныхикоэффициентовЛагранжа.
Метод обобщенного Лагранжиана
Методы прямого поиска для решения задач условной оптимизации
Перваяидея, котораяможетбытьиспользованадляусловнойоптимизации,-это
модифицированиеметодовпрямогопоискасприсваиваниемцелевойфункцииочень
большогозначениявнедопустимойобласти. ОднакомодификацияметодаХука-Дживса
неэффективна: спомощьюданногометодаоказываетсяневозможнодвигатьсявдоль
границыдопустимойобластиисходимостьдостигаетсявпервойжеточкеграницы, где
иуказываетсяусловныйминимум.
НеудачнойоказываетсяимодификацияметодаНелдера-Мидаввидутого, что
вблизиграницымногогранник "уплощается" истягивается, чтоиостанавливаетметод
(илирезкозамедляетегопослетого, какданноеограничениепересталобыть
активным). Прямаямодификациядругихметодовпрямогопоискатакженебыла
особенно успешной, за исключением, быть может, случайного поиска. Однако
алгоритмыслучайногопоискамынебудемрассматриватьвэтомразделе.
КомплексныйметодБокса
Более эффективную модификацию метода Нелдера-Мида предложил Бокс,
которыйуказал, чточислоточеквмногогранникедолжнобытьбольше n+1. Таким
образом, Бокспредложилвместосимплексаиспользовать комплекс, тоестьнесамую
простуюфигурусоответствующейразмерности.
Рассмотримзадачуоптимизации:
z
=
f(X)
→
min,
АлгоритмБокса.
1. Определитьначальнуюточку X
1
, удовлетворяющуювсемограничениям.
2. Определитьостальные k-1 точкикомплексапоправилу:
X=L+r⋅(U-L),
где L =(l
1
,l
2
,..., l
n
)
T
, U =(u
1
,u
2
,..., u
n
)
T
,
r-псевдослучайнаявеличина, равномернораспределеннаявинтервале (0,1).
3. Вычислитьзначенияфункциивовсехточкахкомплекса, упорядочитьточкипо
величинезначенияфункции.
4. Найтиточку X
h
снаибольшимзначениемфункцииицентр X
0
остальных (k-1)
точек.
5. Получитьновуюточку X
r
отражением X
h
относительно X
0
:
X
r
=(1+α)⋅X
0
- α⋅X
h
, α >0.
6. Проверитьявляетсяли X
r
допустимой.
а)
если
X
r
нарушает
ограничения
по
l
j
или
u
j
,
то
полагаем
или
)(
2
1
0
XXX
rr
+=
7. Вычислить f(X
r
) исравнитьснаибольшимзначениемфункции f(X
k
). Если
f(X
r
)>f(X
k
), тоположить
иперейтикшагу 6.
8. Если f(X
r
)<f(X
k
), тополагаем X
k
=X
r
исноваупорядочиваемточкикомплекса.
9. Осуществляется проверка на сходимость. Если условия сходимости не
выполнены, топереходимкшагу 4. Иначе - остановка.
МетодБоксаприменимкширокомукругузадач. Однакооннегарантируеттого,
чтобудетнайденглобальныйминимуми,крометого, еслицелеваяфункциявогнута
илидопустимаяобластьневыпукла, топоискможетокончитьсянеудачей, таккакв
этомслучаесовсемнеобязательно, чтоцентрдопустимыхточексамбудетдопустимым.
)(
2
1
0
XXX
rr
+=
Методыштрафныхфункций
Основнаяидеяметодовштрафныхфункцийсостоитвпреобразованиизадачи
условнойоптимизациивзадачубезусловнойоптимизациииливпоследовательность
задачбезусловнойоптимизации.
Пустьрешаетсязадачаусловнойоптимизации
z=f(X) → min,
c
j
(X)>0,j=1,2,...,m.
Построимфункциюштрафа P(X):
,
где r>0-коэффициентштрафа.
Тогдаможемзаписатьновуюцелевуюфункциюввиде
.
Если X принимаетдопустимыезначения, т.е.c
j
(X)>0, то ϕ(X,r) принимает
значения, которыебольше f(X), норазностьможноуменьшитьзасчеттого, что r может
бытьоченьмалойвеличиной. Ноесли X хотяидопустим, нооченьблизоккгранице
(хотя
бы
одна
из
функций
c
(X)
близка
к
нулю),
то
значения
функции
P(X),
а
значит,
и
∑
=
=
m
j
j
Xc
rXP
1
)(
1
)(
∑
=
+=
m
j
j
Xc
rXfrX
1
)(
1
)(),(ϕ
Полагая r достаточномалойвеличинойдлятого, чтобывлияние P(X) быломалым
вточкеминимума, можносделатьточкубезусловногоминимумафункции ϕ(X,r) сколь
угодноблизкойкточкеусловногоминимумафункции f(X). Вобщемслучае, решая
последовательностьзадачбезусловнойоптимизациисуменьшающимся r, можно
получитьприближенноерешениезадачиусловнойоптимизации. Наэтомосновантак
называемый SUMT-методФиаккоиМаккормика (методпоследовательнойбезусловной
оптимизации).
Штрафнаяфункция, приведеннаявышеназываетсябарьерной. Другойвид
барьернойфункции (логарифмическаябарьернаяфункция):
.
Этабарьернаяфункциявообщенеопределеназапределамидопустимойобласти.
Штрафныефункциимогутиметьидругойвид. Например, дляограничений-
равенствимеем:
- квадратичнаяштрафнаяфункция,
- абсолютнаяштрафнаяфункция,
∑
=
−=
m
j
x
j
crXP
1
)(ln)(
∑
=
=
m
j
j
XcXP
1
2
)()(
∑
=
=
m
j
j
XcXP
1
)()(
,...3,2,1,))(()(
1
2
==
∑
=
j
m
j
k
j
kXcXP
j
Еслижевпостановкезадачиприсутствуютограничения-равенства (h
j
(X)) и
ограничения-неравенства (g
i
(X)) одновременно, тоштрафнаяфункцияможетбыть
записана, например, ввиде:
P(X)= ,
P(X)= .
Недостатки метода: определяется только локальный минимум, трудности
одномерногопоиска (невездеопределенафункция) непозволяютиспользовать
стандартные методы, плохая обусловленность Гессиана, существенно овражный
характерштрафнойфункциивблизиграницы.
Возможныепутипреодоления: мультистарт, специальныеметодыодномерного
поиска, использованиенапредварительныхэтапах "гибридных" методоввсочетаниис
алгоритмами, имеющимихорошиесвойствалокальнойсходимости, иовражными
алгоритмами.
(
)
(
)
max ( ), ( ( ))g X h X
i j
ji
0
2
2
+
∑∑
max( ( ),) ( )g X h X
i j
ji
0+
∑∑
Методыпроектированияиредукцииградиента
Это - целоесемействоалгоритмов, котороеещеназываютметодамидопустимых
направлений.
Основнаяидея: выбранноенаправлениепоискапроектируетсяналинейную
комбинациюизлинейныхилилинеаризованныхограничений.
Алгоритмыэтогосемействаотличаютсяспособамиопределениянаправления,
однаковсеонихарактеризуютсятем, чтопоискначинаетсясдопустимогорешенияи
развиваетсяприлинеаризованныхограниченияхвнаправлении, обеспечивающем
уменьшениецелевойфункцииприсохранениитекущейточкивнутридопустимой
области. Обычно часть ограничений-неравенств заменяется равенствами, чем
уменьшаетсяразмерностьзадачи. Приэтомвовлекаютсяневсеограничения, атолько
активные. Вслучае, когданапересечениеподмножестваограниченийпроектируется
градиент целевой функции, метод оптимизации называется методом проекции
градиента.
Другиеподходыкрешениюзадачусловнойоптимизации
Линейная аппроксимация. Нелинейные функции в задаче оптимизации
заменяютсячленамипервогопорядкарядаТейлоравокрестноститекущейточки, после
чего
решается
задача
ЛП
.
При
определенных
условиях
последовательность
получаемых
Условия, прикоторыхдостигаетсясходимость:
1. Оптимизируемая функция и функции-ограничения непрерывны и
дифференцируемы.
2. Допустимоемножествозамкнуто, выпуклоинепусто.
3. Функции-ограниченияограничены.
4. Функцииограничений-неравенстввогнуты.
5. Оптимизируемаяфункциявыпукла.
6. Сумма квадратов функций ограничений-равенств является выпуклой в
допустимойобласти.
Недостатки:
1. Медленнаясходимость, еслитекущиеточкибратьтолькодопустимымиили
близкимикним.
2. Еслииспользоватьнедопустимыеточки, тонеясно, какихсравниватьдругс
другом (например, f(X
1
)>f(X
2
), но c(X
1
)>c(X
2
) ивобеихточкахограничениенарушено).
3. Еслицелеваяфункциясущественнонелинейна, толинеаризованнаязадачадает
слишкомнеточноенаправлениепоиска.
4
.
Трудно
учитывать
имеющиеся
априорные
данные,
которые
могли
бы
ускорить