Методы оптимизации при наличии ограничений

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

Целевую функцию f(X)=f(x₁,x₂,...,x_n) и функции h_j(X)=h_j(x₁,x₂,...,x_n), j=1,...,m; g_s(X)=g_s(x₁,x₂,...,x_n), s=1,...,p, задающие ограничения, будем рассматривать как функции, заданные в точках n-мерного евклидова пространства Eⁿ.

Изучим наиболее употребительные методы решения рассматриваемых задач вида

min{f(X)| X R (3.1)

где R-допустимая область, задаваемая ограничениями типа равенств и неравенств

. (3.2)

В случае гладких выпуклых функций f(X),h_j(X),g_s(X) поставленная задача (3.1) может быть решена с применением необходимых и достаточных условий, устанавливаемых теоремами Куна-Таккера. Однако для решения большинства практических задач используются приближённые численные методы. Рассмотрим некоторые из них, представляющие две группы методов.

1. Методы, использующие преобразование задачи условной оптимизации в эквивалентную последовательность задач безусловной оптимизации путём введения в рассмотрение вспомогательных функций. Эти методы называют методами последовательной безусловной оптимизации.

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

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

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

МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОЙ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Метод штрафных функций

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

(3.3)

где P(X,r_k) - присоединённая функция, играющая роль штрафа за нарушение ограничений (3.2) исходной задачи (3.1); r_k –весовой коэффициент, с помощью которого достигается компромисс между необходимостью удовлетворения ограничений (3.2) и процессом минимизации целевой функции f(X).

Присоединённая функция P(X,r_k), называемая штрафной функцией, подбирается так, чтобы при больших k расширенная функция F(X,r_k) мало отличалась от f(X) при и быстро возрастала при удалении точки Х от допустимой области R. При этом можно выбрать P(X,r_k) так, чтобы расширенная функция F(X,r_k) обладала свойствами, позволяющими использовать для решения задач (3.3) достаточно эффективные методы безусловной минимизации.

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

(3.4)

где .

Как нетрудно заметить, функция (3.4) тождественно равна нулю, если , то есть если выполняются все ограничения исходной задачи. Но при нарушении хотя бы одного из ограничений возникает "штраф", величину которого можно сделать сколь угодно большой за счёт выбора параметра r_k>0. Поэтому при решении последовательности задач (3.3) требуют выполнения условия при , чем достигается возрастание штрафной функции P(X,r_k) при . При этом минимизация расширенной функции F(X,r_k) обеспечивает выполнение ограничений исходной задачи со всё большей точностью.

Обычно, если штрафная функция строится в виде (3.4), начальная точка поиска выбирается вне допустимой области R. На каждом k-том этапе определяется точка X^*(r_k) минимума расширенной функции F(X,r_k) при заданном значении параметра r_k с помощью одного из методов безусловной минимизации. Полученная точка X^*(r_k) используется в качестве начальной на следующем этапе, выполняемом при большем значении параметра r_k. При непрерывном возрастании r_k последовательность точек X^*(r_k) стремится к точке X*- точному решению исходной задачи (3.1).

В качестве условия окончания поиска можно использовать неравенства

P(X*(r_k),r_k) , , (3.5)

где параметры точности.

Поскольку элементы последовательности {X*(r_k)} приближаются к точке Х* извне допустимой области, рассмотренный метод называют методом внешней точки.

Метод барьерных функций

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

(3.6)

Идея метода заключается в сведении задачи (3.6) к последовательности задач безусловной минимизации

, (3.7)

где присоединенная функция выбирается таким образом, чтобы при больших k она мало отличалась от целевой функции f(X) во внутренних точках , но неограниченно возрастала при приближении точки X к границе области R. Влияние такой функции при больших k состоит в создании "барьера" с крутыми склонами вдоль границы допустимой области. Поэтому они и называются барьерными функциями.

Такими свойствами обладает, например, функция

(3.8)

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

Начальная точка задаётся только внутри области R. На каждом k-ом этапе ищется точка минимума расширенной функции при заданном значении r_k с помощью одного из методов безусловной минимизации. Полученная точка используется в качестве начальной на следующем этапе, выполняемом при уменьшающемся значении параметра r_k. При последовательность точек стремится к точке условного минимума X^*. Барьерные функции как бы препятствуют выходу из множества R, а если решение задачи лежит на границе, то процедура метода приводит к движению изнутри области к границе.

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

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