Комбинированный метод штрафных функций

Вернемся к рассмотрению задачи условной оптимизации (3.1) со смешанными ограничениями. Данный метод является обобщением методов, изученных в предыдущих пунктах 3.1.1 и 3.1.2. А именно, для учета ограничений типа равенств применяют штрафные функции (как в методе внешней точки), дляограничений типа неравенств – барьерные функции.

Таким образом, в основе комбинированного метода лежит сведение исходной задачи условной минимизации (3.1) к последовательности задач без ограничений вида

,

где присоединенная функция имеет вид

(3.9)

Начальная точка задается внутри допустимой области R, то есть при строгом выполнении ограничений типа неравенств , s=1,...,p. На каждом k-том этапе точка минимума расширенной функции ищется при заданном значении r_k с помощью одного из методов безусловной минимизации. Полученная точка используется в качетве начальной на следующем этапе, выполняемом при уменьшающемся значении параметра r_k. При последовательность точек стремится к точному решению X^* исходной задачи.

Типовой пример

Найти минимум функции f(X)=(x₁-2)²+(x₂-1)² при смещанных ограничениях h(X)=x₁-2x₂+1=0; g(X)=-0,25x₁²-x₂²+1³0.

Воспользуемся комбинированным методом штрафных функций.

Построим расширенную функцию: ;

Минимизацию F(X,r) выполним градиентным методом в соответствии с которым направление спуска выбирается по антиградиенту . Тогда минимизирующая последовательность построится по рекуррентной формуле

, k=0,1,2,...

Для этого на каждом шаге нам понадобятся значения функций:

;

;

Следуя методу градиентного спуска, координаты (k+1)-й точки X^k+1 будут вычисляться так:

; .

В качестве исходной точки выберем X⁰=(0,5;0,5). Результаты решения последовательности задач при увеличивающемся значении r, начиная с r=1, приведены в таблице

N	r			f(X*(r))	h(X*(r))	g(X*(r))
		0,500	0,500	2,500	0,500	0,680
		0,872	0,841	1,298	0,190	0,210
		0,846	0,885	1,345	0,076	0,038
		0,838	0,904	1,359	0,030	0,007
Точное решение	0,823	0,911	1,393

Задание для лабораторной работы

Решить задачи условной оптимизации со смешанными ограничениями:

1. Найти минимум функции f(X)=x₁²+x₂²-4x₁-2x₂+5 при ограничениях h(X)=-x₁+2x₂=1; g(X) = -0,25x₁²-x₂²³1;

2. Найти минимум функции f(X)=x₁²+x₂²-16x₁-10x₂+89 при ограничениях h(X)=2x₁²-12x₁+9x₂-27=0; g(X) = -5x₁²+16x₂+80³0;

3. Найти минимум функции f(X)=x₁²+x₂²-14x₁-4x₂+53 при ограничениях h(X)=2x₁²+25x₂ – 125=0; g(X) = -x₁²+2x₁+4x₂-3³0;

4. Найти минимум функции f(X)=x₁²+9x₂²-10x₁-18x₂+34 при ограничениях h(X)=x₁+x₂ – 5=0; g(X) = -0,5x₁²+x₂ - 4.5³0;

5. Найти минимум функции f(X)=x₁²+4x₂²-10x₁ -16x₂+41 при ограничениях h(X)=x₁²-4x₁+x₂ -1=0; g(X)=-x₁²+4x₁+3x₂ -3³0;

6. Найти минимум функции f(X)=x12+4x22-8x1-16x2+32 при ограничениях h(X)=-x1+x2 -1=0; g(X)=-2x12+4x1+x2-1³0;

7. Найти минимум функции f(X)=x₁²+9x₂²-10x₁-36x₂+61 при ограничениях h(X)=x₁²-4x₁+4x₂- 12=0; g(X)=-3x₁²+7x₂ + 27³0;

МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ

Постановка задачи выпуклого программирования

Рассмотрим задачу выпуклого программирования (ЗВП)

(3.10)

Введем обозначения

(3.11)

Тогда задачу (3.10) можно записать следующим образом

(3.13)