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

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

14 возвращаются к п.10 и далее по алгоритму.

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

ку, сравнивая её с двумя ранее рассчитанными. Все численные методы раз-

личаются именно алгоритмом выбора этой новой точки.

3.2 Оценка качества метода оптимизации

В зависимости от того, за сколько шагов находится решение, различают

методы конечно-шаговые и бесконечно-шаговые. В конечно-шаговых мето-

дах решение находится за конечное число шагов. Такие методы встречаются

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

целочисленной оптимизации. Как правило, методы являются бесконечно-

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

ство шагов. При этом точного решения найти невозможно и решение ищется

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

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

В связи с тем, что главной особенностью численных методов является

их итеративность, т. е. движение к точке решения (экстремума) с некоторым

шагом, важнейшей характеристикой их является сходимость. Говорят, что

метод сходится, если при





точка





(



— точка решения зада-

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

)()(



 xIxI

. Последовательность точек

называется минимизирующей

(максимизирующей). Основная задача при конструировании метода — раз-

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

бы задача имела решение. Но для одной и той же задачи может быть разрабо-

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

длиннее, другие короче, приводя к одной и той же точке решения. Поэтому

эффективность сходящегося метода можно охарактеризовать с помощью по-

нятия скорости сходимости. Выделяют сходимость линейную, сверхлинейную

и квадратичную.

Линейная сходимость: последовательность

при





сходится к

точке



линейно, если существуют такие константы

)

(



k , что



 xxgxx

kk 1

при



что означает, что расстояние до точки экстремума



x от последующей точки



 xx

k 1

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



 xx

, т. е. с

каждым шагом, начиная с шага

k , происходит приближение к точке экстре-

мума; коэффициент

определяет скорость сходимости и остаётся неизмен-

ным от шага к шагу. Выражение

)

(



означает, что

изменяется между

0 и 1. Если



, то



 xxxx

kk 1

и с каждым последующим шагом

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

предыдущем шаге. Если, например,



, то



 xxxx

5,0

и с

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

быть не больше половины расстояния на предыдущем шаге. Таким образом,

при уменьшении

увеличивается скорость сходимости. На самом деле, па-

раметр

не задают, а рассчитывают и сравнивают для различных методов,

выбирая наиболее быстрый. Это можно сделать теоретически, можно и чис-

ленно в процессе расчётов. В последнем случае можно проводить экспери-

менты с различными типами целевых функций.

Сверхлинейная сходимость: последовательность

при





схо-

дится к точке



сверхлинейно, если







 xxgxx





g при





где по сравнению с предыдущим случаем коэффициент

с каждым шагом

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





g ),

т. е. становясь всё более малой, но положительной величиной.

Квадратичная сходимость: последовательность

при





сходит-

ся к точке



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

k и



, что

1 

 xxCxx

при



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

k , новое расстояние до точки экстремума

сравнивается с квадратом расстояния на предыдущем шаге. При квадратич-

ной сходимости обеспечивается ускорение при подходе к точке экстремума.

Например, если на данном шаге расстояние уменьшилось в 2 раза по сравне-

нию с расстоянием на предыдущем шаге, то на следующем шаге уменьшение

составит уже в 4 раза по сравнению с настоящим шагом и т. д.

Очевидно, что самыми быстрыми являются методы с квадратичной схо-

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

нем месте по скорости — с линейной сходимостью.

При теоретических исследованиях сходимости методов определённую

проблему представляет то, что точка экстремума



в общем случае не из-

вестна и определить расстояние до неё невозможно. Поэтому при исследова-

нии сходимости могут брать образцовую целевую функцию с точно извест-

ной точкой экстремума и рассматривать метод на её примере.

3.3 Условия остановки счёта

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

найдена точно, но это достигается не во всех методах. В большинстве мето-

дов расчёты выполняются итерационно с приближением к точке экстремума,

но её точного значения не определяют, а определяют приближённое значение

с некоторой заданной погрешностью. Существует несколько условий оста-

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

Условие малого шага:





 kk

xx ,

где



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

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

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

Условие малого различия значений целевой функции:

)()(





 kk

xIxI ,

где



— заданная положительная величина; смысл условия в том, что зна-

чения целевой функции в новых точках практически не отличается от тако-

вых в предыдущих точках, следовательно, найден экстремум. Формула для

этого случая отличается от предыдущей формулы. В предыдущей формуле

ищется расстояние между точками (поэтому используется обозначение с

двойными линиями ), так как

может быть вектором, а во второй форму-

ле ищется абсолютная величина разности значений целевой функции (поэто-

му используется обозначение с одинарными линиями ).

Условие стационарности:

)(







xdI

где



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

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

вают её значение — в точке экстремума производная должна быть равна ну-

лю. Но в данном случае из-за приближённых расчётов это может не быть до-

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

тельной или отрицательной, но для сравнения берётся её абсолютная величи-

на).

3.4 Установление начальных границ интервала

Установление границ интервала является самым первым этапом числен-

