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

f(x) = Q, g(x) £ Q.

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

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

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

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

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

l*₀ f¢₀ (x*)+ l*_i f¢_i (x*)+ m*_j g¢_j (x*) = Q. (3.7)

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

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

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

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

hÎR^m (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.

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

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

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

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

||x  P_W x|| £ ||x  y|| при всех y Î W.

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

x^{n +1} = P_W (xⁿ  aⁿ f¢₀ (xⁿ ))

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

Рис. 3.4.

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

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

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

(f ¢₀ (xⁿ ),x  xⁿ ) ® min, (3.8)

g_i (xⁿ ) + (g¢_i (xⁿ ),x  xⁿ ) £ 0, i = 1, ..., l. (3.9)

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