- •А.В. Аттетков, С.В. Галкин, В.С. Зарубин
- •ПРЕДИСЛОВИЕ
- •Задания для самопроверки
- •ОСНОВНЫЕ ОБОЗНАЧЕНИЯ
- •Буквы латинского алфавита
- •Буквы греческого алфавита
- •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
- •Аттетков Александр Владимирович Галкин Сергей Владимирович Зарубин Владимир Степанович
- •МЕТОДЫ ОПТИМИЗАЦИИ
Это означает, что множество X Q целиком попадает в п-мерный шар с центром в точке х° и радиусом
„ Гг 4(/(ж°) —М) 1 Д = тах|5, --------—--------
т.е. оно ограничено.
На замкнутом ограниченном множестве X Q непрерывная функция f(x) достигает своего наименьшего значения [V] в некоторой точке х* Так как при х Е £2 \ X Q выполняются со отношения f(x) > /(ж 0) ^ /(ж*), точка х* является точкой наи меньшего значения функции и в пределах множества Г2. ►
Замечание 3.5. Теорема 3.19 перестает быть верной, если в ней условие сильной выпуклости заменить условием выпук лости или строгой выпуклости: строго выпуклая (в частности, выпуклая) функция может и не достигать своего наименьшего значения на замкнутом множестве. Такова, например,.функция f(x) = е х одного действительного переменного. Вторая произ водная этой функции положительна: f n(x) = ех. Поэтому она является строго выпуклой. В то же время функция f(x) воз растающая и не имеет точек локального минимума, т.е. она не достигает наименьшего значения.
3.6. Примеры минимизации квадратичных функций
Использование необходимого и достаточного условий ло кального минимума выпуклой функции рассмотрим на при мерах минимизации квадратичных функций. Любая квадра тичная функция f(x) может быть представлена в виде суммы f(x) = (фж, ж) + (с, х) квадратичной (Qx, х) и линейной (с, х) форм, при этом матрица Гессе Н(х) этой функции постоянна и связана с матрицей Q квадратичной формы соотношени ем Н = 2Q.
Рассмотрим квадратичную функцию |
|
1(я) = ^(Нх,х) + (с,х) |
(3.37) |
с положительно определенной матрицей Гессе |
Н порядка п |
и фиксированным вектором с Е К71. Градиент этой функции равен
grad/(ж) = Нх + с. |
(3.38) |
Так как матрица Н положительно определена, то она имеет обратную матрицу Н~1. Из необходимого условия grad f{x*) =
=0 локального минимума функции с учетом (3.38) находим, что функция имеет единственную стационарную точку х* =
=- Н ~ 1 с.
Рассматриваемая функция сильно выпуклая на выпуклом множестве Шп (см. пример 3.13). Значит, эта функция строго выпуклая (см. 3.5). Поэтому, согласно теоремам 3.14 и 3.15, необходимое условие локального минимума является и доста точным условием. В стационарной точке х * функция (3.37) принимает значение
/(* * ) = ~\ {НН-'с, H~lc) + (с, H~lc) = 1 (с, Н~1 с ) . (3.39)
Отметим, что если матрица Н квадратичной функции не является положительно определенной, то она может быть выро жденной. В этом случае либо функция не имеет стационарных точек, либо стационарных точек бесконечно много.
Пример 3.15. Исследуем на минимум функцию f(x 1,0:2) = = х\ + 2Х\Х2 + 4 ж2.
Рассматриваемая функция представляет собой квадратич
ную функцию с матрицей Гессе |
|
|
Н = 2 |
1 |
1 |
1 |
4 |
Нетрудно проверить (например, с помощью критерия Силь вестра), что матрица Н положительно определенная. Зна чит, функция имеет единственную стационарную точку х* = = —Н~1с = —Н ~10 = 0, в которой принимает наименьшее зна чение.
Пример 3.16. Квадратичная функция/(я 1,22) = х2 + 2 х\Х2 также представляет собой квадратичную форму и имеет ма трицу Гессе
Эта матрица знаконеопределенная, но является невырожден ной. Поэтому функция имеет единственную стационарную точку х* = —Н ~ 1 0 = 0 . Но поскольку функция не выпуклая (матрица не является неотрицательно определенной), делать какие-либо заключения о наличии экстремума в точке х* нель зя. И действительно, точка 0 не является ни точкой локального минимума, ни точкой локального максимума, так как ее матри ца Гессе в этой точке знаконеопределенная [V].
Нетрудно убедиться, приведя квадратичную форму к кано ническому виду, что график рассматриваемой функции пред ставляет собой гиперболический параболоид с седловой точкой
(О, 0). |
Функция ip(t) = /(£,()) = t2 |
(сечение |
функции f(x 1,^2) |
при Х2 |
= 0) имеет при t = 0 строгий локальный минимум, в |
||
то время как функция ф(Ь) = |
= —t2 |
(сечение функции |
f{x 1,^2) при х\ = —Х2 ) при t = 0 имеет строгий локальный мак симум.
Пример 3.17. Квадратичную функцию f(x 1 ^x2 ) =х\ + + 2 х\Х2 + х\ можно записать в виде f(x 1,2:2) = (#i + Я2)2 От сюда сразу следует, что она достигает наименьшего значения, равного нулю, в каждой точке прямой х\ + Х2 = 0. Матрица Гессе этой функции имеет вид
и является неотрицательно определенной. Значит, функция вы пуклая, а каждая стационарная точка является точкой наи меньшего значения функции. Необходимое условие локального минимума приводит к системе уравнений
Г 2xi + 2х2 = О,
\ 2xi + 2х2 = О,
из которой заключаем, что стационарной является любая точка вида (t, —t), t G К, т.е. точка, лежащая на прямой xi + Х2 = 0.
Приведя квадратичную форму /(х 1,хг) = (xi +Х 2)2 к кано ническому виду, легко убедиться, что график функции пред ставляет собой параболический цилиндр [III].
Пример 3.18. Квадратичная функция
/ (xi,Х2) = 6х2 - 4X IX2 + 3x2 + 4>/5(xi + 2x2) + 22 |
(3.40) |
далее используется в качестве базовой при сравнительном ана лизе различных численных методов безусловной минимизации и выявлении достоинств и недостатков их вычислительных свойств. Поэтому представляет интерес подробное аналити ческое исследование свойств этой функции.
Функцию /( х i,X2) можно представить в виде
f(x) = (А х , х) + (Ь, х) + с, |
(3.41) |
где х = (xi, Х2) Е К2,
Матрица А положительно определенная, так как имеет угловые миноры A I = 6 > 0 H A 2 = 6*3 —(—2)2 = 14 > 0. Значит, рассма триваемая функция сильно выпуклая в М2 и имеет единствен ную стационарную точку ж*, являющуюся точкой наименьшего
значения. Эту точку можно найти по формуле х* = —Н 1Ь, где Н = 2 А — матрица Гессе функции. Так как
А~ 1 |
W 3 |
2 \ |
|
14 V2 |
6 / ’ |
||
|
|||
* = _JL_ /3 |
Л ( 4v/^ |
= ( ~ ^ \ |
|
Х ~ 28 ( 2 |
6 ) { s V 5 j ~ V - 2 ^ ; - |
В этой точке функция принимает значение /(ж*) = —28. Приведем квадратичную форму (Аж, ж) функции к канони
ческому виду. Для этого найдем собственные значения матри цы А, составив ее характеристическое уравнение det(A —XI) = = 0, где I — единичная матрица второго порядка. В данном случае это уравнение имеет вид
Раскрывая определитель в левой части уравнения, получаем (6 — А) (3 —Л) —4 = 0, или А2 —9А + 14 = 0. Это квадратное уравнение имеет корни Ai = 2 и Аг = 7, которые и являются собственными значениями матрицы А. Поскольку собственные значения различны, а матрица А симметрическая, то соответ ствующие этим собственным значениям собственные векторы ортогональны [V].
Координаты собственных векторов найдем, решая СЛАУ (А —А/)е = 0, которая при A = AI = 2 H A = A2 = 7 с в о д и т с я к соответствующим системам
4^1 - 2x2 = 0, |
Г |
—х \ - |
2x2 = 0, |
{- 2 xi + Х2 = 0, |
} |
- 2 xi - |
4^2 = 0. |
Решением первой системы является вектор (1 2)т , а второй — вектор (—2 1)т Нормируя эти векторы, получаем единичные
векторы е° = (l/\/5 2/у/Ь) и е\ = (—2/л/5 1/\/б) , образую щие в М2 ортонормированный базис. В этом базисе матрицей
квадратичной формы является диагональная матрица Л с диа гональными элементами, совпадающими с собственными зна чениями, а квадратичная форма (А х , х) примет канонический вид (Лу, у) = Aiу\ + Х2У2 = 2у? + 7у|, у = (уъ у2).
Координаты собственных векторов е° и е^, записанные по столбцам, формируют матрицу перехода U к новому, канони ческому базису, которая в данном случае имеет вид
_L - ± \ у/Ъ Vb
2 1 7!
\у/Е л/5 /
Поскольку матрица U определяет переход от одного ортонормированного базиса к другому, она является ортогональной [IV]. Поэтому обратную матрицу С/-1 можно найти с помощью транспонирования: С/-1 = С/т С помощью матрицы перехода можно найти координаты вектора Ъв новом базисе по формуле Ь° = U- 1 Ь, что в рассматриваемом случае дает
b° A = J _ ( 1 2 W 4 V 5 |
20 |
ЩJ ~ л/5 V- 2 1 ) I 8у/5 |
0 |
Таким образом, квадратичная функция в новой системе коор динат принимает вид
fi{yi >У2 ) = 2у\ + 7у\ + 20yi + 22.
С помощью выделения полных квадратов проводим дальнейшее упрощение вида функции:
/ПУьУг) = 2(yi + 5)2 + 7уз - 28,
или / 2(21,Z2 ) = 2z\ + 7z\ - 28, где z\ = у\ + 5 и z2 = у2. Из найденного представления функции вытекает, что график рас сматриваемой функции представляет собой эллиптический па раболоид [III].