МЕТОД ПРОЕКЦИИ ГРАДИЕНТА (МЕТОД РОЗЕНА)

Будем рассматривать задачу (2.1)-(2.2) и предполагать в этом случае

,

(3.1)

где .

Обозначим через матрицу А набор векторов :

: , где

(3.2)

В каждой текущей допустимой точке под рабочим списком L будем понимать подмножество ограничений, активных в этой точке.

Все ограничения, которые входят в рабочий список, будут составлять часть ограничений вида (3.2).

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

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

,

(3.3)

где – направление, а – длина шага.

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

3.1 Выбор направления

В методе проекций градиента направление выбирается следующим образом:

1. Если текущая точка является внутренней области , то в качестве направления берется антиградиент.

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

Необходимо учитывать два условия:

а) значение функции цели должно уменьшаться;

б) направление не должно выводить из области решений.

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

;

.

Отсюда можем определить, что:

;

;

.

(3.4)

Теорема 3.1. Решением задачи поиска минимальной функции при ограничении () является вектор

, где

	;	(3.5)
	.	(3.6)

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

Для того чтобы убедиться в том, что полученные направления удовлетворяют условию (3.4), достаточно умножить матрицу на матрицу проектирования:

.

3.2 Определение длины шага на каждой итерации.

Вначале найдем для текущей точки и направления максимальную длину шага, при котором мы будем оставаться внутри области допустимых решений. Для этого в новой точке должны выполняться все ограничения вида (2.2). При этом все ограничения рабочего списка в новой точке будут выполняться как строки и равенства, поэтому проверять следует только ограничения, которые не входя в рабочий список.

,

,

,

,

.

(3.7)

Так как точка , то в этой точке будут выполняться все ограничения вида (2.2).

Рассмотрим две ситуации, которые будут возникать при анализе формулы (3.7):

1.

В этом случае при любом значении ограничение (3.7) будет выполняться.

2.

,

,

,

(3.8)

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

,

.

(3.9)

3.3 Критерий оптимальности

Итерационная процедура вида (3.3) будет продолжаться до тех пор, пока в некоторой текущей точке не будут выполняться условия Куна-Таккера, которые будут проверяться только в том случае, если на текущем шаге вектор направления движения

3.4 Изменение рабочего списка

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

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

.

Если , то это оптимальная точка.

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

3.5 Общая схема метода проекции градиента

Шаг 0. Определение допустимой точки .

Шаг 1. Построение .

Шаг 2. Если , то переходим на шаг 6.

Шаг 3. Определяем , .

Шаг 4. Если , то добавляем ограничение в .

Шаг 5. , . Переходим на шаг 1.

Шаг 6. Определение , решение системы Куна-Таккера.

Шаг 7. Если , то – решение задачи. Остановка алгоритма. Иначе – удаление ограничений из и переход на шаг 1.

Пример

Задана функция с ограничениями

.

Выполнить один шаг методом проекции градиента.

Решение

1. В качестве допустимойточки возьмём

.

2. В данной точке активными являются лишь ограничения неотрицательности параметров и . Тогда

и в соответствие с (3.6) имеем:

.

Так как – нулевая матрица, то из (3.5) видно, что .

3. Определим λ как решение системы Куна-Таккера:

;

;

.

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

Тогда получим новую матрицу , для которой

,

.

Имеем

4. Для определения найдем минимум функции

.

Для определения максимальной длины шага рассчитаем , где – ограничения, не входящие в рабочий список:

;

;

и выберем минимальное из двух значений:

;

.

Получили, что .

5. Переходим на шаг 1 для новой допустимой точки:

.

4 МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ
(МЕТОД ЗОЙТЕНДЕЙКА)

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

.

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

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

Рассмотрим задачу вида (2.1)-(2.2). Линеаризация фигурирующих в этой задаче функций путем их разложения в ряд Тейлора в окрестности точки приводит к следующей задаче:

при ограничениях

.

(4.1)

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

Перемещение из точки в точку задаетсясоотношением

.

Подстановка в задаче (4.1) вместо вектора его текущего значения приводит к задаче

при ограничениях

.

(4.2)

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

		(4.3)
	и	(4.4)

Любой вектор , удовлетворяющий неравенствам (4.3) и (4.4), одновременно является вектором допустимого направления.

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

(4.5)

при условиях

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

Алгоритм метода возможных направлений

Шаг 1. Пусть – некоторая допустимая точка задачи (2.1)-(2.2) с ограничениями в виде неравенств.

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

Шаг 3. Если , то определяется максимальная длина шага , осуществляемого в направлении без выхода за пределы допустимой области задачи (1.1)-(1.2):

.

Затем определяется :

.

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

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

Пример.

Задана функция

с ограничениями

.

Выполнить один шаг методом возможных направлений.

Решение.

1. В качестве допустимойточки возьмём

.

2. Вычислим градиенты функции и в точке :

,

.

В данной точке активными являются лишь ограничения неотрицательности параметров и . Тогда

.

Решив задачу

симплекс-методом, получаем .

Для определения максимальной длины шага рассчитаем , где – ограничения, не входящие в рабочий список:

,

и выберем минимальное из двух значений:

,

.

Получили, что . Тогда

.

Переходим на шаг 2 для новой допустимой точки:

.

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

Пример выполнения задания для курсового проекта

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

1 Построение математической модели

1.1 Обозначенияинеформальнаяпостановка

Введём необходимыеобозначения. Обозначимполубесконечную полосу буквой S. Количество кругов обозначим n, i-й круг – T_i, радиус i-го круга – r_i, . Примем за полюс круга его центр. Границей размещения назовём отрезок на полосе S, после которого не расположено ни одного круга. Расстояние от начала полосы до этого отрезка обозначим Z (рис.1.1).

Рисунок 1.1 – Геометрическое представление задачи

Параметрами размещения i-го круга являются координаты его центра (x_i, y_i). Так как они имеют определенный физический смысл, то их можно считать составляющими вектора Х_i.

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

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

1.2 Область допустимых решений задачи

Если существует набор векторов Х_i, , такой, который попадает в область допустимых значений D, то задача имеет решение и данный набор векторов является одним из решений.

Область D описывается условиями:

а) круги должны принадлежать полосе (рис. 1.2):

T_i (Х_i) S, . (1.1)

Рисунок 1.2 – Геометрическое представление условия принадлежности кругов полосе

б) круги не должны пересекаться между собой (рис. 1.3):

int T_i(Х_i) ∩ int T_j(Х_j) = 0, ; . (1.2)

Для формализации условий не пересечения был разработан аппарат Ф-функции [14].

Рисунок 1.3 – Геометрическое представление условия не пересечения пары кругов

1.3 Использование Ф-функций