4.5.6. Непрямые методы условной оптимизации

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

Градиентный метод поиска седловой точки. Пусть для задачи поиска минимума, сформулированной в виде (48),(49), введена

функция Лагранжа L(X,Λ)= f (x1, x2 ,..., xn )+ ∑m λ j z j (x1, x2 ,..., xn ),

j=1

причем имеют место условия xi ≥0, i=1,2,…n; λj≥0, j=1,2,…m. В п. 4.5.1 было отмечено, что решение такой задачи достигается в седловой точке функции L, в которой должны соблюдаться условия (53), (54). Более удобной для построения численных алгоритмов по сравнению с (53) является запись первого необходимого условия достижения седловой точки в форме условий КунаТаккера:

x

≥ 0 при

∂L

X0,Λ0

= 0 , i=1,2,…n;

∂x

i0

i

xi 0 =0 при

∂L

X

0

,

0 ≥ 0, i=1,2,…n;

∂x

Λ

i

λ j0 ≥ 0 при

∂L

X0

,Λ0

= 0 , j=1,2,…m;

∂λ j

λj 0 =0 при

∂L

X 0

,Λ0

≤ 0 , j=1,2,…m.

∂λj

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

∂L		∂f	m	∂z j
	=		+ ∑λ j		; i=1,2,…n;
∂x		∂x		∂x
i		i	j=1	i

∂L = z j ; j=1,2,…m.

∂λj

Анализируя представленные соотношения, отметим следующее:

111

1.Функция Лагранжа линейно зависит от λ. Поэтому условие вогнутости функции Лагранжа по λ выполняется всегда.

2.Условие выпуклости функции Лагранжа по x в силу линей-

ной зависимости ее частных производных по xi от частных производных функций f и zj сводится к выпуклости всех указанных функций.

3.Задачу, для которой выполняется последнее условие, называют задачей выпуклого программирования. В задачах выпуклого программирования условия Куна-Таккера оказываются достаточными для наличия седловой точки.

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

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

игарантии того, что найденное решение действительно дает глобальный, а не локальный, экстремум, такие алгоритмы не дают.

Рассмотрим простейший вариант градиентного алгоритма:

1.Выбирают некоторую начальную точку, определяемую ко-

ординатами X[k]=(x1 [k],x2 [k],…,xn [k]), Λ[k]=(λ0[k],λ1[k],...

...,λm

[k]), k=0.

2. Вычисляют значения частных производных в данной точке:

∂L

∂f

m

∂z j

=

X[k],

Λ[k]+ ∑λ j [k]

X[k],Λ[k]; i=1,2,…n;

∂x

∂x

∂x

i

k

i

j=1

i

∂L

= z j (X[k]); j=1,2,…m.

∂λ

j

k

3. Рассчитывают координаты следующей точки:

xi [k +1]= xi

[k]−ak

∂L

; i=1,2,…n (движение по коорди-

∂x

k

i

натам xi в сторону уменьшения функции L);

[k +1]= λ

[k]+ a

∂L

λ

j

j

k

; j=1,2,…m (движение по коор-

∂λ

j

k

динатам λj

в сторону увеличения функции L).

112

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

5.Пункты 2...4 повторяют, пока приращения координат при переходе к следующей точке не окажутся достаточно малыми.

Известны различные варианты и модификации такого алгоритма, различающиеся способом выбора или изменения коэффи-

циента ak и другими деталями.

Методы штрафных функций преобразуют задачу с ограничениями в последовательность задач безусловной оптимизации некоторых вспомогательных функций. Последние получаются путем модификации целевой функции с помощью функций-ограничений таким образом, чтобы ограничения в явном виде в задаче оптимизации не фигурировали. Это обеспечивает возможность применения методов безусловной оптимизации. В общем случае вспомогательная функция имеет вид F(X,a)=f(X)+Ф(X,а). Здесь f(X) – целевая функция задачи оптимизации; Ф(X,а) – “штрафная” функция; параметр а>0.

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

Метод внутренних штрафных функций применяется для ре-

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

кгранице допустимой облас-

ти G (рис. 34). Иными словами, приближение к границе “штрафуется” рез-ким увеличением значения функции F(X,а). На границе G построен “барьер”, препятствующий нарушению ограничении в процессе безусловной минимизации

	F(X,а). Поиск минимума	Рис. 34
	вспомогательной функции

113

