Методы оптимизации

Назад § 2. Задача безусловной оптимизации Вперед

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

Зигмунд Фрейд. Введение в психоанализ

Здесь мы введем основные понятия и проведем теоретическое исследование задачи безусловной оптимизации. Отметим, что эта задача в теоретическом плане достаточно полно изучена в курсе математического анализа. Мы лишь повторим важнейшие факты, обращая внимание на "оптимизационную" специфику.

2.1. Определения.

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

f(x) ® min,(1)

где f: Rm ® R. Точка x* О Rm называется решением задачи (1) (или точкой глобального безусловного минимума функции f), если

f(x*) Ј f(x)(2)

при всех x О Rm. Если неравенство (2) выполнено лишь для x, лежащих в некоторой окрестности Vx* точки x*, то точка x* называется локальным решением задачи (1), или точкой локального безусловного минимума функции f. Если неравенство (2) строгое при всех x x*, то говорят о строгом глобальном и, соответственно, строгом локальном минимумах. Решение задачи (1) иногда обозначают argmin f(x) (или, более полно, argminxОRm f(x); когда речь идет о задачах безусловной оптимизации в обозначениях argminxОRm f(x) и minxОRm f(x) мы будем всегда опускать индекс "x О Rm"). Обычно из контекста ясно о каком минимуме (локальном, глобальном и т. д.) идет речь.

Аналогичные понятия (максимумов) определяются для задачи

f(x) ® max.

З а д а ч а  2.1. Докажите, что точка x* является точкой глобального безусловного (соответственно, локального, строгого) максимума функции f в том и только том случае, когда она является точкой глобального безусловного (соответственно, локального, строгого) минимума функции -f.

Поэтому всюду в дальнейшем мы будем заниматься только задачами о минимумах, все время помня, что задачи о максимумах к ним сводятся. Таким образом, слово "оптимизация" в нашем контексте будет всегда синонимом слова "минимизация".

2.2. О линейных операторах в Rm.

Напомним, что линейный оператор A в Rm называется самосопряженным или симметричным, если при всех x, y О Rm

(Ax, y) = (x, Ay).

Известно, что оператор A симметричен в том и только том случае, когда его матрица симметрична (т. е.переходит в себя при транспонировании).

Оператор A называется невырожденным, если у него нулевое ядро ker A, т. е. если он переводит в нуль только нуль. Другими словами, уравнение Ax = Q имеет только нулевое решение. Из курса алгебры известно, что оператор A невырожден в том и только том случае, если определитель его матрицы отличен от нуля.

Оператор A называется положительно определенным (часто пишут A > 0), если

(Ax, x) > 0

при всех ненулевых x О Rm. В соответствии с критерием Сильвестра оператор A положительно определен в том и только том случае, если все главные диагональные миноры матрицы оператора A положительны. Наконец, оператор A называется неотрицательно определенным (пишут A і 0), если при всех x О Rm

(Ax, x) і 0.

Аналогично определяются понятия отрицательно и неположительно определенных операторов.

Если оператор A - lI, где I тождественный оператор на Rm, а l О R, положительно (неотрицательно) определен, то часто пишут A > l (соответственно, A і l). Аналогично определяются записи A < l и A Ј l.

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

l Ј A Ј L,

в том и только том случае, если все точки спектра s(A) оператора A лежат на отрезке [l, L]:

l Ј li Ј L.(3)

В частности, поскольку норму в Rm мы считаем евклидовой, для симметричных операторов A имеют место утверждения

||A|| = 
max
liОs(A)
{|li|} Ј max{|l|, |L|}. 
(4)

2.3. О дифференцируемости функций на Rm.

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

Вектор a О Rm такой, что

f(x + h) - f(x) - (a, h) = o(h)

при всех h О Rm называется производной или градиентом функции f в точке x. Здесь и ниже символ o(h) обозначает произвольную функцию, обладающую свойством

o(h)
||h||
 ® 0 при h® Q.

Функция f называется при этом дифференцируемой в точке x. Градиент обычно обозначается f ў(x), или grad f(x), или Сf(x). Мы будем, как правило, использовать первое обозначение. Известно, что в координатной форме градиент имеет вид

