«Алгоритмическая выпуклая оптимизация Диссертация на соискание ученой степени доктора физико-математических наук по ...»

20th International Symposium on Mathematical Programming, Чикаго, 2009;

7th EUROPT Workshop on Operations Research, Реманген, 2009;

7th Brazilian Conference on Continuous Optimization, Кампинас, 2008;

International Conference on Optimization and Operations Research, Северобайкальск, 2008;

School "New Paradigms in Optimization Аскона, 2008;

International conference "High Performance Optimization Амстердам, 2008;

INFORMS meeting on Continuous Optimization, Атланта, 2008;

School on Continuous Optimization, Эйн Геди, 2007;

International Conference on Continuous and Discrete optimization, Ватерлоо, 2007;

International Conference on Nonlinear Optimization, Люмини, 2007;

School on Operations Research and Optimization, Зиналь, 2007;

International Workshop on Continuous Optimization VOCAL, Будапешт, 2006;

International Symposium on Mathematical Programming. Рио-де-Жанейро, 2006;

International Conference on Semidenite Programming. Сингапур, 2006;

Annual INFORMS meeting. Сан-Франциско, 2005;

International conference on positive polynomials. Люмини, 2005;

International Workshop on Nonlinear Optimization, Обервольфах, 2005;

French-German-Spain conference on Operations Research. Авиньон, 2004;

International conference "High Performance Optimization Амстердам, 2004;

International workshop on semidenite programming. Ватерлоо, 2004.

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

• Университет г.Льеж (Бельгия), апрель 2012.

• Независимый Университет, Москва, сентябрь 2012.

• Ecole nationale de la statistique et de l’administration conomique (Paris Tech), Париж (Франция), ноябрь 2012.

• Университет г.Вены (Австрия), май 2013.

• Традиционная Математическая Школа по Управлению и Оптимизации, Сенеж, Моск.обл., июнь 2013.

Глава Предварительные результаты 1.1 Классификация выпуклых функций 1.1.1 Нормы и производные Всюду ниже мы работаем с конечномерным вещественным векторным пространством, обычно обозначаемым буквой E (возможно, с индексом). Это пространство снабжается нормой · E, точный смысл которой при необходимости будет уточнен. Пространство линейных функций на E (двойственное пространство) обозначается через E. Для s E и x E будем обозначать через s, xE значение линейной функции s в точке x. Другими словами, это скалярное произведение s и x. Конечно же, наиболее важным случаем является E = E = Rn. Тогда Для пространства квадратных матриц Mm,n вводится фробениусово скалярное произведение:

Пространство симметрических n n-матриц S n интерпретируется как подпространство в Mn,n с соответствующим определением скалярного произведения.

Норма в двойственном пространстве определяется стандартным способом:

который обеспечивает выполнение неравенства Коши – Буняковского:

Если не возникает двусмысленности, то индексы у скалярных произведений и норм обычно опускаются.

Для определения евклидовой нормы в E нам потребуется самосопряженный положительно определенный линейный оператор B : E E. Тогда В этом случае s = s, B 1 s1/2, s E. Если вид оператора B легко определяется из контекста, то соответствующий индекс опускается.

Иногда в наших рассуждениях используется отношение двойственности между выпуклыми функциями, заданными на прямом и двойственном пространствах. Для выпуклой функции f (x), x E, ее сопряженная (по Фенхелю) функция относительно выпуклого замкнутого множества Q E определяется следующим образом:

В этом определении допускается случай, когда dom fQ = E. Если Q E, то соответствующий индекс опускается.

Мы часто будем пользоваться следующим результатом..

Лемма 1.1.1 Для степени p 1 рассмотрим функцию p (x) = p xp. Тогда Доказательство.

Действительно, если p > 1, то для всех s E имеем Если же p = 1, то искомый результат получается взятием предела при p 1. В этом случае функция 1 (s) является индикаторной функцией единичного шара в E.

Если Q E, то утверждение леммы 1.1.1 может быть записано в виде неравенства Гельдера:

Иногда более удобно пользоваться следующим вариантом:

Норма, используемая для измерения расстояний в E, естественным образом приводит к нормам для производных функций в пространстве E. Так, например, для функции f (x), x E, можно определить ее k-ю смешанную производную вдоль направлений h1,..., hk Тогда k f (x) = max {Dk f (x)[h1,..., hk ] : h1 =... = hk = 1}1. В частности, для k = 1 имеем Для k = 2 получаем Если оператор A : E E является неотрицательно определенным, то 2Ah1, h Ah1, h1 + Ah2, h2. Следовательно, для выпуклых функций 1.1.2 Классы гладких функций Классификация дифференцируемых выпуклых функций основывается на уровне гладкости их производных. Будем обозначать через F·,L (Q) класс функций, которые k раз непрерывно дифференцируемы на некотором выпуклом множестве Q и у которых p-я производная удовлетворяет условию Гельдера с параметром [0, 1]:

При этом если k = p, то первый индекс опускается. Индекс · тоже опускается, если смысл нормы ясен из контекста или если это норма общего вида. Указание на множество тоже отсутствует, если Q E. И для = 0 мы отождествляем соответствующий класс с его замыканием. Другими словами, это означает, что производная p f (·) существует почти всюду и ее вариация ограничена по норме константой L.

При = 1 константа L имеет естественную интерпретацию.

Лемма 1.1.2 Пусть f - k +1 раз непрерывно дифференцируемая функция на множестве Q, и k 0. Положим Тогда f FL (Q).

Для упрощения обозначений мы считаем, что 0 f (x) f (x).

Доказательство.

Действительно, k f (y) k f (x) = k+1 f (x + (y x))(y x)d. Таким образом, Приведем несколько важных примеров. Мы будем в основном рассматривать случай k = 1 или 2 и значения параметра гладкости = 0 или 1.

• Включение f FL (Q) означает, что f удовлетворяет условию Липшица с константой L:

• Включение f FL (Q) означает, что у функции f ограничено изменение (суб)градиентов:

• Включение f FL (Q) означает, что у функции f градиенты удовлетворяют условию Липшица:

• Включение f FL (Q) означает, что у функции f липшицев гессиан:

В качестве иллюстрации рассмотрим функцию d3 (x) = 1 x3 с евклидовой нормой (см.

формулу (1.1.3)).

Лемма 1.1.3 Для любых x, y E выполняется неравенство Доказательство.

Для x E имеем Зафиксируем две точки x, y E и произвольное направление h E. Положим x( ) = Пусть сначала 0 [x, y]. Тогда функция ( ) непрерывно дифференцируема на [0, 1] и Обозначим = x( )·h Поэтому и мы получаем неравенство (1.1.14) из (1.1.7).

Приведем также следующий тривиальный результат.

Лемма 1.1.4 Пусть f FL (Q), k 0. Тогда для всех x, y Q выполняется неравенk+1, ство Доказательство.

Действительно, для доказательства неравенства (1.1.15) заметим, что Чтобы доказать неравенство (1.1.16), запишем и повторим вышеприведенные выкладки.

В этой работе мы обычно рассматриваем выпуклые функции. Пересечение этого функционального класса с F·,L (Q) обозначается через C·,L (Q), где смысл индексов остается без изменения. Наиболее важным для нас классом является класс CL (Q) состоящий из функций с гельдеровым градиентом.

Лемма 1.1.5 Пусть f CL (Q). Тогда для любых x, y Q и [0, 1] справедливы неравенства Доказательство.

Неравенство (1.1.17) следует из выпуклости функции f и неравенства (1.1.15). Чтобы доказать неравенство (1.1.18), обозначим x = x + (1 )y. Тогда x x = (1 )(x y) и y x = (y x). Таким образом, Складывая эти неравенства с коэффициентами и 1 соответственно, получаем неравенство (1.1.18).

Докажем теперь неравенство (1.1.19). Обозначим p = 1 + и q = p1 = 1 +. Рассмотрим функцию (y) = f (y) f (x) f (x), y x 0, y E. Заметим, что CL. Таким образом, Минимизируя обе части этого неравенства по u, в силу леммы 1.1.1 получаем Это в точности неравенство (1.1.19).

Мы будем часто пользоваться следующим достаточным условием для класса CL (Q).

Теорема 1.1.1 Пусть выпуклая функция f дважды непрерывно дифференцируема на выпуклом множестве Q. Положим L = sup{2 f (x)h, h : h 1, x Q}. Тогда f CL (Q).

Доказательство немедленно следует из леммы 1.1.2 и представления (1.1.7).

1.1.3 Равномерно выпуклые функции Помимо уровня гладкости, нам понадобится как-то охарактеризовать кривизну выпуклых функций. Это можно сделать с помощью понятия равномерно выпуклых функций.

Пусть функция f (x) (суб)дифференцируема на выпуклом замкнутом множестве. Она называется равномерно выпуклой на Q степени p 2, если существует такая константа Константа p называется параметром выпуклости этой функции. Прибавляя к такой функции произвольную выпуклую функцию, мы не меняем ни степень, ни параметр. Заметим, что степень p = 2 соответствует сильно выпуклым функциям.

