Презентация - Семенкин Е.С. Методы оптимизации

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

Обсуждениеметодов

Материал, предложенный в данном разделе, представляет собой лишь

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

оптимизационных пакетов и инструкции пользователя. Однако эффективность

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

значительно большей степени, чем эффективность программ для безусловной

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

теоретическихисследований. Поэтомуприведемнекоторыерекомендации, которые

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

исследований.

Сравнительнопростыметодысдифференцируемымицелевымифункциямии

линейными ограничениями. Для их решения разработано много эффективных

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

дажепрощезадачибезограниченийтойжеразмерности, таккакограничения-равенства

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

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

умноженияматриц. Дляэтихзадачподходят, конечно, иметодыфункцииЛагранжа.

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

всегдарационально. Например, программыМ.ПауэллаилиК.Шиттковскогоочень

эффективны относительно критерия количества обращений к подпрограммам

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

вычисленийнаитерациюизанимаютбольшеоперативнойпамятиЭВМ.

Поэтомуболеепростыеметодыпроекцииилиредукцииградиентовмогутбыть

предпочтительнейдляэтогоклассазадач. Еслиограничениялинейны, ацелевая

функциянедифференцируема, топоследниеметодымогутбытьлегкообобщеныпутем

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

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

спецификулинейныхограниченийудаетсяредко.

Для задач локальной минимизации (умеренной размерности - несколько

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

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

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

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

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

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

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

Важнымусловиемэффективногопримененияметодовусловнойоптимизации

являетсявыбор "подходящих" масштабовфункциицелииограничений, атакже

независимыхпеременных. Теоретическиалгоритмычастоинвариантныотносительно

выборамасштабов, ногарантировать, чтоэтимсвойствомбудутобладатьтакжеи

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

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

величинами.

Врядлиможноожидатьтакогожеответа (т.е. точкиминимума), еслипотомуже

алгоритмуградиентноготипабудутминимизироватьсяфункции f(X) и 10

-17

f(X). Для

второй функции многие точки допустимого множества будут признаваться

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

программепороговыезначенияэтойнормы. Почтидлявсехалгоритмовнежелательно,

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

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

функцииблизкокединице, амаксимальноееезначение, возведенноевкуб, не

превышаетмаксимальнодопустимого (дляданнойЭВМ) числа.

Болеесложновыбратьмасштабыпеременныхифункцийограничений. Хорошо

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

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

можнонайтисоображения, каклинейнотрансформироватьнезависимыепеременные,

чтобыоптимальносогласоватьмасштабы, нореализоватьихвпрактическихзадачах

оченьсложно. Поэтомуобычноограничиваютсявыборомнекоторых "естественных"

масштабов.

Кроме хорошей определенности к функциям ограничений выдвигается

дополнительное требование: их влияние должно быть примерно равным, т.е.

одинаковыеприращенияпеременныхдлявсехфункцийдолжнывызыватьизменения

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

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

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

До конца автоматизировать выбор масштабов невозможно, а учитывать

рекомендацииотносительномасштабированиянаэтаперазработкиалгоритмови

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

Взадачахусловной (такжекакибезусловной) оптимизацииследуетиспользовать

как можно больше информации о производных. Если известны аналитические

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

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

дифференцируемы, наиболееэффективныметодыфункцииЛагранжа. Этотвывод

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

опубликованныевнаучнойлитературе. Однакоэтиметодынеприменимы, еслицелевая

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

барьеров, адлябезусловнойминимизациибарьерной (штрафной) функциивыбирать

метод (например, Ньютонаилипеременнойметрики) взависимостиотвозможности

использоватьпроизводные.

Сложнеевыбратьэффективныйметоддляминимизациифункций, которые

определяютсяприпомощиалгоритмаЭВМ, ноприэтомпогрешностистольбольшие,

чточисленноедифференцированиестановитсябессмысленным. Тогдаограничения

учитываютсяприпомощиметодовштрафовилибарьеров, абезусловнаяоптимизация

осуществляетсяоднимизметодовпоиска. Присозданиитакихалгоритмовмногое

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

применениятакихалгоритмов. Некоторыерекомендациипоиспользованиюметодов

поискаиштрафовданывыше. Дляоченьширокогоклассазадачприменимметод

скользящего

допуска

НометодыфункцииЛагранжазначительноэффективнее, еслифункциизадачи

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

ЭВМ.

Иногдавозникаютнедоразумениясточностьюполученногорешения. Неопытный

пользовательнадеется, чтоточностьполученногорешенияравна ε, еслиприпомощи

величины ε определеноусловиеостановки. Такоемнениеформируетсяврезультате

применения подпрограмм для решения более элементарных задач, например

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

вычисленияпроводятсясмашиннойточностью. Гарантироватьточностьрешениязадач

оптимизацииможнолишьвисключительныхслучаях. Практическиусловияостановки

определяютсянесколькимиспособами.

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

заданнойточностьюнеобходимыхусловийминимума. Однакотакиеусловиямогут

удовлетворять (особеннодляневыпуклыхзадач) точки, вкоторыхзначенияфункции

далекиотминимума, какдалекиисамиточкиотточкиминимума. Вообщеговоря, в

"ложной" точкеминимумаантиградиентцелевойфункциинаправленнаружуобластии

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

требованийнацелевуюфункциюиограничения, тонельзягарантироватьмонотонное

убываниепроекцииградиентанакасательнуюплоскостькдопустимойобласти, что

объясняетвозможностьсуществования "ложных" точекминимума.

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

замедлениемубываниязначенийцелевойфункции, например, внесколькихследующих

одназадругойитерацияхзначенияцелевойфункциипочтинеменяются. Это

характернодляокрестностилокальногоминимума, нонетолькодлянее. Поэтому

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

минимизациюпридругихпараметрахалгоритмаилиприпомощидругогоалгоритма.

Частобываютполезныграфическиепредставления (разрезы, линииуровня) целевой

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

Подчеркнемещераз, чтозадачиусловнойоптимизациисложныиуниверсальных

методовихрешениянесуществует. Привыбореалгоритмадляконкретнойзадачи

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

лежатвосновеалгоритма. Математическаятеорияоптимизациихорошоразработана,

новсежеврешениисложныхпрактическихзадачнеобойтисьбезопределеннойдоли

искусства.

ДИНАМИЧЕСКАЯ ОПТИМИЗАЦИЯ

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

комплекса конкурирующих целей в некоторый определенный момент времени

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

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

достигаетсямаксимум (минимум) заданнойцелевойфункции, иназываетсязадачей

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

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

комплексаконкурирующихцелейнапротяжениинекоторогопромежуткавремениот

начальногомоментадоконечногоформализуетсяследующимобразом.

Рассмотрим некоторые переменные величины, называемые управляющими

параметрами. Задано некоторое множество функций времени, называемое

множествомуправления. Задачасостоитввыбореуправляющихпараметровкак

функций времени, принадлежащих множеству управлений. Выбранные функции

временивсвоюочередьопределяют, какойвидимеютфункциивременинекоторых

других переменны, с помощью которых описывается поведение системы. Эти

переменныеназываются фазовымикоординатами. Значенияфазовыхкоординатв

каждый момент времени выбираются таким образом, чтобы максимизировать

(минимизировать) заданный целевойфункционал, зависящийотфазовыхкоординати

управляющихпараметров (итеидругиерассматриваютсякакфункциивремени).

Функциивременидляуправляющихпараметровидляфазовыхкоординатсвязаныс

помощьюсистемыдифференциальныхуравнений, называемых уравнениямидвижения.

Задача,

представленная

указанной

форме,

называется

задачей

управления

Строгая формулировка задачи

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

время (моментвремени), фазовыекоординаты, управляющиепараметры, уравнения

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

Время t измеряетсякакнепрерывнаявеличина. Предполагается, что t изменяетсяв

некоторомфиксированномпромежутке: отначальногомомента t

, которыйобычно

известен, доконечногомомента t

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

времязаданонапромежутке

≤ t ≤ t

Состояниесистемывлюбоймоментвремени t изуказанногопромежутка

характеризуетсяспомощью n вещественныхчисел x

(t), x

(t),…, x

(t), называемых

фазовымикоординатами. Составленныйизфазовыхкоординат n-мерныйвектор

x(t)=(x

(t), x

(t),…, x

(t))', (1)

называемый фазовым вектором (фазовой точкой), можно геометрически

интерпретироватькакточкувn-мерномевклидовомпространстве Е

. Каждая фазовая

координата считаетсянепрерывнойфункциейвремени, поэтому фазоваятраектория

{x(t)}={x(t)∈Е

≤t≤t

}

Началомэтойкривойявляетсяфиксированное начальноесостояние

x(t

)=x

, (2)

аокончанием – конечноесостояние

x(t

)= x

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

Выборы (решения), которыенужноосуществлятьвкаждыйданныймомент

времени t изуказанногоинтервала, характеризуютсяспомощью r вещественныхчисел

(t), u

(t),…, u

(t), называемыхуправляющимипараметрами. Составленныйиз

управляющихпараметров r-мерныйвектор-столбец

u(t)=(u

(t), u

t),…, u

(t))', (3)

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