f ў(x) = ж
и
f(x)
x1
, ..., f(x)
xm
ц
ш
 = ж
и
f(x1, ..., xm)
x1
, ..., f(x1, ..., xm)
xm
ц
ш
.

Функция f: Rm ® Rm дифференцируемая в каждой точке называется дифференцируемой.

Если дополнительно найдется линейный самосопряженный оператор A: Rm ® Rm такой, что при всех h О Rm

f(x + h) - f(x) - (f ў(x), h) - 1
2
(Ah, h) = o(h2),

где запись o(h2) означает, что

o(h2)
||h||2
 ® пpи h® Q,

то f называется дважды дифференцируемой в точке x, а оператор A называется второй производной функции f в точке x и обозначается f ўў(x) либо С2f(x). Матрицей, отвечающей оператору A = f ўў(x), служит, как нетрудно видеть, так называемая матрица Гессе или гессиан функции f:

Aж
з
з
з
з
з
з
з
и
2f(x)
x1x1
···2f(x)
x1xm
:···:
2f(x)
xmx1
···2f(x)
xmxm
ц
ч
ч
ч
ч
ч
ч
ч
ш
.

З а д а ч а  2.2*. Пусть A — линейный самосопряженный оператор в Rm, b О Rm, c О R и f(x) = (Ax, x)/2 + (b, x) + c. Докажите, что f ў(x) = Ax + b, и f ўў(x) = A.

Если функция F: Rm ® Rk, то линейный оператор A: Rm ® Rk такой, что

F(x + h) - F(x) - Ah = o(h)

называется производной функции F в точке x и обозначается F ў(x) (это обобщение понятия градиента на случай функций со значениями в Rk).

Если функция F: Rm ® R дифференцируема, то ее градиент можно рассматривать как функцию из Rm в Rm: каждому x О Rm ставится в соответствие точка из f ў(x) О Rm.

З а д а ч а  2.3*. Докажите, что [f ў(x)]ў = f ўў(x). Поясним: здесь [f ў(x)]ў производная функции x ® f ў(x), действующей из Rm в Rm, а f ўў(x) — вторая производная функции f: Rm ® Rm.

Еще одно полезное понятие. Функция F: Rm® Rk по определению удовлетворяет условию Липшица с константой L, если при всех x, y О Rm

||F(x) - F(y)|| Ј L ||x - y||.

З а д а ч а  2.4*. Пусть F: Rm ®Rk дифференцируема. Докажите, что F удовлетворяет условию Липшица с константой L, в том и только том случае, если ||F ў(x)|| Ј L при всех x.

Ниже нам потребуется следующее простое утверждение. Если f: Rm ® R дважды непрерывно дифференцируемая функция, то для того, чтобы ее градиент f ў удовлетворял условию Липшица с константой L необходимо и достаточно, чтобы при всех x О Rm выполнялось неравенство f ўў Ј L. Действительно, в силу задачи 2.3 при всех t О R и x, h О Rm

(f ў(x + th), th) - (f ў(x), th) = (f ўў(x)th, th) + (o(th), th).

Но тогда в силу условия Липшица для f ў

(f ўў(x)h, h) Ј 1
t2
|(f ў(x + th) - f ў(x), th)| + |o(th, th)|
t2
 Ј

Ј L||th||2
t2
 +  ||o(th)|| · ||th||
t2

 = L ||h||2 + 

||o(th)||
t
||h||.

Устремляя t к 0, получим неравенство

(f ўў(x)h, h) Ј L ||h||2,(5)

эквивалентное нужному неравенству f ўў(x) Ј L.

З а д а ч а  2.5. Докажите обратное утверждение.

В заключение пункта еще одно обозначение. Мы будем писать f О C, f О C1 и f О C2, если f соответственно непрерывна, непрерывно дифференцируема и дважды непрерывно дифференцируема.

2.4. Необходимое условие локального экстремума.

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

Теорема Ферма. Если f — дифференцируемая функция и x* — ее локальный минимум, то f ў(x*) = 0.

Напомним  д о к а з а т е л ь с т в о  теоремы. Допустим противное: f ў(x*) Q. Положим xt = x* - tf ў(x*) для всех t > 0. Тогда, во-первых, очевидно, xt - x* ® Q при t ® 0 и, во-вторых, по определению градиента,