F(X,а) необходимо начинать с внутренней точки области G. При этом в процессе оптимизации траектория спуска никогда не выйдет за пределы допустимой области. Все перечисленные особенности функции Ф(X,а) определили наименование рассматриваемой группы методов.

Таким образом, внутренняя штрафная функция Ф(X,а) должна обладать следующими свойствами:

→ ∞ при x G,

Φ(X, a)= → 0 при x G, x dG, a → 0,→ ∞ при x G, x → dG,

где dG – граница области G.
Внутренние штрафные	функции задаются в форме
Φ(X,a)= a ∑m ϕj (z j (X)), где ϕj	– непрерывные дифференцируе-
j=1

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

ренних штрафных			функций используют, например, такие:
Φ(X,a)= a ∑m	1		, Φ(X,a)= −a ∑m ln(z j (X)).
j=1 z j (X)			j=1

Алгоритм метода внутренних штрафных функций состоит в следующем:

1.В качестве начальной точки X[0] выбирают произвольную внутреннюю точку области G.

2.Задаются некоторой монотонно убывающей сходящейся к нулю последовательностью {ak}, k=1,2,..., положительных чисел.

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

X[1]=X(а1). Эту точку используют в качестве начальной для решения задачи поиска минимума функции F(X,а2 ) и так далее.

4.Вычисления прекращают при выполнении условий |f(X[k])–

f(X[k–1])|≤ε, ||X[k]–X[k–1]||≤δ, где ε, δ – заданные числа, определяющие точность вычислений.

Таким образом, метод внутренних штрафных функций предусматривает последовательное решение задач безусловной минимизации функций F(X,аk ), k=1,2,..., причем решение предыдущей задачи X(аk) используется в качестве начальной точки для поиска

114

Рис. 35

последующего вектора X(аk+1). Для задач, содержащих непрерывные функции и имеющих локальные минимумы внутри области G, последовательность полученных таким образом точек сходится

к точке локального минимума X .

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

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

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

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

Φ(X, a)= 0	при x G,
→ ∞	при x G, a → ∞.

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

m1		ψ		(g		(X))+	m2	φ	(h		,
Φ(X,a)= a	∑		j		j		∑			(X))
								l	l
j=1							l=1

где ψj, φj – непрерывные дифференцируемые функции, определяемые соответственно ограничениями-неравенствами и равенствами исходной задачи нелинейного программирования. Одна из применяемых на практике внешних штрафных функций имеет вид

115

	m1		[max(0, g		(X))]2	+	m2	(h	(X))2		,
Φ(X,a)= a		∑		j			∑
								l
	j=1						l=1
где max(0, g)= 0	при g ≤ 0, .
g	при g > 0.

Алгоритм метода внешних штрафных функций формулируется так же, как и алгоритм метода внутренних штрафных функций, и обладает аналогичными свойствами. Однако в этом случае не тре-

буется, чтобы начальная точка X[0] G, а последовательность {ak}, k=1,2,..., положительных чисел должна быть монотонно возрастающей.

Анализ методов штрафных функций позволяет сделать следующие выводы об их вычислительных свойствах. В соответствии с методами внутренних штрафных функций ведут поиск решения, не выходя за пределы допустимой области. Это весьма важно в тех случаях, когда целевая функция или ограничения не определены за пределами допустимого множества. Кроме того, прервав вычисления в любой момент времени, мы всегда получим допустимое решение. Однако для задания в качестве начальной некоторой допустимой точки иногда требуется решать задачу, по сложности сравнимую с исходной задачей нелинейного программирования. В этом смысле метод внешних штрафных функций предпочтительнее, так как он обеспечивает решение из любой начальной точки. В результате программирование на ЭВМ алгоритмов внешних штрафных функций существенно упрощается. Общим недостатком методов штрафных функций является сложность вспомогательной функции F(X,а), которая часто имеет овражную структуру, особенно при больших a. Кроме того, при больших значениях а точность вычислений минимума F(X,а) существенно снижается из-за ошибок округления ЭВМ.

Комбинированные алгоритмы штрафных функций. Вспомога-

тельная функция F(X,а) включает в себя слагаемые в виде внутренних штрафных функций ϕ(X,а) для ограничений-неравенств и

внешних штрафных функций φ(X,а) для ограничений-равенств. При этом для внутренней щтрафной функции используется убывающая последовательность коэффициентов {ak}, k=1,2,..., а для внешней – последовательность {1/ak}, k=1,2,..., удовлетворяющая сформулированным выше требованиям.

116