Любая равномерно выпуклая функция растет быстрее линейной. Таким образом, ее множества уровня всегда ограничены. Из этого следует, что задачи с равномерно выпуклыми целевыми функциями и непустыми допустимыми множествами всегда разрешимы.

Более того, их оптимальное решение всегда единственно.

Складывая два неравенства (1.1.20) с переставленными x и y, получаем Оказывается это неравенство является также и достаточным условием равномерной выпуклости (правда, с другим значением параметра).

Лемма 1.1.6 Пусть для некоторых p 2 и > 0, и всех x, y Q выполняется неравенство Тогда функция f равномерно выпукла на Q со степенью p и параметром.

Доказательство.

Действительно, Замечание 1 Сопоставляя неравенства (1.1.21) и (1.1.22), легко увидеть, что не бывает равномерно выпуклых функций со степенью p < 2. В противном случае, применяя эти утверждения последовательно, мы получим p.

Лемма 1.1.7 Пусть функция f является равномерно выпуклой на Q со степенью p 2.

Тогда Доказательство.

Предположим что функция f достигает минимума на E в точке x Q. Тогда Теперь зафиксируем произвольную точку x Q и рассмотрим выпуклую функцию (y) = f (y)f (x), y. Эта функция будет равномерно выпуклой со степенью p и параметром p.

Более того, она достигает минимума в точке y = x Q. Поэтому, применив предыдущее неравенство к функции (y), мы получим формулу (1.1.23).

Приведем один важный пример равномерно выпуклой функции. Зафиксируем произвольную точку x0 E. Обозначим dp (x) = p x x0 p, где норма выбрана евклидовой (см.

формулу (1.1.3)). Тогда Лемма 1.1.8 Для любых x, y E выполнены неравенства Доказательство.

Без ограничения общности можем считать, что x0 = 0. Тогда Для доказательства неравенства (1.1.24) нам нужно показать, что правая часть последнего неравенства не меньше чем Не ограничивая общности, можно считать, что x = 0 и y = 0. Тогда обозначив мы получим неравенство, которое нужно доказать:

Так как правая часть этого неравенства выпукла по, нам нужно рассмотреть только при всех 0.

Второе из неравенств (1.1.27) получается из нижней оценки для дроби поскольку ее минимум достигается при = 1. Для доказательства первого неравенства заметим что оно выполнено при = 1. Если 0 и = 1, то нам нужно оценить снизу дробь Так как модуль любого коэффициента полинома (1 )p2 не превосходит 2p2, первое из неравенств (1.1.27) тоже доказано. Это доказывает неравенство (1.1.24), и для доказательства неравенства (1.1.25) остается воспользоваться леммой 1.1.6.

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

Теорема 1.1.2 Пусть функция f является равномерно выпуклой на множестве Q со степенью p и параметром p. Тогда fQ FL (E ) с параметрами Доказательство.

Так как функция f равномерно выпукла, ее сопряженная функция fQ определена для любого s E. Более того, она дифференцируема, и Условия оптимальности для этой задачи оптимизации записываются следующим образом:

Выберем произвольные s1, s2 E. Обозначим x1 = x(s1 ), x2 = x(s2 ). Тогда в силу неравенства (1.1.29) Складывая эти неравенства, получаем Равномерно выпуклые функции обладают следующим важным свойством.

Теорема 1.1.3 Пусть функция f является равномерно выпуклой на Q со степенью p и параметром p > 0. Обозначим x = arg min f (x). Тогда для всех x Q выполнено неравенство Доказательство.

Действительно, в силу условия оптимальности Таким образом, неравенство (1.1.30) следует из оценки (1.1.20).

1.1.4 Сильно выпуклые функции Сильно выпуклые функции являются одним из самых важных функциональных классов в выпуклой оптимизации. Сильная выпуклость очень важна в следующих ситуациях.

• Присутствие сильно выпуклых функциональных компонент в задаче оптимизации существенно ускоряет скорость сходимости численных методов.

• Сильно выпуклые функции часто используются в схемах с регуляризацией.

• Простые сильно выпуклые функции используются в качестве прокс-функций в методах оптимизации, учитывающих геометрию допустимых множеств.

В этом пункте мы остановимся на наиболее важных свойствах сильно выпуклых функций.

Прежде всего для удобства ссылок перепишем наиболее важные неравенства пункта 1.1.3 для случая p = 2. Если функция f является сильно выпуклой, то для всех x, y Q выполнены следующие неравенства:

Все эти неравенства являются необходимыми и достаточными условиями для сильной выпуклости функции f с параметром 2.

Дважды дифференцируемые сильно выпуклые функции допускают следующую характеризацию:

Иногда это условие легче проверить в его двойственной форме.

Лемма 1.1.9 Для положительно определенного самосопряженного линейного оператора A : E E условие > 0, эквивалентно следующему неравенству:

Доказательство.

Заметим, что Таким образом, условие (1.1.35) эквивалентно следующему:

Минимизируя правую часть этого неравенства по h получаем оценку (1.1.36).

Если норма · в E является евклидовой (см. формулу (1.1.3)), то условие (1.1.35) обеспечивает неотрицательную определенность оператора A B. Таким образом, простейшая квадратичная функция d2 (x) = 1 x2 является строго выпуклой с параметром 2 = 1. Другая важная ситуация рассмотрена в следующем примере.

Пример 1.1.1 Пусть E = Rn. Рассмотрим функцию энтропии Определив скалярное произведение s, x = s x, получаем следующее представление для ее производных:

прямую и двойственную норму:

мы видим, что s, [2 (x)]1 s (s )2 x(i). Таким образом, в силу леммы 1.1.9 и услоi= вия (1.1.34) мы получаем, что функция энтропии является строго выпуклой относительно 1 -нормы на множестве с параметром выпуклости 2 = 1.

1.2 Методы гладкой минимизации первого порядка 1.2.1 Прямой и двойственный градиентные методы В этом параграфе мы рассматриваем методы решения следующей оптимизационной задачи:

где Q - выпуклое замкнутое ограниченное множество, и f CL (Q). Для простоты будем считать, что константа L известна. Позже мы увидим что от этого предположения легко отказаться.

Обозначим через TQ (x) Q оптимальное решение следующей задачи минимизации:

Обычно оно называется градиентным отображением. Если норма · не является строго выпуклой, то задача (1.2.2) может иметь несколько решений. В этом случае обозначение TQ (x) будет использоваться для любого из них. В силу неравенства (1.1.17) для любого x Q имеем Обозначим через d(x) некоторую прокс-функцию множества Q. Предполагается что функция d(x) является непрерывной и сильно выпуклой на множестве Q с параметром выпуклости единица. Для простоты предположим что d(x) дифференцируема. Обозначим через x0 центр множества Q:

Не ограничивая общности, будем считать что d(x0 ) = 0. Таким образом, при любом x Q имеем Теперь мы можем определить брегмановское расстояние между точками x и y. Ясно что, С помощью этого расстояния можно вычислить брегмановскую проекцию:

Ввиду неравенств (1.2.5) и (1.1.17), у нас всегда будет Рассмотрим теперь простейший метод решения задачи (1.2.1).

Теорема 1.2.1 Пусть f CL (Q). Тогда для всех k 1 выполнено неравенство Доказательство.

Условия оптимальности для вспомогательной задачи в методе (1.2.7) имеет следующий вид:

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

При k 0 повторяем: Вычисляем xk = arg min k (x).

Теорема 1.2.2 Пусть последовательность {xk }k0 сформирована методом (1.2.10). Обоk значим yk = TQ (xk ) и yk = k+ Доказательство.

Докажем по индукции, что при всех k 0 выполнено неравенство При k = 0 имеем Предположим, что неравенство (1.2.12) справедливо при некотором k 0. Функция k (x) сильно выпукла с параметром единица. Следовательно, Осталось заметить, что k (x) (x0, x) + L f (x). Таким образом, Заметим? что двойственный градиентный метод не поддерживает монотонности минимизирующей последовательности {yk }k0. Для ее построения нам не нужны дополнительные вычисления значения функции и градиента.

1.2.2 Быстрый градиентный метод Напомним что скорость сходимости прямого и двойственного градиентных методов (1.2.8), (1.2.11) не является оптимальной. Более эффективный быстрый градиентный метод формирует две последовательности точек {xk } Q и {yk } Q так, чтобы они удовлеk=0 k= творяли следующему условию:

i и последовательность {i } сформирована из положительных шаговых множителей. Покажем? как это можно сделать.

Действительно, для k = 0 выберем любое 0 (0, 1] и y0 = TQ (x0 ). Тогда в силу неравенств (1.2.4) и (1.2.3) имеем и это в точности условие (R0 ).

Обозначим Лемма 1.2.1 Пусть последовательность {k } удовлетворяет условию Предположим, что соотношение (Rk ) выполнено при некотором k 0. Выберем k = k+ Ak+ Тогда соотношение (Rk+1 ) также будет выполнено.

