Анализ методов определения минимального, максимального значения функции без ограничения

 

Определяем величину шага:

Находим :

 

 

Получили новую точку с координатами

Проверка:

 

 

 

И так далее до выполнения условий точности вычисления экстремума функции:

 

 

2.2 Метод сопряженных направлений

 

Рассматриваемый метод является градиентным методом второго порядка. Назовем некоторые направления . Эти направления называются сопряженными по отношению к некоторой положительно определенной матрице Гессе (Н), если выполняется соотношение:

 

 (2.6)

 

При единичной матрице Гессе сопряженность направлений означает их ограниченность:

 

 

 

 

 

 

 

Рис. 2.1

 

Дана функция:

 

 

с начальной точкой . - точка безусловного экстремума.

1) Найдем градиент функции в  точке  :

 

 

Выберем

 

,

 

где , имеем .

1) Из начальной точки мы должны шагнуть по направлению . Для этого найдем оптимальный шаг по формуле:

 

 

Находим координаты с помощью величины шага:

 

 

Получили новую точку с координатами

2) Примем точку за начальную. Определяем:

 

 

Найдем координаты сопряженного вектора :

, тогда имеем: ;

, пусть  , тогда

Найдем оптимальный шаг:

 

 

Находим координаты с помощью величины шага:

 

 

Получили новую точку с координатами - точка минимума.

Значение функции в этой точке равно .

 

 

3. Анализ методов определения минимального, максимального значения функции при наличии ограничений

 

Напомним, что общая задача условной оптимизации выглядит так

f(x) ® min, x Î W,

где W — собственное подмножество Rm. Подкласс задач с ограничениями типа равенств выделяется тем, что множество W задается ограничениями вида

 

fi(x) = 0,

 

где fi: Rm ®R (i = 1, ..., k).

Таким образом, W = {x Î Rm: fi(x) = 0, i = 1, ..., k}.

Нам будет удобно писать у функции f индекс "0". Таким образом, задача оптимизации с ограничениями типа равенств записывается в виде:

 

f0(x) ® min, (3.1)

fi(x) = 0, i = 1, ..., k. (3.2)

 

Если обозначить теперь через f функцию на Rm со значениями в Rk, координатная запись которой имеет вид f(x) = (f1(x), ..., fk(x)), то (3.1)–(3.2) можно также записать в виде f0(x) ® min, f(x) = Q.

Геометрически задача с ограничениями типа равенств — это задача о поиске наинизшей точки графика функции f0 над многообразием W (см. рис. 3.1).

 

 

Рис. 3.1

 

Точки, удовлетворяющие всем ограничениям (т. е. точки множества W), обычно называют допустимыми. Допустимая точка x* называется условным минимумом функции f0 при ограничениях fi(x) = 0, i = 1, ..., k (или решением задачи (1)–(2)), если при всех допустимых точках x f0(x*) £ f0(x). (3.3)

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

Правило множителей Лагранжа.

Описываемый ниже необходимый признак локального условного минимума был сформулирован Лагранжем. Определим F: Rm ® Rk+1, положив F(x) = (f0(x), f1(x), ..., fk(x)). Заданная на Rm×Rk+1 скалярная функция Лагранжа M по определению принимает значения в R и задается равенством

 

M(x, m) = (m, F(x)) =  mi fi(x) (x Î Rm, m Î Rk+1).

 

Координаты вектора m, т. е. числа m0, m1, ..., mk называются множителями Лагранжа или двойственными переменными. Оказывается, имеет место следующая теорема, часто именуемая правилом множителей Лагранжа:

Теорема. Пусть F Î C1 и x* — локальный условный минимум функции f0 при ограничениях fi(x) = 0 (i = 1, ..., k). Тогда найдется ненулевой вектор m* такой, что x* является стационарной точкой функции x® M(x, m*):

 

M¢x(x, m*)|x=x*= m*i f ¢i(x*)= Q

 

Правило множителей Лагранжа доставляет необходимое условие локального условного минимума и поэтому позволяет искать точки, "подозрительные" на экстремум. В самом деле, для нахождения точки (x*, m*) Î Rm+k+1, т. е. для нахождения m + k + 1 неизвестных, мы имеем m + k уравнений

 

f(x) = Q, M¢x(x, l)= Q.

 

Поскольку, очевидно, множители Лагранжа можно искать с точностью до постоянного множителя, то в общей ситуации этих уравнений хватает для отыскания x*.

Регулярные точки.

Допустимая точка x задачи (3.1)–(3.2) называется регулярной, если векторы {f ¢i(x)}ki=1линейно независимы. Оказывается, что если x* — регулярная точка минимума, то в векторе m* можно считать m*0 ненулевым, а поскольку множители Лагранжа определяются с точностью до множителя, можно считать, что m*0 = 1. Чтобы сформулировать это утверждение более точно, введем следующие обозначения. Пусть l Î Rk, а функция Лагранжа в регулярном случае определяется равенством

 

L(x, l) = f0(x) + (l, f(x)) = f0(x) +  li fi(x) (x Î Rm, l Î Rk).

 

