5.4.4. Метод оптимизации второго порядка

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

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

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

Условия оптимальности второго порядка.

Лемма 5.2. Пусть имеет непрерывные частные производные второго порядка и допустим что в точке х матрица Гесса не является отрицательно полуопределенной. Тогда существует точка у такая, что

Доказательство. В силу того, что не является отрицательно полуопределенной, существует направление такое, что

Определим по направление где

(если можно выбрать произвольно или Тогда

Воспользовавшись разложением в ряд Тейлора, найдем

для некоторого 0, 00 1. На основе соотношения (5.8) и непрерывности Я должно существовать такое достаточно малое что имеет место

Полагая и подставляя (5.9) и (5.11) в соотношение (5.10), получаем

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

Теорема 5.3. Пусть имеет непрерывные частные производные второго порядка. Допустим, максимизирует на Тогда и матрица Гесса отрицательно полуопределенна.

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

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

Так как имеет непрерывные частные производные второго порядка, то матрица Гесса

Любая симметричная матрица Н порядка имеет собственных значений (некоторые из них могут быть равными), и единичных собственных векторов Эти собственные векторы и

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

Каждому собственному значению соответствует единичный собственный вектор ей который удовлетворяет уравнению

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

где означает евклидову норму и

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

где Е — матрица, строками которой являются собственных векторов

а - диагональная матрица с собственными значениями на диагонали,

Из представления Н в виде (5.15) и свойств собственных векторов (5.14) следует, что

Продолжая это рассуждение, мы можем показать, что матрица Н отрицательно полуопределена тогда и только тогда, когда

Так как матрица Гесса зависит от х, мы выразим эту зависимость в явной форме для собственных

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

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

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

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

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

где интервал . Отображение переводит где

а — это вектор, определяемый следующим образом:

При может быть взята равной произвольно или —1. Здесь, конечно, -наибольшее собственное значение, -соответствующий собственный вектор.

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

отрицательно полуопределенной. Это следует из выражения (5.19), так как если отрицательно полуопределена, то Множитель аналогичен в лемме 5.2 и обеспечивает неравенство

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

Сходимость будет доказана при помощи теоремы сходимости А. Напомним, что выполнение условия 1 этой теоремы предполагается. Установим выполнение условия 2 теоремы сходимости А. Пусть х не является подходящей точкой. Первоначально предположим, что Тогда, воспользовавшись соотношением (5.22), получим

и результат следует из теоремы 2.1.

Пусть теперь х не является подходящей точкой но матрица не является отрицательно полуопределенной. В этом случае где или так как не является отрицательно полуопределенной матрицей.

Тогда, учитывая соотношение (5.18),

так как Кроме того, согласно

Тогда улучшения можно достигнуть, используя процедуру, рассмотренную при доказательстве леммы 5.2, что устанавливает справедливость условия 2а. То, что условие 26 выполняется, следует непосредственно.

Доказательство условия 3. Для установления сходимости процедуры осталось только показать выполнение условия 3. Для этого отображение разбивается на компоненты и доказывается замкнутостъ каждой из них. Тогда согласно результатам гл. 4 замкнутость А будет установлена.

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

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

Начнем с рассмотрения отображения которое данную точку х переводит в Пусть

и

Нужно показать, что

Другими словами, необходимо установить, что является собственным вектором для Собственный вектор решает систему уравнений (5.13), которая может быть переписана в виде

где — единичная матрица и

Вспомнив, что как так и непрерывны, и перейдя к пределу в уравнении (5.23), придем к соотношению

Следовательно, является собственным вектором для Кроме того, все нормализованы, так что переходя к пределу, получаем

Значит, — собственный вектор для

Таким образом, отображение замкнуто.

Теперь рассмотрим отображение где

Это отображение может быть выражено в виде произведения двух замкнутых отображений типа скаляр на вектор, одно из которых — отображение а другое —

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

В соответствии с конструкцией отображения мы должны доказать замкнутость отображения Это отображение по данному х определяет Пусть

Замкнутость будет доказана, если мы покажем, что или, другими словами,

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

Если в первом случае

то, используя выражение (5.25) и непрерывность градиента, имеем для достаточно больших

Но по определению для этих и из (5.24) следует, что

Кроме того, (5.26) дает Поэтому и в этом случае А замкнуто.

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

Таким образом, проверены все три возможных случая, и замкнуто.

В нашем построении далее следует отображение

Но оно представляет собой произведение отображений типа скаляр на вектор. Замкнутость следует из леммы 4.6в, так как входит в компактное множество и Наконец, отображение является суммой отображений Так как непрерывно и замкнуто, то лемма 4.4 устанавливает замкнутость

Чтобы доказать замкнутость мы применим лемму 4.2. В качестве упр. 7 читателю предлагается

доказать, что предположения леммы 4.2 удовлетворяются, так что отображение А замкнуто.

Следовательно, метод второго порядка сходится.