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

[пианист]

Я бы все-таки советовал до всего попробовать сделать расчет в каком-то из хороших пакетов и посмотреть на решение.
Печально, конечно, что свободные не умеют QP, но думаю, оформить некоммерческое использование вполне в рамках возможного.

[mserg]

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

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

Или не вуаля?

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

А в смысле использования готовых пакетов квадратичного / нелинейного программирования - вуаля.

Из свободных знаю Couenne, но раньше были некоторые проблемы ввода модели в решатель. Как сейчас - не знаю.
Возможно Scip умеет решать такие задачи - не вникал

Если ТС выложит данные, то можно проверить на Couenne.

[DLL]

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

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

А зачем там $x_i^2x_j^2$ ? Иксы же и так положительны.

[dsge]

Задача все же относится к квадратичному программированию. Ограничения, которые выглядят нелинейными, задают об’единение гиперплоскостей. Это значит, что задача решается за полиномиальное время.

[vpb]

dsge
Дык, этих гиперплоскостей (точнее, подпространств, т.к. они на обязательно коразмерности 1) может быть очень много. Скажем, множество точек с соотношениями $x_1x_2=x_3x_4=\ldots=x_{2m-1}x_{2m}=0$, (где $n=2m$) --- это объединение $2^m$ пространств размерности $m$, попарно не содержащихся друг в друге.

(Оффтоп)

Что за заколдованная задача: два ЗУ с ней ошиблись (ввиду позднего часа...)

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

зачем там $x_i^2x_j^2$ ? Иксы же и так положительны.

Верно, квадраты лишние.

[dmd]

DLL

Цитата:

$M=\{1, 2, ... , m\}$

какова конкретная величина $m$?

Цитата:

$N$ - подмножество $M^2$

как конкретно определяется $N$?

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

[Sender]

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

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

Эмм, может, я чего-то не понимаю, но не означает ли это условие, что из всех $x_i$ ненулевым может быть максимум один? Если бы нашлось два, ненулевым было бы и их произведение.

[vpb]

Sender в сообщении #1373769 писал(а):

но не означает ли это условие, чт

Нет, не означает. $N$ --- это не множество всех пар $(i,j)$ с $1\leq i,j\leq M$, $i\ne j$, а, вообще говоря, некоторое его подмножество.

[Sender]

А, да. Не заметил определение $N$. Тогда это условие можно интерпретировать как принадлежность нулевых иксов множеству вершинных покрытий графа $(M,N)$. Перебор всех вершинных покрытий - та ещё задача.

[DLL]

dmd в сообщении #1373731 писал(а):

DLL

Цитата:

$M=\{1, 2, ... , m\}$

какова конкретная величина $m$?

Цитата:

$N$ - подмножество $M^2$

как конкретно определяется $N$?

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

Количество переменных $x_i$ порядка нескольких сотен (например, $m=200$ или $m=300$).
Что касается множества несовместности переменных $N = \{ (k,l) \in \{1, 2, ..., m \}^2: x_k x_l = 0 \}.$
Несовместных переменных достаточно много, тоже порядка нескольких сотен. В случае, когда $m = 200$, может оказаться, что $Card(N)$ = 100.
P.S: что касается входных данных, то можно пользоваться следующей целевой функцией

$$ 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), $$

где $\gamma_1, \gamma_2 \in (0,1),$ а вектор $b_2$ состоит из положительных чисел. Матрицу $a$ и вектор $b_1$ можно задать случайно с элементами из некоторого интервала $(-C, C)$.

[DLL]

Провел численный эксперимент на простом примере:

$$F = (x - 0.5)^2 + (y - 0.3)^2 + (z - 0.7)^2 + (u - 0.4)^2$$

при ограничениях

$$x + y + z + u \le 2, x \le 1, y \le 1, z \le 1, u \le 1,$$

с одним условием несовместности

$$yz = 0.$$

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

$$F_D = (x - 0.5)^2 + (y - 0.3)^2 + (z - 0.7)^2 + (u - 0.4)^2 + D yz$$

к точному решению. Интересно, можно ли какие-нибудь явные оценки сходимости в общем случае получить?

[dmd]

а неизвестные целые или действительные?

-- Пн фев 04, 2019 08:12:56 --

если целые, то

(модель)

var x binary;
var y binary;
var z binary;
var u binary;

s.t. st1 : x+y+z+u <= 2;
s.t. st2 : y*z <= 0;

minimize F : (x-1/2)^2 + (y-3/10)^2 + (z-7/10)^2 + (u-2/5)^2;

option solver cplex;
option cplex_options 'timing=1 threads=3 display=1 mipdisplay=4 mipinterval=10000';

solve;

printf ("\nF = " & F & "\n");
printf ("{x,y,z,u} = {" & x & "," & y & "," & z & "," & u & "}");
printf ("\n");

(решение)

CPLEX 12.8.0.0: timing=1
threads=3
display=1
mipdisplay=4
mipinterval=10000
MIQCP Presolve eliminated 1 rows and 2 columns.
Reduced MIQCP has 5 rows, 8 columns, and 14 nonzeros.
Reduced MIQCP has 2 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQCP has 1 quadratic constraints.
Probing time = 0.00 sec. (0.00 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 3 threads.
LP Presolve eliminated 5 rows and 8 columns.
All rows and columns eliminated.
Initializing dual steep norms . . .
Root relaxation solution time = 0.02 sec. (0.00 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.5900     0                      0.5900        0
*     0     0      integral     0        0.5900        0.5900        0    0.00%
Found incumbent of value 0.590000 after 0.02 sec. (0.03 ticks)
      0     0        cutoff              0.5900        0.5900        0    0.00%
Elapsed time = 0.02 sec. (0.03 ticks, tree = 0.01 MB)

Root node processing (before b&c):
  Real time             =    0.02 sec. (0.03 ticks)
Parallel b&c, 3 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.02 sec. (0.03 ticks)

Times (seconds):
Input =  0
Solve =  0
Output = 0
CPLEX 12.8.0.0: optimal integer solution; objective 0.59
0 MIP simplex iterations
0 branch-and-bound nodes
No basis.

F = 0.5900000000000001
{x,y,z,u} = {0,0,1,0}

Эта модель не показательна, ни о чем не говорит, лучше бы более приближенные к реальности тестовые данные

[Sender]

пианист в сообщении #1373580 писал(а):

Печально, конечно, что свободные не умеют QP

И z3 не умеет?

[DLL]

dmd в сообщении #1373965 писал(а):

а неизвестные целые или действительные?

Неизвестные $x_i$ являются действительными, положительными числами (не целыми).

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

[пианист]

Про z3 ничего не знаю, сори.
Вроде по описанию это прувер..
Но, да, на самом деле , конечно, высказался слишком категорично. Собс-но, я же сам видел вполне себе gpl поделия, которые анонсировали, что умеют делать нелинейные оптимизации.
Сам такими не пользовался, поэтому не берусь советовать (CPLEX тоже не, но слышал хорошие отзывы от людей, чьему мнению доверяю).
Что касаемо как, можно глянуть документацию, возможно, там есть ответ на вопросы.