Unexpected infeasibility

Nonconvex
1

Hi,

I am trying to solve an optimization problem (in Matlab) with quadratic constraints. However, I am encountering an unexpected feasibility problem. I am listing a simplified version of the code below:

n=6;
A=10;
w=25;

cvx_begin

    variable x(2.*n);                 
    dual variables constr_0{n} constr_1 constr_2;

    % Quadratic constraint: g'x + x'Hx <=0
    for j=(n+1):(2.*n-1)

        H=zeros(2.*n,2.*n);     
        H(j-n,j-n)=-1;

        g=zeros(2.*n,1);            
        g(j+1)=1;
        g(j)=-1;

        constr_0{j-n}: abs(g'*x) + 2.*quad_form(x,H) <= 0;   

    end

    % equality constraints
    c1=zeros(2.*n,1);                 
    c1(n+1)=1;
    constr_1: c1'*x==A;

    c2=zeros(2.*n,1);                  
    c2(2.*n)=1;
    constr_2: c2'*x==0;                 

cvx_end

When I try to solve this problem, cvx returns an Infeasible problem. This is unexpected since this problem is in fact feasible. For example, the solution

     x=[0,5,10,15,20,25,10,10,6,4,2,0]'

satisfies all constraints in the above problem. I have tried using both SDPT3 and SeDuMi solvers with the same result. Changing the precision (both increase and decrease) also had no effect. Note that one slightly unusual feature of this problem is that H is negative semi-definite (rather than the more common positive semi-definite).

I am a novice at cvx, so any advice would be very much appreciated. Thanks!

2

Actually, if H is negative semidefinite, then CVX should be rejecting this problem altogether, because it is not convex. Would you please submit a bug report to http://support.cvxr.com with the data you are using?

EDIT: Actually, nevermind! I have found the bug that is causing CVX to accept this blindly. In fact, what it’s doing is substituting -H for H. So that is changing the nature of the constraint, and likely rendering it infeasible. Nevertheless, the problem you are trying to solve is not convex and so CVX cannot solve it.

I have updated a fix for this problem to the CVX web site. It’s only urgent if you need to construct concave quadratic forms! Indeed, I am now considering whether it was a good idea to try to make quad_form “intellegent” enough to do the right thing for negative definite H. How hard would it be to require users negate their negative definite matrices? I don’t have negative_semidefinite sets, either… :stuck_out_tongue:

3

Hi Michael,

Thanks very much for the answer! Are you aware of any software that can deal with negative semidefinite constraints?

Thanks again,

   Marshall
4

No, I don’t. Nonconvex quadratic programming is a pretty rich research topic but it is not one I am involved in.