Очевидно, L(x, l) = M(x, m), где m = (1, l).

Теорема (правило множителей Лагранжа в регулярном случае).

Пусть F Î C1, а x* — регулярное локальное решение задачи (3.1)–(3.2). Тогда найдется ненулевой вектор l* Î Rk такой, что

L¢x(x*, l*)= Q.

Одно достаточное условие локального минимума.

Говорят, что линейный оператор A положительно определен на подпространстве E, если (Ax, x) > 0 при всех x Î E. Касательным подпространством к многообразию W в точке y называется множество TWy = {x Î Rm: (f ¢(y), x) = 0, i = 1, ..., k}. Касательной гиперплоскостью к многообразию W в точке y называется множество

 

W¢y = {x Î Rm: fi(y) + (f ¢(y), x-y) = 0, i = 1, ..., k}.

 

Теорема (достаточное условие минимума).

Пусть F Î C2, а x* — регулярная стационарная точка функции Лагранжа, т. е., в частности, L¢(x*, l*) = Q при некотором ненулевом l* Î Rk. Тогда, если Lxx¢¢(x*, l*)положительно определен на TWx*, то точка x* является локальным решением задачи (3.1)–(3.2).

Методы решения задач с ограничениями типа равенств.

Мы будем рассматривать ниже только регулярный случай. Один из естественных подходов к решению задач типа (3.1)–(3.2) основывается на необходимом условии экстремума — правиле множителей Лагранжа. Если бы можно было утверждать, что решению x* задачи (3.1)–(3.2) соответствует экстремум (x*, l*) функции Лагранжа L, то к функции L можно было бы применять разработанные методы решения безусловных задач. Однако, так утверждать нельзя. В самом деле, если в точке x ограничения не выполняются, то за счет выбора l функцию L (поскольку по l она линейна) можно сделать как сколь угодно большой положительной, так и сколь угодно большой отрицательной. Поэтому естественно искать решение x* как первые m координат стационарной точки функции Лагранжа, например, методом Ньютона, мы приходим к методу Ньютона решения задач с ограничениями типа равенств — это просто метод Ньютона решения уравнения L¢(x, l) = Q (в регулярном случае):

 

L¢(xn, ln) + L¢¢(xn, ln)(xn+1 - xn, ln+1 - ln) = Q

 

в "координатной" форме

 

L¢x(xn,ln) + L¢¢xx(xn,ln)(xn+1 - xn) + L¢¢xl(xn,ln)(ln+1 - ln) = Q,

L¢l(xn,ln) + L¢¢xl(xn,ln)(xn+1 - xn) + L¢¢ll(xn,ln)(ln+1 - ln) = Q.

 

Остается подставить в эти уравнения явные выражения производных функции Лагранжа (учитывая, в частности, что L¢¢ll(xn,ln) = Q):

 

f ¢0(xn)+ [f ¢(xn)]*ln + (f ¢¢0(xn)+ lnif ¢¢i(xn)) (xn+1 - xn) + [f ¢(xn)]*(ln+1 - ln) = Q,f(xn) + f ¢(xn)(xn+1 - xn) = Q

 

и мы получаем m+k линейных уравнений для нахождения m+k неизвестных (xn+1, ln+1).

Описанный метод обладает всеми достоинствами и всеми недостатками метода Ньютона решения безусловных задач, в частности, он лишь локально сходится и требует большого объема вычислений. Поэтому попытаемся модифицировать градиентный метод, приспособив его к решению условной задачи (3.1)–(3.2). Поскольку, как сказано выше, точка (x*, l*) - это седловая точка функции Лагранжа, то естественно пытаться с помощью градиентного метода минимизировать ее по x, одновременно максимизируя ее по l:

 

xn+1 = xn - aL¢x(xn,ln), ln+1 = ln + aL¢l(xn,ln),

или, что то же xn+1 = xn - a(f ¢0(xn)+ [f ¢(xn)]*ln), ln+1 = ln + af(xn).

 

Можно доказать, что этот метод (его обычно называют методом Эрроу — Гурвица) при естественных ограничениях на гладкость и при условии положительной определенности оператора L¢¢xx(x*,l*) локально линейно сходится.

Описанные методы относятся к разряду двойственных методов, поскольку в итерационном процессе участвуют как прямые (x), так и двойственные (l) переменные.

Можно строить также прямые методы решения условных задач. Например, реализовать идею о том, что следующее приближение градиентного метода. Приближение xn+1 ищется как минимум функции x ® (f ¢0(xn),x - xn) + a||x - xn||2 на касательной гиперплоскости W¢xn. Здесь "штрафной член" a||x - xn||2 позволяет "минимизировать" линейную функцию x ® (f ¢0(xn),x - xn). Таким образом, мы приходим к прямому методу

 

xn+1 = argmin [(f ¢0(xn),x - xn) + a||x - xn||2], (3.4)

fi(xn) + (f ¢i(xn),x - xn) = 0, i = 1, ..., k. (3.5)

 

Ограничения (3.5) в этом методе — это, очевидно, линеаризации ограничений (3.2) в точке xn: минимум ищется на касательной гиперплоскости W¢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) = Q, g(x) £ Q.

 