Доказательство.

Действительно, пусть выполнено условие (Rk ). Тогда, так как функция d(x) сильно выпукла, получаем Далее, в силу соотношения (Rk ) и первого из правил (1.2.14) В силу условия (1.2.13) имеем A1 k. Таким образом, мы можем продолжить наши выкладки следующим образом:

Наконец заметим, что k [0, 1]. Для произвольного x Q определим Тогда в силу первого из соотношений (1.2.14) имеем Поэтому в силу неравенства (1.2.3) и второго из правил (1.2.14) заключаем, что Учитывая это неравенство в конечной оценке (1.2.16), мы приходим к требуемому результату.

Ясно, что имеется много способов удовлетворить условия (1.2.13). Рассмотрим следующий пример.

и условия (1.2.13) будут выполнены.

Доказательство.

Теперь мы можем обосновать скорость сходимости следующего метода.

При k 0 повторяем следующие операции.

Вычисляем f (xk ) и f (xk ). Находим yk = TQ (xk ).

Теорема 1.2.3 Пусть последовательности {xk } и {yk } сформированы методом (1.2.18). Тогда при всех k 0 справедлива оценка (k+1)(k+2) Таким образом, где x - оптимальное решение задачи (1.2.1).

Доказательство.

Действительно, выберем последовательность {k } в соответствии с рекомендациями леммы 1.2.2. Тогда в силу леммы 1.2.1 и выпуклости функции f (x) имеем Осталось воспользоваться соотношениями (1.2.17).

Заметим что, вообще говоря, метод (1.2.18) не обеспечивает монотонность минимизирующей последовательности. Однако иногда это свойство является весьма желательным.

Для его обеспечения можно воспользоваться следующим приемом.

Заметим что в доказательстве леммы 1.2.1 нам нужно, чтобы точка yk+1 удовлетворяла условию Давайте изменим правила формирования точки yk в методе (1.2.18) следующим образом.

Ясно, что в этом случае 1.2.3 Минимизация гладких сильно выпуклых функций Если у функции f CL параметр выпуклости 2 оказывается строго положительным, то соответствующая задача минимизация становится гораздо проще. Ее сложность теперь будет зависеть от числа обусловленности Это число корректно определено для произвольных норм. Однако, оказывается для некоторых норм оно не слишком показательно.

Лемма 1.2.3 Пусть функция f дважды дифференцируема по крайней мере в одной точке. Тогда ее число обусловленности относительно 1 -нормы не может быть меньше, чем размерность пространства переменных.

Доказательство.

Пусть функция f дважды дифференцируема в точке x Q. Обозначим A = 2 f (x). В силу условий (1.1.9) с k = 1, (1.1.34) и (1.1.36) получаем Если отождествить E с Rn, то оператор A может быть представлен симметрической положительно определенной матрицей. Мы измеряем расстояния в прямом пространстве с помощью 1 -нормы, а значит С другой стороны, 2 = max{s, A1 s : |s(i) | 1, i = 1,..., n}.

Рассмотрим теперь случайный вектор s, компоненты которого принимают значения ±1 с равными вероятностями. Тогда Таким образом, мы заключаем, что Матрица A положительно определена, следовательно A + A1 2I. Таким образом, для любой матрицы A, допустимой для этой задачи, имеем Этот результат подтверждает, что число обусловленности лучше всего определять относительно евклидовых норм. По крайней мере, в этом случае наши оценки сложности могут не зависеть от размерности пространства.

В оставшейся части этого параграфа мы предполагаем? что расстояния в пространстве E измеряются с помощью евклидовой нормы (1.1.3). Выберем d(x) = d2 (x) = 1 x2. В этом случае брегмановские расстояния имеют очень простое представление:

Давайте оценим в новой ситуации скорость сходимости прямого градиентного метода (1.2.7).

Теорема 1.2.4 Пусть функция f принадлежит CL (Q) и ее параметр выпуклости положителен. Если последовательность {xk }k0 сформирована методом (1.2.7), то при всех k 1 справедлива оценка Доказательство.

Обозначим rk = 1 xk x 2. Пользуясь теми же рассуждениями, что и в начале доказательства теоремы 1.2.1, получаем (1.2.24) Обозначим k = L [f (xk ) f ]. Так как метод (1.2.7) монотонен, при всех k 0 имеем Отметим, что оценка скорости сходимости метода (1.2.25) непрерывна по параметру 2. Если 2 0, то она переходит в оценку (1.2.8). Для того чтобы обеспечить подобное поведение двойственного градиентного метода (1.2.10), нам придется изменить его схему.

Двойственный градиентный метод (строго выпуклые функции) При k 0 повторяем следующие операции.

Вычисляем xk = arg min k (x). Пересчитываем Теорема 1.2.5 Пусть последовательность {xk }k0 сформирована методом (1.2.10). Поk ства Доказательство.

Доказательство очень похоже на доказательство теоремы 1.2.2. Прежде всего докажем по индукции, что при всех k 0 выполнено неравенство При k = 0 имеем Предположим, что неравенство (1.2.28) верно при некотором k 0. Заметим, что Так как функция k (x) сильно выпукла с параметром единица, Осталось заметить, что k+1 (x) 2 x x0 2 + L Ak f (x). Таким образом, Поскольку L Как и для прямого градиентного метода (1.2.7), оценка скорости сходимости двойственного градиентного метода (1.2.26) непрерывна по 2. Когда 2 стремится к нулю, правая часть неравенства (1.2.27) монотонно возрастает и достигает уровня (1.2.11).

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

Обозначим через OptN (x0 ) точку yN, полученную с помощью метода (1.2.18) после N итераций, запущенных из точки x0. Зададим N =1/2 (f )+1 и рассмотрим следующий процесс:

Мы пользуемся евклидовой метрикой, поэтому Следовательно, ввиду определения числа N мы получим uk+1 x 2 uk x. Таким образом, метод (1.2.29) достигнет точности за итераций. Для прямого и двойственного градиентного методов мы можем гарантировать только оценку в O((f ) ln 1 ) итераций.

1.3 Самосогласованные функции и барьеры 1.3.1 Определение и свойства самосогласованных функций В этой работе мы не собираемся детально рассматривать полиномиальные методы внутренней точки. Поэтому ниже приводится очень краткая версия соответствующей теории, которая необходима только для описания некоторых свойств выпуклых множеств и для формулировки вспомогательных оптимизационных задач.

Рассмотрим выпуклую замкнутую функцию f (x) C 3 (dom f ) с открытой областью определения. Зафиксируем некоторую точку x dom f и направление u Rn. Рассмотрим функцию как функцию одной переменной t dom (x; ·) R. Обозначим Определение 1.3.1 Функция f называется самосогласованной, если найдется такая константа Mf 0, что неравенство выполнено при всех x dom f, u Rn.

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

Приведем одно эквивалентное определение самосогласованной функции.

Лемма 1.3.1 Функция f является самосогласованной тогда и только тогда, когда при всех x dom f и всех u1, u2, u3 Rn выполнено неравенство Мы примем это утверждение без доказательства, так как оно требует привлечения специальны фактов из теории три-линейных форм.

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

Остановимся на нескольких примерах.

Пример 1.3.1 1. Линейная функция. Пусть Тогда и мы заключаем, что Mf = 0.

2. Выпуклая квадратичная функция. Рассмотрим где A = AT 0. Тогда и мы также получаем Mf = 0.

3. Логарифмический барьер для луча. Рассмотрим Тогда Таким образом, функция f (x) является самосогласованной с константой Mf = 2.

4. Логарифмический барьер для множеств второго порядка. Пусть A = AT 0. Рассмотрим вогнутую функцию Положим f (x) = ln (x), dom f = {x Rn | (x) > 0}. Тогда Единственным нетривиальным случаем является 1 = 0. Обозначим = 2 /1.

Тогда Таким образом, эта функция является самосогласованной, Mf = 2.

5. Легко проверить, что ни одна из следующих функций не является самосогласованной:

Приведем теперь основные свойства самосогласованных функций.

Теорема 1.3.1 Пусть функции fi являются самосогласоваными с константами Mi, i = и областью определения dom f = dom f1 dom f2.

Доказательство.

Функция f является выпуклой и замкнутой как сумма выпуклых и замкнутых функций.

Зафиксируем произвольные x dom f и u Rn. Тогда Обозначим i = D2 fi (x)[u, u] 0. Тогда Правая часть этого неравенства не меняется при замене (1, 2 ) на (t1, t2 ), t > 0. Таким образом, можно считать, что Обозначим = 1. Тогда правая часть последнего неравенства будет равной Эта функция выпукла по. Она достигает максимума на концах отрезка.

Следствие 1.3.1 Пусть функция f является самосогласованной с константой Mf. Если A = AT 0, то функция также является самоcогласованной с константой M = Mf.

Доказательство.

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

Следствие 1.3.2 Пусть функция f является самосогласованной с константой Mf, и пусть > 0. Тогда функция (x) = f (x) также является самосогласованной с константой M = Mf.

