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

1.2.1. Преобразование задач с ограничениями к задачам безусловной оптимизации

 

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

Рассмотрим задачу нелинейной оптимизации с прямыми и функциональными ограничениями:

 

(1.2)

 

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

 

(1.3)

 

где  – вектор новых варьируемых параметров.

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

 

(1.4)

 

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

 

(1.5)

 

Переформулированная в новых переменных задача примет вид:

 

(1.6)

 

 

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

 

(1.7)

 

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

 

Таблица 1 – Типы ограничений и функций преобразования.

Тип ограничений	Функция преобразования

 

Рассмотрим основные подходы к учету функциональных ограничений. Пусть решается задача минимизации целевой функции f(X) с функциональными ограничениями, представленными в виде системы неравенств (1.8) и равенств (1.9):

 

	(1.8)
	(1.9)

 

Для учета функциональных ограничений обычно используется метод штрафных функций. При этом осуществляется переход от исходной целевой функции f(X) к следующей функции:

 

(1.10)

 

Здесь S(X) — штрафная функция (функция штрафа), отличная нуля вне допустимой области D;  - коэффициент штрафа, значение которого может быть постоянным или меняться на различных итерациях. Во втором случае параметр  настраивается в ходе оптимизационного процесса (k - номер итерации).

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

Существует два метода построения штрафных функций:

· метод внутренних штрафных функций (барьерных функций);

· метод внешних штрафных функций.

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

 

(1.11)

 

При этом предполагается, что ограничения-равенства (1.9) в задаче отсутствуют. Тогда целевая функция оптимизационной задачи примет вид:

 

	(1.12)
или
	(1.13)

 

При этом параметр  выбирается таким образом, чтобы его значения стремились к нулю при  (k - номер итерации).

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

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

 

	(1.14)
	(1.15)

 

При этом если ограничения не нарушаются, то есть  и , то S(X)=0. Если ограничения нарушаются, то величина “штрафа” зависит от степени нарушения ограничения.

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

 

(1.16)

 

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