Задача квадратичной оптимизации (практический случай)

[DLL]

Интересует практические методы решения (задача простая, но полагаю что могут быть какие-то подводные камни, когда речь идет о практическом примении в индустрии). Необходимо минимизировать квадратичную функцию большого числа переменных $x_i, i \in M=\{1, 2, ... , m\}$:

$$ F = \sum_{i,j} A_{ij} x_i x_j + \sum_{i} B_i x_i + C $$

при следующих условиях
1) $0 \leqslant x_i \leqslant X_i,$
2) $\sum_{i} x_i = X^{max},$
3) $x_i x_j = 0 \,\,\forall (i,j) \in N$
где $N$ - подмножество $M^2$.

[StaticZero]

DLL, про матрицу $A$ что известно? И каковы попытки решения?

[B@R5uk]

DLL в сообщении #1373380 писал(а):

3) $x_i x_j = 0 \,\,\forall (i,j) \in N$

Отсюда разве не следует, что все иксы равны нулю и целевая функция тоже? Может вы всё-таки имели в виду другое ограничение?

-- 01.02.2019, 16:09 --

DLL в сообщении #1373380 писал(а):

2) $\sum_{i} x_i = X^{max},$

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

-- 01.02.2019, 16:12 --

DLL в сообщении #1373380 писал(а):

1) $0 \leqslant x_i \leqslant X_i,$

Есть раздел математики, называющийся "Линейное программирование", он как раз решает такие и более общие задачи. Однако не стоит заблуждаться из-за слова "программирование" в названии. Решения задач имеют исключительно аналитические выражения, благодаря чему он больше напоминает линейную алгебру, хотя ничего не мешает переложить эти решения в программу.

[DLL]

StaticZero
Матрица разреженная. Без условия 3), получается обычная задача на условный экстремум.
Но условие 3) по сути означает, что если одна переменная не нуль, то другая точно нуль.
Вот только перебором в этом месте не хотелось бы заниматься

B@R5uk

Цитата:

Отсюда разве не следует, что все иксы равны нулю и целевая функция тоже? Может вы всё-таки имели в виду другое ограничение?

Множество $N$ может состоять из одного элемента, например $\{1,2\}$, это означает $x_1 x_2 = 0$, то есть если $x_1$ не нуль, то $x_2$ точно нуль.

[dsge]

Терминология. Квадратичное программирование - это когда целевая функция квадратичная, а ограничения линейные. В этом случае существуют хорошо отработанные алгоритмы, основанные на некотором обобщении симплекс-метода. В вашем случае ограничения нелинейные, значит это относится к нелинейному программированию. Попробуйте для начала какой-нибудь стандартный метод в стандартном пакете. Или посмотрите получится ли что-нибудь удобоваримое после метода Лагранжа.

[пианист]

CPLEX, вроде, доступен для некоммерческого использования, QP умеет.
Правда, я не знаю, как это, не возьмусь советовать.

[DLL]

ОК, но я думаю прежде всего с логической точки зрения надо разобраться с ограничениями:

$$x_i x_k = 0.$$

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

[dsge]

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

[vpb]

Точное решение в разумное время невозможно, в том смысле, что эта задача NP-полна. Если бы ее в разумное время удалось решить, то тем самым решилась бы одна из "задач тысячелетия", а именно P/NP.

Рассмотрим частный случай. Пусть у нас есть вогнутая квадратичная функция, и мы хотим найти минимум ее на параллелепипеде. Легко понять, что минимум достигается в одной из вершин. Но чтоб найти, в какой именно, всех их придется-таки перебрать. Так как уже эта задача NP-полна. (См, например, Floudos, Pardalos (eds.) Encyclopedia of optimization, статья "Concave programming" ). Или же удовольствоваться приближенным подходом, скажем, встать в одну из вершин, посмотреть, в какой из соседних значение наименьшее, переместиться туда и т.п., а когда придем в ту, из которой смещаться некуда, считать, что это кандидат на точку минимума.

И возможные множества ненулевых переменных $x_i$ тоже перебирать придется.

-- 01.02.2019, 23:07 --

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

[DLL]

vpb в сообщении #1373520 писал(а):

Точное решение в разумное время невозможно, в том смысле, что эта задача NP-полна. Если бы ее в разумное время удалось решить, то тем самым решилась бы одна из "задач тысячелетия", а именно P/NP.

Рассмотрим частный случай. Пусть у нас есть вогнутая квадратичная функция, и мы хотим найти минимум ее на параллелепипеде. Легко понять, что минимум достигается в одной из вершин. Но чтоб найти, в какой именно, всех их придется-таки перебрать. Так как уже эта задача NP-полна. (См, например, Floudos, Pardalos (eds.) Encyclopedia of optimization, статья "Concave programming" ). Или же удовольствоваться приближенным подходом, скажем, встать в одну из вершин, посмотреть, в какой из соседних значение наименьшее, переместиться туда и т.п., а когда придем в ту, из которой смещаться некуда, считать, что это кандидат на точку минимума.

