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

[artempalkin]

Задача такая (это из одного из вступительных экзаменов ВШЭ):

Найти минимум функции $||Ax-b||^2_2$ на множестве $x^TPx-q^Tx+w\leqslant 0$, где $A\in\mathbb{R}^{m\times n}$, $\operatorname{rk} A=m$, $b,q\in\mathbb{R}^n$, $w\in\mathbb{R}$, $P$ - симметрическая положительно определенная матрица.

Я что-то не совсем понимаю, как подступиться к этой задаче. Для начала, насколько я понимаю, множество, которое нам дано, является внутренностью какой-то поверхности (я так понимаю, в линейноалгебраической терминологии она называется поверхностью второго порядка), поэтому нам достаточно рассмотреть минимум нашей ф-ии на $x^TPx-q^Tx+w= 0$. Далее в целом можно расписать все поэлементно и составить функцию Лагранжа и искать условный экстремум как безусловный, просто брать частные производные и прочее.

Другой вариант как-то матрично тут все обрабатывать. Например, $||Ax-b||=(Ax-b)^T(Ax-b)$ и что-то можно раскрыть, но как-то я не вижу, как можно с этим работать. Более того, наше множество - не линейное пространство, а как работать с какими-то произвольными множествами в линейном пространстве, идей вообще нету.

Подскажите, как подступиться

[thething]

Заметьте, что задача -- выпуклая, т.е. при определённых условиях необходимые условия экстремума будут и достаточными.

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

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

А что требуется? А то ответы могут лежать в интервале: "Отрапортовать, что это задача квадратичного программирования" до "разработать новый метод решения квадратичного программирования при квадратичных ограничениях".
А так - https://en.wikipedia.org/wiki/Quadratic ... ic_program

[artempalkin]

thething в сообщении #1526707 писал(а):

Задача-то несложная

В том-то и дело, что там все задачи довольно простые :)

$L(x,\lambda)=x^TA^TAx-2b^TAx-b^b+\lambda(x^TPx-q^Tx+w)$
$\Delta L=2x^TA^TA\Delta x-2b^TA\Delta x+\lambda (2x^TP\Delta x-q^T\Delta x)$
Но как тут найти "производную"? Разделить на $||\Delta x||=\sqrt{\Delta x^T\Delta x}$? Даже если так, дальше нужно приравнивать нулю, и что-то я не пойму, как это сделать и какие выводы из этого можно получить :(

-- 22.07.2021, 11:24 --

Я так понимаю, мы просто приравниваем коэффициент при $\Delta x$ к нулю (хотя не до конца понимаю, почему). Получается

$$x^T(2A^TA+2\lambda P)=2b^TA+q^T,$$

откуда вроде как выражается $x$, который потом можно подставить во второе условие для нахождения $\lambda$. Но тут, на самом деле, мы сталкиваемся с возможностью вырожденности матрицы $2A^TA+2\lambda P$, и что с ней делать?

И почему мы коэффициент приравниваем нулю? :) Я не понимаю теоретических обоснований, если честно :(

-- 22.07.2021, 11:28 --

Запишу в более нормальном виде

$$(2A^TA+2\lambda P)x=2A^Tb+q.$$

[thething]

artempalkin в сообщении #1526720 писал(а):

И почему мы коэффициент приравниваем нулю?

Хмм, а вот при минимизации функции одной переменной $f(x)$, Вы понимаете, почему мы "коэффициент" приравниваем к нулю? А также, что это вообще за "коэффициент"?

artempalkin в сообщении #1526720 писал(а):

Но тут, на самом деле, мы сталкиваемся с возможностью вырожденности матрицы $2A^TA+2\lambda P$, и что с ней делать?

Сталкиваемся. Ничего особо не делать. Проверять, имеет ли система решения, смотря по правой части. Но в параметрах этого не сделаешь. Поэтому, я думаю, тут надо описать все возможные сценарии, как при решении обычной задачи с параметрами.

Кстати, если это задача со вступительного экзамена, то вступительного -- куда именно? Не для школьников же она.

[artempalkin]

thething в сообщении #1526726 писал(а):

А также, что это вообще за "коэффициент"?

Коэффициент, конечно, неудачное слово, речь идет о строке, которую мы умножаем на $\Delta x$.

thething в сообщении #1526726 писал(а):

Хмм, а вот при минимизации функции одной переменной $f(x)$, Вы понимаете, почему мы "коэффициент" приравниваем к нулю?

При исследовании числовой функции мы приравниваем нулю не коэффициент при $\Delta x$ (или при $dx$), а все-таки отношение линейной части приращения функции к приращению аргумента. Это означает, что мы ищем такие точки, в которых функция (в каком-то смысле) не меняется по $x$, только там могут быть точки экстремума. Здесь же я не могу "сократить" на $\Delta x$, хмммм... Что-то не могу обернуть это вокруг моей головы.

-- 22.07.2021, 16:46 --

thething в сообщении #1526726 писал(а):

Кстати, если это задача со вступительного экзамена, то вступительного -- куда именно? Не для школьников же она.

Это вступительные в магистратуру

[thething]

artempalkin в сообщении #1526741 писал(а):

Коэффициент, конечно, неудачное слово

Вы подумали, что я придираюсь к слову "коэффициент" (ну, если чуть-чуть), а я про то, чтобы вы вспомнили, что это в принципе такое, и каковы необходимые условия экстремума функций многих переменных.

[artempalkin]

thething в сообщении #1526752 писал(а):

Вы подумали, что я придираюсь к слову "коэффициент" (ну, если чуть-чуть), а я про то, чтобы вы вспомнили, что это в принципе такое, и каковы необходимые условия экстремума функций многих переменных.

Ну как бы да, строго говоря, при каждом $\Delta x_i$ коэффициент и будет частной производной по этой переменной от функции Лагранжа (так интуитивно должно быть). Тогда в этом плане все сходится и логично!

thething в сообщении #1526726 писал(а):

Сталкиваемся. Ничего особо не делать. Проверять, имеет ли система решения, смотря по правой части. Но в параметрах этого не сделаешь. Поэтому, я думаю, тут надо описать все возможные сценарии, как при решении обычной задачи с параметрами.

Ну то есть в таком случае получается, что при некоторых лямбдах, при которых матрица вырожденна, будет существовать не единственное решение этого уравнения (не единственное $x$). Тогда нужно взять все это множество $x$ и подставить в наше условие ($x^TPx-q^Tx+w\leqslant 0$). Если какие-то удовлетворят, значит, на них и будет достигаться экстремум. Правильно я понимаю? И это никак аналитически в общем виде не оформить, просто написать, так сказать, словами, как отдельный случай, так ведь?

[svv]

Потеряли $\lambda$ при $q$.

[artempalkin]

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

Потеряли $\lambda$ при $q$.

Да, спасибо, что интересно, я ее дважды терял при письме тоже :) Но в целом в этой задаче мне не столько интересен ответ, сколько сам принцип.

