2014 dxdy logo

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

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


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


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



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


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

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


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

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


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

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

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



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

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


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

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