Search code examples
mathematical-optimizationcvxpy

How do I make a ranged constraint in CVXPY?


I want to minimize the change between two vectors using CVXPY, but I get a DCPError:

import cvxpy as cv


proposed_vector = cv.Variable(100)
prob = cv.Problem(
    cv.Minimize(
        # guess_vector is my initial starting vector of length 100
        cv.sum(cv.abs(proposed_vector - guess_vector))
    ),
    [
        cv.abs(proposed_vector) <= 0.01, # all elements need to be <= 0.01
        cv.sum(proposed_vector) == 0,  # sum needs to be zero
        cv.sum(cv.abs(proposed_vector)) <= 2.5,  # abs sum needs to be <= 2.5
        proposed_vector[idx] == 0.,  # idx are particular indices that need to be zero
        cv.sum(cv.abs(proposed_vector)) >= 0.2,  # abs sum needs to be >= 0.2
    ]
)
prob.solve()
>>>
DCPError: Problem does not follow DCP rules. Specifically:
The following constraints are not DCP:
0.2 <= Sum(abs(var1958311), None, False) , because the following subexpressions are not:
|--  0.2 <= Sum(abs(var1958311), None, False)

The issue is with the last constraint, cv.sum(cv.abs(proposed_vector)) >= 0.2,. Basically I want the sum of absolute values to be in a range from 0.2 to 2.5, but I am not sure how to code this, as chain expressions are not allowed in CVXPY:

0.2 <= cv.sum(cv.abs(proposed_vector)) <= 1.2

Is there a way to encode this constraint, even by making the problem DQCP or some other way?


Solution

  • cvxpy is for convex problems only. But something like

      abs(x) >= a
    

    is not convex. You can linearize this using extra binary variables. E.g.

       abs(x) >= a 
    
           <=>
    
       xplus - xmin = x
       xplus + xmin >= a
       xplus <= M*δ
       xmin <= M*(1-δ)
       xplus,xmin >= 0
       δ ∈ {0,1}  
    

    This is now convex as the relaxations are convex. We have moved the problematic part into the binary variable.

    Note that abs(x) <= b is easier. That is convex, and cvxpy will allow that directly.