Основы теории оптимизации (стр. 7 )

(f ′′(x)h, h) ≤ Λ ||h||2,

(5)

эквивалентное нужному неравенству f ′′(x) ≤ Λ.

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

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

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

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

Напомним д о к а з а т е л ь с т в о теоремы. Допустим противное: f ′(x*) ≠ Θ. Положим xt = x* – tf ′(x*) для всех t > 0. Тогда, во-первых, очевидно, xt – x* → Θ при 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: Ω1×Ω2 → R (Ω1 Rn, Ω2 Rm), если при всех (x, y) Ω1×Ω2 выполнены неравенства

f(x*, y) ≤ f(x*, y*) ≤ f(x, y*)

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

Рис. 2.

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

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

Пусть 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* не является точкой локального минимума. Последнее означает наличие последовательности xn→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.

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

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

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

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

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

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