точкувE

.Управлением ("траекториейуправления") называетсяфункция

{u(t)}={u(t)∈Е

≤t≤t

}. (4)

Требуется, чтобы каждый управляющий параметры являются кусочно-

непрерывнойфункциейвремени. Поэтомууправлениепредставляетсобойкусочно-

непрерывную

функцию

времени

Значениями

этой

функции

каждый

данный

момент

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

некоторымограничениям. Этиограничениявобщейформесостоятвтом, что

управляющийвекторвкаждыймоментвремениизинтервала t

≤ t ≤ t

должен

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

евклидовапространства

u(t)∈Ω,t

≤t≤t

Обычнопредполагается, чтомножество Ω являетсявыпуклымикомпактным (т.е.

замкнутымиограниченным) ичтооноинвариантноотносительновремени. Управление

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

функциювремени, значениякоторойвлюбоймоментвремениизуказанногоинтервала

принадлежат Ω. Множество управлений U – это множество всех допустимых

управлений. Управлениедолжнопринадлежатьуказанномумножествууправлений, т.е.

u(t)∈U.

Фазоваятраектория {x(t)} определяетсяиз уравненийдвижения, т.е. изсистемы

дифференциальных уравнений, в которых скорость изменения каждой фазовой

координаты представлена в виде функции фазовых координат, управляющих

параметровивремени

x' = f(x(t), u(t), t),

или

развернутом

виде

== )()(

txt