Целевая функция квадратичного программирования Cgal

Я пытаюсь минимизировать функцию, подобную следующей:

25*x^2 + 45*x*y + y^2

и аналогичные ограничения, такие как:

(25 + y) + 25*x <= 1

в CGAL::Quadratic_program.

Чтобы ввести «25x ^ 2» и «y ^ 2» в целевую функцию, я могу сделать следующее:

qp.set_d(X, X, 50);
qp.set_d(Y, Y, 2);

а как насчет "45*x*y"?

И как добавить это ограничение "(25 + y) + 25*x ‹= 1" На мой взгляд, так, но я не уверен с 25:

qp.set_a(X, 0, 25);
qp.set_a(Y, 0, 1);
qp.set_b(0, 1);

Одним из решений должно быть обновление функции до такой формы: "y + 25*x ‹= -24"

qp.set_a(X, 0, 25);
qp.set_a(Y, 0, 1);
qp.set_b(0, -24);

(Пожалуйста, поправьте меня, если я ошибаюсь)

Буду благодарен за любые советы, особенно по проблеме "45*x*y".


person Pavel Sedlář    schedule 19.04.2018    source источник


Ответы (1)


Ваш подход с заменой "(25 + y) + 25*x ‹= 1" на "y + 25*x ‹= -24" очевидно правильный.

Для целевой функции попробуйте:

qp.set_d(X, Y, 90);

но ваша матрица D:

25     22.5
22.5    1

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

person Anton Malyshev    schedule 19.04.2018
comment
Я использовал плохой пример примера (приношу извинения за это), а именно, сумму большего количества уравнений этой формы: (4 * X + 3Y) ^ 2 -> 16 * X ^ 2 + 24 * X * Y + 9Y ^ 2 и т. д.. Это уже положительно полуопределенное, верно? :] - person Pavel Sedlář; 19.04.2018
comment
Спасибо, приятель, ты мне очень помог, кстати: есть ли способ получить значения параметров в формате с плавающей запятой, а не в целом? - person Pavel Sedlář; 19.04.2018
comment
Пожалуйста, примите / проголосуйте за ответ, если он помог. Не уверен, как изменить тип данных решателя с int, но как насчет чисто математического решения - переформулировать задачу с помощью масштабирования: x_new = x * 10^k для достаточно большого k, например x_new = x * 100000?.. - person Anton Malyshev; 20.04.2018
comment
Я уже сделал это, но у меня есть другая проблема, я не знаю, как получить также отрицательные значения в параметрах (только ноль и больше, но это не лучшее решение, если вы понимаете), вы делали что-то подобное раньше? - person Pavel Sedlář; 20.04.2018
comment
Не должно быть проблем с передачей отрицательных значений - person Anton Malyshev; 20.04.2018
comment
В соответствии с этим 3a^2 + b^2 +2ab + a+ 6b + 2 в wolfram alpha значения равны (5/4, -17/4), но когда я пишу это в такой код: qp.set_d(0, 0, 6); qp.set_d (1, 1, 2); qp.set_d(1, 0, 2); qp.set_c(0, 1); qp.set_c(1, 6); qp.set_c0(2); и вывод равен 0, 0 - person Pavel Sedlář; 20.04.2018
comment
(Кстати: похоже, что 2xy равно set_d(y, x, 2), потому что я получаю лучшие результаты в другом уравнении:]) - person Pavel Sedlář; 20.04.2018
comment
Это интересно, они указывают, что вы должны передать 2D-матрицу в документах. Вероятно, из-за формулировки целевой функции 1/2‹x, Dx› + ‹c, x›, где ‹ , › — скалярное произведение. - person Anton Malyshev; 20.04.2018
comment
OK. Благодарю. И вы пробовали формулу выше для результата? Может быть, я делаю что-то не так, не могли бы вы дать мне правильный код для получения правильных результатов, пожалуйста? Я имею в виду, чтобы получить результаты выше, а не нули. ;) - person Pavel Sedlář; 20.04.2018
comment
А как насчет qp.set_d(0, 0, 6); qp.set_d (1, 1, 2); qp.set_d(0, 1, 4); qp.set_c(0, 1); qp.set_c(1, 6);? Также попробуйте qp.set_d(0, 0, 6); qp.set_d (1, 1, 2); qp.set_d(0, 1, 2); qp.set_d(1, 0, 2); qp.set_c(0, 1); qp.set_c(1, 6); - person Anton Malyshev; 20.04.2018
comment
Первый ответ правильный. ;-) Определенно последний вопрос: умеете ли вы извлекать только значения переменных? - person Pavel Sedlář; 22.04.2018
comment
@PavelSedlář, что вы подразумеваете под извлечением только значений переменных? - person Anton Malyshev; 23.04.2018
comment
Обычно я получаю это: status: OPTIMAL objective value: 8/1 variable values: 0: 2/1 1: 3/1 и мне нужны только значения переменных, например, в этой форме [4.2, 3.45878, 5.2365 и т. д.] - person Pavel Sedlář; 23.04.2018
comment
В этом случае я бы проанализировал вывод, используя perl/bash/awk. - person Anton Malyshev; 23.04.2018
comment
Привет чувак, это снова я. Есть ли возможность настроить количество итераций для более быстрого получения некоторых результатов? Спасибо,. ;) - person Pavel Sedlář; 11.05.2018
comment
к сожалению ничего подобного не нашел - person Anton Malyshev; 11.05.2018
comment
Хорошо, а знаете ли вы другую библиотеку оптимизации для квадратичного программирования? Когда у меня есть 3000 параметров + 9000 ограничений, это занимает слишком много времени (6 часов в 340 итерациях и не останавливается) - person Pavel Sedlář; 11.05.2018
comment
На рынке есть действительно хорошее программное обеспечение, такое как Xpress, CPLEX, не уверен насчет бесплатной версии. - person Anton Malyshev; 11.05.2018
comment
Здравствуйте, у меня к вам два последних вопроса. 1. Программа qp (CGAL::SMALLER, ложь, 0, ложь, 0); // МЕНЬШЕ означает минимизировать функцию или есть что-то еще? Что произойдет, если я изменю МЕНЬШЕ на БОЛЬШЕ/БОЛЬШЕ 2. Есть ли возможность добавить начальные точки к параметрам, откуда может начаться оптимизация? как в палладе? github.com/latture/pallas-solver :) - person Pavel Sedlář; 15.05.2018