MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Optimization Toolbox 2.2 Руководство пользователя

А.Г.Трифонов. Оптимизация при наличии ограничений

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

Применительно к уравнению (3-1) (GP) уравнения Куна-Таккера записываются в виде

(3-26)

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

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

Последовательное квадратичное программирование SQP

SQP метод является одним из самых современных методов в области нелинейного программирования. Шитковский [38], к примеру, успешно реализовал и провел тестовые расчеты по данной версии оптимизации и получил всестороннее превосходство, по сравнению с другими тестовыми методами, в части эффективности, точности и процента успешного решения задачи для большого числа тестовых задач.

Основанный на работах Бигса [1], Хана [24] и Пауэлла ([34], [35]) данный метод позволяет достаточно точно имитировать метод Ньютона для оптимизации при наличии ограничений, как это сделано для оптимизации без наличия ограничений. На каждой основной итерации осуществляется аппроксимация Гессиана для функций Лагнранжа при помощи квазиньютоновского модифицированного метода. Такой подход далее будет востребован для постановки подзадачи QP, решение которой далее уже используется для формирования направления поиска в процедуре линейного поиска. Обзор методов SQP можно найти в работах Флетчера [15], Гиль и др. [21], Пауэлла [37] и Шитковского [25]. Тем не менее, далее приводится описание обобщенного метода.

Согласно описанию задачу метода GP (уравнение 3-1) основная идея постановки подзадачи QP заключается в квадратичной аппроксимации функции Лагранжа.

(3-27)

Последнее представляет собой упрощение уравнения 3-1 при предположении, что связанные ограничения могут быть представлены через ограничения в виде неравенств. Посредством линеаризации нелинейных ограничений можно получить подзадачу QP.

Подзадача квадратичного программирования (QP)

(3-27)

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

Параметр при длине шага определяется из соответствующей процедуры линейного поиска, которая обеспечивает приемлемое уменьшение получаемой функции выгоды (см. раздел Корректировка матрицы Гессе). Матрица является положительно определенной аппроксимацией матрицей Гессе для Лагранжевой функции. (уравнение 3-27). может быть корректироваться посредством любого из квазиньютоновских методов, хотя метод BFGS (смотри раздел Корректировка матрицы Гессе), скорее всего, является наиболее популярным.

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

Рассмотрим функцию Розенброка (уравнение 3-2) при наличии дополнительных нелинейных ограничений в виде неравенств, g(x),

(3-29)

При применении метода SQP эта задача решается за 96 итераций по сравнению с 140 итерациями для задач без ограничений. На рисунке 3-6 представлен путь к точке решения начиная со стартовой точки .

Рис. 3-6. Применение метода SQP для функции Розенброка (уравнение 3-2) с линеаризованными нелинейными ограничениями

Реализация метода SQP

Реализация метода SQP состоит из трех основных стадий, которые далее кратко обсуждаются в следующих подразделах

  • Корректировка матрицы Гессе для Лагранжевой функции.

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

  • Вычисление линейного поиска и функции выгоды

Корректировка матрицы Гессе

На каждой главной итерации положительно определенная квазиньютоновская аппроксимация для функции Лагранжа , H, рассчитывается с помощью метода BFGS, где представляют собой оценку множителей Лагранжа.

 , где

(3-30)

Пауэл вообще [35] рекомендует поддерживать значения матрицы Гессе положительно определенными, даже не смотря на то, что в точке эти решения могут и не иметь положительные решения. Положительные значения матрицы Гессе поддерживаются в том случае, если величина будет больше нуля для каждой корректировки и, что H инициализируется как положительно определенная матрица. Когда величина не является положительной, то параметр модифицируется поэлементно, шаг за шагом, так что бы выполнялось условие . Обобщенная цель такой модификации заключается в том, что бы несколько изменить элементы , которые составляют основной вклад в положительно определенную корректировку, как можно меньше. Таким образом, на начальной стадии принятой модификации, отрицательный наибольший элемент их набора последовательно уменьшается на половину. Такая процедура продолжается до тех пор, пока больше или равна 1e-5. Если после такой процедуры все равно остается положительной, то производится модификация y путем добавления некого вектора v, умноженного на некую скалярную постоянную w, а именно,

(3-31)

где

если и

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

Программы fmincom, fvinmax, fgoalattain и fseminf реализованы на основе метода SQP. Если опционный параметр Display установлен как отображение информации на каждой итерации 'iter', то выводится различная информация, включая значение функции и максимальное нарушение поставленных ограничений. Также отображается модифицированный Гессиан, в случае, если он претерпевает некую коррекцию на первоначальной стадии выполняемой процедуры с целью поддержания его положительного значения. Если Гессиан подвергается вторичной корректировке на второй стадии приведенного выше подхода, то отображается его вторичное значение. Если подзадача QP не является выполнимой, то этот факт так же отображается. Такая отображаемая информация, как правило, не представляет особого интереса, но указывает на то, что данная задача является существенно нелинейной, а сходимость может быть более длительной, чем обычно. Иногда отображаемое сообщение не изменяется, что указывает, что величина будет порядка нуля. Это может указывать, что постановка задачи является неправильной или проводится оптимизация прерывистой функции.

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

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