Покажем что самосогласованность является аффинно-инвариантным свойством.

Теорема 1.3.2 Рассмотрим линейный оператор A(x) = Ax + b: Rn Rm. Пусть функция f (y) является самосогласованной с константой Mf. Тогда функция (x) = f (A(x)) также является самосогласованной с константой M = Mf.

Доказательство.

Ясно что функция (x) является выпуклой и замкнутой. Зафиксируем произвольные x dom = {x : A(x) dom f } и u Rn. Обозначим y = A(x), v = Au. Тогда Таким образом, Следующее утверждение показывает, что локальные характеристики самосогласованной функции отражают глобальные свойства ее области определения.

Теорема 1.3.3 Пусть функция f является самосогласованной. Если dom f не содержит прямых, то гессиан этой функции 2 f (x) является невырожденным в любом x dom f.

Доказательство.

Предположим, что 2 f (x)u, u = 0 при некотором x dom f и u Rn, u = 0. Рассмотрим точку y = x + u dom f и функцию Заметим, что Поскольку () 0, мы заключаем, что (0) = 0. Таким образом, эта функция является частью решения следующей системы дифференциальных уравнений:

Однако эта система имеет единственное тривиальное решение. Таким образом () = для всех допустимых.

Мы показали, что функция () = f (y ) является линейной:

Предположим, что существует такое, что y (dom f ). Рассмотрим такую последовательность {k }, что k. Тогда Заметим что zk epi f, но z epi f, поскольку y dom f. Это противоречит замкнутости функции f. Рассматривая направление u, и предполагая, что этот луч пересекает границу, мы опять приходим к противоречию. Таким образом, мы заключаем, что y dom f при всех. Однако это противоречит предположениям теоремы.

Опишем поведение самосогласованных функций у границы области определения.

Теорема 1.3.4 Пусть функция f является самосогласованной. Тогда для любой точки x (dom f ) и любой последовательности выполняется условие f (xk ) +.

Доказательство.

Заметим, что последовательность {f (xk )} ограничена снизу:

Предположим, что она ограничена сверху. Тогда она имеет по крайней мере одну предельную точку f. Можно считать, что эта точка единственна. Таким образом, Заметим, что zk epi f, но z epi f, поскольку x dom f. Это противоречит замкнутости функции f.

Таким образом, мы доказали, что f (x) является барьерной функцией для множества Cl (dom f ).

Основные неравенства Зафиксируем некоторую самосогласованную функцию f (x). Мы будем считать, что Mf = 2 (в противном случае можно умножить f (x) на соответствующую константу, см. следствие 1.3.2). Такие функции называются стандартно самосогласованными. Мы также будем предполагать, что область определения dom f не содержит прямых (в силу теоремы 1.3.3 это обеспечивает невырожденность всех гессианов 2 f (x)).

Обозначим Ясно, что | v, u | v · u x. Назовем u x локальной нормой направления u относительно точки x, а f (x) = f (x) - локальной нормой градиента2 f (x).

Зафиксируем произвольные x dom f и u Rn, u = 0. Рассмотрим следующую функцию одной переменной:

с областью определения dom = {t R : x + tu dom f }.

Лемма 1.3.2 При всех допустимых t выполняется неравенство | (t) | 1.

Доказательство.

Действительно, Следствие 1.3.3 Область определения функции (t) содержит интервал Доказательство.

Поскольку f (x + tu) при приближении точки x + tu к границе области dom f (см.

теорему 1.3.4), функция 2 f (x + tu)u, u не может быть ограниченной. Таким образом, dom {t | (t) > 0}. Остается заметить, что в силу леммы 1.3.2.

Иногда f (x) называется ньютоновским убыванием функции f в точке x.

Рассмотрим следующий эллипсоид:

Он называется эллипсоидом Дикина функции f в точке x.

Теорема 1.3.5 1. При всех x dom f выполнено включение W 0 (x; 1) dom f.

2. При всех x, y dom f выполнено неравенство Доказательство.

1. В силу следствия 1.3.3 область определения dom f содержит множество (поскольку (0) = 1/ u x ). Это множество есть в точности W 0 (x; 1).

2. Выберем u = y x. Тогда и (1) (0) + 1 в силу леммы 1.3.2. Это в точности неравенство (1.3.2).

3. Если y x x < 1, то (0) > 1 и в силу леммы 1.3.2 имеем (1) (0) 1. Это и есть неравенство (1.3.3).

Теорема 1.3.6 Пусть x dom f. Тогда для любого y W 0 (x; 1) выполнены соотношения Доказательство.

Зафиксируем произвольное направление u Rn, u = 0. Рассмотрим функцию Обозначим yt = x + t(y x). Тогда в силу леммы 1.3.1 и неравенства (1.3.3) имеем Таким образом, Проинтегрировав это неравенство по t [0, 1], получаем Это в точности соотношение (1.3.4).

Следствие 1.3.4 Пусть x dom f и r = y x x < 1. Тогда матрицу можно оценить сверху и снизу следующим образом:

Доказательство.

Действительно в силу теоремы 1.3.6 имеем Остановимся еще раз на наиболее важных свойствах самосогласованных функций.

• В любой точке x dom f можно указать эллипсоид принадлежащий dom f.

• Внутри эллипсоида W (x; r) с радиусом r [0, 1) функция f почти квадратична:

для всех y W (x; r). Выбирая r достаточно малым, можно довести качество квадратичной аппроксимации до любого нужного нам уровня.

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

Теорема 1.3.7 При всех x, y dom f справедливы неравенства где (t) = t ln(1 + t).

Доказательство.

Обозначим y = x + (y x), [0, 1], и r = y x x. Тогда в силу (1.3.2) имеем Далее, пользуясь неравенством (1.3.5), получаем Теорема 1.3.8 Пусть x dom f and y x x < 1. Тогда где (t) = t ln(1 t).

Доказательство.

неравенства (1.3.3) имеем Далее, пользуясь неравенством (1.3.7), получаем Теорема 1.3.9 Неравенства (1.3.2), (1.3.3), (1.3.5), (1.3.6), (1.3.7) и (1.3.8) являются необходимыми и достаточными характеристиками самосогласованных функций.

Доказательство.

Мы уже доказали следующие импликации:

Докажем теперь импликацию (1.3.6) определение 1.3.1. Пусть x dom f и x u dom f для [0, ). Рассмотрим функцию Обозначим r = ux [ (0)]1/2. Предполагая что неравенство (1.3.6) выполняется для всех x и y из dom f, получаем Таким образом, Следовательно, D3 f (x)[u, u, u] = (0) (0) 2[ (0)]3/2, и это есть определение 1.3.1 с Mf = 2. Импликация (1.3.8) определение 1.3.1 доказывается аналогично. В вышеприведенных теоремах используются две вспомогательные функции (t) = t ln(1 + t) и ( ) = ln(1 ). Заметим, что Таким образом, функции (t) и ( ) являются выпуклыми. Мы будем часто пользоваться разными соотношениями между этими функциями. Ниже они представлены в явном виде.

Лемма 1.3.3 При всех t 0 и [0, 1) Как мы видели в примере 1.3.1 и следствии 1.3.1, эта функция самосогласована. Заметим, что Таким образом, f (x) =| 1 x |. Следовательно, при = 0 получим f0 (x) = 1 для всех x > 0. При этом f0 не ограничена снизу.

Если > 0, то x = 1. Заметим, что мы можем гарантировать существование минимуf ма проверкой в точке x = 1, даже если очень мало.

Рассмотрим теперь схему редуцированного метода Ньютона.

Теорема 1.3.12 При всех k 0 справедлива оценка Доказательство.

ства (1.3.8) и леммы 1.3.3 имеем Итак, для всех таких x dom f, что f (x) > 0, один шаг редуцированного метода Ньютона уменьшает значение функции f (x) по крайней мере на константу () > 0.

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

Опишем теперь локальную сходимость стандартного метода Ньютона.

Заметим, что скорость сходимости этого процесса может измеряться разными способами. Мы можем смотреть на невязку по функции f (xk ) f (x ), или на локальную норf му градиента f (xk ) = f (xk ) k, или на локальную оценку расстояния до минимума xk xf xk. В конце концов, можно смотреть и на расстояние до минимума в фиксированной метрике задаваемой самой точкой минимума. Докажем, что все эти меры локально эквивалентны.

Теорема 1.3.13 Пусть f (x) < 1. Тогда где последнее неравенство справедливо при r (x) < 1.

Доказательство.

Обозначим r = x x x и = f (x). Неравенства (1.3.15) следуют из теоремы 1.3.10.

Далее, в силу неравенства (1.3.5) имеем Это и есть правая часть неравенства (1.3.16). Если r 1, то левая часть этого неравенства тривиальна. Предоложим, что r < 1. Тогда f (x) = G(x x ), где где H = [2 f (x)]1/2 G[2 f (x)]1/2. В силу следствия 1.3.4 имеем Следовательно, H Таким образом, f (x) (r). Применив (·) к обеим частям этого неравенства, мы получим оставшуюся часть неравенства (1.3.16).

