Метод проекций градиента для решения ЗЛП

[Karoed]

Общий вид задачи:
целевая функция
$ Cx \to extr $
ограничения
$ Ax \leqslant 0 $
Здесь
$ A $ - матрица размера $ (m \times n) $
$ C \in R^n $ - вектор коэффициентов целевой функции (строка)
$ x \in R^n $ - вектор переменных (столбец)
Хочется решить эту задачу методом проекции градиентов, кажется такая адаптация для ЗЛП называется методом Карамаркаре....
Сразу замечу, что речь не о симплекс методе, его экспоненциальная скорость сходимости меня не устроит.
Идея в том, чтобы каждый раз делать шаг в сторону проекции градиента целевой функции на многообразие $ \left\{ x | Ax \leqslant 0 \right\} $
Станет понятно если посмотреть на рисунок:

Здесь:
Чёрные тонкие линии это ограничения.
Жирный многоугольник это множество допустимых переменных $ x $.
Красные линии это линии уровня целевой функции.
Красная стрелка указывает направление градиента.
Чёрная стрелка - это проекция градиента на линейное многообразие.
Алгоритм:
1) В начальный момент есть допустимая точка
Её можно найти проверив всевозможные пересечения ограничений, на попадание в многообразие $ \left\{ x | Ax \leqslant 0 \right\} $.
2) Дальше проверяем если шаг по градиенту не выводит из множества допустимых переменных, то пользуемся градиентным методом
$U_{k+1} = U_k + \alpha * C$
$\alpha$ - длина шага, находится как решение задачи минимизации функции одной переменной
иначе
пользуемся методом проекции градиентов
$U_{k+1} = U_k + \alpha * P(C)$, где $P$ - оператор проектирования $P=B^T(B^TB)^{-1}B$
B - матрица из транспонированных градиентов тех ограничений, которые обратились в равенства (грани многообразия на которых находится точка).
3) Если $U_{k+1} = U_{k}$, то мы нашли максимум.

Вопросы. Когда я попытался решить задачу таким способом обнаружил:
1) Не могу спроектировать градиент. $P(C)$ не работает, в случае одного активного ограничения матрица $B^TB$ не обращается.
2) Для поиска длинны шага непонятно как решить задачу минимизации.
Источник
Чтобы понять как работает метод проекций градиента я использовал статью.

[Karoed]

Я понимаю, что довольно сложно переменить метод к задачи для которой он не предназначен.
Возможно кто-нибудь знает источник с описанием алгоритма Карамаркара в моём случае задачи. (т.е. без ограничений $ x_i \geqslant 0, i=0..n $)
Я смотрел "Введение в исследование операций" Хемди А. Таха, там есть описание метода. Оно мне не подходит - лишние ограничения на положительность переменных.

[MaximVD]

1) Насколько я понимаю, Вы проектирует градиент на линейное пространство $L = \{ x \mid B x = 0 \}$. Так?
Если да, то у Вас неправильная формула для оператора проектирования. Пусть $P(c)$ - проекция вектора $c$ на $L$, тогда $c - P(c)$ ортогонально $L$. $L$ - есть ортогональное дополнение линейной оболочки строк матрицы $B$, поэтому $c - P(c)$ должно принадлежать линейной оболочке строк матрицы $B$, т.е. $c - P(c) = B^T y$, где $y$ - некоторый вектор. Тогда $B c - B P(c) = B B^T y$. Так как $P(c)$ проекция на $L$, то $B P(c) = 0$, отсюда, если строки матрицы $B$ линейно независимы, то находим $y$ и получаем, что

$$ P(c) = ( E - B^T (B B^T)^{-1} B ) c. $$

В случае одного активного ограничения $B B^T$ будет числом.

2) Если вам нужна задача минимизации, то решается она очень легко. Если уже знаем $U_k$, то ищем следующую точку в виде $U_k - \alpha c$ (или $U_k - \alpha P(c)$. Если Вы решаете задачу максимизации, то будет "+", а не "-"). Подставим всё, получим, что надо найти минимум $c U_k - \alpha c^2$ на множестве $A U_k - \alpha A c \le 0$, а это есть задача нахождения минимума линейной функции на множестве заданном линейными ограничениями, которая решается совсем несложно (а если учесть, что $Ac \le 0$ или $A P(c) \le 0$, то решение почти очевидно).

[мат-ламер]

Связи между методом проекции градиента и алгоритмом Кармаркара я не знаю. Смутно подозреваю, что предложенный метод будет иметь такую же эффективность (в смысле количества щагов), что и симплекс-метод, хотя трудоёмкость одного шага у симплекс-метода меньше. Что касается возможности применения алгоритма Кармаркара к предложенной задаче ЛП (не буду называть как она называется, потому как постоянно путаю названия), то, во-первых, можно перейти к двойственной задаче. Во-вторых, попробуйте применить к исходной задаче метод барьеров. При этом, на каждом шаге получается задача нелинейного программирования без ограничений, к которой можно применить метод Ньютона. Получим мы при этом полиномиальную сходимость - не знаю.

[Karoed]

Так получилось, что я спрятал существенный момент. Самая обыкновенная система ограничений:
$\begin{cases} a_{10}+a_{11}x_1+a_{12}x_2+...+a_{1n}x_n\leq0;\\ a_{20}+a_{21}x_1+a_{22}x_2+...+a_{2n}x_n\leq0;\\ ...\\ a_{m0}+a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n\leq0.\end{cases}$
Когда у меня есть точка множества $(x_1^{'}; x_2^{'}; ... x_n^{'})$ (где-то на границе). Я имею набор активных ограничений:
$\begin{cases} a_{act_10}+a_{act_11}x_1^{'}+a_{act_12}x_2^{'}+...+a_{act_1n}x_n^{'}=0;\\ a_{act_20}+a_{act_21}x_1^{'}+a_{act_22}x_2^{'}+...+a_{act_2n}x_n{'}=0;\\ ...\\ a_{act_p0}+a_{act_p1}x_1^{'}+a_{act_p2}x_2^{'}+...+a_{act_pn}x_n^{'}=0.\end{cases}$
И вот туда мне и нужно проецировать... если я правильно понимаю. Короче говоря есть свободный член.

мат-ламер писал(а):

Во-вторых, попробуйте применить к исходной задаче метод барьеров.

А есть источник. Мне надо подробно про метод прочитать.

[мат-ламер]

Karoed в сообщении #419651 писал(а):

мат-ламер писал(а):

Во-вторых, попробуйте применить к исходной задаче метод барьеров.

А есть источник. Мне надо подробно про метод прочитать.

см. http://www.stanford.edu/~boyd/cvxbook/