Выбор наилучшего подходящего направления
Ограничение 
называется активным в фиксированной точке 
, если 
.
Шаг 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, то в качестве длины шага берётся 
.
Типовой пример
Решить задачу выпуклого программирования
где f0(X)=x12+x22-10x1-6x2+34;
f1(X)=x12-4x1-x2+4;
f2(X)=-x1+2x2-1.
Выполним одну итерацию рассмотренного метода возможных направлений. В качестве начального приближения выберем точку Х0=(3;2).
Определим индексные множества активных ограничений в точке Х0
I(X0)={i 
I: fi(X0)=0}={1}; I+(X0)={i: xi=ci}=0; I-(X0)={i: xi=0}={2}.
Поставим задачу выбора наилучшего подходящего направления S0 в точке Х0 как задачу линейного программирования с нормализацией №3:
.
Здесь S=(s1,s2)-искомый вектор; 
-вспомогательная переменная; 
-градиенты соответствующих функций в точке Х0,то есть векторы
; 
.
Итак, получили задачу в виде
Решим её симплекс-методом. Вначале, для приведения задачи к канонической форме, введём дополнительные переменные и выполним замену s1=1-y1; s2=1-y2; =y3-y4.
Тогда, задача запишется так:
.
Дальнейший процесс решения приведён в таблице 3.1.
Таблица №3.1
| N | C | P | B | A1 | A2 | A3 | A4 | A5 | A6 | t |
| A5 | -1 | |||||||||
| A6 | -1 | |||||||||
| -1 | ||||||||||
| A5 | -1 | |||||||||
| A3 | -1 | |||||||||
Таким образом, в результате решения задачи выбора подходящего направления в точке Х0=(2;0) найден вектор S0=(1;1). Построим луч, исходящий из точки Х0 по направлению вектора S0
Определим длину шага 
в этом направлении. Для этого найдём вначале то значение 
, при котором луч 
пересекает границу допустимой области R.То есть найдём положительные корни уравнений
.
А именно,уравнений 
.
Таким образом, величина 
. Далее, определим значение 
, при котором функция 
достигает минимума по . Для этого приравняем к нулю производную её по и найдём корень полученного уравнения
.
Отсюда получим 
. Следовательно, искомое значение 
.
Итак, найдена новая точка 
. Итерация завершена.