Точное решение линейной оптимизационной задачи

[DLL]

Рассмотрим матрицу $m \times n, n > m$.
Мы ищем вектор X такой что $AX = B, X \in R^n$
При условии что $\|X\|^2 = x_1^2 + x_2^2 + ... + x_n^2 \rightarrow min$

Первая нетривиальная задача получается получается когда $m = 2, n = 3$.
Тогда используя метод множителей Лагранжа, можно получить линейную систему на все переменные $X$ и $\Lambda$.
Определяющим фактором является детерминант системы линейных уравнений на $\Lambda$, он равняется сумме квадратов всех миноров $2 \times 2$ матрицы $A$.
Действительно, когда все такие миноры нулевые, то решить исходную задачу (для произвольной правой части $B$) просто невозможно.
Можно как-нибудь просто это обобщить для произвольных $m,n$?

[Евгений Машеров]

У нас имеется уравнение плоскости. Ищем расстояние от плоскости до начала координат. Для этого находим ближайшую точку.

[мат-ламер]

DLL в сообщении #1581974 писал(а):

Можно как-нибудь просто это обобщить для произвольных $m,n$?

Что именно "это" вы хотите обобщить? Перед этим вы написали:

DLL в сообщении #1581974 писал(а):

решить исходную задачу (для произвольной правой части $B$) просто невозможно.

Что решить эту задачу невозможно? В принципе? Но это не так.
(Хотя, может мы с вами по-разному понимаем выражение "решить задачу").

[Евгений Машеров]

Я как-то привык, что вектора и матрицы как-то разделяются шрифтом. А то мне всё кажется, что X и B - матрицы.

[svv]

DLL в сообщении #1581974 писал(а):

Мы ищем вектор X такой что $AX = B, X \in R^n$

Совместность системы гарантируется?

[krum]

в таких задачах обычно считают, что ранг матрицы $A$ максимален. Какой смысл рвассматривать зависимые уравнения?

[мат-ламер]

DLL в сообщении #1581974 писал(а):

Действительно, когда все такие миноры нулевые,

Тогда ранг матрицы $A$ равен единице (нулевой ранг не рассматриваем). И все её строки выражаются через какую-то единственную её строку.

DLL в сообщении #1581974 писал(а):

, то решить исходную задачу (для произвольной правой части $B$) просто невозможно.

То есть решение задачи состоит в том, не для всех векторов правой части существует нужная нам точка.

DLL в сообщении #1581974 писал(а):

Можно как-нибудь просто это обобщить для произвольных $m,n$?

Как-бы это всё очевидно в любых размерностях.

[svv]

DLL в сообщении #1581974 писал(а):

$n > m$

krum в сообщении #1582047 писал(а):

в таких задачах обычно считают, что ранг матрицы $A$ максимален. Какой смысл рассматривать зависимые уравнения?

Ну, тогда решением задачи будет вектор
$x=A^T(AA^T)^{-1}b$
Вопрос к DLL: нужны ли какие-то комментарии?

[DLL]

svv в сообщении #1582117 писал(а):

$x=A^T(AA^T)^{-1}b$
Вопрос к DLL: нужны ли какие-то комментарии?

А вот у этой матрицы $(AA^T)$ детерминант равен сумма квадратов миноров $m$ на $m$?
Для матрицы 2 на 3 ровно так и получается..

[svv]

DLL в сообщении #1582772 писал(а):

А вот у этой матрицы $(AA^T)$ детерминант равен сумма квадратов миноров $m$ на $m$?

Да, это непосредственно получается из формулы Бине-Коши.
См. Гантмахер, «Теория матриц», глава 1, параграф 2, пункт 5 (стр. 17-18).
Недавно упоминал эту формулу тут.

Кстати, формулу $x=A^T(AA^T)^{-1}b$ можно получить не с помощью метода Лагранжа, а из общих теор.соображений.