Задача оптимизации

[classman]

Решить задачу оптимизации,

$$\min\lVert Ax - b\rVert^2_{2}$$

​при условии, что

$$x^TPx - q^Tx + w\leq0$$

где $x\in R^n, A\in R^{m\times n}( \operatorname{rank}(A)=m), b\in R^m, q\in R^n, w\in R, P$​ - положительно определенная симметричная матрица

-- 11.07.2019, 17:22 --

Целевую функцию можно легко привести к виду $x^TA^TAx - 2b^TAx + b^Tb$. Только не сильно понятно, что это даст.
Можно заметить, что целевая функция и множество, на котором оно задано - оба выпуклые и воспользоваться Куном-Таккером. И тогда получим систему из двух уравнений, решение которой будет довольно громоздким.
$$ \begin{equation*} \begin{cases} 2A^T(Ax-b) + \lambda(2Px-q) = 0, \\ \lambda(x^TPx - q^Tx + w) = 0 \end{cases} \end{equation*}​ $$
\lambda \in R_{+}$

есть у кого какие-нибудь идеи?

[vpb]

classman
Это частный случай так называемой "подзадачи доверительной области", или "trust region subproblem". Область оптимизации --- эллипсоид, а целевая функция квадратична. Линейным преобразованием получаем задачу о минимуме квадратичной функции на шаре. Решается она не очень просто. Почитайте, например, книгу Дэннис-Шнабель, Численные методы безусловной оптимизации и решения систем нелинейных уравнений, параграф 6.4, а также Nocedal, Wright, Numerical optimization, глава 4.

[classman]

vpb в сообщении #1404575 писал(а):

classman
Это частный случай так называемой "подзадачи доверительной области", или "trust region subproblem". Область оптимизации --- эллипсоид, а целевая функция квадратична. Линейным преобразованием получаем задачу о минимуме квадратичной функции на шаре. Решается она не очень просто. Почитайте, например, книгу Дэннис-Шнабель, Численные методы безусловной оптимизации и решения систем нелинейных уравнений, параграф 6.4, а также Nocedal, Wright, Numerical optimization, глава 4.

Спасибо! Обязательно посмотрю, но вообще говоря, задача не предполагает знания численных методов.
Интересно, насколько изменилась бы задача, если бы $\operatorname{rank}(A) = n$

[vpb]

Если было бы известно $\lambda$, то $x$ можно найти просто как $x=(1/2)(A^TA+\lambda P)^{-1}(2A^Tb+\lambda q)$. Но $\lambda$ неизвестно, и, насколько я знаю, конечными методами не находится. Если это задача типа учебной, то сие странно. А откуда, правда, она взялась ?

[classman]

vpb в сообщении #1404639 писал(а):

Если было бы известно $\lambda$, то $x$ можно найти просто как $x=(1/2)(A^TA+\lambda P)^{-1}(2A^Tb+\lambda q)$. Но $\lambda$ неизвестно, и, насколько я знаю, конечными методами не находится. Если это задача типа учебной, то сие странно. А откуда, правда, она взялась ?

Вступительный экзамен в институт

[vpb]

Своеобразно !

[nootnoot]

Добрый день
В итоге - какое решение задачи?

[DeBill]

vpb в сообщении #1404639 писал(а):

Если было бы известно $\lambda$, то $x$ можно найти просто как

Ну, и подставим это ИКС в уравнение границы области, да и решим полученное уравнение (типа, степени $2n$) относительно $\lambda$...

[classman]

DeBill в сообщении #1406926 писал(а):

vpb в сообщении #1404639 писал(а):

Если было бы известно $\lambda$, то $x$ можно найти просто как

Ну, и подставим это ИКС в уравнение границы области, да и решим полученное уравнение (типа, степени $2n$) относительно $\lambda$...

$A^TA$ - вырожденная. Не получится, вроде как

[classman]

vpb

vpb в сообщении #1404575 писал(а):

Область оптимизации --- эллипсоид

я тут подумал, если область оптимизации эллипсоид, разве он может принимать отрицательные значения?.
Может $x^TPx - q^Tq + w\geq 0$ всегда?

[DeBill]

classman в сообщении #1407806 писал(а):

$A^TA$ - вырожденная. Не получится, вроде как

Но зато $\lambda P + A^TA$ - невырождена....Вроде как получится....