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

Пусть задано –некоторое начальное приближение. Методом условного градиента найдена т. .Строим функцию: и решаем вспомогательную зад. Пусть –решение вспомогательной задачи минимизации заметим, что

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

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

Замечание:

1. Метод условного градиента является эффективным в том случае, когда вспомогательная зад. допускает простое решение;

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

• Задают некоторое значение и проверяют условие (6)

• В случае выполнения (6), ; иначе дробят

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

Теорема3

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

34. Алгоритм метода покоординатного спуска.

Рассмотрим задачу . Пусть выбрано некоторое начальное приближение. И мтодом покоординатного спуска было получено приближение . Ч/з , , обозначим координатные вектора (1 на j-ом месте). Положим и для , где определяется из условия . И следующее приближение , если для некоторого k , то процесс вычисления заканчивают, А т считают приближением к точке минимума.

Данный метод хорошо подходит для задач с параллепипедными ограничениями,

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

35. Сходимостсь метода скорейшого спуска

Т.1:Пусть в задаче (1) , целевая функция J(x) непрер. диффер.,огранич. с низу и её градиент удовл.вект.усл.Липшица

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

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

Точка в методе скор. спуска определяется из условия, что . Тогда имеем

(3)

Нер-во (3) обосновывает релаксационность процесса. Т.о. послед-сть монотонно убывает. Ф-ия ограничена снизу, поэтому посл-ть как монотонно убывающая и огранич. снизу имеет предел

. Перейдя в нер-ве (3)к пределу получаем . 2) мн-во М(х⁰) явл. огранич. В силу построения М(х⁰)-замкн. мн-во. Ф-ия f(x) непрер., поэтому по т.Вейштрасса реш. зад. Миним-ии ф-ии f(x) по мн-ву M(x⁰) сущ. Поэтому мн-во Х_* решений зад.(1) не явл. пустым и Х_* явл. подмн-ом M(x⁰). Т.о. посл. х^к явл. оранич. Из огранич. послед-сти можно выделить сходящуюся.Пусть подпосл-ть . Поэтому но т.к. -ф-ия непр., то этот предел равен ф-ии любая предельная т. посл. . А т.о. хотябы одна предельная т.сущ. то мн-во .Докажем теперь, что . Ф-ия расстояния от т. до мн. , поэтому сходящуюся. Пусть подпосл. ; .Ф-ия расстояния явл. непрер. ф-ей точки, поэтому . Но по первой части док-ва, каждая предельная точка посл.{x^k} , то Последне ра-во справедливо для любой сходящейся посл-ти {x^k}: 3)Пусть ф-ия f(x)-выпукла , тогда на м-ве М(х⁰) зад.(1) имеет решение т.е. сущ.т. Отсюда . По cв-ву неотр-ти остатка выпуклой ф-ии имеем где D< в силу огран-ти М(х⁰). Переходя к пределу в последнем нер-ве получаем , т.е. посл. явл. минимизир. Аналогично 2-ой части док-ва доказыв., что