Общий вид задачи:
целевая функция

ограничения

Здесь

- матрица размера


- вектор коэффициентов целевой функции (строка)

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

Станет понятно если посмотреть на рисунок:

Здесь:
Чёрные тонкие линии это ограничения.
Жирный многоугольник это множество допустимых переменных

.
Красные линии это линии уровня целевой функции.
Красная стрелка указывает направление градиента.
Чёрная стрелка - это проекция градиента на линейное многообразие.
Алгоритм:1) В начальный момент есть допустимая точка
Её можно найти проверив всевозможные пересечения ограничений, на попадание в многообразие

.
2) Дальше проверяем если шаг по градиенту не выводит из множества допустимых переменных, то пользуемся градиентным методом

- длина шага, находится как решение задачи минимизации функции одной переменной
иначе
пользуемся методом проекции градиентов

, где

- оператор проектирования

B - матрица из транспонированных градиентов тех ограничений, которые обратились в равенства (грани многообразия на которых находится точка).
3) Если

, то мы нашли максимум.
Вопросы. Когда я попытался решить задачу таким способом обнаружил:
1) Не могу спроектировать градиент.

не работает, в случае одного активного ограничения матрица

не обращается.
2) Для поиска длинны шага непонятно как решить задачу минимизации.
ИсточникЧтобы понять как работает метод проекций градиента я использовал
статью.