Сходимость и оценка погрешности метода

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

, где (6)

;

В этом случае справедлива теорема.

Теорема 1. Пусть и - выпукла на . Тогда для последовательности , определяемой условиями (3), (6), имеют место соотношения:

(7)

Если, кроме того, в (6) ( ), то справедлива оценка:

(8)

Следует заметить, что , найденное по формуле (4), удовлетворяет (6) с .

Метод условного градиента Алгоритм

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

Он может быть использован для задач следующего вида:

(9)

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

Опишем метод.

Пусть известно -е приближение . Приращение функции в точке можно представить в виде

.

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

, (10)

и определим вспомогательное приближение из условий

(11)

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

Рассмотрим в качестве примера нахождение точки в случае, когда множество представляет собой -мерный параллелепипед:

,

В этом случае функция , или , очевидно достигает своей нижней грани на в точке , где

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

В общем случае не всегда удается получить в явном виде вспомогательное приближение . В таких ситуациях вместо (11) используются следующие условия:

(12).

Допустим, что точка , удовлетворяющая условиям (12) (или (11)), уже найдена. Тогда -е приближение будем искать в виде

(13).

В силу выпуклости множества всегда .

Если (это может случиться, например, когда ) имеем независимо от способа выбора в (13). При определении точно из условия (11) имеем:

или

при всех . Как известно, это означает, что точка удовлетворяет необходимому условию минимума в задаче (9). Более того, если если выпукла, то данное условие явлется и достаточным, т.е. в этом случае задача (9) решена.

Теперь рассмотрим один из способов выбора шага .

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

(14).

В частности, для функции

, (15)

где - симметричная положительно определенная матрица порядка , , определяемая в соответствии с (15), вычисляется следующим образом. Вначале вычисляется промежуточная величина:

(16)

Затем находится искомое значение :

В качестве можно выбирать любую точку . В качестве критериев окончания счета можно использовать неравенства (5):

Метод условного градиента описан.

Сходимость метода и оценка погрешности

Метод условного градиента сходится с оценкой:

(17)

Задание к лабораторной работе

Разработать программу нахождения минимума функции вида (2), завиящей от двух переменных, при помощи метода наискорейшего спуска и метода условного градиента. Для метода условного градиента в качестве множества взять прямоугольник:

.

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

Начальная точка выбирается произвольно.

Результаты должны содержать: координаты точки минимума для функции , минимальное значение функции и количество итераций.