Выбор наилучшего подходящего направления

Ограничение называется активным в фиксированной точке , если .

Шаг 1. Введем в рассмотрение множества индексов активных ограничений в точке :

-индексное множество активных нелинейных ограничений;

-индексное множество активных линейных ограничений;

.

Шаг 2. Введем в рассмотрение множество n-мерных векторов в точке и построим множество

Очевидно, что множество представляет собой множество возмо-жных направлений в точке ,т.е направлений не выводящих за пределы допустимой области.

Если -внутренняя точка множества R, то пусто, т.е. нет активных ограничений и на выбор вектора s не накладывается никаких ограничений.

Шаг 3. Введем искусственную переменную и определим множество (n+1)-мерных векторов с компонентами :

.

Задачу выбора подходящего направления сформулируем как задачу линейного программирования:

(3.17)

Очевидно, что при множества и совпадают. Если , то из ограничения следует, что и направление s будет подходящим. В этом случае , т.е. s не направлено по касательной к нелинейным границам. При этом, чем больше , тем больше отличается от нуля , т.е. тем больший угол образуется между s и внешней нормалью . Если , то точка оказывается точкой минимума функции . Это доказывается следующей теоремой.

Теорема 3. Точка является точкой минимума функции на множестве R, регулярном по Слейтеру, тогда и только тогда, когда для всех , удовлетворяющих неравенству .

Пусть

Система ограничений запишется в виде:

Когда речь идёт о выборе направления, нас интересует направление, которое задаётся некоторым вектором произвольной длины, но при решении ЗЛП (3.17) может оказаться неограниченной. Поэтому возникает необходимость наложить на длину S некоторые ограничения, которые называются нормализациями. Известны такие нормализации:

№1. .

№2.

№3.

№4. .

Определение длины шага

Пусть в точке определено наилучшее подходящее направление . Выберем теперь длину шага в этом направлении, т.е. найдём такое число , при котором принимает по в допустимой области минимальное значение

Эту задачу удобно решать в два этапа:

Шаг 1. Определить значение _.

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

Шаг 2. Выбираем число .

Минимум может достигаться вне области R, тогда в качестве длины шага выбираем . Если же минимум достигается в R, то в качестве длины шага берётся .

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

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

где f₀(X)=x₁²+x₂²-10x₁-6x₂+34;

f₁(X)=x₁²-4x₁-x₂+4;

f₂(X)=-x₁+2x₂-1.

Выполним одну итерацию рассмотренного метода возможных направлений. В качестве начального приближения выберем точку Х⁰=(3;2).

Определим индексные множества активных ограничений в точке Х⁰

I(X⁰)={i I: f_i(X⁰)=0}={1}; I₊(X⁰)={i: x_i=c_i}=0; I_-(X⁰)={i: x_i=0}={2}.

Поставим задачу выбора наилучшего подходящего направления S⁰ в точке Х⁰ как задачу линейного программирования с нормализацией №3:

.

Здесь S=(s₁,s₂)-искомый вектор; -вспомогательная переменная; -градиенты соответствующих функций в точке Х⁰,то есть векторы

; .

Итак, получили задачу в виде

Решим её симплекс-методом. Вначале, для приведения задачи к канонической форме, введём дополнительные переменные и выполним замену s₁=1-y₁; s₂=1-y₂; =y₃-y₄.

Тогда, задача запишется так:

.

Дальнейший процесс решения приведён в таблице 3.1.

Таблица №3.1

N	C	P	B	A1	A2	A3	A4	A5	A6	t
		A5					-1
		A6					-1
						-1
		A5							-1
		A3					-1

Таким образом, в результате решения задачи выбора подходящего направления в точке Х⁰=(2;0) найден вектор S⁰=(1;1). Построим луч, исходящий из точки Х⁰ по направлению вектора S⁰

Определим длину шага в этом направлении. Для этого найдём вначале то значение , при котором луч пересекает границу допустимой области R.То есть найдём положительные корни уравнений

.

А именно,уравнений .

Таким образом, величина . Далее, определим значение , при котором функция достигает минимума по . Для этого приравняем к нулю производную её по и найдём корень полученного уравнения

.

Отсюда получим . Следовательно, искомое значение .

Итак, найдена новая точка . Итерация завершена.