f(xt) = f(x*) + (f ў(x*), xt - x*) + o(xt - x*) =

= f(x*) + (f ў(x*), -tf ў(x*)) + o(-tf ў(x*)) =

= f(x*) - й
л

||f ў(x*)||2 + 

o(-tf ў(x*))
t
щ
ы
.
(6)

Поскольку ||f ў(x*)|| > 0, а

o(-tf ў(x*))
t
 = ||f ў(x*)||· o(-tf ў(x*))
||(-tf ў(x*)||
 ® 0 пpи t® 0,

выражение в квадратных скобках в правой части (6) при всех достаточно малых t положительно и поэтому при всех достаточно малых положительных t

f(xt) < f(x*),

что противоречит тому, что x* = argmin f(x).

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

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

f ў(x) = 0,(7)

или, что то же самое, система m (вообще говоря, нелинейных) уравнений с m неизвестными

f(x1, ..., xm)
xi
 = 0,   i = 1, ..., m,

определяет точки "подозрительные на минимум". Точки, удовлетворяющие уравнению (7), называются стационарными точками функции f.

Стационарная точка x* функции f может быть либо точкой локального минимума, либо точкой локального максимума, либо не быть ни той, ни другой (см. рис. 1).

Стационарные точки
Рис. 1.
Точка (x*, y*) называется седловой точкой функции f: W1×W2 ® R (W1 М Rn, W2 М Rm), если при всех (x, y) М W1×W2 выполнены неравенства

f(x*, y) Ј f(x*, y*) Ј f(x, y*)

(см. рис. 2). Если эти неравенства выполняется лишь для x достаточно близких к x* и y достаточно близких к y*, то, естественно, добавляется эпитет локальная.

Седловая точка
Рис. 2.
Легко доказать, что седловая точка непрерывно дифференцируемой функции всегда является стационарной точкой и, очевидно, никогда не является точкой экстремума.

2.5. Теорема о локальном минимуме (необходимые и достаточные условия второго порядка).

Пусть x* — стационарная точка дважды дифференцируемой функции f. Для того, чтобы точка x* была точкой (локального) минимума функции f необходимо, чтобы оператор f ўў(x*) был неотрицательно определен и достаточно, чтобы он был положительно определен.

Д о к а з а т е л ь с т в о. Необходимость. Пусть x* — точка минимума и h произвольный вектор из Rm. Поскольку (в силу теоремы Ферма) x* — стационарная точка,

0 < f(x* + th) - f(x*) = 1
2

(f ўў(x*)th, th) + o((th)2) 

при всех достаточно малых t О R. Отсюда при всех t 0

(f ўў(x*)h, h) + o((th)2)
t2
 > 0.

Переходя в полученном неравенстве к пределу при t® 0 и учитывая, что как легко видеть, o((th)2)/t2 ® 0 при t ® 0, получим нужное неравенство

(f ўў(x*)h, h) і 0.

Достаточность. Пусть f ўў(x*) положительно определен, а стационарная точка x* не является точкой локального минимума. Последнее означает наличие последовательности x n® x* при n ® Ґ такой, что f(xn) < f(x*). Положим hn = xn - x*. По определению второй производной, учитывая, что x* стационарна,


0 > f(x* + thn) - f(x*) = 

1
2

(f ўў(x*)hn, hn) + o((hn)2). 

Если теперь обозначить hn/||hn|| через gn, то последнее неравенство (поделив его на ||hn||2) можно переписать в виде


(f ўў(x*)gn, gn) + 

o((hn)2)
||hn||2
 < 0.
(8)

Поскольку ||gn|| = 1, а сфера в Rm компактна, последовательность {gn}, не ограничивая общности, можно считать сходящейся к некоторому лежащему на ней (и следовательно, отличному от нуля) вектору g0. Предельный при n ® Ґ переход в неравенстве (8) приводит к противоречащему положительной определенности оператора f ўў(x*) неравенству

(f ўў(x*)g0, g0) Ј 0.

Теорема доказана.

З а д а ч а  2.6. Исследуйте на экстремум функцию f: R2 ® R, задаваемую формулой f(x1, x2) = x12/a+ x22/b,при различных a и b.

2.6. Замечания о существовании решений.

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

З а д а ч а  2.7. Приведите пример задачи (1) с непрерывной (или, даже, со сколь угодно гладкой) ограниченной снизу (f(x) і l при некотором l и всех x О Rm) функцией f, не имеющей решения.

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

Теорема о разрешимости задачи безусловной оптимизации. Пусть функция f непрерывна и при некотором a О Rm множество Sa = {x О Rm: f(x) Ј a} непусто и ограничено. Тогда задача (1) имеет по крайней мере одно решение.

Д о к а з а т е л ь с т в о. Множество Sa замкнуто.

З а д а ч а  2.8*. Докажите.

Поэтому Sa — компактное подмножество Rm. В силу теоремы Вейерштрасса, очевидно, функция f достигает на Sa своего минимума: x* = argminxОSa f(x). Очевидно, x* — решение задачи (1), поскольку f(x*) Ј a в Sa, а вне Sa функция f принимает значения бóльшие a.

З а д а ч а  2.9. Приведите пример (непостоянной) функции f, для которой задача (1) разрешима, а условия теоремы 2.6 не выполнены.

2.7. Замечания о единственности решений.

Вопрос о единственности (как, впрочем, и о существовании) решений весьма важен в теоретическом плане. Например, если x* — единственное решение задачи (1) и {xk} М Rm ограниченная последовательность такая, что f(xk) ® f(x*) = min f(x) при k® Ґ, то xk ® x* = argmin f(x) при k ® Ґ. Такое свойство бывает полезным при исследовании приближенных методов решения оптимизационных задач.

З а д а ч а  2.10. Докажите сформулированное утверждение (воспользуйтесь компактностью последовательности {xk}).

Точка x* локального минимума дважды дифференцируемой функции f называется невырожденной, если оператор f ўў(x*) невырожден. Она называется локально единственной, если в некоторой ее окрестности Vx* нет других точек локального минимума функции f.

З а д а ч а  2.11. Приведите пример функции f, имеющей локально строгую, но не локально единственную точку минимума.

Теорема о локальной единственности решений. Невырожденная точка локального минимума локально единственна.

Д о к а з а т е л ь с т в о. Допустим противное: x* не является локально единственной точкой минимума, т. е. найдется сходящаяся к x* последовательность {xn} локальных минимумов функции f. Тогда (см. задачу 2.3)

f ў(xn) - f ў(x*) = f ўў(x*)(xn -x*) + o(xn - x*).

Поскольку xn и x* — локальные минимумы и, следовательно, стационарные точки, f ў(xn) = f ў(x*) = Q. Далее, положим (как мы уже делали) gn = (xn - x*)/||xn - x*||. Тогда, очевидно,


f ўў(x*)gn = 

o(xn - x*)
||xn - x*||
.
(9)

Далее рассуждения стандартны: {gn} лежит на единичной сфере в Rm, поэтому ее можно считать сходящейся к некоторому пределу g 0 Q. Переходя к пределу в (9), получаем

f ўў(x*)g0 = Q,

что противоречит невырожденности оператора f ўў(x*).

З а д а ч а  2.12. Восстановите детали доказательства.

2.8. Выпуклые функции на Rm.

Особенно легко вопросы существования и единственности решаются для выпуклых функций. Эти функции являются очень важным объектом в теории оптимизационных задач. Начнем с определений.

Функция f: Rm ® R называется выпуклой, если при всех x, y О Rm и l О (0, 1)

f(lx + (1 - l)y) Ј lf(x) + (1 - l)f(y).(10)

Если неравенство (10) строгое, то f называется строго выпуклой. Геометрически выпуклость означает, что график функции на интервале (x, y), соединяющем любые точки x и y, лежит не выше прямой, соединяющей точки (x, f(x)) и (y, f(y)) (см. рис. 3а). Функция f сильно выпукла (с константой c > 0), если неравенство (10) выполняется в следующей более сильной форме

f(lx + (1 - l)y) Ј lf(x) + (1 - l)f(y) + c
2
l(1 - l)||x - y||2.
(11)

К определению выпуклости и сильной выпуклости функций
Рис. 3.

Геометрически это понятие можно интерпретировать так. Пусть точки отрезка [x, y], соединяющего точки x и y, параметризованы параметром l: l ® lx + (1 - l)y. Правая часть неравенства (11) определяет на этом отрезке полином j второго порядка (от l). График сильно выпуклой функции над отрезком [x, y] должен лежать ниже параболы — графика этого полинома (см. рис. 3б).

Критерий выпуклости дифференцируемой функции. Для того, чтобы дифференцируемая функция f была выпуклой необходимо и достаточно выполнения при всех x, y О Rm неравенства

f(x) - f(y) і (f ў(y), x - y).(12)

Действительно, определим на отрезке [0, 1] функцию j, положив

j(l) = f(lx + (1 - l)y).

Очевидно функция j выпукла одновременно с функцией f. Кроме того, легко показать, что

jў(l) = (f ў(lx + (1 -l)y), x - y).

Неравенство (12) в новых обозначениях переписывается в виде

j(1) - j(0) і jў(0),

или, если воспользоваться формулой Лагранжа,

jў(t) і jў(0),(13)

где t — некоторая точка интервала (0, 1). Из курса математического анализа известно, что для дифференцируемых функций выпуклость эквивалентна монотонности производной. Поэтому, если f выпукла, то jў монотонна. Следовательно, имеет место эквивалентное (12) неравенство (13).

З а д а ч а  2.13. Докажите обратное утверждение.

Геометрически доказанное утверждение означает, что значения функции f(x) "лежит выше" гиперплоскости Hy = {(x, x) О Rm×R: x = f(y) + (f ў(y), x - y)}, касательной в точке (y, f(y)) к графику Gr f = {(x, x) О Rm× R: x = f(x)} при всех y О Rm (см. рис. 4).

Критерий выпуклости дифференцируемой функции
Рис. 4.

Строгая выпуклость дифференцируемой функции, как легко видеть, эквивалентна строгому при x y неравенству (12). Сильная же выпуклость функции f эквивалентна выполнению при всех x и y неравенства

f(x) - f(y) і (f ў(y), x - y) + c||x - y||2.(14)

З а д а ч а  2.14*. Докажите последнее утверждение.

З а д а ч а  2.15*. Докажите, что f О C2 сильно выпукла с константой c в том и только том случае, если f ўў(x) і c при всех x О Rm.

2.9. Теорема о разрешимости для сильно выпуклой функции.

Задача (1) с дифференцируемой сильно выпуклой функцией разрешима.

Д о к а з а т е л ь с т в о. Неравенство (14) для y = Q и произвольного x имеет вид

f(x) і f(Q) + (f ў(Q), x) +c||x||2.(15)

Для a = f(Q) множество Sa = {x О Rm: f(x) Ј a}, во-первых, непусто, поскольку содержит точку Q, а во-вторых, ограничено, поскольку вне шара B(Q, ||f ў(Q)||/c)

f(x) > a.

Действительно, продолжая (15), при ||x|| > ||f ў(Q)||/c имеем

f(x) і f(Q) + (f ў(Q), x) + c||x||2 і a - |(f ў(Q), x)| + c||x||2 і

і a + c||x||2 - ||f ў(Q)|| · ||x|| = a + ||x||(c||x|| - ||f ў(Q)||) > a.

Заключение теоремы теперь следует из теоремы 2.6 о разрешимости задачи безусловной оптимизации.

З а д а ч а  2.16. Покажите, что для выпуклой (и даже для строго выпуклой) функции утверждение теоремы в общем случае не верно.

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

Задача (1) со строго выпуклой функцией не может иметь более одного решения.

Д о к а з а т е л ь с т в о. В предположении существования двух точек минимума x* и x** (очевидно тогда, что f(x*) = f(x**)), в силу строгой выпуклости, получим противоречащее равенству x* = argmin f(x) неравенство

f ж
и
x* + x**
2
ц
ш
 <  f(x*)
2
 +  f(x**)
2
 = f(x*).


File based on translation from TEX by TTH, version 3.05.
Created 4 Jun 2002, 22: 42.