2014 dxdy logo

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

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


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


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



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


05/06/19
27
Решить задачу оптимизации,
$$\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
3075
classman
Это частный случай так называемой "подзадачи доверительной области", или "trust region subproblem". Область оптимизации --- эллипсоид, а целевая функция квадратична. Линейным преобразованием получаем задачу о минимуме квадратичной функции на шаре. Решается она не очень просто. Почитайте, например, книгу Дэннис-Шнабель, Численные методы безусловной оптимизации и решения систем нелинейных уравнений, параграф 6.4, а также Nocedal, Wright, Numerical optimization, глава 4.

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


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

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


05/06/19
27
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
3075
Своеобразно ! :shock:

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


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

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


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

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

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


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

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


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

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


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

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

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


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

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

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

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



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

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


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

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