Python Linear Programming

Question

I am trying to solve the following equation:

maximize x^{T}Ax where x is a 3 X 1 vector of the variables to be maximized and A is a 3 X 3 matrix of values.

So basically x^{T} = [a,b,c] which are the unknowns to be maximized and A could be something like

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

Could someone show me how to represent this in the form of a maximization problem using PuLP or some other linear programming package in python?

Any help would be much appreciated. I am extremely new to this area and have not idea how to get started representing this formulation.

I have so far tried to use CVXPY to model this function. I have the following code but am seeing an error:

    [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.

Not all questions need code, but in this case it looks more like you just dumped the question and are hoping someone writes the solution for you. This isn't actually a programming question, it's a math question. You need to have a rudimentary understanding of Python before any answer here might help you. — Adam Smith
Yes I have more than a rudimentary understanding of python. I'd just like someone to point me in the right direction as far as an example or some such thing is concerned as I completely lack any sort of understanding of the field of optimization or linear programming and the corresponding packages in python. — Nikhil
Sounds like you need a tutorial, because this is an XY problem. Your real question seems to be "How do I perform linear programming in Python" which appears Too Broad. A quick google search turned up this tutorial about PuLP which might help you. — Adam Smith
@AdamSmith I've seen that already. But they don't seem to be working with quadratic terms in the objective which is what I have in my objective function. — Nikhil

Erwin Kalvelagen Erwin Kalvelagen · Accepted Answer · 2016-06-08T22:07:27

I don't believe PuLP supports quadratic programming (QP). Your model is quadratic and PuLP is only for linear programming models (LPs and MIPs). There are quite a few options to express QPs in Python. High performance commercial solvers often provide Python bindings, and otherwise you can look at for example CVXOPT. Notice that only convex QPs are "easy" to solve. If you have a non-convex QP things become much more difficult and you may need to look at a global solver (there not as many of those type of solvers). Non-convex QPs can be reformulated via the KKT conditions as a linear MIP model, although these models may not always perform very well.

Python Linear Programming

1 Answers