Общие сведения о численных методах оптимизации. Условия оптимальности.

Как мы видели в § 1 (см. пример 1.1), иногда удается получить решение задачи оптимизации в явном виде, но в большинстве случаев ее приходится решать численно, с применением ЭВМ. Причем, как правило, наиболее эффективными оказываются методы, разработанные специально для решения задачи оптимизации.

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

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

3.1 Понятие о численных методах оптимизации. Любой численный метод (алгоритм) решения задачиоптимизации основан на точном или приближенном вычислении ее характеристик (значений целевой функции и функций, задающих границу допустимого множества, а также их производных). На основании полученной информации строится приближение к решению задачи - искомой точке минимума х* или, если такая точка не единственна, к множеству точек минимума. Иногда, если это требуется, строится приближение к минимальному значению целевой функции f*.

Алгоритмы, использующие лишь информацию о значениях минимизируемой функции, называются алгоритмами нулевого порядка; алгоритмы, использующие также информацию о значениях первых производных – алгоритмами первого порядка; алгоритмы использующие, кроме того, информацию о вторых производных – алгоритмами второго порядка.

Работа алгоритма состоит из двух этапов. На первом этапе вычисляются предусмотренные алгоритмом характеристики задачи. На втором этапе по полученной информации строится приближение к решению. Обычно для задания алгоритма достаточно указать способ выбора точек приближения x^k = (х₁^k, …, х_n^k) Î C, k= 1, 2…, (конечно, при условии, что уже решен вопрос о том, какие именно характеристики решаемой задачи следует вычислять).

Определение 1.4. Выбор точек приближения называется поиском точек.

Если все точки выбираются одновременно до начала вычислений, то алгоритм минимизации называется пассивным. Однако для решения большинства задач точки приближения выбираются поочередно, т.е. точка х ^{( k+ 1)} выбирается тогда, когда уже выбраны точки предыдущих вычислений х ⁽¹⁾, х ⁽²⁾, …, х ^{( k )} и в каждой из них произведены предусмотренные алгоритмом вычисления. Такие алгоритмы называются последовательными.

Определение 1.5. В последовательных алгоритмах вычисление предусмотренных алгоритмом характеристик задачи в точке х ^{( k )}и поиск точки х ^{( k+ 1)}вместе составляют шаг метода или, что то же самое, итерацию метода.

Методы оптимизации можно условно разделить на две основные группы: конечношаговые и бесконечношаговые. Конечношаговыми или конечными, называются методы, гарантирующие отыскание решения задачи за конечное число шагов. Бесконечношаговыми называются методы, для которых достижение решения гарантируется лишь в пределе.

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

Определение 1.6. Будем говорить, что метод сходится если последовательность х ^{( k )}® х *при k ®¥, где х* - решение задачи (1.1) Если f (x ^{( k )}) ® f (x *), при k ®¥, то последовательность х ^{( k )} называют минимизирующей.

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

Рис. 1.1.

которой изображен на рис. 1.1, минимизирующая последовательность х ^{( k )} = k не сходится к точке минимума х * = 0. В случае, когда точка минимума х * не единственна, под сходимостью метода понимается следующее: для каждой точки х * минимума функции f можно построить данным методом такую последовательность х ^{( k )} Î Х,, что х ^{( k )} ® х *при k ® ¥.

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

Определение 1.7. Пусть { х ^{( k )}}Î C и х ^{( k )} ® х * при k ®¥. Говорят, что последовательность х ^{( k )} сходиться к х *

а) линейно (с линейной скоростью или со скоростью геометрической прогрессии), если существуют константа 0 < q < 1 и натуральное число k ₀ такие, что

|| х ^{( k+ 1)} - х* || £ q || х ^{( k )} - х* || при k ³ k ₀; (1.4)

б) сверхлинейно (со сверхлинейной скоростью), если

|| х ^{( k+ 1)} - х* || £ q_{k +1} || х ^{( k )} - х* ||, q_k ® +0 при k ® ¥. (1.5)

в) квадратично, если существуют константа С ³ 0 и натуральное число k ₀ такие, что

|| х ^{( k +1)} - х* || £ С || х ^{( k )} - х *||² при k ³ k ₀. (1.6)

