Unbounded model with binary variable and exp constraint

1

Hi, I’m a new user and probably the solution of my problem is simple. However, I’m studying a convex model with constraints “b<=g(x)” defined by convex function like:

g(x)=x for x<=1

g(x)=2-e^(1-x) for x>1

so, to make CVX and Mosek solve the problem I needed to use the ‘big M’ approach and to add a binary variable (any suggestion to avoid using exp functions or binary variables?).

I successfully modeled the problem, I think, but CVX says it’s Unbounded. The model is big, but i find that the next code gives also the status Unbounded and Optimal value ‘-Inf’

cvx_begin

    variables x
    
    variable z binary
    
    minimize ( x )
    
    subject to
    
        1<=x;
        
        x<=5*z;
        
        0<=10-exp(-x);

cvx_end

If I comment one or both of the two last constraints CVX gives the right Optimal value 1.
I’m using CVX 2.1 under professional license and mosek academic license, under MATLAB on Windows 32-bit.

UPDATE: If I run the “cvx_version” command and then I run the code, CVX gives me the following error

Function ‘subsindex’ is not defined for values of class ‘struct’.

Error in cvxprob/solve (line 247)
[ x, status, tprec, iters2, y, z ] = shim.solve( [ At, Anew2 ], [ b ; bnew ], c, cones, true, prec, solv.settings,
eargs{:} );

Error in cvx_end (line 88)
solve( prob );

Error in inf_error_test (line 18)
cvx_end

If, then, I run “cvx_setup” together with the path to the cvx_license.dat file, then I came back to the initial situation: status Unbounded and optimal value -Inf

2

I suspect you are encountering a limitation of CVX’s successive approximation method to deal with the exp, namely that it doesn’t work correctly with integer or binary variables - see Optimization problems containing binary variable and CVX reports unbounded status but with viable solution .

MOSEK 9 will natively support the exponential cone, so once MOSEK 9 is released and a version of CVX is released which supports that caability, you might be in luck if you need that combination, which I don’t think you do for this problem.

You wrote g(x)=x for x<=1, but you constrain 1<= x, so that branch is not even used, and there would be no need for Big M modeling of a conditional. Do you want this to work for any value of b? I guess b is a lower bound on x? I presume you didn’t do the correct Big M modeling, and don’t even show b in your program. In any event, you can separately solve 2 problems, both of which have easy solutions not requiring an optimizer, and pick the “best”. If you need help to do the correct Big M modeling, read http://www.fico.com/en/node/8140?file=5125 .

As for the last constraint (branch), which is inconsistent between your description and code, I’ll address the description. b <= 2 - exp(1-x) can be re-written as 1-x <= log(2 - b). This will avoid use of exponential cone in CVX, because log(2 - b) is a constant (I’m assuming b is an input, not a CVX variable), so this is just an affine (linear) constraint.

3

In the original model the constraints of the form "b<=g(x)"are between variables “b” and “x” and the “x” can vary up and down the thresold value defining the function “g(x)” (the function in the first post is only an example of the form of the convex functions that i have to use).

However the following is the original code of my model

[matr_archi_E,matr_archi_U, num_archi, num_tempi, cost_E, obj, cost_F, cost_g]=piccolo_grafo;
[Aeq]=crea_matrice_eq(matr_archi_E,matr_archi_U, num_archi, num_tempi);  

K=1000;
M=num_tempi*num_archi;
lb=zeros(M,1);

cvx_begin
variables x(M+num_archi) b(M) d(M)
variable z(M) binary
minimize ( obj*x );
subject to

        lb<=b;
        lb<=d;
        zeros(M+num_archi,1)<=x;
    
        x(1:M)-cost_g{1}<=K*z;
        
        b<=cost_g{2}.*x(1:M);
        
        b<=cost_g{3}-cost_g{4}.*exp(cost_g{5}.*(x(1:M)-cost_g{1}))+K*(1-z);
        
        Aeq*[x;b;d]==[zeros(M,1);cost_F;cost_E];

cvx_end

Except the variables ‘x’, ‘b’, ‘d’ and ‘z’ the others are all suitable constants that make the problem feasible and bounded. In particular, the functions like ‘g’ are defined by the constants in the arrays of the cell array ‘cost_g’. I (tried) to use the ‘big M’ approach with the 4th and the 6th constraints with the ‘M’=K.
This script also gives back an unbounded status and an otimal value -Inf.

The code in the first post isn’t related very much to the original model: it’s only a way to find a fix by removing all the constraints and the variables that are not involved in the error. If the unbounded status of that (yes, simple and with useless constraints) model cannot be fixed, probably I would not be able to solve the original model.

I’m very sorry because my english is probably bad.

Why does the error change when i run ‘cvx_version’?

5

I don’t know why the error changes when you run cvx_version. You’ll have to wait for someone else to address that.

Do not use binary or integer variables in combination with CVX’s successive approximation method - that combination produces incorrect results, including the possibility of erroneous declaration of the problem being unbounded.

I presume cost_g{4} is >= 0, otherwise your 2nd to last constraint would be non-convex. Given that b is a CVX variable, i don’t see how you can avoid use of CVX’s approximation method (prior to MOSEK 9 with CVX support), except as follows:

Install CVXQUAD https://github.com/hfawzi/cvxquad and the exponential.m replacement for CVX’s version, as discussed at the link. This will invoke CVXQUAD’s Pade Appoximant method and avoid use of CVX’s successive approximation method for certain log and exp related functions (such as entr and rel_entr). But for use of exp as you have, in order for CVXQUAD’s Pade Appoximant method to be invoked instead of CVX’s successive approximation method, I believe you are going to have to re-write the constraint to explicitly use the exponential cone (you can try it first before re-writing, but I think you will have to re-write) using the exponential cone construct
{ x, y, z } == exponential( 1 ) with y = 1,
per mcg;s answer at Solve optimization problems of exp function I don’t know for sure whether the CVXQUAD approach will work correctly when there are binary variables. I have used it only for continuous variable problems and can not test it with binary variables. But I don’t know of any reason why it shouldn’t work correctly. I recommend solving a simple problem first, and then building up to the problem you really want to solve.

I leave you to check that you have done the Big M modeling correctly.

6

It is kind of cool, and also sad, that the only academic mention of CVX’s successive approximation method is in someone else’s paper.

7

Ok! The model can be successfully solved using CVXQUAD. Thank you very much.