1.6 алгоритмы и методы безусловной оптимизации

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

Ее решение будет рассмотрено в подходах задачи безусловной минимизации гладкой функции [77].

Данная задача непосредственно связана с условиями существования экстремума в точке:

Необходимое условие первого порядка. Точка называется локальным минимумом на , если найдется для . Согласно теореме Ферма если - точка минимума на и дифференцируема в , то .

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

Необходимое условие второго порядка. Если - точка минимума на и дважды дифференцируема в ней, то .

Достаточное условие второго порядка. Если в точке дважды дифференцируема, выполнено необходимое условие первого порядка () и , то - точка локального минимума.

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

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

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

И, наконец, сами доказательства сходимости обычно строятся на том, что показывается, как «невязка» в условии экстремума стремится к нулю.

При решении оптимизационных задач существенны требования существования, единственности и устойчивости решения.

Существование точки минимума проверяется при помощи теоремы Вейерштрасса:

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

При анализе единственности точки экстремума применяются следующие рассуждения:

Точка минимума называется локально единственной, если в некоторой ее окрестности нет других локальных минимумов. Считается, что - невырожденная точка минимума, если в ней выполнено достаточное условие экстремума второго порядка (,).

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

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

Пусть метод оптимизации приводит к построению минимизирующей последовательности, следует ли из этого ее сходимость к решению?

Если вместо исходной задачи минимизации решается задача, сходная с ней, можно ли утверждать близость их решений?

В [77] приводится следующее определение устойчивости:

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

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

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

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

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

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

Для сильно выпуклых функций:

,

где - константа сильной выпуклости.

Для невырожденной точки минимума:

,

где - наименьшее собственное значение матрицы .

Как видно, в каждом из этих определений играет роль характеристики «запаса устойчивости» точки минимума.

Кроме в качестве характеристики устойчивости точки минимума используют «нормированный» показатель , называемый обусловленностью точки минимума .

,

.

Можно сказать, что характеризует степень вытянутости линий уровня в окрестности - «овражность» функции (чем больше , тем более «овражный» характер функции).

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

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

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

Пусть функция дифференцируема на , градиент удовлетворяет условию Липшица:

,

ограничена снизу:

и удовлетворяет условию

.

Тогда в градиентном методе с постоянным шагом градиент стремится к 0: , а функция монотонно убывает: .

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

При решении задачи оптимизации методом Ньютона используется подход, заключающийся в итерационном процессе вида

и в нахождении точки экстремума как решения системы из n уравнений с n неизвестными

.

В методе Ньютона производится линеаризация уравнений в точке и решение линеаризованной системы вида

.

Анализ достоинств и недостатков итерационных методов оптимизации можно свести в таблицу (см. табл. 3).

Таблица 3

Достоинства и недостатки итерационных методов оптимизации

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

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

, .

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

.

Такой метод называют демпфированным методом Ньютона. Возможные подходы к способу выбора шага :

Вычисление по формуле ;

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

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

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

Метод тяжелого шарика, использующий итерационную формулу , где , - некоторые параметры. Введение инерции движения (член ) в некоторых случаях приводит к ускорению сходимости за счет выравнивания движения по «овражистому» рельефу функции;

Метод сопряженных градиентов. Здесь параметры оптимизации находятся из решения двумерной задачи оптимизации:

,

.

Кроме всех вышеперечисленных методов оптимизации существует еще класс методов, основанных на идее восстановления квадратичной аппроксимации функции по значениям ее градиентов в ряде точек. К ним относятся:

Квазиньютоновские методы, имеющие общую структуру , где матрица пересчитывается рекуррентно на основе информации, полученной на k-й итерации, так что . К числу таких методов относятся ДФП (метод Давидона-Флетчера-Пауэлла) и BFGS или БФГШ (метод Бройдена-Флетчера-Гольдфарба-Шанно) [46].

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