Оптимальная система автоматического управления (стр. 4 из 7)
L(xn, n) + L(xn, n)(xn+1 xn, n+1 n) =
в "координатной" форме
Lx(xn,n) + Lxx(xn,n)(xn+1 xn) + Lx(xn,n)(n+1 n) = ,
L(xn,n) + Lx(xn,n)(xn+1 xn) + L(xn,n)(n+1 n) = .
Остается подставить в эти уравнения явные выражения производных функции Лагранжа (учитывая, в частности, что L(xn,n) = ):
f 0(xn)+ [f (xn)]*n + (f 0(xn)+
nif i(xn)) (xn+1 xn) +[f (xn)]*(n+1 n) = ,f(xn) + f (xn)(xn+1 xn) = и мы получаем m+k линейных уравнений для нахождения m+k неизвестных (xn+1, n+1).
Описанный метод обладает всеми достоинствами и всеми недостатками метода Ньютона решения безусловных задач, в частности, он лишь локально сходится и требует большого объема вычислений. Поэтому попытаемся модифицировать градиентный метод, приспособив его к решению условной задачи (3.1)–(3.2). Поскольку, как сказано выше, точка (x*, *) - это седловая точкафункции Лагранжа, то естественно пытаться с помощью градиентного метода минимизировать ее по x, одновременно максимизируя ее по :
xn+1 = xn Lx(xn,n), n+1 = n + L(xn,n),
или, что то же xn+1 = xn (f 0(xn)+ [f (xn)]*n), n+1 = n + f(xn).
Можно доказать, что этот метод (его обычно называют методом Эрроу — Гурвица) при естественных ограничениях на гладкость и при условии положительной определенности оператора Lxx(x*,*) локальнолинейно сходится.
Описанные методы относятся к разряду двойственных методов, поскольку в итерационном процессе участвуют как прямые (x), так и двойственные () переменные.
Можно строить также прямые методы решения условных задач. Например, реализовать идею о том, что следующее приближение градиентного метода. Приближение xn+1 ищется как минимум функции x (f 0(xn),x xn) + ||x xn||2 на касательной гиперплоскости xn. Здесь "штрафной член" ||x xn||2 позволяет "минимизировать" линейную функцию x (f 0(xn),x xn). Таким образом, мы приходим к прямому методу
xn+1 = argmin [(f 0(xn),x xn) + ||x xn||2], (3.4)
fi(xn) + (f i(xn),x xn) = 0, i = 1, ..., k. (3.5)
Ограничения (3.5) в этом методе — это, очевидно, линеаризации ограничений (3.2) в точке xn: минимум ищется на касательной гиперплоскости xn.
Один из распространенных методов решения задач с ограничениями, с которым мы еще столкнемся — так называемый метод штрафов. Он позволяет сводить задачу с ограничениями к задаче без ограничений и суть его заключается в наказании за невыполнение ограничений. Именно, вместо минимизации функции f0 с ограничениями (3.2) минимизируется функция fs(x) = f0(x) + s||f(x)||2 без ограничений, в которой s — положительный параметр.
Теперь рассмотрим постановку задач с ограничениями типа неравенств gj(x) 0, j = 1, ..., l (6).
Рис. 3.2
Как и в предыдущем параграфе определяются допустимые точки, локальный и глобальный, строгий и нестрогий минимумы. Так же мы будем использовать обозначения f и g для функций из Rm в Rk и Rl, соответственно, определяемые координатами fi и gj. Поэтому задачу (3.1)- (3.3), (3.6) можно записывать в виде
f(x) = , g(x) .
(напомним, что неравенство g(x) означает покоординатные неравенства).
f0(x) min, f(x) = , g(x) .
Через J(x) будет обозначаться множество индексов так называемых активных ограничений: J(x) = {j {1, ..., l}: gj(x) = 0} — это номера ограничений, которые в данной точке существенны.
Теорема (обобщенное правило множителей Лагранжа).
Пусть f0, f, g C1, а x* — локальное решение задачи f0(x) min, f(x) = , g(x) . Тогда найдутся такие *0 R, * Rk, * Rl, не равные одновременно нулю, такие, что *j 0 при j J(x*) и
*0 f 0(x*)+ *i f i(x*)+ 
*j gj(x*) = . (3.7)
Регулярный случай.
Так же, как и в случае ограничений-равенств, в случае общей задачи нелинейной оптимизации, необходимый признак, информативен только в случае, если *0 0. В этой ситуации, так же как и в предыдущем параграфе можно разделить (3.7) на *0 и, следовательно, считать его равным единице. Это позволяет ввести функцию Лагранжа L: Rm×Rk×Rk R (в регулярном случае) равенством
(x, , ) = f0(x) + (, f(x)) + (, g(x)).
Условие регулярности в случае общей задачи выглядит сложнее. Именно, допустимая точка x называется регулярной, если векторы f 1(x),..., f k(x) линейно независимы и для некоторого ненулевого вектора
hRm (f i(x),h) = 0 при i = 1, ..., kи (gj(x),h) < 0 при j J(x).
Геометрически, эти условия означают, что, во-первых, вектор h является касательным к многообразию, выделяемому ограничениями-равенствами (т. е. ортогонален всем градиентам f i(x)),и, во-вторых, он образует с градиентами gj(x)активных ограничений (указывающими, очевидно, вовне множества ) тупой угол
Рис. 3.3
3.1 Методы возможных направлений
Эти методы основываются на следующем простом понятии. Вектор (направление) z в допустимой точке x назовем возможным, если малое перемещение в этом направлении уменьшает значение функции f0 и не выводит из множества допустимых точек, т. е. если при достаточно малых s точка xs = x + sz допустима и f(xs) < f(x). Если теперь на каждом шаге сдвигаться в возможном направлении на достаточно малое расстояние, то мы очевидно получим релаксационную последовательность, которая во многих случаях будет сходиться к решению задачи. Методы этого типа называются методами возможных направлений.
3.2 Методы проекции градиента
Проекцией Px точки x Rm на множество Rm называется любая ближайшая к x точка множества :
||x Px|| ||x y|| при всех y .
В тех случаях, когда проекцию точки на множество допустимых точек найти достаточно легко (например, когда — линейное подпространство, полупространство, шар, Rm и т. д.) используют метод проекции градиента:
xn+1 = P(xn nf 0(xn))
(см. рис. 3.3) являющийся прямым обобщением градиентного метода
Рис. 3.4
Можно доказать, например, что если функция f0 C1сильно выпукла и f удовлетворяет условию Липшица, а множество замкнуто и ограничено, то метод проекции градиента сходится со скоростью геометрической прогрессии.
3.3 Методы линеаризации
Суть этих методов, как следует из названия, состоит в линеаризации минимизируемой функции и ограничений в очередной точке xn строящейся релаксационной последовательности и объявлении следующим значением xn+1 решения получающейся линейной задачи, т. е. задачи
(f 0(xn),x xn) min, (3.8)
gi(xn) + (gi(xn),x xn) 0,i = 1, ..., l. (3.9)
Чтобы эта (линейная) задача была разрешима либо добавляют штраф в минимизируемую функцию, заменяя (3.8), например, задачей
(f 0(xn), x xn) + ||x xn||2 min,
либо добавляя к (20) простые ограничения, которые делают множество допустимых точек этой задачи ограниченным, например, (линейные) ограничения
xi xni n 0, xi + xni n 0 (i = 1, ..., m).
3.4 Методы штрафов
Основная идея здесь заключается в переходе от задачи (1), (3) к задаче безусловной оптимизации, в которой "наказывается" либо удаление от множества допустимых точек (внешний штраф), либо приближение изнутри множества к его границе (внутренний штраф). Различают методы внешних штрафов и внешних штрафов. При методе внешних штрафов задачу решают тем или иным методом решения безусловных задач, увеличивая на каждом шаге штраф s. Как и в случае задач с ограничениями-равенствами, основным недостатком метода штрафов является рост числа обусловленности s. На несколько другой идее основываются так называемые методы внутренних штрафов или барьеров. Образно его можно описать так: у границы множества возводятся барьеры, не позволяющие приближаться к его границе.