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

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

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)= ,

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

то есть D₁>0, D₂>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)= , D₁=4+r_s>0, D₂=(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