2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Задача оптимизации
Сообщение11.07.2019, 16:59 


05/06/19
26
Решить задачу оптимизации,
$$\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_{+}$

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

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


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

 Профиль  
                  
 
 Re: Задача оптимизации
Сообщение11.07.2019, 19:10 


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

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

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


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

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


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

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

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


18/01/15
1974
Своеобразно ! :shock:

 Профиль  
                  
 
 Re: Задача оптимизации
Сообщение24.07.2019, 18:47 


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

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


10/01/16
2188
vpb в сообщении #1404639 писал(а):
Если было бы известно $\lambda$, то $x$ можно найти просто как

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

 Профиль  
                  
 
 Re: Задача оптимизации
Сообщение30.07.2019, 04:26 


05/06/19
26
DeBill в сообщении #1406926 писал(а):
vpb в сообщении #1404639 писал(а):
Если было бы известно $\lambda$, то $x$ можно найти просто как

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


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

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


05/06/19
26
vpb
vpb в сообщении #1404575 писал(а):
Область оптимизации --- эллипсоид

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

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


10/01/16
2188
classman в сообщении #1407806 писал(а):
$A^TA$ - вырожденная. Не получится, вроде как

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

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



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

Сейчас этот форум просматривают: teleglaz


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

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