Решить задачу оптимизации $$\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 - положительно определенная симметричная матрица

задан 29 Июл '19 22:46

изменен 29 Июл '19 22:48

10|600 символов нужно символов осталось
0

Целевую функцию можно привести к виду $$x^TA^TAx - 2b^TAx + b^Tb$$Только не сильно понятно, что это даст. Можно заметить, что целевая функция и множество, на котором оно задано - оба выпуклые и воспользоваться Куном-Таккером. И тогда получим систему из двух уравнений. $$2A^T(Ax-b) + \lambda(2Px-q) = 0$$ $$\lambda(x^TPx - q^Tx + w) = 0$$

$$\lambda \in R_{+}$$ Есть идеи?

ссылка

отвечен 29 Июл '19 22:48

@classman: а зачем множитель "лямбда" в уравнении, когда произведение равно нулю?

(30 Июл '19 12:31) falcao

@falcao Либо множитель равен нулю, либо само ограничение в точке минимума. Т.е. если ограничение не активно, то lambda=0, такое ограничение можно не учитывать

(30 Июл '19 12:37) classman

@classman: у Вас в конце написано, что лямбда принадлежит R+. Это множество положительных чисел, или неотрицательных? Если первое, то можно сократить, не думая.

(30 Июл '19 12:47) falcao

@falcao множество неотрицательных конечно. Иначе нет смысла в этом множителе. Это условие доп. нежесткости

(30 Июл '19 12:54) classman

@falcao можно еще обратить внимание на матрицу A^T*A. Она вырожденная. Возможно решений нет, а возможно это опечатка в условии и rankA = n, а не m

(30 Июл '19 12:55) classman

@falcao такой вопрос, может быть знаете. Если P - положительно определенная матрица. Не значит ли это, что x^TPx−qTx+w всегда больше либо равен нулю? вообще говоря, это уравнение эллипсоиды, разве ее значение может быть отрицательным? Мнимые эллипсоиды конечно не в счет.

(30 Июл '19 14:06) classman

@classman: конечно, нет -- ведь даже для одномерного случая получается квадратный трёхчлен с положительным коэффициентом, значение которого запросто может быть отрицательным (w выбираем по своему усмотрению).

(30 Июл '19 15:21) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×125

задан
29 Июл '19 22:46

показан
314 раз

обновлен
30 Июл '19 15:21

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru