Error with the following optimization

(jack) #1

Given two vectors v1, v2 of size n=20, I am trying to solve the following

cvx_begin 
    variable x(n);
    variable a1;
    variable a2;
    w_comb = a1 * v1 + a2 * v2;
    maximize( w_comb'*x  ); 
    subject to
        -x_r <= x <= x_r;
        a1 + a2 == 1;
        a1 >= 0; a2 >= 0;
cvx_end

but, I get the following error (Mosek proceeds to solve this as a conic):

Error using cvx/quad_form (line 230)
The second argument must be positive or negative semidefinite.

Error in * (line 261)
[ z2, success ] = quad_form( xx, P, Q, R );

Do I need additional constraints on a1, a2?

(Mark L. Stone) #2

You are violating CVX’s DCP rules by multiplying variables in w_comb by the variable (elements in) x. This is recognized by CVX as an indefinite quadratic form which is neither convex nor concave, hence the somewhat cryptic error message.

Please carefully read Why isn't CVX accepting my model? READ THIS FIRST! .

(jack) #3

Thank you very much!
Is there a way that I could re-formulate the obj. so that it would fit within DCP’s rules?
For instance, I think that w_comb can be written as a constraint: w_comb = V*a where the column entries of the matrix V would be the vectors v1,v2 and a would be a column vector of [a1,a2]'?

Any alternatives would be much appreciated. Thank you.

(Mark L. Stone) #4

That reshuffling doesn’t help anything.

If the weighting factors a1 and a2 were fixed (i.e., input data rather than CVX variables), then this would be a Linear Programming problem. The same holds if x were fixed and a1 and `a2 were allowed to be variables.

Because of the equality constraint a1 + a2 == 1, you could solve a series of problems, one problem for each value of a1 from 0 by 0.01 (or whatever) to 1, then fix a1 and the corresponding value of a2, and solve the CVX problem. Then pick the best solution from among these problems.

(jack) #5

Thank you. Is there an ADMM type of approach, which uses CVX that may fit my problem? Thank you.

(Mark L. Stone) #6

CVX can not be used for non-convex problems, other than for non-convexities which can be handled by binary or integer restrictions.

However, CVX can be used as a DCP convex sub-problem solver within a larger non-convex algorithm. However, each (sub) problem provided to CVX must satisfy its rules.

if you really have a non-convex problem, you may be better off using software designed for such than trying to rig up your own “poor man’s” solver which iterativlely calls CVX.