ной оптимизации. Его суть сводится к тому, чтобы выбрать исходную точку,

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

тремума, причём зама точка остаётся пока неизвестной. Сам поиск экстрему-

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

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

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

найденными опытным путём. Но всё же некоторые обоснования делаются и

для эвристических методов. Одним из эвристических методов определения

пробной точки при поиске экстремума является метод Свенна (Swann W. H.).

Этот метод рассматривается далее на примере целевой функции одной пере-

менной. В соответствии с ним (



)-я пробная точка определяется по ре-

куррентной формуле из предыдущей

-й точки:

kkk

xx 







где



— величина шага по

, подбираемая некоторым способом (один из

которых рассматривается ниже), причём знак шага выбирается путём сравне-

ния значений )(

xI , )(

xI  и )(

xI  , т. е. значений целевой функ-

ции в предыдущей точке, справа от неё и слева от неё (верхний индекс

—

номер точки, но не степень).

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

ется только один экстремум, например (для определённости), минимум.

Если )()()(

xIxIxI  , то точка минимума должна рас-

полагаться правее точки

и величина шага



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

вследствие чего продолжается движение вправо.

Если )()()(

xIxIxI  , то точка минимума должна рас-

полагаться левее точки

и величина шага



выбирается отрицательной,

вследствие чего продолжается движение влево.

Если )()()(

xIxIxI  , то точка минимума должна рас-

полагаться между точками )(

x  и )(

x  и можно считать, что

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

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

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

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

Пример 3.1. Минимизируется целевая функция

)100()( xxI  . Выбе-

рем произвольно начальную точку



и величину шага 5

Вычисляются значения в исходной точке, справа и слева от неё:

4900)30()(

 IxI ;

4225)530()(

 IxI

;

5625)530()(

 IxI

Проверяется условие: )()()(

111

xIxIxI  , которое принима-

ет вид:

4225

4900

5625



, т. е. выполняется. Это означает, что величина



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

35530



xx . В ней значение целевой функции уже рассчитано:

4225)35()(

 IxI .

Следующая точка 4552352

123



xx , в которой вычисляется

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

3025)45()(

 IxI .

Проверяется условие 3025)(4225)(

 xIxI , которое выполняется.

Следовательно, необходимо продолжить движение вправо от точки



Следующая точка: 6552452

2234



xx , целевая функция:

3025)(1225)65()(

 xIIxI ,

продолжаем движение вправо.

Следующая точка: 10552652

3345





, целевая функция:

1225)(25)105()(

 xIIxI ,

продолжаем движение вправо.

Следующая точка: 185521052

4456





, целевая функция:

25)(7225)185()(

 xIIxI ,

заканчиваем расчёты.

В результате шести шагов вычислений выбраны границы интервала, в

котором находится точка экстремума:

185





Далее необходимо осуществлять поиск в этих границах.

3.5 Исключение интервалов

После нахождения границ интервала, начинается поиск решения (точки

экстремума) внутри этих границ. Основная проблема — обеспечить как мож-

но более быстрое нахождение решения. При этом стремятся не проверять все

точки

, так как их может быть бесконечное множество, а только те, в кото-

рых может быть экстремум. Для этого анализируют возможность нахожде-

ния экстремума в той или иной части интервала и отбрасывают ту часть, ко-

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

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

точки экстремума. Этот подход и называется кратко "исключением интерва-

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

нет экстремума".

Большинство методов численной оптимизации построены на исключе-

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

именно интервал необходимо исключить. Чем больше исключаемый интер-

вал, тем эффективнее метод.

При безусловной оптимизации исключение интервалов осуществляется

только путём анализа текущей ситуации в ходе расчётов. При условной оп-

тимизации (при наличии ограничений) в исключении интервалов участвуют

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

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

жительные значения переменных

, то сразу исключается интервал [–∞,0].

Далее в ходе расчётов уже не нужно учитывать это ограничение. Но некото-

рые ограничения могут появляться и в процессе расчётов. Таким образом,

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

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

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

расчётов. Соответственно этому, можно выделить методы безусловной опти-

мизации и методы условной оптимизации. Последние являются более уни-

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

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

лительных операций и работают медленнее.

4 Численные методы безусловной оптимизации

4.1 Принципы построения численных методов безусловной

оптимизации

Под безусловной оптимизацией понимают процесс нахождения точки

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

чения

. В этом случае по тому или иному алгоритму (в зависимости от кон-

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

расчёт в них целевой функции, анализируются результаты расчёта в несколь-

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

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

тремума.

Эффективность конкретного метода оптимизации определяется скоро-

стью сходимости (раздел 3.2), т. е. числом пробных точек, последовательный

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

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

или иного конкретного метода.

Различают две обобщённые стратегии выбора пробных точек:

1) пассивную (параллельную);

2) активную (последовательную).

При пассивной (параллельной) стратегии пробные точки выбираются за-

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

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

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

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

При активной (последовательной) стратегии начинают расчёты с выбо-

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

от результатов расчётов в предыдущих точках.

Пассивная стратегия является наиболее универсальной, так как позво-