И возможные множества ненулевых переменных $x_i$ тоже перебирать придется.

Можно разбить задачу исходную на $2^{Card(N)}$ подзадач, при чем в каждой мы точно знаем какой набор переменных нулевой.
И уже каждая подзадача квадратичная с линейными ограничениями. Вот только проблема, что экспоненциальный рост сложности совсем не пойдет для практических целей.

Цитата:

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

Возможно, можно улучшить представление целевой функции $F$.
Например, так

$$ F = \gamma_1 ||A \cdot x + b_1||^2_2 + \gamma_2 (x \cdot b_2), \gamma_1 > 0, \gamma_2 > 0. $$

[vpb]

У Вас два раза буква $A$ использована: в первом сообщении и в последнем. Вы подразумеваете, что существуют матрица $a$ и векторы $b_1$ и $b_2$ такие, что

$$ F=\sum_{i,j} A_{ij}x_ix_j + \sum_i B_ix_i +C=\gamma_1\|ax+b_1\|_2^2+\gamma_2(xb_2) \quad ?$$

Если так, то ситуация совершенно другая, потому, что целевая функция выпукла. Что же до перебора разных наборов ненулевых переменных, то в общем случае избежать этого нельзя (даже тогда, когда в целевой функции квадратичной части вообще нет, т.е. функция линейна).

[DLL]

vpb в сообщении #1373533 писал(а):

У Вас два раза буква $A$ использована: в первом сообщении и в последнем. Вы подразумеваете, что существуют матрица $a$ и векторы $b_1$ и $b_2$ такие, что

$$ F=\sum_{i,j} A_{ij}x_ix_j + \sum_i B_ix_i +C=\gamma_1\|ax+b_1\|_2^2+\gamma_2(xb_2) \quad ?$$

Если так, то ситуация совершенно другая, потому, что целевая функция выпукла.

Да, ситуация именно такая с $F$.

Цитата:

Что же до перебора разных наборов ненулевых переменных, то в общем случае избежать этого нельзя (даже тогда, когда в целевой функции квадратичной части вообще нет, т.е. функция линейна).

Ну перебор точно не пойдет, например если условий несовместности около 100, то это получается $2^{100} > 10^{20}$, что чересчур дофига. А вот такой стандартный трюк не пойдет? Приближенно условия несовместности можно регулиризовать

$$x_i x_k - \epsilon = 0.$$

[mserg]

А почему бы не линеаризовать $x_ix_j=0$ с помощью псевдобулевой переменной $z_{i,j}$?
Вместо нелинейного равенства появятся 2 линейных неравенства:
$x_i \le X^{max} z_{i,j}$
$x_j \le X^{max} (1-z_{i,j})$
И, вуаля, частично-целочисленная задача квадратичного программирования (если $A$ все же положительно определенная).
Или не вуаля?

[vpb]

DLL в сообщении #1373541 писал(а):

Приближенно условия несовместности можно регулиризовать

$$x_i x_k - \epsilon = 0.$$

Во-первых, это в численном смысле совершенно неустойчиво. Во-вторых, если делать так: одни выражать через другие, пользуясь этими соотношениями, и рассматривать задачу от меньшего числа переменных --- тогда задача потеряет выпуклость.

Можете попробовать сделать так: добавить слагаемое $D\sum_{(i,j)\in N} x_i^2x_j^2$, где $D$ --- какое-то большое число. Эта функция выпукла, и получается задача минимизации выпуклой функции на выпуклом многограннике. Более того, когда $D$ стремится к бесконечности, точка $x^\ast_D$, в которой достигается минимум, стремится к точке минимума исходной задачи.

А вот теперь самое интересное, я даже писать стесняюсь... Если немного продолжить эти рассуждения, то увидим, что как бы относительно просто научились решать такую задачу: какого максимального размера клика есть в данном графе ? При условии, конечно, что умеем "быстро" находить минимум выпуклой функции на выпуклом множестве, скажем на кубе. Получается так: или мы придумали, как показать, что P=NP ; или задачи выпуклой оптимизации сложней, чем я до сих пор думал; или у меня ввиду позднего часа слегка ум за разум тово. Я думаю, что если тщательней продумать, то подводный булыжник таки обнаружится. На всяк случай, если Вы сами или кто другой заинтересуется: есть две книги, Немировский, Юдин, Сложность задач и эффективность методов оптимизации, и Нестеров, Вводные лекции о выпуклой оптимизации. Собирался я их поизучать, да руки не дошли пока...

-- 02.02.2019, 02:52 --

mserg в сообщении #1373545 писал(а):

Или не вуаля?

Думается, что все же не вуаля, в том смысле, что эта задача не проще исходной...

[vpb]

Подумавши. Заскок, конечно: $x^2y^2$ не выпукла. Увы. Но все равно, возможно, в таком подходе есть потенциал. Не для "задач тысячелетия", правда, а для практики.