А.Г.Трифонов.

Решение задачи квадратичного программирования.

На каждой основной итерации метода SQP решается задача QP в следующей форме, где относится к i-той стоке матрицы размерностью m х n:

Используемый в тулбоксе Оптимизация метод основан на стратегии активных наборов (более известен как метод проекций) и аналогичен методу, описанному в работе Гиля и др., [20] [19]. Этот метод был модифицирован применительно для задач Линейного программирования (LP) и Квадратичного программирования (QP).

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

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

Принятая матрица формируется из последних колонок разложения QR матрицы , где l есть число активных ограничений, а так же справедливо l < m. Т.е. определяется как

где

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

После дифференцирования по p получим

Член имеет отношение к проекции градиента квадратичной функции, поскольку он является проекцией градиента в подпространстве функций . Член есть так называемая проекция Гессиана. Полагая, что матрица Гессе H является положительно определенной (что справедливо применительно к реализации метода SQP), то минимум функции q(p) в подпространстве функций будет определяться условием , и, следовательно, для поиска минимума функции необходимо решение системы линейных уравнений.

А шаг в направлении минимума будет в следующем виде

Вследствие квадратичной природы целевой функции на каждой итерации следует, что существует только одно возможное значения размера шага . Единичный шаг в направлении как раз и есть шаг в направлении минимума функции, ограниченной пределами нулевого пространства . Если будет возможно принять такой шаг, без нарушения принятых ограничений, то это как раз и будет решение QP (см. уравнение 3-33). В противном случае, шаг вдоль направления в сторону ближайшего ограничения будет меньше единицы и в активный набор на следующей итерации будут включены новые ограничения. Расстояние до границ ограничений в любом направлении можно представить как

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

В случае включения n независимых ограничений в активный набор, без локализации минимум, то для соответствия невырожденной системе линейных уравнений

следует рассчитывать множители Лагранжа.

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

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

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

Упомянутый выше алгоритм QP можно модифицировать применительно к задачам LP путем установки на каждой итерации направления поиска в направление наискорейшего спуска, где является градиентом взятой целевой функции (равенство коэффициентов линейной целевой функции).

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

Где есть градиент целевой функции для текущей итерации (т.е.).

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

Линейный поиск и функция выгоды

Решение подзадачи QP приводит к формированию вектора , который, в свою очередь, используется при формировании новой итерации типа

Для того, что бы получить достаточное уменьшение функции выгоды оценивается параметр длины шага . Реализованная в данном алгоритме функция выгоды была ранее использована Наном [24] и Поуэлом [35] и имеет следующий вид.

Поуэл рекомендует введение следующего штрафного параметра:

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

Где представляет собой эвклидову норму.

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

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

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

Данный алгоритм представляет собой продвижение вдоль краев многогранника, определенного принятыми ограничениями, от одной вершины к другой при снижении величины целевой функции, f^T x, на каждом шаге. Далее приводится описание улучшенной версии исходного метода симплексного алгоритма, который так же приводит к оптимальным решениям, находящихся на вершинах многоугольника.