Наконец, неравенства (1.3.17) следуют из оценок (1.3.6) и (1.3.8).

Оценим теперь локальную скорость сходимости стандартного метода Ньютона (1.3.14).

Это будет удобнее сделать в терминах локальной нормы градиента f (x).

Теорема 1.3.14 Пусть x dom f и f (x) < 1. Тогда точка принадлежит dom f. При этом Доказательство.

Обозначим p = x+ x, = f (x). Тогда p x = < 1. Таким образом, x+ dom f (см.

теорему 1.3.5). В силу теоремы 1.3. Далее, где G = [2 f (x + p) 2 f (x)]d. Следовательно, где H = [2 f (x)]1/2 G[2 f (x)]1/2. В силу следствия 1.3.4 имеем Таким образом, H max 1, 1 2 = 1, и мы заключаем, что Теорема 1.3.14 дает нам следующее описание области квадратичной сходимости метода (1.3.14):

где является корнем уравнения (1)2 = 1. В этом случае мы можем гарантировать, что f (x+ ) < f (x).

Таким образом, наши результаты обосновывают следующую стратегию решения исходной задачи (1.3.11).

• Первая стадия: f (xk ), где (0, ). На этой стадии мы применяем редуцированный метод Ньютона. На каждой итерации этого метода выполнено неравенство Таким образом, число шагов на этой стадии ограничено следующим образом:

• Вторая стадия: f (xk ). На этой стадии мы применяем стандартный метод Ньютона. Этот процесс сходится квадратично:

Можно показать, что локальная сходимость редуцированного метода Ньютона (1.3.12) тоже квадратична:

Однако мы предпочитаем переключающуюся стратегию, поскольку она дает лучшие оценки эффективности. Соотношение (1.3.18) может быть обосновано так же, как это сделано в теореме 1.3.14.

1.3.3 Самосогласованные барьеры и метод отслеживания траектории Мотивировка В предыдущем пункте мы показали, что метод Ньютона очень эффективен для минимизации стандартной самосогласованной функции. Такая функция всегда является барьером для своей области определения. Давайте посмотрим, как эти функции могут быть использованы в схемах последовательной безусловной минимизации.

В этом пункте мы будем работать с задачами минимизации специального вида. Обозначим dom f = Cl (dom f).

Определение 1.3.2 Задача минимизации называется стандартной, если она представлена в форме где Q - выпуклое замкнутое множество. Предполагается, что известна самосогласованная функция f, у которой dom f = Q.

Рассмотрим параметрическую штрафную функцию с параметром t 0. Заметим, что функция f (t; x) самосогласована по x (см. следствие 1.3.1). Обозначим Эта траектория называется центральной для задачи (1.3.19). Можно ожидать, что x (t) x при t. Нашей целью является отслеживание этой траектории.

Напомним, что стандартный метод Ньютона, применяемый к функции f (t; x), сходится квадратично (см. теорему 1.3.14). Более того, у нас имеется явное описание области квадратичной сходимости:

Давайте посмотрим на наши возможности, предположив, что нам известна точка x = x (t) при некотором t > 0.

Мы собираемся увеличить t:

При этом мы хотим сохранить x в области квадратичной сходимости метода Ньютона для функции f (t + ; ·):

Заметим, что пересчет t t+ не меняет гессиан барьерной функции:

Таким образом, нетрудно понять, насколько большим может быть шаг. Действительно, из условия оптимальности первого порядка можно выписать уравнение центральной траектории:

Поскольку tc + f (x) = 0, получаем Поэтому если мы хотим увеличивать параметр t с линейной скоростью, то необходимо предположить, что величина равномерно ограничена на dom f.

Таким образом, мы приходим к определению самосогласованного барьера.

Определение самосогласованного барьера Определение 1.3.3 Пусть функция F (x) является стандартной самосогласованной. Мы назовем ее -самосогласлванным барьером для множества dom F, если для всех x dom F. Число называется параметром этого барьера.

Заметим, что в этом определении не требуется невырожденность гессиана 2 F (x).

Однако если это так, то неравенство (1.3.21) может быть записано в эквивалентной форме Иногда удобна следующая форма неравенства (1.3.21):

(Чтобы ее получить для направления u удовлетворяюшего условию 2 F (x)u, u > 0, заменим u в неравенстве (1.3.21) на u и найдем максимум левой части по.) Заметим, что условие (1.3.23) может быть записано в матричной форме:

Давайте проверим, какие из самосогласованных функций примера 1.3.1 являются также и самосогласованными барьерами.

Пример 1.3. a = 0 эта функция не будет самосогласованным барьером, поскольку 2 f (x) = 0.

2. Выпуклая квадратичная функция. Пусть A = AT 0. Рассмотрим функцию Тогда f (x) = a + Ax и 2 f (x) = A. Таким образом, Ясно, что это выражение неограничено сверху на Rn. Таким образом, квадратичная функция не является самосогласованным барьером.

3. Логарифмический барьер для луча. Рассмотрим следующую функцию одной переменной:

Следовательно, функция F (x) является -самосогласованным барьером для множества {x > 0} с параметром = 1.

4. Логарифмический барьер для выпуклой области второго порядка. Пусть A = AT 0. Рассмотрим вогнутую квадратичную функцию Положим F (x) = ln (x), dom f = {x Rn | (x) > 0}. Тогда Таким образом, 2F (x), u 2 F (x)u, u 21 1 1. Следовательно, F (x) является -самосогласованным барьером с параметром = 1.

Приведем несколько простейших свойств самосогласованных барьеров.

Теорема 1.3.15 Пусть функция F (x) является самосогласованным барьером. Тогда функция c, x + F (x) самосогласованна на множестве dom F.

Доказательство.

Так как F (x) - самосогласованная функция, можно воспользоваться Следствием 1.3.1. Вышеупомянутое свойство является важным для методов отслеживания траектории.

Теорема 1.3.16 Пусть функции Fi являются i -самосогласованными барьерами, i = 1, 2.

Тогда функция является самосогласованным барьером для выпуклого множества dom F = dom F1 dom F с параметром = 1 + 2.

Доказательство.

В силу теоремы 1.3.1 функция F будет самосогласованной. Зафиксируем произвольную точку x dom F. Тогда Наконец, покажем, что значение параметра самосогласованного барьера является аффинноинвариантной характеристикой.

Теорема 1.3.17 Рассмотрим линейный оператор A(x) = Ax+b, A(x) : Rn Rm. Пусть функция F (y) является -самосогласованным барьером. Тогда функция (x) = F (A(x)) также является -самосогласованным барьером, но для множества Доказательство.

Функция (x) является стандартной самосогласованной функцией в силу теоремы 1.3.2.

Зафиксируем произвольную точку x dom. Тогда y = A(x) dom F. При всех u Rn имеем Таким образом, Основные неравенства Покажем, что локальные характеристики самосогласованного барьера (градиент и гессиан) обеспечивают нас глобальной информацией о структуре его области определения.

Теорема 1.3.18 1. Пусть функция F (x) является -самосогласованным барьером. Тогда для любых x, yindom F выполняется неравенство Более того, если F (x), y x 0, то 2. Стандартная самосогласованная функция F (x) является -самосогласованным барьером тогда и только тогда, когда Доказательство.

1. Пусть x, y dom F. Рассмотрим функцию Если (0) 0, то неравенство (1.3.25) тривиально. Если (0) = 0, то неравенство (1.3.26) тоже тривиально. Предположим, что (0) > 0. В силу определения (1.3.23) имеем Таким образом, функция (t) возрастает и является положительной при t [0, 1]. Более того, для любых t [0, 1] имеем Это означает, что F (x), y x = (0) < при всех t [0, 1]. Таким образом, неравенство (1.3.25) доказано. Более того, Выбирая t = 1, получаем неравенство (1.3.26).

2. Обозначим (x) = e F (x). Тогда Таким образом, в силу определения (1.3.24) функция (x) является вогнутой в том и только том случае, когда функция F (x) является -самосогласованным барьером. Осталось заметить что неравенство (1.3.27) эквивалентно неравенству с точностью до взятия логарифма от обеих его частей.

Докажем теперь теорему о рецессивном направлении.

Теорема 1.3.19 Пусть функция F является -самосогласованным барьером, а направление h явялется рецессивным для области dom F. Тогда для любых x dom F выполнено неравенство Доказательство.

Единственный нетривиальный случай есть 2 F (x)h, h > 0. Рассмотрим функцию (t) = F (x + th). Это самосогласованный барьер. Таким образом, в силу теоремы 1.3.11 условие 2 (1) = 2 F(x),h < 1 означает, что функция (t) достигает своего минимума. Однако в силу неравенства (1.3.25) F (u), h 0 при любом u dom F. Таким образом, если минимум функции достигается при некотором t > 0, то (t) const при всех t t. Но для самосогласованного барьера это невозможно (см., например, неравенство (1.3.5)). Следствие 1.3.5 Пусть x dom F и y Cl (dom F ). Тогда выполняется неравенство Доказательство.

