Линейное программирование на Python

Я пытаюсь решить следующее уравнение:

maximize x^{T}Ax, где x - это 3 X 1 вектор переменных, которые нужно максимизировать, а A - это 3 X 3 матрица значений.

Итак, в основном x^{T} = [a,b,c], которые следует максимизировать, а A может быть чем-то вроде

A = [ [29, 29, 79], [28, 28, 48], [9, 40, 0 ]]

Может ли кто-нибудь показать мне, как представить это в виде проблемы максимизации с использованием PuLP или другого пакета линейного программирования на Python?

Любая помощь приветствуется. Я новичок в этой области и не знаю, как начать представлять эту формулировку.

До сих пор я пытался использовать CVXPY для моделирования этой функции. У меня есть следующий код, но я вижу ошибку:

    [1] A = np.array([[29,29,79],[28,28,48],[9,40,0]])
    [2] x=Variable(3)
    [3] objective=Minimize(x.T*A*x)
     Warning: Forming a nonconvex expression (affine)*(affine).
  warnings.warn("Forming a nonconvex expression (affine)*(affine).")
    [4] constraints=[0<=x,x<=1,sum_entries(x)==1] #what I'm trying to say is each entry of x should be between 0 and 1 and all entries should add up to 1.
    [5] prob = Problem(objective, constraints)
    [6] prob.solve()
    DCPError: Problem does not follow DCP rules.

python optimization linear-programming pulp
person Nikhil    schedule 08.06.2016    source источник
comment
Не для всех вопросов нужен код, но в этом случае это больше похоже на то, что вы просто сбросили вопрос и надеетесь, что кто-то напишет решение за вас. На самом деле это не вопрос программирования, это математический вопрос. Вам нужно иметь элементарное понимание Python, прежде чем любой ответ здесь может вам помочь.   -  person Adam Smith    schedule 08.06.2016
comment
Да, у меня более чем элементарное понимание Python. Я просто хотел бы, чтобы кто-то указал мне в правильном направлении в том, что касается примера или чего-то подобного, поскольку мне совершенно не хватает какого-либо понимания области оптимизации или линейного программирования и соответствующих пакетов в python.   -  person Nikhil    schedule 09.06.2016
comment
Похоже, вам нужен учебник, потому что это проблема XY. Ваш настоящий вопрос, похоже, заключается в том, как мне выполнить линейное программирование на Python, который кажется слишком широким. Быстрый поиск в Google показал это руководство по PuLP, которое может вам помочь.   -  person Adam Smith    schedule 09.06.2016
comment
@AdamSmith Я это уже видел. Но, похоже, они не работают с квадратичными членами в целях, которые у меня есть в моей целевой функции.   -  person Nikhil    schedule 09.06.2016

Ответы (1)


arrow_upward
0
arrow_downward

Я не верю, что PuLP поддерживает квадратичное программирование (QP). Ваша модель является квадратичной, а PuLP предназначен только для моделей линейного программирования (LP и MIP). Есть довольно много вариантов выражения QP в Python. Высокопроизводительные коммерческие решатели часто предоставляют привязки Python, в противном случае вы можете посмотреть, например, CVXOPT. Обратите внимание, что «легко» решить только выпуклые КП. Если у вас невыпуклый QP, все становится намного сложнее, и вам может потребоваться глобальный решатель (таких решателей не так много). Невыпуклые QP могут быть переформулированы с помощью условий KKT как линейная модель MIP, хотя эти модели не всегда могут работать очень хорошо.

person Erwin Kalvelagen    schedule 08.06.2016
comment
спасибо за вклад. В настоящее время я использую cvxpy.org/en/latest, но вижу ошибку когда я пытаюсь ввести следующую целевую функцию: A = np.array([[29,29,79],[28,28,48],[9,40,0]]) objective=Minimize(x.T*A*x) Я вижу ошибку Forming a nonconvex expression (affine)*(affine). warnings.warn("Forming a nonconvex expression (affine)*(affine)."). Есть идеи, как я могу это исправить? Или что делаю не так? - person Nikhil; 09.06.2016
comment
Cvxopt предназначен для выпуклых задач, и кажется, что вы пытаетесь передать невыпуклую задачу. - person Erwin Kalvelagen; 09.06.2016
comment
Хм, верно, но я не понимаю, является ли проблема невыпуклой по своей природе или я могу изменить представление целевой функции, чтобы сделать его выпуклым? То есть могу ли я как-то переформулировать проблему, чтобы сделать ее выпуклой? @erwinkalvelagen - person Nikhil; 09.06.2016
comment
1. Зависит от данных в матрице Q, 2. Если вы знаете, как это сделать, возможно, вас ждет Нобелевская премия. - person Erwin Kalvelagen; 09.06.2016
comment
:) ха-ха, понятно, понял. О какой Q-матрице вы имеете в виду? - person Nikhil; 09.06.2016
comment
Все пишут x'Qx. Это обычное обозначение. Вам, вероятно, стоит почитать об этом. - person Erwin Kalvelagen; 09.06.2016