(3-32)

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

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

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

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

(3-33)

где

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

(3-34)

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

(3-35)

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

(3-36)

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

(3-37)

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

(3-38)

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

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

(3-39)

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

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

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

(3-40)

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

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

(3-41)

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

(3-42)

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

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

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

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

(3-43)

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

(3-44)

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

(3-45)

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

(3-46)

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

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

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

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

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

Основной алгоритм.

Алгоритм симплексного метода включает в себя две фазы:

Фаза 1. - Расчет начальной основной допустимой точки.

Фаза 2. - Расчет оптимального решения согласно поставленной задаче.

Примечание. Применительно к программе linprog нельзя принимать исходную точку х0 для расчета по алгоритму симплексного метода. Если все же х0 будет передано в качестве входного аргумента, то программа linprog игнорирует эту точку х0 и расчитывает свою собственную начальную точку.

Фаза 1. При выполнении фазы 1 в данном алгоритме определяется начальное основное допустимое решение (см. определения из раздела Основные и неосновные переменные) посредством решения кусочно-правильной вспомогательной задачи линейного программирования. Целевая функция этой вспомогательной задачи является линейной штрафной функцией

,

где члены Pj(xj) определены как

P(x) служит мерой того, как много точка х переступает нижний и верхний граничные условия. А вспомогательная задача будет

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

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

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

  • Выбирается одна переменная, называемая как вводимая переменная, из небазисных переменных и добавляется соответствующая колонка из небазисного вида в рассматриваемый базисный вид (в соответствии с принятыми определениями см. раздел Базисные и небазисные переменные).

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

  • Проводится корректировка текущего решения и значения текущей цели.

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

Предварительная подготовка.

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

Исключаются колонки, которые имеют только один ненулевой элемент, а так же исключаются их соответствующие строчки.

Для каждого уравнения из числа ограничений , где a есть строчные елементы для Aeq, в данном алгоритме для линейной комбинации в виде rlb и rub, рассчитываются нижняя и верхняя границы. Такой подход является справедливым в случае конечных значений нижней и верхней границ. Если или rlb или rub равно b, то эта константа называется принудительным ограничением. В данном алгоритме каждый раз устанавливается некая переменная соответствующая ненулевоиу коэффициенту из , равному его верхней или нижней границе в зависимости от принудительного ограничения. Далее согласно алгоритму удаляются колонки, соответствующие этим переменным, а так же удаляются соответствующие принудительным ограничениям строчки.

Использование симлексного алгоритма.

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

'LargeScale' в 'off' и 'Simplex' в 'on'.

options = optimset('LargeScale', 'off', 'Simplex', 'on')

Далее вызывается функция linprog с соответствующими входными опциями и аргументами. Детали использования функции linprog приведены соответсвующем разделе.

В ситуации если программа определит недопустимость или наличие неограниченнности при выполнении процедуры предварительной подготовки данных, то Linprog возвращает пустые выходные аргументы на месте x и fval. Linprog возвращает значение текущей точки в ситациях, когда

  • Есть превышение максимального числа итераций.

    Будет определено, что поставленная задача является невыполнимой или не имеющей границ относительно фаз 1 и 2.

  • Когда задача не имеет предельных границ, то linprog возвращает значения x и fval относительно направления отсутствия предельных границ.

Основные и неосновные переменные.

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

(Отметим, что A и b не являются некими матрицей или вектором, определяющими неравенства в исходной задаче). Предположим, что A есть матрица размерностью m-х-n с рангом m < n и соотвествующими колонками {a1a2, ..., an}. Примем, что является пространством колонок A, с набором индексов B = {i1, i2, ..., im} и N = {1, 2, ..., n}. N является дополнением B. Субматрица AB есть так называемый базис, а дополнительная субматрица AN есть так называмый небазис. xB есть вектор базисных переменных и xN есть вектор небазисных переменных. При выполнении каждой итерации фазы 2 данного алгоритма производится замена одной колонки текущего базиса на колонку небазиса и, соответственно, корректируются переменные xB и xN.

Если х есть решение системы и все небазисные переменные для xN равны или их нижней или верхней границе, то х называется базисным решением.

Литература

[1]  Chvatal, Vasek, Linear Programming, W. H. Freeman and Company, 1983.

[2]  Bixby, Robert E., "Implementing the Simplex Method: The Initial Basis," ORSA Journal on Computing, Vol. 4, No. 3, 1992.

[3]  Andersen, Erling D. and Knud D. Andersen, "Presolving in Linear Programming," Mathematical Programming, Vol. 71, pp. 221-245, 1995.


Поиск по сайту:

Система Orphus

Яндекс.Метрика