Обозначим x() = x + (y x) и () = F (x()). Тогда Теорема 1.3.20 Пусть функция F (x) является -самосогласованным барьером. Тогда для всех таких x dom F и y dom F, что выполнено неравенство Доказательство.

В силу предположения (1.3.30) и неравенства (1.3.5) имеем С другой стороны, в силу неравенства (1.3.25) получаем а это и есть неравенство (1.3.31).

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

Определение 1.3.4 Пусть функция F (x) является -самосогласованным барьером для множества dom F. Точка называется аналитическим центром выпуклого множества dom F, порождаемым барьером F (x).

Теорема 1.3.21 Предположим, что аналитический центр -самосогласованного барьера F (x) существует. Тогда для любого x dom F выполнено неравенство С другой стороны, для любого такого x Rn, что x x x 1, верно включение x dom F.

Доказательство.

Первое утверждение следует из теоремы 1.3.20 ввиду равенства F (x ) = 0. Второе утверF ждение следует из теоремы 1.3.5.

Таким образом, асферичность множества dom F относительно точки x, измеренная в метрике · xF, не может быть больше + 2. Хорошо известно, что для любого выпуклого множества в R существует метрика, в которой его асферичность не превосходит n (теорема Джона). Однако нам удалось оценить асферичность в терминах параметра барьера. Это число не связано непосредственно с размерностью пространства.

Заметим также что для множества dom F, не содержащего прямых, существование точки x означает его ограниченность (поскольку тогда гессиан 2 F (x ) невырожден, см. теорему 1.3.3).

Следствие 1.3.6 Пусть множество dom F ограничено. Тогда для любых x dom F и v Rn выполняется неравенство Доказательство.

Воспользуемся следующим представлением:

С другой стороны, в силу теорем 1.3.5 и 1.3.21 имеем Таким образом, воспользовавшись опять теоремой 1.3.21, получаем Заметим, что v = v. Таким образом, мы можем считать, что v, x x 0. Метод отслеживания траектории Мы готовы описать барьерную модель нашей задачи минимизации. Это стандартная задача минимизации у которой ограниченное выпуклое замкнутое допустимое множество Q dom F имеет непустую внутренность и снабжено -самосогласованным барьером F (x).

Напомним, что мы собираемся решать задачу (1.3.32) с помощью отслеживания центральной траектории:

где f (t; x) = tc, x + F (x) и t 0. Ввиду условия оптимальности первого порядка любая точка этой траектории удовлетворяет уравнению Поскольку множество Q ограничено, его аналитический центр x существует и лежит на центральной траектории:

Мы будем отслеживать центральную траекторию, пересчитывая точки, удовлетворяющие приближенному условию центрирования:

где параметр центрирования достаточно мал.

Покажем, что такая стратегия приводит нас к цели.

Теорема 1.3.22 Для любого t > 0 выполняется неравенство где c - оптимальное значение задачи (1.3.32). Если точка x удовлетворяет условию центрироания (1.3.36), то Доказательство.

Пусть x является решением задачи (1.3.32). В силу неравенств (1.3.34) и (1.3.25) имеем Далее, пусть x удовлетворяет условию (1.3.36). Обозначим = f (t;·) (x). Тогда в силу неравенства (1.3.22), теоремы 1.3.13 и неравенства (1.3.36).

Проведем анализ одного шага метода отслеживания траектории. Пусть x dom F.

Рассмотрим следующую итерацию:

Теорема 1.3.23 Если точка x удовлетворяет условию (1.3.36):

где < =, то для множителя, удовлеворяющего условию выполняется неравенство t+ c + F (x+ ).

Доказательство.

Тогда и в силу теоремы 1.3.14 имеем Осталось заметить, что условие (1.3.40) эквивалентно следующему:

(напомним, что ( ( )) =, см. лемму 1.3.3).

Покажем, что изменение параметра t в схеме (1.3.39) будет достаточно большим.

Лемма 1.3.4 Пусть x удовлетворяет условию (1.3.36). Тогда Доказательство.

Действительно, в силу неравенств (1.3.36) и (1.3.22) имеем Выпишем подходящие значения параметров в схеме (1.3.39). В оставшейся части этого пункта мы предполагаем, что Мы показали, что центральная траектория может отслеживаться с помощью правил (1.3.39). При этом возможно как увеличение, так и уменьшение параметра t. Нижняя оценка на скорость увеличения параметра t дается неравенством а верхняя оценка на скорость уменьшения параметра такова:

Итак, общая схема решения задачи (1.3.32) выглядит следующим образом.

Оценим трудоемкость вышеприведенной схемы.

Теорема 1.3.24 Схема (1.3.43) останавливается не более чем через N шагов, где Более того, в момент остановки выполнено неравенство c, xN c.

Доказательство.

Заметим, что r0 x0 x x0 1 (см. теорему 1.3.13). Таким образом, в силу теоремы 1.3.6 имеем Обсудим вышеприведенную оценку сложности. Ее основным членом является Заметим, что число c оценивает сверху изменение линейной функции на множестве dom F (см. теорему 1.3.21). Таким образом, отношение может интерпретироваться как относительная точность решения.

В процессе (1.3.43) есть один серьезный недостаток. Иногда бывает трудно обеспечить выполнение начального условия В таком случае приходится прибегать к вспомогательному процессу вычисления подходящей стартовой точки. Соответствующая стратегия анализируется в следующем пункте.

Нахождение аналитического центра Таким образом, нам необходимо найти приближение к аналитическому центру множества dom F. Рассмотрим следующую задачу минимизации:

где функция F является -самосогласованным барьером. Для запуска метода из предыдущего пункта, нам необходимо найти приближенное решение x dom F этой задачи, удовлетворяющее условию при некотором (0, 1).

Для этого можно применить две различные стратегии. Первая из них – это обычный редуцированный метод Ньютона. Вторая стратегия основана на отслеживании вспомогательной траектории.

Рассмотрим сначала первую стратегию.

Редуцированый метод Ньютона для аналитического центра итераций.

Доказательство.

Действительно, в силу теоремы 1.3.12 имеем Схема метода отслеживания траектории немного сложнее. Пусть у нас есть точка y dom F. Определим вспомогательную центральную траекторию следующим образом:

где t 0. Эта траектория удовлетворяет уравнению Таким образом, она связывает две точки: стартовую точку y0 и аналитический центр x :

Эту траекторию можно отслеживать с помощью процесса (1.3.39) с уменьшающимся параметром t.

Оценим скорость приближения вспомогательной центральной траектории y (t) к аналитическому центру.

Лемма 1.3.5 При всех t 0 выполняется неравенство Доказательство.

Эта оценка вытекает из формулы (1.3.46) и следствия 1.3.6.

Выпишем соответствующую итеративную процедуру.

Отслеживание вспомогательной центральной траектории Эта схема отслеживает вспомогательную траекторию y (t) при tk 0. Она пересчитывает точки {yk }, удовлетворяющие приближенному условию центрирования Критерий остановки этого процесса:

Он гарантирует, что F () x 1k (см. теорему 1.3.14).

Выпишем оценки сложности этого процесса.

Теорема 1.3.26 Процесс (1.3.47) останавливается не более чем через итераций.

Доказательство.

Напомним, что мы зафиксировали следующие значения параметров:

Мы выбрали t0 = 1. Таким образом, в силу теоремы 1.3.23 и леммы 1.3.4 имеем Далее, в силу леммы 1.3.5 получаем Таким образом, процесс прервется по крайней мере после выполнения следующего неравенства:

Теперь можно обсудить сложность обеих стратегий. Основной член в оценке сложности вспомогательной схемы отслеживания траектории выглядит так:

Для вспомогательного редуцированного метода Ньютона это O(F (y0 ) F (x )). Мы не можем напрямую сравнить эти оценки. Однако более точный анализ показывает преимущество метода отслеживания траектории. Также важно, что его оценка сложности подобна оценке сложности основного метода отслеживания траектории. Действительно, если применить схему (1.3.43) вместе с (1.3.47), то мы получим следующую оценку для всего процесса:

Логарифмически однородные барьеры Очень часто множество стандартной задачи минимизации представляется как пересечение аффинного многообразия с выпуклым конусом. Такие конические задачи стимулировали интерес к специальным самосогласованным барьерам для выпуклых конусов.

Определение 1.3.5 Пусть выпуклый замкнутый конус K имеет непустую внутренность.

Выпуклая барьерная функция F (x), dom F = int K, называется логарифмически однородной, если для любых x int K и > 0 выполнено тождество Контанта > 0 называется параметром этого барьера.

