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

Question

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.

Patentor

Answer 1

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.

Riggall

wait a minute. $x$ and $y$ here are vectors. what do you mean by the log of a vector? – Ulaulah

@Ulaulah in my example, x and y are not vectors. Looking back, my answer should have been a comment because it does not really solve the problem. Furthermore, I am not sure that the set described in the question is a convex set – Riggall

Answer 2

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.

Divinadivination

Answer 3

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]])

Malaguena