2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 "Задача оптимизации"
Сообщение21.07.2021, 22:01 


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

Найти минимум функции $||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)$ и что-то можно раскрыть, но как-то я не вижу, как можно с этим работать. Более того, наше множество - не линейное пространство, а как работать с какими-то произвольными множествами в линейном пространстве, идей вообще нету.

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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 04:57 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 10:38 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 11:13 


14/02/20
355
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.$$

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 12:53 
Заслуженный участник
Аватара пользователя


27/12/17
1300
Антарктика
artempalkin в сообщении #1526720 писал(а):
И почему мы коэффициент приравниваем нулю?

Хмм, а вот при минимизации функции одной переменной $f(x)$, Вы понимаете, почему мы "коэффициент" приравниваем к нулю? А также, что это вообще за "коэффициент"?
artempalkin в сообщении #1526720 писал(а):
Но тут, на самом деле, мы сталкиваемся с возможностью вырожденности матрицы $2A^TA+2\lambda P$, и что с ней делать?

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

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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 16:38 


14/02/20
355
thething в сообщении #1526726 писал(а):
А также, что это вообще за "коэффициент"?

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

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

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

-- 22.07.2021, 16:46 --

thething в сообщении #1526726 писал(а):
Кстати, если это задача со вступительного экзамена, то вступительного -- куда именно? Не для школьников же она.

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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 19:04 
Заслуженный участник
Аватара пользователя


27/12/17
1300
Антарктика
artempalkin в сообщении #1526741 писал(а):
Коэффициент, конечно, неудачное слово

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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 20:51 


14/02/20
355
thething в сообщении #1526752 писал(а):
Вы подумали, что я придираюсь к слову "коэффициент" (ну, если чуть-чуть), а я про то, чтобы вы вспомнили, что это в принципе такое, и каковы необходимые условия экстремума функций многих переменных.

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

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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 20:55 
Заслуженный участник


23/07/08
9024
Харьков
Потеряли $\lambda$ при $q$.

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 21:06 


14/02/20
355
svv в сообщении #1526760 писал(а):
Потеряли $\lambda$ при $q$.

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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 22:17 
Заслуженный участник


23/07/08
9024
Харьков
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$.

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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 22:38 


14/02/20
355
svv в сообщении #1526764 писал(а):
Тут, наверное, $b\in\mathbb R^m$, размерность этого вектора равна размерности вектора $Ax$, то есть числу строк матрицы $A$.

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

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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение22.07.2021, 22:42 
Заслуженный участник


23/07/08
9024
Харьков
Ладно. :-)

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение23.07.2021, 03:04 
Заслуженный участник


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

-- 23.07.2021, 02:12 --

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

 Профиль  
                  
 
 Re: "Задача оптимизации"
Сообщение23.07.2021, 05:43 
Заслуженный участник
Аватара пользователя


27/12/17
1300
Антарктика
artempalkin в сообщении #1526758 писал(а):
Ну то есть в таком случае получается, что при некоторых лямбдах, при которых матрица вырожденна, будет существовать не единственное решение этого уравнения (не единственное $x$).


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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 28 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group