CODEWITHSUNDEEP
pythonpython-2.7mathematical-optimizationconvex-optimizationcvxpy
Creator
Creator

Reputation: 43

How to create an inequality constraint on the inner product of two columns in CVXPY?

Suppose my constraint is the product of the first column and third column of the matrix variable is greater than one. How can I implement in CVXPY? Example:

w = Variable(4,3)

In Matlab, my constraint would be:

w(:,1)'*w(:,3)>1

How can I implement it in CVXPY? Or can we perform dot product under CVXPY? numpy.dot is not supported by CVXPY.

Upvotes: 5

Views: 4017

Answers (3)

Rodrigo de Azevedo
Rodrigo de Azevedo

Reputation: 1145

You have a strict inequality constraint on the northeast entry of the Gram matrix Q := W.T * W, which is symmetric and positive semidefinite. Hence, do work with Gram matrix Q instead and then introduce the strict inequality constraint Q[0,2] > 1.

For example, here's a semidefinite program (SDP) with zero objective:

>>> from cvxpy import *
>>> Q = Semidef(3)
>>> objective = Minimize(0)
>>> constraints = [ Q[0,2] > 1 ]
>>> prob = Problem(objective,constraints)
>>> prob.solve()
0.0
>>> Q.value
matrix([[  2.33101529e+00,   2.57980002e-30,   1.76709537e+00],
        [  2.57980002e-30,   2.57740598e-15,  -2.00304682e-30],
        [  1.76709537e+00,  -2.00304682e-30,   2.33101529e+00]])

Note that the northeast entry is 1.76709537e+00 > 1. To recover matrix W from Gram matrix Q, use the Cholesky decomposition and append a row of zeros to obtain a 4 x 3 matrix, as follows:

>>> import numpy as np
>>> L = np.linalg.cholesky(Q.value)
>>> W = (np.insert(L, 3, np.array([0,0,0]), axis=1)).T
>>> W
matrix([[  1.52676628e+00,   1.68971508e-30,   1.15741053e+00],
        [  0.00000000e+00,   5.07681591e-08,  -7.79768444e-23],
        [  0.00000000e+00,   0.00000000e+00,   9.95698832e-01],
        [  0.00000000e+00,   0.00000000e+00,   0.00000000e+00]])

Let us verify:

>>> W.T * W - Q.value
matrix([[  0.00000000e+00,   0.00000000e+00,   0.00000000e+00],
        [  0.00000000e+00,   0.00000000e+00,   7.00649232e-46],
        [  0.00000000e+00,   7.00649232e-46,   0.00000000e+00]])

Upvotes: 0

Sergey Dovgal
Sergey Dovgal

Reputation: 664

If both variables are positive then the set {x * y > 1} is actually convex, while the function x*y is neither convex nor concave. This can be checked by looking at eigenvalues of matrix of second derivatives

(x*y)'' = 
[[0, 1],
 [1, 0]]

which are {-1, 1}. The matrix is not positive-definite and is not negative-definite.

Sometimes you can transform a problem so that it becomes convex. In this case this is possible by taking a logarithm of both sides:

log(x) + log(y) >= 0

this is a valid restriction because both log(x) and log(y) are concave functions and the inequality is greater-than-or-equal. This constraint will pass the "disciplined convex programming" rules. Good luck.

Upvotes: 4

dave-cz
dave-cz

Reputation: 413

It's not possible to multiply two Variables, all constraints have to be linear (in general DCP).

CVXPY raise DCPError if you try to do a forbidden operation.

import cvxpy
x = cvxpy.Variable()
y = cvxpy.Variable()
constraints = [x*y > 1]

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Python27\lib\site-packages\cvxpy\expressions\expression.py", line 43, in cast_op
    return binary_op(self, other)
  File "C:\Python27\lib\site-packages\cvxpy\expressions\expression.py", line 226, in __mul__
    raise DCPError("Cannot multiply two non-constants.")
cvxpy.error.DCPError: Cannot multiply two non-constants.

You can use slack variable to avoid this if at least one variable is integer/boolean. Otherwise you can use any nonlinear solver e.g. IPOPT.

The same question was answered here.

Upvotes: 3

Related Questions