(напомним, что неравенство g(x) £ Q означает покоординатные неравенства).

 

f0(x) ® min, f(x) = Q, g(x) £ Q.

 

Через J(x) будет обозначаться множество индексов так называемых активных ограничений: J(x) = {j Î {1, ..., l}: gj(x) = 0} — это номера ограничений, которые в данной точке существенны.

Теорема (обобщенное правило множителей Лагранжа).

Пусть f0, f, g Î C1, а x* — локальное решение задачи f0(x) ® min, f(x) = Q, g(x) £ Q. Тогда найдутся такие l*0 Î R, l* Î Rk, m* Î Rl, не равные одновременно нулю, такие, что m*j ³ 0 при j Î J(x*) и

 

l*0 f ¢0(x*)+  l*i f ¢i(x*)+ m*j g¢j(x*) = Q. (3.7)

 

Регулярный случай.

Так же, как и в случае ограничений-равенств, в случае общей задачи нелинейной оптимизации, необходимый признак, информативен только в случае, если l*0¹ 0. В этой ситуации, так же как и в предыдущем параграфе можно разделить (3.7) на l*0 и, следовательно, считать его равным единице. Это позволяет ввести функцию Лагранжа L: Rm×Rk×Rk ® R (в регулярном случае) равенством

 

(x, l, m) = f0(x) + (l, f(x)) + (m, g(x)).

 

Условие регулярности в случае общей задачи выглядит сложнее. Именно, допустимая точка x называется регулярной, если векторы f ¢1(x),..., f ¢k(x) линейно независимы и для некоторого ненулевого вектора

 

hÎRm (f ¢i(x),h) = 0 при i = 1, ..., k и (g¢j(x),h) < 0 при j Î J(x).

 

Геометрически, эти условия означают, что, во-первых, вектор h является касательным к многообразию, выделяемому ограничениями-равенствами (т. е. ортогонален всем градиентам f ¢i(x)),и, во-вторых, он образует с градиентами g¢j(x)активных ограничений (указывающими, очевидно, вовне множества W) тупой угол

 

Рис. 3.3

 

3.1 Методы возможных направлений

 

Эти методы основываются на следующем простом понятии. Вектор (направление) z в допустимой точке x назовем возможным, если малое перемещение в этом направлении уменьшает значение функции f0 и не выводит из множества допустимых точек, т. е. если при достаточно малых s точка xs = x + sz допустима и f(xs) < f(x). Если теперь на каждом шаге сдвигаться в возможном направлении на достаточно малое расстояние, то мы очевидно получим релаксационную последовательность, которая во многих случаях будет сходиться к решению задачи. Методы этого типа называются методами возможных направлений.

 

3.2 Методы проекции градиента

 

Проекцией PWx точки x Î Rm на множество W Ì Rm называется любая ближайшая к x точка множества W:

 

||x - PWx|| £ ||x - y|| при всех y Î W.

 

 

В тех случаях, когда проекцию точки на множество допустимых точек найти достаточно легко (например, когда W — линейное подпространство, полупространство, шар, Rm и т. д.) используют метод проекции градиента:

 

xn+1 = PW(xn - anf ¢0(xn))

 

(см. рис. 3.3) являющийся прямым обобщением градиентного метода

 

Рис. 3.4

 

Можно доказать, например, что если функция f0 Î C1 сильно выпукла и f ¢ удовлетворяет условию Липшица, а множество W замкнуто и ограничено, то метод проекции градиента сходится со скоростью геометрической прогрессии.

 

3.3 Методы линеаризации

 

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

 

(f ¢0(xn),x - xn) ® min, (3.8)

gi(xn) + (g¢i(xn),x - xn) £ 0, i = 1, ..., l. (3.9)

 

Чтобы эта (линейная) задача была разрешима либо добавляют штраф в минимизируемую функцию, заменяя (3.8), например, задачей

 

(f ¢0(xn), x- xn) + d||x - xn||2 ® min,

 

либо добавляя к (20) простые ограничения, которые делают множество допустимых точек этой задачи ограниченным, например, (линейные) ограничения

 

xi - xni- an £ 0, -xi + xni- an £ 0 (i = 1, ..., m).

 

3.4 Методы штрафов

 

Основная идея здесь заключается в переходе от задачи (1), (3) к задаче безусловной оптимизации, в которой "наказывается" либо удаление от множества W допустимых точек (внешний штраф), либо приближение изнутри множества W к его границе (внутренний штраф). Различают методы внешних штрафов и внешних штрафов. При методе внешних штрафов задачу решают тем или иным методом решения безусловных задач, увеличивая на каждом шаге штраф s. Как и в случае задач с ограничениями-равенствами, основным недостатком метода штрафов является рост числа обусловленности s. На несколько другой идее основываются так называемые методы внутренних штрафов или барьеров. Образно его можно описать так: у границы множества W возводятся барьеры, не позволяющие приближаться к его границе.

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

 

4. Нахождение экстремума функции при наличии ограничения

 

4.1 Метод симплексных процедур

 

Дана функция:

 

.