[svv]

artempalkin в сообщении #1526691 писал(а):

$A\in\mathbb{R}^{m\times n}$, $\operatorname{rk} A=m$, $b,q\in\mathbb{R}^n$

Тут, наверное, $b\in\mathbb R^m$, размерность этого вектора равна размерности вектора $Ax$, то есть числу строк матрицы $A$.

А вдруг это не ошибка, а ключ? Тогда $m=n$, и $A$ обратима. Задачка на внимательность, так сказать.

[artempalkin]

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

Тут, наверное, $b\in\mathbb R^m$, размерность этого вектора равна размерности вектора $Ax$, то есть числу строк матрицы $A$.

А вдруг это не ошибка, а ключ? Тогда $m=n$, и $A$ обратима. Задачка на внимательность, так сказать.

Хаха, нет :) Это ошибка. Я заметил (понял) это уже через какое-то время после того, как написал сообщение и не стал исправлять, надеясь, что никто не заметит :) но кое-кто внимательно исследует!
В принципе, как я понимаю, необратимость или обратимость матрицы А не играет такой большой роли. Мне даже кажется, она не играет никакой роли. Важно только то, лежит ли $b$ в пересечении образа матрицы $A$ и нашего множества или нет, потому что если лежит, то расстояние будет $0$, ну и какие-то решения у задачи будут (хотя если матрица обратима, тогда решение в таком случае можно записать явно)

[svv]

Ладно.

[vpb]

Было. В конечном виде эта задача не решается. Она, как бы, сводится к задаче о решении уравнения вида $f(\lambda)=0$, где $f$ --- некоторая выпуклая (!) функция одного переменного. Но последнее не решается.

-- 23.07.2021, 02:12 --

artempalkin в сообщении #1526720 писал(а):

В том-то и дело, что там все задачи довольно простые :)

Как видим, не все ... Вроде, Стокс любил такие приколы: тем, кто хотел поступить к нему в ученики, на экзамене давал неразрешимые задачи. И вот, дал Максвеллу задачу о распределении молекул в газе по скоростям. А тот возьми да и выведи распределение Максвелла....

[thething]

artempalkin в сообщении #1526758 писал(а):

Ну то есть в таком случае получается, что при некоторых лямбдах, при которых матрица вырожденна, будет существовать не единственное решение этого уравнения (не единственное $x$).

В том уравнении, которое Вы решаете, необратимости матрицы не будет, там же строгая положительная определённость у неё, которую я упустил из виду в условии.

Необратимость будет в другом случае, про который Вы благополучно забыли (или специально не упомянули). Ну, тот, связанный с дополняющей нежёсткостью и т.д. Вот, посмотрите хотя бы тут.

В общем виде, конечно, задача не решится, но, думаю, тут этого и не просят. Пришли к уравнению, и достаточно.

Вообще, по-хорошему, оформите чётко все условия в методе множителей (см. ссылку) и рассмотрите все случаи. Там будут возникать ещё какие-то "подозрительные" решения, и проверку надо делать подстановкой в неравенство не того, что Вы нарешали сейчас (тут у Вас и так уравнение, из которого теоретически можно найти лямбду), а того, что Вы упустили.