Тождество (1.3.48) приводит ко многим интересным следствиям. Дифференцируя его по x, получаем Дифференцируя теперь первое из равенств (1.3.49) по в точке = 1, получаем Более того, дифференцируя равенство (1.3.48) по в точке = 1, получаем Это равенство имеет два важных следствия. Предположим, что конус K точечный (не содержит прямых). Тогда в силу теоремы 1.3.3 гессиан 2 F (x) невырожден. Таким образом, Следовательно, является параметром барьера F. В то же время это неравенство может быть записано как Этот результат приводит к полезному следствию.

Лемма 1.3.6 Пусть x0 int K и x {x K : F (x0 ), x x0 0}. Тогда Доказательство.

Действительно, 1.3.4 Конструирование самосогласованных барьеров Границы на параметр В предыдущем пункте мы рассмотрели метод отслеживания траектории для задачи где Q – выпуклое замкнутое множество с непустой внутренностью, для кторого известен -самосогласованный барьер F (x). С помощью этого барьера мы можем решить задачу (1.3.55) за O · ln итераций. Напомним, что наиболее сложная часть каждой итерации состоит в решении системы линейных уравнений.

В этом пункте мы изучим пределы применимости данного подхода. Мы получим нижние и верхние оценки для параметра самосогласованного барьера. Мы также обсудим классы выпуклых задач, для которых постановка (1.3.55) может быть обеспечена вычислимыми барьерами.

Начнем с нижней оценки на параметр барьера.

Лемма 1.3.7 Пусть функция f (t) является -самосогласованным барьером для интервала (, ) R, < <. Тогда Доказательство.

Заметим, что в силу своего определения. Предположим, что < 1. Поскольку функция f (t) является барьером для (, ), найдется такое число (, ), что f (t) > при всех t [, ).

