Quadratic-​Equation-C​onstrained Optimization

Dear all,

I am trying to solve a bilevel optimization as follows,

I then transformed the lower-level optimization with KKT conditions and obtained a new optimization problem:

The toughness is the constraint . I am wondering whether there exists a solver that can efficient deal with this constraint?

Thank you all in advance.

Answer 1

[Bruno Luong]

There is

https://www.mathworks.com/help/optim/ug/coneprog.html

but only for linear objective function.

You migh iterate on by relaxing succesively the cone constraint and second order objective like this

while not converge
   x1 = quadprog(...) % ignoring tau change (remove it as opt variable)
   x2 = coneprog(...) % replace quadratic objective (x2'*H*x2 + f'*x2) by linear (2*x1'*H + f')*x2
until converge

Otherwise you can always call FMINCON but I guess you already know that?

[Yize Wang]

Hi Bruno, Thank you for your answer. I assume the toughness results from the complementary slackness, but the coneprog does not seem to deal with this since μ should also be part of the decision variable. Am I right about this?

[Bruno Luong]

If you set the decision variables of coneprog() as a long vector of

X = [tau; x; mu; lambda]

Thus, the tau index is 1:n;

The x index is n+(1:n);

The mu index is 2*n+(1:n).

If the matrix Asc is defined with Asc(i,j) has value 1 for (i,j) == (n+k,2*n*k) for k=1,...n; and 0 elsewhere

Then

X'*Asc*X = dot(tau,x).

If you set bsc, dsc, gamma = 0, the cone constraint becomes

dot(mu,x) = 0

This is exactly what you want.

[Yize Wang]

Thanks a lot!

[Johan Löfberg]

Late to the game here, but the discussion above is not correct. A constraint of the form mu'*x=0 is nonconvex and cannot be represented using second-order cones. If that was the case, P=NP as it would allow us to solve linear bilevel programming problems in polynomial time, as these can be used to encode integer programs...

It appears the discussion confuses x'*Asc*x == 0 (a nonconvex quadratic constraint) and the generation of a SOCP constraints ||Asc*x + 0|| <= 0 + 0*x (note the linear operator inside the norm)