- •А.В. Аттетков, С.В. Галкин, В.С. Зарубин
- •ПРЕДИСЛОВИЕ
- •Задания для самопроверки
- •ОСНОВНЫЕ ОБОЗНАЧЕНИЯ
- •Буквы латинского алфавита
- •Буквы греческого алфавита
- •1. ЗАДАЧИ ОПТИМИЗАЦИИ
- •1.1. Основные понятия
- •1.2. Некоторые простые примеры
- •1.3. Задачи оптимального проектирования
- •1.4. Задачи оптимального планирования
- •1.5. Классы задач оптимизации
- •Вопросы и задачи
- •2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ
- •2.1. Предварительные замечания
- •2.3. Оптимальный пассивный поиск
- •2.4. Методы последовательного поиска
- •2.5. Сравнение методов последовательного поиска
- •2.6. Методы полиномиальной аппроксимации
- •2.7. Методы с использованием производных
- •Вопросы и задачи
- •3. МИНИМИЗАЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ
- •3.2. Выпуклые функции
- •3.4. Условия минимума выпуклых функций
- •3.5. Сильно выпуклые функции
- •ф{t) = (grad/(а; + th), h)
- •3.6. Примеры минимизации квадратичных функций
- •3.7. Минимизация позиномов
- •Qj = '%2aijci = Q> J = !.*»•
- •Вопросы и задачи
- •4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ
- •4.1. Релаксационная последовательность
- •4.2. Методы спуска
- •4.4. Минимизация квадратичной функции
- •4.5. Сопряженные направления спуска
- •5. АЛГОРИТМЫ МЕТОДОВ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ
- •|iufc|
- •5.3. Метод Ньютона
- •5.4. Модификации метода Ньютона
- •5.5. Квазиньютоновские методы
- •Вопросы и задачи
- •6. АЛГОРИТМЫ ПРЯМОГО ПОИСКА
- •6.1. Особенности прямого поиска минимума
- •6.2. Использование регулярного симплекса
- •6.4. Циклический покоординатный спуск
- •6.5. Метод Хука — Дживса
- •Щ + bjej,
- •6.6. Методы Розенброка и Пауэлла
- •Вопросы и задачи
- •7. АНАЛИТИЧЕСКИЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- •7.2. Минимизация при ограничениях типа равенства
- •7.4. Седловая точка функции Лагранжа
- •7.5. Двойственная функция
- •7.6. Геометрическое программирование
- •Вопросы и задачи
- •8. ЧИСЛЕННЫЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- •8.1. Метод условного градиента
- •8.2. Использование приведенного градиента
- •8.5. Метод проекции антиградиента
- •СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
- •ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
- •ОГЛАВЛЕНИЕ
- •Математика в техническом университете Выпуск XIV
- •Аттетков Александр Владимирович Галкин Сергей Владимирович Зарубин Владимир Степанович
- •МЕТОДЫ ОПТИМИЗАЦИИ
4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ
Численное решение задач безусловной минимизации функ ций многих переменных, как правило, значительно сложнее, чем решение задач минимизации функций одного переменного. В самом деле, с ростом числа переменных возрастают объемы вычислений и усложняются конструкции вычислительных алго ритмов, а также более сложным становится анализ поведения
целевой фунции.
Методы численного решения задач многомерной безуслов ной минимизации многочисленны и разнообразны. Условно их можно разделить на три больших класса в зависимости от ин формации, используемой при реализации метода.
1 . М етоды нулевого порядка, или прямого поиска, стратегия которых основана на использовании информации только о свойствах целевой функции.
2. Методы первого порядка, в которых при построе нии итерационной процедуры наряду с информацией о целевой функции используется информация о значениях первых произ водных этой функции.
3. Методы второго порядка, в которых наряду с ин формацией о значениях целевой функции и ее производных первого порядка используется информация о вторых производ ные функции.
Методы первого и второго порядков хорошо разработаны. Для большинства из них имеется строгое обоснование, прове дено аналитическое исследование их свойств, доказана сходи мость, получены оценки скорости сходимости для некоторых классов целевых функций. Описание алгоритмов этих мето дов и иллюстрирующие эти алгоритмы примеры представлены
ниже (см. 5). Методы прямого поиска (см. 6) менее изучены, большинство из них носят эвристический характер и не имеют теоретического обоснования. В то же время, они достаточно просты в реализации, что предопределяет их широкое приме нение при решении прикладных задач оптимизации.
В настоящее время не существует универсального метода, применимость которого была бы оправдана и эффективна во всех случаях. Выбор того или иного метода, его программная реализация должны быть согласованы с конкретными условия ми, вытекающими из специфики решаемой задачи безусловной минимизации. В этой главе изложены некоторые общие свой ства численных методов безусловной минимизации.
4.1. Релаксационная последовательность
Пусть требуется найти точку ж* Е Мп, в которой ограничен ная снизу целевая функция /(ж ), определенная в R71, достигает своего наименьшего значения. Будем считать, что эта точка существует, так что задачу оптимизации можно представить в виде
/ ( ж ) min, хеШ 71 |
(4.1) |
Отметим, что такая точка может быть и не единственной. Общей чертой всех численных методов решения этой задачи
является последовательный переход от точки x k~l к точке х к, k Е N, начиная с некоторой начальной точки ж0 G Кп, причем
на каждой итерации с номером к выполняется условие |
|
fk = f ( x k) S* f(x k~1) = Д _ 1, k e N. |
(4.2) |
Так как целевая функция ограничена снизу, то в силу признака Вейерштрасса [I] невозрастающая последовательность {Д } схо дится к некоторому пределу. Однако из этого в общем случае еще не следует, что итерационная последовательность {ж^}
точек a;fcEMn, соответствующих значениям /*, сходится, а если она и сходится, то ее пределом является точка х* £ Кп миниму ма функции /(ж ), удовлетворяющая (4.1).
Последовательность {х к} уэлементы х к £ Шп которой удовле творяют неравенству (4.2), называют релаксационной. Чи сленные методы, применяемые для построения такой последо вательности, относят к классу методов спуска. Это назва ние можно связать, с тем, что, например, при минимизации функции f(x 1,^2) двух переменных уменьшение ее значения
при переходе от точки (x^—1, |
х) к точке |
{xk,xk) |
означа |
ет спуск с линии уровня f(x 1,2:2) = fk-i на |
линию |
уровня |
/ ( s и х2) = fk < fk-V
При анализе сходимости релаксационной последовательнос ти удобно рассматривать невозрастающую последовательность
Ш , где <pk = fk - f* > 0 (при (рк - 0 принимаем х* = х к).
Для оценки сходимости этой последовательности используют следующие утверждения*
Лемма 4.1. Если для элементов последовательности
выполнены условия |
|
|
|
|
Щ-1 ~<Рк> 7fc¥>Li> |
4>к- 1 > 0, |
7fe ^ 0, keN , |
(4.3) |
|
то справедлива оценка |
|
|
|
|
<Рт<-------S W |
- , |
гпе N. |
(4.4) |
|
1 |
+ ¥>о Е |
7fc |
|
|
|
fc=i |
|
|
|
◄ После почленного деления первого неравенства в |
(4.3) на |
|||
<Pk-i<Pk находим |
|
|
|
|
|
1 |
<Рк- |
> 7 к- |
|
|
|
|
|
<Рк |
<Рк- 1 |
4>к |
Суммируя это неравенство по /с от 1 до тп, получаем
771 л |
л |
л |
л |
ТП |
£r[\<Pk |
4 > к -4 > т |
Ч>0 |
£ £ |
откуда следует (4.4). ►
Теорема 4.1. Пусть минимизируемая функция /(® ) вы пукла и дифференцируема на множестве а последователь ность {х к} является релаксационной. Если
___________fk—1 fk_________ |
к е N, |
(4.5) |
||
|grad/(®fc-1)|2 1®*- 1 |
— ®*|2’ |
|||
|
|
то справедлива оценка (4.4). ◄ С учетом (4.10) запишем
<Рк- 1 ~<Рк = f k - 1 — fk —
______________f k - 1 ~ fk
' («r a d /<x ‘ “ 1)- x ‘ " ‘ - x ' ) 2 *
fk- 1 “ /fc
|grad/(® fc_1)|2 |®fc_1 — x*\2^k~l
Согласно лемме 4.1, получаем оценку (4.4). ►
Чтобы использовать теорему 4.1, необходимо располагать оценками для значений 7^, определяемых равенствами (4.5). В общем случае получить такие оценки до проведения численного решения задачи достаточно сложно, а в процессе этого реше ния остается неизвестной разность х к~1 —х* Однако для не которых численных методов безусловной минимизации удается установить, что 7 ^ const > 0 начиная с некоторого номера к. Тогда в соответствии с (4.4) величина <рт имеет порядок мало сти 1 /т при т -> оо.
Если для дифференцируемой в К" функции /(® ) множест во Хо = {® € Шп: /(® ) ^ /(® 0)} ограничено, т.е. его диаметр
diamXo = rj(x°) = rj конечен, то \xk 1 —х*\ ^ 77, и поэтому в условиях теоремы 4.1 с учетом (4.5) имеем
>fk—l - fk
^k ' 772|grad/(ccfc“ 1)|2’
В итоге оценка (4.4) принимает вид
= ----------- |
m ---------------- |
, m 6 N. |
(4.6) |
1 _i_ |
Л —1 —fk |
|
|
V2 |
Igrad/ ^ |
- 1)!2 |
|
Сумма в правой части полученной оценки имеет нулевое значение, если последовательность {Д } постоянна. Предполо жим, что эта последовательность не является постоянной и для некоторого номера га выполнено неравенство ffh-i ~ fm > 0- То гда при га > га
771 |
|
fin—l frh |
|
Л - 1 - fk |
2 |
|
|
Е|gradf { x k~l |
|grad f(x k~l)I2 |
> 0 |
и, отбрасывая в знаменателе правой части (4.6) единицу, полу чаем оценку
4>т = /го - /• < |
77 |
(4.7) |
--------- -------, m ^fh. |
||
E |
/fc- 1 —fk |
|
K=L I grad/(ж * -1) I2 |
|
Оценку (4.7) легко вычислить, и ее использование в процессе численного решения задачи минимизации не вызывает затруд нений.
Лемма 4.2. Если для элементов последовательности {(рь} выполнены условия
<Рк- 1 |
^ Wife- 1 j |
4>к- 1 > о , Tfc^O, к е N, |
(4.8) |
то справедлива оценка
ТТ1
4>т< </>оехр( ~ £ п ) , т е К |
(4.9) |
к=1
◄ Из неравенств в (4.8) следует, что rjt 6 (0,1) и га
фт ^ (1 ~ Тт)фт—1 ^ ^РО
к=1
Отсюда, учитывая, что 1 — ^ ехр(—т>), приходим к (4.9). ►
Пусть минимизируемая целевая функция f(x ) является вы пуклой и дифференцируемой на множестве Шп. Тогда, согласно теореме 3.11 и неравенству Коши — Буняковского, для любого k Е N получаем
О < (pk-i = Д _ 1 - / , < (grad/(®fc-1), ж*-1 - ж*) ^
^ |grad/(®fc_1)j |ж*- 1 .-ж*|. (4.10)
Теорема 4.2. Пусть функция f(x ) выпукла и дифференци руема в Кп, множество X Q = {х Е W1: f(x ) ^ /(ж 0)} ограниче но, а последовательность {а^} является релаксационной. Если
|
|
|
|
* € Ч |
(4-п ) |
|
где г) = diamXo |
— |
диаметр множества |
X Q , то |
справедлива |
||
оценка (4.9). |
|
|
|
|
|
|
◄ Используя (4.10) и учитывая, что |ж*- 1 |
— as*|^ т), находим |
|||||
Ч>к-\ — <Р к= Д - 1 |
- |
Д ^ |
( Д - 1 ~ 1к)<Рк-\ |
|
||
|grad/ (аг*- 1) 1 |ж*- 1 — ж* |
|
|||||
|
|
|
ъ |
( Д - 1 - |
fk)y>k- 1 |
_ |
|
|
|
^ |
7?|grad/(a;fc- 1)| |
T m “ 1 |
Согласно лемме 4.2, получаем оценку (4.9). ►
При выполнении условий теоремы 4.2 оценка (4.9) имеет вид
f ( x m) - f ( x * )
Д®°) - /( * * ) |
|
|
i)- |
(4Л2> |
Теорема 4.3. |
Для сильно выпуклой и дифференцируемой |
|||
в Rn функции f(x ) |
при |
|
|
|
|
_ |
fk- 1 - fk |
k e N, |
(4.13) |
Tk |
|
7 |grad/(®fc- 1)|2’ |
где 7 — параметр сильной выпуклости функции / (ж), справед ливы оценки (4.9) и
\хт- |
х*\г ^ |
т е N. |
(4.14) |
|
|
7 |
|
◄В силу теоремы 3.18 |
при k е N имеем |
|
|
<Рк= fk - Л < -|grad/(a:fc)|2, |
|®fc - ®*|2 < 2—— — = -tpk. |
||
7 |
|
7 |
7 |
Последнее неравенство равносильно оценке (4.14), а из первого неравенства вытекает, что
fk—l —fk |
= Тк<Рк' |
Фк- 1 ~ tPk = f k - l - fk > |gra(i |
Согласно лемме 4.2, получаем оценку (4.9). ►
Заменяя в оценке (4.9) величины тк их выражениями по формулам (4.13), а также величины щ — fk~ f*i приходим к следующей оценке:
/(« " ■ ) - /(» • ) < ( у - |
Л - 1 - Д |
m €N . (4.15) |
/(* ° ) -/(* * ) |
Р\ 7“ |grad/(x‘ - ‘ )|2 |
Используя (4.14) и (4.9), а затем заменяя |
величины |
по |
|
формулам (4.13), получаем оценку |
|
|
|
\хт —х * |2 |
fk—1 fk \ |
771 £ N. |
(4.16) |
|
|grad/(®fc_1)|2/ |
||
|
’ |
|
Эти две оценки позволяют в процессе численного решения за дачи минимизации накапливать информацию о приближении значений Д к значению /*, а в случае сильно выпуклой мини мизируемой функции — и о приближении точки х к к искомой точке х* минимума этой функции.
Практически можно задать некоторое число е > 0, связанное с выбранной точностью вычислений, и проводить итерации до тех пор, пока не будет нарушено неравенство
Д - 1 - д |
(4.17) |
|grad/(ж* -1U2 ^ £, k Е N , |
а затем либо повысить точность вычислений, либо перейти к другому методу спуска.
Поиск точки х* обычно прекращают при выполнении на к-й итерации одного или обоих неравенств:
|*fc - я*-1 ! < £Ь |/(xfc) - f(x k~l)\< £2, (4.18)
где £\ и £2 — заданные достаточно малые положительные чи сла, называемые параметрами точности поиска. В слу чае минимизации дифференцируемой функции необходимым условием того, что ж* Е W1— точка ее минимума, является ра венство grad /(ж*) = 0. При этом условием прекращения поиска на к-й итерации может быть выполнение неравенства
|grad/(xfc_1)| < £ 3, £3 > 0 . |
(4.19) |
Если при проведении итераций к значению Д = /(ж*) схо дится последовательность {Д } значений Д = f ( x k) миними зируемой функции /(ж ), то говорят о слабой сходимости применяемого метода (или соответствующего алгоритма), а если сходится к точке ж* и последовательность {ж*}, то о силь ной сходимости этого метода (или алгоритма).