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

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

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

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

f(x) ® min,

(1)

где f: R^m ® R. Точка x* О R^m называется решением задачи (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. О линейных операторах в R^m.

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

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

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

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

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

(Ax, x) > 0

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

(Ax, x) і 0.

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

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

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

l Ј A Ј L,

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

l Ј li Ј L.

(3)

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

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

(4)

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

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

Вектор a О R^m такой, что

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

при всех h О R^m называется производной или градиентом функции 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: R^m ® R^m дифференцируемая в каждой точке называется дифференцируемой.

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

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

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

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

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

A =  ж з з з з з з з и ¶2f(x) ¶x1¶x1 ··· ¶2f(x) ¶x1¶xm : ··· : ¶2f(x) ¶xm¶x1 ··· ¶2f(x) ¶xm¶xm ц ч ч ч ч ч ч ч ш .

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

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

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

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

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

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

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

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

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

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

(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 О C¹ и f О C², если f соответственно непрерывна, непрерывно дифференцируема и дважды непрерывно дифференцируема.

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

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

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

Напомним  д о к а з а т е л ь с т в о  теоремы. Допустим противное: f ў(x*) № Q. Положим x_t = x* - tf ў(x*) для всех t > 0. Тогда, во-первых, очевидно, x_t - 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.

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 — произвольный вектор из R^m. Поскольку (в силу теоремы Ферма) 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)²)/t² ® 0 при t ® 0, получим нужное неравенство

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

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

0 > f(x* + thn) - f(x*) =  1 2 (f ўў(x*)hn, hn) + o((hn)2).

Если теперь обозначить hⁿ/||hⁿ|| через gⁿ, то последнее неравенство (поделив его на ||hⁿ||²) можно переписать в виде

(f ўў(x*)gn, gn) +  o((hn)2) ||hn||2  < 0.

(8)

Поскольку ||gⁿ|| = 1, а сфера в R^m компактна, последовательность {gⁿ}, не ограничивая общности, можно считать сходящейся к некоторому лежащему на ней (и следовательно, отличному от нуля) вектору g⁰. Предельный при 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 О R^m) функцией f, не имеющей решения.

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

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

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

З а д а ч а  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) и {x^k} М R^m — ограниченная последовательность такая, что f(x^k) ® f(x*) = min f(x) при k® Ґ, то x^k ® x* = argmin f(x) при k ® Ґ. Такое свойство бывает полезным при исследовании приближенных методов решения оптимизационных задач.

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

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

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

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

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

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

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

f ўў(x*)gn =  o(xn - x*) ||xn - x*|| .

(9)

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

f ўў(x*)g0 = Q,

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

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

2.8. Выпуклые функции на R^m.

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

Функция f: R^m ® R называется выпуклой, если при всех x, y О R^m и 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 О R^m неравенства

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) "лежит выше" гиперплоскости H_y = {(x, x) О R^m×R: x = f(y) + (f ў(y), x - y)}, касательной в точке (y, f(y)) к графику Gr f = {(x, x) О R^m× R: x = f(x)} при всех y О R^m (см. рис. 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 О C² сильно выпукла с константой c в том и только том случае, если f ўў(x) і c при всех x О R^m.

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

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

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

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

(15)

Для a = f(Q) множество S_a = {x О R^m: 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 T_EX by T_TH, version 3.05.
Created 4 Jun 2002, 22: 42.