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

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

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

· Метод проекции градиента

1. Применение в задаче с ограничениями типа равенств

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

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

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

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

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

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

Расчет заканчивается в точке , в которой , . В полученной точке требуется обязательная проверка выполнения достаточных условий минимума задачи (УО). Точное равенство свидетельствует о точном выполнении необходимых условий экстремума, при этом вектор множителей Лагранжа определяется по формуле

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

Обоснование. Проекцией точки на множество называют ближайшую к точку этого множества и обозначают ее , т.е. такую точку , что

где – расстояние от точки (элемента) до множества .

Основные свойства операции проектирования.

а) Если , то .

б) Если – замкнутое множество, то любая точка имеет проекцию на множество . Если при этом – выпуклое множество, то проекция единственна.

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

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

г) Если – выпуклое замкнутое множество, и − проекции точек и на , то

т.е. длина проекции отрезка на выпуклое множество не превосходит длины самого отрезка.

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

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

Утверждение (сходимость). Пусть выпуклая, дифференцируемая на функция, градиент которой удовлетворяет на множестве условию Липшица с константой L. Пусть множество − выпуклое и замкнутое, множество решений задачи (УО) не пусто, а . Тогда и, если сильно выпукла, то со скоростью геометрической прогрессии.

Определение: Функцию , определенную на выпуклом множестве называют сильно выпуклой, если .

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

2. Применение в задаче с ограничениями типа неравенств

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

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

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

где – матрица размера , и проекцией на нее вектора . Для выявления неравенств, активных в точке , задается погрешность определения активных ограничений . Активными считаются те ограничения, для которых . Число p активных в точке ограничений не должно превышать n.

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

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

Проекция в точке , в которой активны p ограничений, определяется точкой

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

а –наименьший шаг, при котором

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

Процедура точек последовательности обеспечивает последовательное движение вдоль границы допустимой области. При выполнении неравенства , вычисляется приближение вектора множителей Лагранжа :

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

Утверждение о сходимости как для случая равенств.

· Метод возможных направлений Зойтендейка

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

Вектор d называется возможным направлением спуска в точке , если существует такое , что и для всех .

Дата добавления: 2014-01-05