Здравствуйте, уважаемые математики.

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

Пример задачи:
$$ \inf ||x||^2 \\ \text{s.t.} \begin{cases} x = X \lambda \\ \sum\limits_{i=1}^n \lambda_i = 1 \\ \lambda_i \ge 0,\ i =1,2,\dots,n \end{cases} $$
$%X-$% матрица, содержащая координаты точек, которые принадлежат некоторому множеству, то есть первое ограничение задаёт выпуклую оболочку этого множества. А сама задача на поиск минимального расстояния до этого множества. Соответственно, интересуют способы перехода к эквивалентным задачам, без ограничений на знак $%\lambda$%.

задан 29 Июн '16 5:16

изменен 29 Июн '16 13:55

Обозначения непонятны. Что реально требуется найти?

(29 Июн '16 9:27) falcao

@falcao, я расписал условие $%\lambda \in \varDelta_n$% на то, что это означает. Интересно, можно ли перейти к эквивалентной задаче, (решив которую, мы сможем узнать решение этой задачи) которая не содержит ограничений на знак переменных.

(29 Июн '16 13:51) zhildemon

вроде как избавиться от неравенств в системе невозможно. Впрочем существует метод сведения задачи поиска условного экстремума к поиску безусловного. См например: http://math.semestr.ru/math/lagrange.php

(29 Июн '16 14:00) abc

@abc, максимизация идёт по $%\lambda\ge 0$%, а следовательно мы остаёмся при своих =)

(29 Июн '16 14:14) zhildemon

@zhildemon в случае неравенств он тоже применим

(29 Июн '16 14:19) abc

а ну да, если линейную систему превратить в нелинейную, то наверное можно избавиться и от неравенств...

(29 Июн '16 14:23) abc
2

Можно заменить $% \lambda_i=\gamma_i^2$% и вместо оптимизации в кубе перейти к поиску величины $%Xf(\gamma) $% на сфере $%\sum \gamma_i^2 =1 $%, где $%f(\gamma)= (\gamma^{2},\dots, \gamma^{2} )$%. От ограничений на положительность избавились, а зачем?

(29 Июн '16 14:30) Urt

@Urt, спасибо, интересно сравнить, что будет работать быстрее. Методы решения используются разные для разных типов задач, надо эмпирически глянуть как будет меняться время при больших размерностях в разных случаях.

(29 Июн '16 15:12) zhildemon
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×76

задан
29 Июн '16 5:16

показан
373 раза

обновлен
29 Июн '16 15:12

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

по почте:

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

по RSS:

Ответы

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

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