1
$\begingroup$

I have the underdetermined outer optimization problem $$\text{min}_{x\geq 0}\quad \|Ax-b_1\|_2^2+\|AT(x)-b_2\|_2^2$$ with $A\in\mathbb{R}^{m\times n}$ and $m<<n=64^2$ or in corresponding CVX Matlab code

variable x(n) nonnegative
minimize(sum( (A*x-b1).^2 + (A*T(x,p1,p2,p3,p4,p5)-b2).^2 ))

where p1,...,p5 are fixed parameters required by the function T. Inside T there is another linear minimization problem $$\begin{aligned}\text{min}_{c,q} \quad &1^\top q&\\\text{s.t.}\quad&Dc-x \leq q\\-&Dc-x \leq -q\end{aligned}$$ with $D\in\mathbb{R}^{n\times n}$ or in Matlab syntax

function value = T(x,p1,p2,p3,p4,p5)
... something happens ...
cvx_begin
    variable c(n)
    variable q(n)
    minimize sum(q)
    subject to
        D*c-x <= q
        -D*c-x >= -q
cvx_end
... something else happens and calculates return value ...

Unfortunately I get the error

Undefined function 'newcnstr' for input arguments of type 'cvx'.

Error in cvx/lt (line 22)
b = newcnstr( evalin( 'caller', 'cvx_problem', '[]' ), x, y, '<' );

after the cvx_end line in the function T.

I encountered this error several times before when dealing with other problems, but this time I cannot replace the outer optimization with a build in Matlab function, since fmincon is far to slow. Replacing the inner problem by linprog is too slow as well, unfortunately.

Is it possible to nest CVX optimization problems like that? If yes, how? Are there any other ideas what I could try?

$\endgroup$
1
$\begingroup$

Is it possible to nest CVX optimization problems like that? If yes, how?

I don't think you can, no. CVX is designed to model convex programs; as such, it cannot model nonconvex programs (but could model their convex relaxations). In general, the bilevel linear programming case can yield a nonconvex feasible set (see this presentation by Chris Fricke, slides 40-44), which would make it impossible for CVX to solve these correctly, so this construction is probably not allowable for CVX.

Are there any other ideas what I could try?

In order to try other ideas, it would help to know if $T$ is a smooth function.

$\endgroup$
0
$\begingroup$

Sorry if my comment is way too late but I just joined this community.

You may consider Bender's decomposition or Dantzig-Wolfe decomposition .. I've done similar thing : min {c'x + E [Q(x)]| x>=0}; where Q(x)= min {q'y|Wy =T(x)-d, y>=0}

I was able to solve it efficiently using Bender's decomposition.

Good Luck,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.