Выбрать точку удовлетворяющую линейной системе неравенств

[R_e_n]

Пишу программу для решения задачи линейного программирования, методом внутренней точки. Если я правильно понял описание алгоритма, то в самом начале нужно выбрать какую-нибудь начальную точку из допустимой области. Вопрос: а как это сделать?
$A \cdot x \leqslant b$
$\min c^T \cdot x $
Матрица $A$ размера $m$ на $n$
Нужно найти хоть какой-нибудь x, для которого верно: $A \cdot x \leqslant b$, подать этот $x$ на вход алгоритму, а он уже найдет тот, который минимизирует $ c^T \cdot x $.

[мат-ламер]

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

[VladimirKr]

Стандартным "входом" является создание т.н. дополнительных переменных $m$ штук справа. То есть, в матричном виде: рассмотрим новую задачу линейного программирования $B\cdot x\leqslant b$, где матрица $B$ есть матрица $A$, расширенная справа единичной матрицей порядка $m$. То есть $B=(AE)$
Легко видеть, что любое решение такой системы $x^T=(x_1,...,x_n,x_{n+1},...,x_{n+m})$ соответствует решению исходной системы $(x_1,...,x_n)$
То есть, просто, вместо исходной задачи решаем задачу ЛП для $B\cdot x\leqslant b$. Здесь же начальное решение выписывается легко: $x^T=(0,...,0,b_1,...,b_m)$, где $b_i$ это компоненты столбца $b$ свободных членов системы.

[мат-ламер]

Хочу дополнить, что начальная точка в методе внутренней точки должна быть действительна внутренней, а не граничной.

мат-ламер в сообщении #927167 писал(а):

иначе промежуточные задачи метода внутренней точки будут плохо обусловленными