3.1. Методы последовательной безусловной оптимизации

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

В соответствии с основной идеей исходную задачу (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.1.2. Метод барьерных функций

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

(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. Этим объясняется, что метод барьерных функций иногда называют методом внутренней точки.