ляет проанализировать любую целевую функцию и выявить все её локальные

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

мумы. Фактически, речь идёт о табулировании целевой функции — расчёте

графика. Но пассивная стратегия сложно реализуется. Во-первых, в случае

вектора

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

вы-

брано

пробных точек, то для вектора из двух

будет уже

точек, а в

общем случае —

, где

— число

(размерность вектора

). Например,

при числе пробных точек



и размерности вектора



получается

общее число пробных точек

20102

10)10( 

N , что представляет собой

фантастическую величину даже для суперЭВМ. Такой рост числа пробных

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

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

случае (при безусловной оптимизации) этот интервал от –∞ до +∞, тогда

процесс расчёта, вообще говоря, может занять бесконечно большое время. В-

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

(физиче-

ский смысл переменных

может быть различным с разными единицами из-

мерения). При слишком большом шаге можно "проскочить" точку решения,

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

сивная стратегия рекомендуется тогда, когда можно каким-либо образом

установить разумные границы начального интервала (например, в случае

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

(одна-

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

чек. Название "параллельная" используется иногда для пассивной стратегии

как антоним слову "последовательный" потому, что расчёты в каждой проб-

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

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

Активная стратегия является более экономичной (эффективной) с точ-

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

мума, что является её достоинством. Недостатком активной стратегии явля-

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

функций с единственным экстремумом, вид которого (максимум или мини-

мум) заранее известен. Если имеется несколько экстремумов, то активные

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

тившийся. Он не обязательно является глобальным. Остальные локальные

экстремумы остаются неизвестными.

Иногда используют смешанные стратегии: на начальном этапе приме-

няют пассивную стратегию, пытаясь оценить общие свойства целевой функ-

ции, в частности, наличие у неё глобального и локальных экстремумов, их

вид, примерные интервалы их размещения. При этом выбирают сравнитель-

но большой шаг между пробными точками. Затем внутри каждого интервала

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

более точные значения точек экстремума.

При построении алгоритма расчётов обязательно используют значения

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

также производные целевой функции.

Из необходимых условий оптимизации (раздел 2.1) следует, что в точке

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

многих переменных в векторе

— его градиент равен нулю). Таким обра-

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

градиент) и двигаться в направлении её уменьшения.

Известно также, что в соответствии с достаточными условиями можно

рассчитывать вторую производную (или матрицу Гессе в случае вектора

) и

по её знаку определять характер экстремума — минимум или максимум. Та-

кие расчёты в пробных точках также помогают определиться с направлением

движения. В соответствии с использованием производных выделяют методы

оптимизации:

1) нулевого порядка — когда в расчётах используют только целевую

функцию;

2) первого порядка — когда в расчётах используют целевую функцию и

её первую производную (или градиент);

3) второго порядка — когда в расчётах используют целевую функцию и

вторую производную (или матрицу Гессе), при этом часто используют также

первую производную (или градиент).

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

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

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

целевых функций, имеющих две непрерывных производных.

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

дачу можно решить аналитически (раздел 2). Если возможно применение ме-

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

шения, которая может быть или не быть точкой экстремума, а затем числен-

но доопределить её тип (максимум, минимум, точка перегиба). Для этого

можно левее и правее найденной точки выбрать ещё по одной пробной точке

и вычислить в них целевую функцию (в дополнение к уже найденному зна-

чению целевой функции в найденной точке), а затем сравнить между собой

полученные три значения. Если значение слева больше, а значение справа

меньше значения в найденной точке (или наоборот), то найденная точка —

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

точках слева и справа меньше, чем в найденной точке, то она — максимум, в

противном случае — минимум.

4.2 Методы нулевого порядка

4.2.1 Общая характеристика методов нулевого порядка

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

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

мы к любым целевым функциям. Но они не являются полностью универсаль-

ными в том смысле, что эффективность метода зависит от постановки задачи

оптимизации. В частности, есть разница между одномерной задачей оптими-

зации (когда вектор

имеет лишь одну составляющую) и многомерной (ко-

гда вектор

имеет несколько составляющих). При единственном

легко

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

необхо-

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

Выделяют как самостоятельные следующие методы нулевого порядка:

1) метод равномерного поиска;

2) метод деления интервала пополам;

3) метод дихотомии;

4) метод золотого сечения;

5) метод Фибоначчи.

4.2.2 Метод равномерного поиска

Метод равномерного поиска является наиболее простым методом

нахождения экстремума (Рисунок 4.1). Он заключается в том, что начальный

интервал разбивается на равные отрезки (шаги)



и в соответствующих точ-

ках рассчитываются значения целевой функции. Затем осуществляется пере-

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

её максимальное и минимальное значения. В соответствии с названием мето-

да все интервалы (шаги) равны между собой. В этом методе используется па-

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

)

(

1min

2max

2min

1max



Рисунок 4.1 — Метод равномерного поиска

Большим достоинством метода является то, что он позволяет найти гло-

бальный экстремум, причём как максимум, так и минимум. В том числе, в