ВОЗМОЖНЫХ НАПРАВЛЕНИЙ МЕТОД
— метод численного решения задачи программирования выпуклого, основанный на построении последовательности точек, каждая из которых получается из предыдущей путем сдвига вдоль направления, не выводящего за пределы допустимой области, и вдоль которого минимизируемая функция убывает.
Пусть задача выпуклого программирования приведена к такому виду: минимизировать 
при ограничениях
где 
— выпуклые дифференцируемые ф-ции, 
вектор. Кроме того, предполагается, что существует точка у такая, что 
. Для каждого 
обозначим через 
мн-во тех индексов I, для которых — 
. Пусть точка 
удовлетворяющая условиям (1), уже построена и имеется 
. Шаг алгоритма, т. е. переход от точки 
производим по следующим правилам.
1) Решаем задачу программирования линейного — минимизировать 
при ограничениях;
где 
— 
-мерный вектор, 
градиент ф-ции 
в точке 
Обозначим решение этой задачи соответственно через 
2) Различают три случая в зависимости от соотношения 
а) 
полагаем 
б) 
полагаем 
в) 
решаем задачу минимизации 
при ограничениях:
Пусть 
— решение этой задачи. Если в результате решения получим 
то точка 
решение исходной задачи. Если 
то 
, а в качестве 
берем вектор 
.
3) Полагаем 
, где 
наибольшее значение t, при котором удовлетворены все неравенства
На этом шаг алгоритма закончен. Точка 
берется за начальную и все повторяется.
Для начала процесса необходимо найти точку 
удовлетворяющую ограничениям (1).
Для этого В. н. м. решается вспомогательная задача: минимизировать 
при ограничениях 
Применение конечного числа шагов В. н. м. к этой задаче, для которой уже легко найти начальную точку, приводит к нахождению точки, удовлетворяющей условию (1). Доказано, что В. н. м. порождает последовательность, все предельные точки которой являются решением задачи выпуклого программирования.
Б. Н. Пшеничный.
