Least Squares in Python Anaconda

[hyp...@gmail.com]

Dear all,

I installed Gurobi via Anaconda on Python 3.5, and just to learn how it works, I tried to solve a simple least squares problem without constraints. ||Ax -b||**2

Given are mxn matrix A and target-vector b with length m, and I just want to calculate the optimal x. This can be easily done in Numpy and Scipy (in fact A and b are Numpy arrays), however, I want to understand the gurubi Python syntax for this simple case before I add quadratic constraints in the next step.

I started with 

m = Model("test")

m.addVar(vtype=GRB.CONTINUOUS, name='w')

How would I add the matrix as a parameter? Can I use or convert the Numpy arrays directly?

Thank you

[Troy Long]

Disclaimer: I'm not a Gurobi expert (and there are others on this forum who are better-equipped to answer this question). Moving on.

You might want to try solving a more symbolically-motivated problem to learn Gurobi  + python than least squares. The problem you want to solve is the following:

min z'Qz

s.t. z = Ax-b

where Q is the identity matrix. What you'll do is generate objects for each variable x and z (using "addVar"), then generate constraints using "addConst" to build the association between z and x. Then you can set the objective to the sum of squares of z. That being said. Gurobi is most likely not going to beat numpy/scipy on solving this type of heavily-structured problem. 

Check out the example tour in the documentation for example code on how to do each of these. You'll be able to use list comprehension to make it easier.

**I'm just typing this code off the top of my head..so it might not be the "best" way to do it**

from gurobipy import *

import numpy as np

m = 60

n = 30

A = np.random.rand(n, m)-0.5

b = np.random.rand(m) - 0.5

mod = Model()

# build variables

z = [mod.addVar(lb=-GRB.INFINITY) for j in range(m)]

x = [mod.addVar(lb=-GRB.INFINITY) for i in range(n)]

# update model with variable changes

mod.update()

# build constraints

zDefConst = [mod.addConstr(z[j],GRB.EQUAL,quicksum([A[i,j]*x[i] for i in range(n)])-b[j]) for j in range(m)]

# build objective

mod.setObjective(quicksum([z[j]*z[j] for j in range(m)]))

# update model with constraints and objective

mod.update()

# execute optimization algorithm

mod.optimize()

# extract x values

bestX = [x[i].X for i in range(n)]

# print the solution

print bestX, mod.objval

[hyp...@gmail.com]

Thank you very much!

Your example works, however, if I change A and b to a complex matrix and vector, respectively, 

A = np.random.rand(n, m)-0.5 + 1j* np.random.rand(n, m)

b = np.random.rand(m) - 0.5 +1j*np.random.rand(m)

I get the following error message: 

GurobiError: Invalid argument to LinExpr multiplication

It seems that the quicksum function does not accept complex numbers?

[Greg Glockner]

> It seems that the quicksum function does not accept complex numbers?

Correct.

[hyp...@gmail.com]

Is there an alternative approach? Or is Gurobi unable to handle complex numbers at all? 

Thank you

[Tobias Achterberg]

Sorry. Gurobi is not able to handle complex numbers.

To be fully precise, it is only able to handle rational numbers, and only if
they can be represented in double precision floating point arithmetics.

Tobias

[hyp...@gmail.com]

I wonder if  the problem can be converted into a real one?  

Does  Gurobi support primal-dual interior point methods? This is where I wanted to get at. I need to solve the stated  least squares problem with quadratic matrix inequality constraints. (all complex matrices)

Thank you very much. 

[Tobias Achterberg]

Yes, Gurobi does have a primal-dual interior point method, the so-called
"barrier method". With this method you can solve *convex* quadratically
constrained programs. This means that you can have a linear or quadratic
objective function, and linear or quadratic constraints, but all quadratic
functions need to be convex (which means that the Q matrices need to be positive
semi-definite).

Tobias

[hyp...@gmail.com]

Indeed, the Q are psd, I made sure of that. The reason I attempt this problem is because I know that it is feasible and solvable, however, I want to verify it myself. 


The only way to do this with the Gurobi solver, is to somehow convert the complex problem into a real one? 




Thank you

[Tobias Achterberg]

Yes, you need to get into the realm of rational numbers.

Tobias