6.3. МЕТОД ПОСТРОЕНИЯ СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ, ИСПОЛЬЗУЮЩИЙ ТОЛЬКО ЗНАЧЕНИЯ ФУНКЦИИ

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

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

Теорема 6.2. Пусть х — точка максимума в многообразии, содержащем направление и — также точка максимума в многообразии, содержащем Допустим, что

Тогда сопряжено с

Доказательство. Из выражения (6.8) видно, что не входит первое многообразие, следовательно, и должны быть линейно независимыми.

Из определения х вытекает, что

и, если раскрыть это, то

Аналогично для

Вычитая из второго равенства первое, получаем

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

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

данным сопряженным направлениям, построено новое сопряженное направление.

Каким же образом могут быть получены точки Пусть — произвольная исходная точка. Допустим, что по этой точке после поиска по направлениям мы определяем точку Точка х получается из точки алгоритмом , где определено по (6.7), а х принята равной Тогда по теореме будет (максимизировать в -мерном многообразии, порожденном и направлениями Если х не является оптимальной точкой, т. е. если х не максимизирует на то может быть определена точка такая, что

Отправляясь из точки мы опять ведем поиск в направлениях достигая Тогда точка максимизирует в многообразии, порожденном и направлениями На основе монотонности Таким образом, Так как максимизируют в многообразиях, содержащих то, полагая получаем, что направления являются сопряженными. Следовательно, у нас есть метод построения дополнительного сопряженного направления (рис. 6.1). На рисунке показано направление Линия представляет собой многообразие, порожденное линия II — многообразие, порожденное Точка х максимизирует на многообразии I, а на многообразии II. Обратите внимание, что в точке для определения требуется движение в отрицательном направлении Направление Чтобы максимизировать отправляясь

Рис. 6.1. Максимизация квадратичной функции с помощью сопря женных направлений: — линии уровня для квадратичной функции

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

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

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

В процедуре используется отображение для которого Кроме того, предполагается, что — точки в

Процедура 1 максимизации квадратичной функции.

Исходный шаг. Пусть даны исходная точка и произвольное направление Вычисляется Полагаем

итерация: даны

а. По расширяющему шагу из получаем

б. Для вычисляются рекурсивно

в. Полагаем

г. Определяется

Заменяем на и переходим к пункту

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

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

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

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

Исходный шаг. Дана исходная точка направлений при этом Для вычисляется определяется и принимается

итерация. Даны

а. По расширяющему шагу из получаем

б. Для вычисляется

в. Полагая вычисляем

г. Принимается .

Заменяем на и переходим к итерации

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

Интерпретация. Чтобы установить, что вычисляются действительно сопряженных направленний, предположим: в конце итерации направления являются сопряженными. Это означает, что точка — максимум на многообразии, порожденном направлениями На итерации полагаем Тогда точка также является максимумом на многообразии, порожденном направлениями Вследствие того, что расширяющий шаг обеспечивает выполнение неравенства направление сопряжено с направлениями Таким образом, на каждой итерации, если процедура не прерывается, вырабатывается новое сопряженное направление (см. также упр. 5).

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

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

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

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

Обратите внимание, что вместо максимума требуется найти минимум. Полагая находим

Исходный шаг. Пусть

Ясно, что Для определения вычислим

Оптимальным является - . Поэтому

Определяем

1-я итерация.

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

Оптимальным является Поэтому

Очевидно, Вычисляем

Определим найдя Тогда

2-я итерация. Нетрудно видеть, что решение. Отметим также, что и -сопряженные направления для

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