Рассмотрим функцию (t) = (ff (t), t [, ). Поскольку f (t) > 0 и функция f (t) является самосогласованной, в силу (t) < 1 имеем Поэтому при всех t [, ) получаем (t) ( )+2(1 )(f (t)f ( )). Это невозможно, так как функция f (t) является барьером, а функция (t) ограничена сверху.

Следствие 1.3.7 Пусть функция F (x) является -самосогласованным барьером для множества Q Rn. Тогда 1.

Доказательство.

Действительно, пусть x int Q. Поскольку Q Rn, существует такое направление u Rn, что прямая {y = x + tu, t R} пересекает границу множества Q. Таким образом, рассматривая функцию f (t) = F (x + tu) и пользуясь леммой 1.3.7, мы получаем нужное утверждение.

Докажем теперь простую нижнюю границу на параметр самосогласованного барьера для неограниченных множеств.

Пусть выпуклое замкнутое множество Q имеет непустую внутренность. Зафиксируем точку x int Q. Предположим, что существуют рецессивные направления {p1,..., pk } множества Q:

Теорема 1.3.27 Предположим, что положительные коэффициенты {i }k удовлетвоi= ряют условию и пусть для некоторых положительных 1,..., k выполнено равенство y = x i pi Q. Тогда параметр любого самосогласованного барьера для множества Q удовлетворяет неравенству Доказательство.

Пусть функция F (x) является -самосогласованным барьером для множества Q. Поскольку pi – рецессивное направление, по теореме 1.3.11 о рецессивном направлении имеем Заметим, что x i pi Q. Таким образом, в силу теоремы 1.3.5 норма направления pi будет достаточно большой: i pi x 1. Поэтому в силу теоремы 1.3.18 получаем Приведем теперь теорему существования самосогласованного барьера. Рассмотрим выпуклое замкнутое множество Q, int Q =, и предположим, что Q не содержит прямых.

Определим поляру множества Q относительно точки x int Q:

Можно показать, что для любого x int Q множество P (x) является выпуклым замкнутым и ограниченным множеством с непустой внутренностью. Обозначим V (x) = vol P (x).

Теорема 1.3.28 Существуют такие абсолютные константы c1 и c2, что функция Функция U (x) называется универсальным барьером множества Q. Заметим, что аналитическая сложность задачи (1.3.55), снабженной универсальным барьером, составляет O n · ln n обращений к оракулу. Такая эффективность невозможна в рамках модели черного ящика.

Вышеприведенный результат имеет в основном теоретический интерес. В общем случае универсальный барьер U (x) не может быть вычислен эффективно. Однако теорема 1.3. показывает, что в принципе такие барьеры существуют для каждого выпуклого множества. Таким образом, применимость нашего подхода ограничивается только нашими возможностями построения вычислимых самосогласованных барьеров с как можно меньшим значением параметра. Процесс построения барьерной модели исходной задачи трудно формализуем. Для каждой конкретной задачи могут существовать разные барьерные модели.

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

В оставшейся части этого параграфа мы покажем как это можно сделать для важных конкретных примеров.

Положительный ортант Для положительного ортанта Rn мы можем выбрать следующий самосогласованный барьер:

(см. Пример 1.3.3 и теорему 1.3.16). Этот барьер называется стандартным логарифмическим барьером для Rn. Покажем, что этот барьер оптимален.

Лемма 1.3.8 Параметр любого самосогласованного барьера для Rn удовлетворяет неравенству n.

Доказательство.

Выберем где ei – i-й базисный вектор в Rn. Тогда условия теоремы 1.3.27 выполняются с i = i = 1, i = 1... n. Таким образом Конус Лоренца Во многих приложениях функциональные компоненты задачи содержат негладкие квадратичные члены вида Ax b. Покажем, как эти элементы могут быть описаны с помощью самосогласованных барьеров.

Лемма 1.3.9 Функция является 2-самосогласованным барьером для выпуклого конуса Доказательство.

Зафиксируем точку z = (x, t) int K2 и ненулевое направление u = (h, ) Rn+1. Обозначим () = (t + )2 x + h 2. Нам нужно сравнить производные функции в точке = 0. Обозначим (·) = (·) (0), (·) = (·) (0). Тогда В зависимости от области приложений, это множество имеет разные названия: конус Лоренца, конус второго порядка, и т. д.

Заметим, что неравенство 2 ( )2 эквивалентно тому, что ( )2 2. Таким образом, нужно доказать, что для направления (h, ) справедливо неравенство Ясно, что можно ограничиться случаем | |> h (в противном случае правая часть неравенства неположительна). Более того, для минимизации левой части неравенства нужно обеспечить равенство sign = sign x, h (поэтому пусть > 0) и x, h = x · h.

Подставляя эти значения в формулу (1.3.56), получаем правильное неравенство.

Наконец, так как 0 ( )2 1 и [1 ]3/2 1 2, получаем Покажем, что полученный барьер оптимален.

Лемма 1.3.10 Параметр любого самосогласованного барьера для конуса K2 удовлетворяет неравенству 2.

Доказательство.

Выберем z = (0, 1) int K2 и некоторое h Rn, h = 1. Обозначим Заметим, что при всех 0 выполняются соотношения z + pi = (±h, 1 + ) K2 и Таким образом, условия теоремы 1.3.27 выполнены, и Полуопределенная оптимизация В полуопределенной оптимизации переменными являются матрицы. Пусть матрица X = {X (i,j) }n i,j=1 является симметричной (обозначение: X S введем следующее скалярное произведение: для произвольных X, Y S nn положим Иногда норма X F называется фробениусовой нормой матрицы X. Для симметрических матриц X и Y справедливо следующее тождество:

В полуопределенной оптимизации нетривиальная часть ограничений задается в форме конуса неотрицательно определенных n n-матриц Pn S nn. Напомним, что X Pn тогда и только тогда, когда Xu, u 0 при всех u Rn. Если Xu, u > 0 для всех ненулевых u, матрица X называется положительно определенной. Такие матрицы составляют внутренность конуса Pn. Заметим, что конус Pn является выпуклым и замкнутым.

Общая формулировка задачи полуопределенной оптимизации выглядит следующим образом:

где матрицы C и Ai лежат в S nn. Для применения к этой задаче метода отслеживания траектории нам нужно построить самосогласованный барьер для конуса Pn.

Пусть матрица X принадлежит int Pn. Обозначим F (X) = ln det X. Ясно, что где {i (X)}n являются собственными значениями матрицы X.

Лемма 1.3.11 Функция F (X) является выпуклой, и F (X) = X 1. Для любого направления S nn выполняются равенства Доказательство.

Зафиксируем такие S nn и X int Pn, что X + Pn. Тогда Таким образом, X 1 F (X). Следовательно, функция F выпукла, и F (x) = X 1.

Далее, рассмотрим функцию () F (X + ), F, [0, 1]. Имеем Таким образом, (0) = 2 F (X), F = X 1 X 1, F.

Последнее равенство обосновывается аналогичным образом с помощью вычисления Теорема 1.3.29 Функция F (X) является n-самосогласованным барьером для конуса Pn.

Доказательство.

Зафиксируем X int Pn и S nn. Обозначим Q = X 1/2 X 1/2 и i = i (Q), i = 1... n.

Тогда в силу леммы 1.3.11 имеем Используя два стандартных неравенства получаем Покажем, что барьер F (X) = ln det X является оптимальным для конуса Pn.

Лемма 1.3.12 Параметр любого самосогласованного барьера для конуса Pn не может быть меньше чем n.

Доказательство.

Выберем X = In int Pn и направления Pi = ei eT, i = 1... n, где ei - это i-й базисный вектор в Rn. Заметим, что для любого 0 выполняется включение In + Pi int Pn.

Более того, Таким образом, условия теоремы 1.3.27 выполняются с i = i = 1, i = 1... n, и мы Надграфики функций одной переменной Приведем самосогласованные барьеры для надграфиков нескольких важных функций от одной переменной.

Логарифм и экспонента. Функция F1 (x, t) = ln xln(ln x+t) является 2-самосогласованным барьером для множества а функция F2 (x, t) = ln t ln(ln t x) является 2-самосогласованным барьером для множества Функция энтропии. Функция F3 (x, t) = ln x ln(t x ln x) является 2-самосогласованным барьером для множества Возрастающая степенная функция. Функция F4 (x, t) = 2 ln tln(t2/p x2 ) является 4-самосогласованным барьером для множества а функция F5 (x, t) = ln x ln(tp x) является 2-самосогласованным барьером для множества Убывающая степенная функция. Функция F6 (x, t) = ln t ln(x t1/p ) является 2-самосогласованным барьером для множества а функция F7 (x, t) = ln x ln(t xp ) является 2-самосогласованным барьером для множества Мы опускаем соответствующие доказательства, так как они основаны на рутинных вычислениях. Можно показать, что приведенные барьеры для всех этих множеств оптимальны (возможно, за исключением Q4 ). Докажем соответствующее утверждение для барьеров Q6 и Q7.

Лемма 1.3.13 Параметр любого самосогласованного барьера для множества p > 0, не может быть меньше двух.

Доказательство.

Зафиксируем > 1 и выберем x = (, ) int Q. Обозначим Тогда x + ei Q для любого 0 и Таким образом, условия теоремы 1.3.27 выполнены, и Это доказывает нужное неравенство, так как может быть произвольно большим.

Глава Современные субградиентные методы 2.1 Прямо-двойственные методы для негладких задач 2.1.1 Введение Мотивировка Исторически субградиентный метод с постоянным шагом был первым численным методом для решения задачи с негладкой выпуклой целевой функцией f (подробные ссылки см. в работе [117]). Для его сходящегося варианта, изложенного в работах [50, 109], необходимо заранее выбрать последовательность шагов {k }, удовлетворяющую условию расходящегося ряда:

Тогда для k 0 можно применять правило с некоторыми gk f (xk ). В другом варианте этой схемы направление движения сначала нормализуется:

где · 2 обозначает стандартную евклидову норму в Rn, задаваемую скалярным произведением Поскольку целевая функция f является негладкой, мы не можем ожидать, что в окрестности решения задачи (2.1.1) субградиенты будут стремиться к нулю. Поэтому условие k 0 необходимо для сходимости процессов (2.1.3) и (2.1.4). С другой стороны, предполагая что gk 2 L, для всех x Rn, получаем Поэтому для любого x Rn, 1 x x0 2 D, имеем мы получим, что fk fD k. Заметим, что условие (2.1.2) необходимо и достаточно для сходимости k 0.

В приведенном анализе сходимость процесса (2.1.3) основывается на том факте, что производная функции lk (x), нижней линейной модели целевой функции стремится к нулю.

Эта модель чрезвычайно важна, поскольку она дает проверяемый критерий остановки.

Однако, посмотрев на структуру линейной функции lk (·), можно заметить одну странную вещь.

Это обстоятельство противоречит здравому смыслу и общим принципам итеративных методов, согласно которым новая информация более важна, чем старая. Таким образом, в стандартной схеме что-то делается не так. К сожалению, простая коррекция этой схемы, по-видимому, невозможна: мы видели, что уменьшающиеся веса ( шаги в прямом пространстве) необходимы для сходимости последовательности {xk }.

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

Но в двойственном пространстве (пространстве линейных функций) нам нужны неубывающие веса. Следовательно, нам необходимы две разные последовательности параметров, каждая из которых ответственна за процессы в прямом и двойственном пространствах.

Идея связать минимизирующую последовательность в прямом пространстве с основным процессом, формируемым в двойственном пространстве, не является новой. Впервые она была реализована в методах зеркального спуска (см. [79]; новые версии и исторический комментарий см. в работах [33, 38]). Однако идея расходящегося ряда каким-то образом просочилась и туда. В результате в евклидовой ситуации метод зеркального спуска, совпадающий с обычным субградиентным методом, разделяет недостаток (2.1.6). В нашем подходе ситуацию удается улучшить. Конечно же, зависимость оценок сложности от точности остается такой же. Однако улучшение константы оказывается существенным:

наилучшая стратегия выбора шаговых множителей в работах [33], [38] дает такую же (бесконечную) константу в оценке скорости сходимости, что и худшая среди новых схем (см.

пункт 2.1.8).

В этом параграфе мы рассматриваем прямо-двойственные субградиентные методы.

По-видимому, эта естественная особенность всех субградиентных методов до сих пор не привлекала к себе внимания. Рассмотрим, например метод (2.1.3). Из неравенства (2.1.5) следует, что Заметим, что число fk (D) может быть легко вычислено. С другой стороны, в выпуклой оптимизации существует только один способ получить нижнюю оценку для оптимального значения некоторой задачи оптимизации. Для этого необходимо получить допустимую точку в некоторой двойственной задаче 1. Таким образом, вычислимость значения fk (D) означает, что у нас имеется допустимое двойственное решение, и сходимость двойственного зазора fk fk (D) к нулю означает, что двойственное решение сходится к оптимальному.

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

Наконец, субградиентные методы, описываемые в этом пункте, сильно отличаются от стандартных “поисковых” методов 2. Например, для задачи (2.1.1) предлагается следующий метод:

где µk = O( k ) 0. Заметим что в этой схеме отсутствуют какие-либо искусственные элементы, призванные искусственно ограничить последовательность тестовых точек.

Содержание В параграфе 2.1.2 мы рассматриваем общую схему метода двойственных усреднений (ДУ) и доказываем верхние оценки для соответствующих функций зазора. Эти оценки будут далее уточняться для соответствующих классов задач. Мы приведем два основных варианта ДУ-методов, простые двойственные усреднения (ПДУ) и взвешенные двойственные усреднения (ВДУ).

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

Имеются в виду методы описываемые в терминах шагов в прямом пространстве. Альтернативой являются методы зеркального спуска [79], в которых основной процесс идет в двойственном пространстве.

В параграфе 2.1.3 мы воспользуемся ДУ-методами для решения задач минимизации на простых множествах. Основной целью этого параграфа является демонстрация того факта что все ДУ-методы являются прямо-двойственными. Для этого мы всегда формулируем некоторую сопряженную задачу и указываем правила формирования последовательности, сходящейся к ее решению. В пункте 2.1.3(A) мы рассматриваем различные формы ДУметодов, применяемых к общим задачам минимизации. В пункте 2.1.3(B) это делается для общих задач безусловной минимизации. В пункте 2.1.3(C) это сделано для минимаксных задач. В этом случае, аппроксимация двойственных множителей соответствует частотам, с которыми соответствующие функциональные компоненты оказываются активными в функции максимума (ср. с [28]). Наконец, в пункте 2.1.3(D) мы рассматриваем прямодвойственные методы для решения задач минимизации с простыми функциональными ограничениями. Для таких задач удается построить приближенное прямо-двойственное решение, несмотря на тот факт, что обычно даже вычисление значения двойственной функции по своей трудоемкости сравнимо с трудоемкостью решения исходной задачи.

В параграфе 2.1.4 мы применяем ПДУ-метод к задаче нахождения седловой точки, а в параграфе 2.1.5 он применяется к вариационным неравенствам. Важной особенностью этой схемы является то, что для разрешимых задач она генерирует ограниченную последовательность точек даже в случае неограниченного допустимого множества. В параграфе 2.1.6 рассматриваются методы решения задачи стохастической оптимизации. Эти методы генерируют случайное приближенное решение (т.е. повторные запуски метода дадут разные результаты). Однако мы доказываем, что среднее значение целевой функции на выходе сходится к оптимальному значению с оптимальной скоростью.

Наконец, в параграфе 2.1.7 мы рассматриваем применение ДУ-методов в моделировании. В пункте 2.1.7(A) показано, что естественная поведенческая стратегия производства (которую мы называем схемой балансированного развития) может рассматриваться как реализация ДУ-метода. В результате удается доказать, что в пределе мы получаем оптимальное решение некоторой оптимизационной задачи. В пункте 2.1.7(B) для некоторой многостадийной задачи минимизации мы сравниваем эффективность предварительного планирования и некоторой динамической стратегии настройки (основанной на ПДУметоде). Динамическая стратегия очень проста в реализации. В то же время, оказывается, что она приводит к результатам сравнимым по своей эффективности с результатами предварительного планирования, даже когда последняя стратегия основана на точном знании будущего.