Установление факта сходимости и оценка скорости сходимости дают существенную информацию о выбранном методе минимизации. Прежде всего, требования которые приходится накладывать для обеспечения сходимости на минимизируемую функцию, показывают область применимости метода. Часто условия сходимости включают в себя, в явном виде требования к начальному приближению. Наконец, анализ скорости сходимости дает полезную количественную и качественную характеристику изучаемого метода оптимизации.

В то же время реальный процесс оптимизации не может быть бесконечношаговым. Кроме того, в ряде случаев условия сходимости труднопроверяемы. Поэтому при выборе подходящего метода решения реальных задач приходится во многом руководствоваться здравым смыслом, опытом, интуицией, а также результатами численных экспериментов. Необходимо также учитывать погрешность исходных данных.

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

3. Условия остановки (критерии окончания счета). Условие остановки может определяться имеющимися в наличии вычислительными ресурсами. Например, может быть задано количество вычислений предусмотренных алгоритмом характеристик минимизируемой функции f.

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

На практике часто используются следующие условия остановки:

|| x ^{(k +1)} - x ^(k) || £ e₁, (1.7)

| ¦(х ^{( k +1)}) - ¦(х ^{( k )})| £ e₂, (1.8)

(1.9)

До начала вычислений выбирается одно из условий (1.7)-(1.9) и соответвствующее ему малое положительное число e _i. Вычисления прекращаются после (k +1)-го шага, если впервые оказывается выполненным выбранное условие остановки. На практике также используются критерии окончания, состоящие в одновременном выполнении двух из условий (1.7)-(1.9) или всех трех сразу.

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

4. Условия оптимальности в общей задаче оптимизации. При изучении любого типа задач оптимизации важное место занимает вопрос об условиях оптимальности, или, как еще говорят, условиях экстремума. Различают необходимые условия оптимальности, т.е. условия, которым должна удовлетворять точка, являющaяся решением задачи, и достаточные условия оптимальности, т.е. условия из которых следует, что данная точка является решением задачи. Интерес к условиям оптимальности объясняется тем, что они во-первых составляют основу качественных методов теории оптимизации, т.е. методов, направленных на изучение свойств задач оптимизации; во-вторых, используются при построении и обосновании численных методов решения этих задач; в третьих, позволяют в простых случаях явно решить задачу. Примером необходимого условия оптимальности является хорошо известное из курса высшей математики свойство безусловного экстремума функции в точке: если функция ¦=¦(х ₁, ¼, х_n) достигает экстремума в точке х*= (х ₁ *, …, х_n *) и является непрерывно дифференцируемой в х*, то ее градиент в этой точке равен нулю.

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

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

1. Сформулируйте общую задачу оптимизации.

2. Дайте определение следующих понятий: целевая функция, допустимое множество, допустимая точка, решение задачи оптимизации.

3. Перечислите основные этапы реализации оптимизационной задачи.

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

5. Приведите примеры оптимизационных задач из практики.

6. Дайте классификацию задач оптимизации.

7. В чем отличие локального минимума от глобального? Проиллюстрируйте примером.

8. Дайте определение строгого минимума.

9. Сформулируйте теорему Вейерштрасса о существовании решения задачи оптимизации.

10. Что понимается под характеристиками задачи оптимизации?

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

12. Какие алгоритмы называют последовательными и какие пассивными?

13. Перечислите основные этапы работы численного алгоритма.

14. Дайте определения следующих понятий: шаг (итерация) метода, конечношаговые и бесконечношаговые методы.

15. Что означает утверждение “Метод сходится”?

16. Что такое минимизирующая последовательность.

17. Чем определяется эффективность сходящегося метода?

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

19. Какие условия остановки счета используются на практике?

20. В чем состоит общая суть всех критериев оптимальности допустимой точки?

21. Укажите все глобальные и локальные экстремумы (если они существуют) следующих функций: а) f = (2 - x)(x + 1)²; б) f = ln(x ² + 1); в) f = x - 2sin x ².

22. Укажите все глобальные и локальные экстремумы функции f = 2 - 3 x + x ³ на множестве а) Х = [-2, 1]; б) Х = [-2, 0].

Глава 2. Методы безусловной