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

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

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

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

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

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

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

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

f ′(xn) – f ′(x*) = f ′′(x*)(xn –x*) + o(xn – x*).

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

f ′′(x*)gn =  o(xn – x*) ||xn – x*|| .

(9)

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

f ′′(x*)g0 = Θ,

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

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

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

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

f(λx + (1 – λ)y) ≤ λf(x) + (1 – λ)f(y).

(10)

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

f(λx + (1 – λ)y) ≤ λf(x) + (1 – λ)f(y) +  c 2 λ(1 – λ)||x – y||2.

(11)

а) б)
Рис. 3.

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

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

f(x) – f(y) ≥ (f ′(y), x – y).

(12)

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

φ(λ) = f(λx + (1 – λ)y).

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

φ′(λ) = (f ′(λx + (1 –λ)y), x – y).

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

φ(1) – φ(0) ≥ φ′(0),

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

φ′(τ) ≥ φ′(0),

(13)

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

Геометрически доказанное утверждение означает, что значения функции f(x) "лежит выше" гиперплоскости

Hy = {(x, ξ) Rm×R: ξ = f(y) + (f ′(y), x – y)},

касательной в точке (y, f(y)) к графику Gr f ={(x, ξ) Rm×R:ξ = 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)

Замечание. Функция f C2 сильно выпукла с константой c в том и только том случае, если f ′′(x) ≥ c при всех x Rm.

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

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

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

f(x) ≥ f(Θ) + (f ′(Θ), x) +c||x||2.

(15)

Для α = f(Θ) множество Sα = {x Rm: f(x) ≤ α}, во-первых, непусто, поскольку содержит точку Θ, а во-вторых, ограничено, поскольку вне шара B(Θ, ||f ′(Θ)||/c)

f(x) > α.

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