3.5. Понятие о методах штрафных функций

Часто бывает удобным вместо исходной задачи условной оптимизации решить задачу безусловной оптимизации, полученной из исходной путём введения в рассмотрение вспомогательной функции. К числу методов, использующих такой подход, относятся методы штрафных функций. Эти методы мы рассмотрим на примере метода штрафов (внутренних штрафов), применённой к задаче условной минимизации:

f(X)  min

(3.5.1)

А именно, вместо задачи (3.5.1) рассмотрим задачу безусловной минимизации

F(X, r_s)=f(X)+P(X, r_s)  min, (3.5.2)

где

P(X, r_s)= ,

=max{0, }= ,

r_s  так называемый параметр штрафа. Функция P(X, r_s) называется штрафной функцией.

3.5.1. Пусть X^*  локально единственное решение задачи (3.5.1) (то есть существует окрестность точки X^*, в которой X^* является единственным решением задачи), функции f(X) и непрерывно дифференцируемы в окрестности точки X^*. Тогда для достаточно больших r_s найдётся точка X^*(r_s) локального минимума функции F(X, r_s) в окрестности X^* и X^*(r_s)=X^*.

Таким образом, для решения задачи (3.5.1) достаточно:

1. Составить функцию F(X, r_s)=f(X)+P(X, r_s).

2. Найти частные производные , j=1, 2, …, n.

3. Решить систему =0, j=1, 2, …, n. Пусть X^*(r_s)  её решение.

4. Исследовать на знакоопределённость матрицу Гессе H(X^*(r_s), r_s) функции F(X, r_s), и если достаточное условие минимума выполняется, то выполняем остальные пункты:

5. Найти пределы x_j(r_s)= . Тогда X^*=( , , …, )  решение задачи (3.5.1).

6. Найти значения функции f(X) в точках X^* локального минимума.

Пример I. Исследовать на условный экстремум функцию:

f(X)=  min

3x₁2x₂5=0.

Решение. 1. Составим функцию F(X, r_s):

F(X, r_s)= + (3x₁2x₂5)².

2. Найдём частные производные , :

=4x₁+3r_s(3x₁2x₂5), =8x₂2r_s(3x₁2x₂5)

3. Решаем систему =0, j=1, 2:



Первое уравнение, умноженное на 2, прибавим ко второму, умноженному на 3: 8x₁+24x₂=0, откуда получаем x₁=3x₂. Теперь подставляем это выражение для x₁, например, в первое уравнение системы: 12x₂33r_sx₂15r_s=0, откуда x₂(r_s)= и x₁(r_s)=3 = .

4. Исследуем на знакоопределённость матрицу Гессе H(X^*(r_s), r_s) функции F(X, r_s). Имеем

=4+9r_s, =8+4r_s, = =6r_s, H(X^*(r_s), r_s)= ,

₁=4+9r_s>0, ₂=(4+9r_s)(8+4r_s)+(6r_s)²=88+72r_s>0,

то есть ₁>0, ₂>0, и матрица Гессе H(X, r_s)=  положительно определённая. Это означает, что достаточные условного минимума выполнены.

5. Найдём пределы x_j(r_s)= , j=1, 2. Имеем

x₁(r_s)= = , x₂(r_s)= = .

Поэтому X^*=( ,  )  решение задачи.

6. Найдём значения функции f(X) в точке X^*=( ,  ) локального минимума: f_min(X)=f(X^*)=2 +4 = = .

Ответ: X=( ,  )  точка условного локального минимума, f_min(X)= .

Пример II. Исследовать на условный экстремум функцию:

f(X)=  min

Решение. 1. Составим функцию F(X, r_s):

F(X, r_s)= + =

=

2. Найдём частные производные , :

=

=

3. Решаем систему =0, j=1, 2:

Случай 1. . Тогда



Первое уравнение, умноженное на 2, прибавляем ко второму, умноженному на 3: 8x₁+24x₂+r_s(x₁1)=0, откуда получаем x₂= x₁ . Теперь подставляем это выражение для x₂, например, в первое уравнение системы, последовательно получим:

, 

  ,

откуда x₁(r_s)= и

x₂= x₁ = = + =

 + = ,

то есть x₂(r_s)= .

При этом имеем

3 2 5= .

Это выражение отрицательно, что вступает в противоречие с условием . Значит, этот случай невозможен.

Случай 2. . Тогда



откуда x₂(r_s)=0 и x₁(r_s)= .

4. Исследуем на знакоопределённость матрицу Гессе H(X^*(r_s), r_s) функции F(X, r_s). Имеем

=4+r_s, =8, = =0,

H(X^*(r_s), r_s)= , ₁=4+r_s>0, ₂=(4+r_s)8>0,

и матрица Гессе H(X^*(r_s), r_s)=  положительно определённая. Это означает, что достаточные условного минимума выполнены.

5. Найдём пределы x_j(r_s)= , j=1, 2. Имеем

x₁(r_s)= =1, x₂(r_s)= 0=0.

Поэтому X^*=(1, 0)  решение задачи.

6. Найдём значения функции f(X) в точке X^*=(1, 0) локального минимума: f_min(X)=f(X^*)=2 +40²=2.

Ответ: X=(1, 0)  точка условного локального минимума, f_min(X)=2.

Пример III. Исследовать на условный экстремум функцию:

f(X)=  min

Решение. 1. Составим функцию F(X, r_s):

F(X, r_s)= + ,

где

=

=

так что функция F(X, r_s) зависит от того, отрицательны или неотрицательны функции и . Поэтому рассмотрим отдельно четыре случая

Случай 1. 0 и 0. Тогда

F(X, r_s)= , = , = ,

 

Но это противоречит условию 0  x₁1.

Случай 2. 0 и >0. Тогда

F(X, r_s)= + ,

= , = ,



откуда x₁(r_s)= и x₂(r_s)= (см. решение Примера I). Но при этом имеем

=3 2 5= <0,

то есть <0  противоречие с условием случая.

Случай 3. >0 и 0. Тогда

F(X, r_s)= + , = , = ,



откуда x₂(r_s)=0 и x₁(r_s)= . При этом оба неравенства выполняются:

(r_s)=1 = >0,

=3 205= .

Как мы уже видели, (см. решение Примера II), X^*=(1, 0)  точка локального минимума: f_min(X)=f(X^*)=2.

Случай 4. >0 и >0. Тогда

F(X, r_s)= + ,

= , = ,



откуда x₁(r_s)= и x₂(r_s)= (см. решение Примера II). Но мы уже видели (см. там же), что тогда , что противоречит условию случая.

Ответ: X=(1, 0)  точка условного локального минимума, f_min(X)=2.

3.6. Упражнения. Исследовать функции на условный экстремум:

1) а)  extr б)  extr

; ;

в)  extr

x₁+x₂+6=0.

2) а)  extr б)  extr

в)  extr г)  extr

3) а)  extr б)  extr

4) а)  extr б)  extr