sci.op-research

If you want to play around with these things easily, you can code these
bi-level problems rather easily as multi-parametric QPs, which you can
solve in MATLAB using YALMIP and MPT

% define variables
sdpvar a x

% define inner problem
inner_objective = a^2;
inner_constraint = a >= 2*x;
region_of_interest = [-10 <= x <= 10];

% solve inner problem parametrically w.r.t x
[temp1,temp2,temp3,Opt_cost,Opt_a] =
solvemp([inner_constraint,region_of_interest],inner_objective,[],x)

% plot the optimizer
plot(Opt_a)

% use parameterized solution in outer problem. this will lead to a
mixed-integer QP since the optimizer Opt_a is piecewise affine
outer_objective = x^2;
outer_constraint = [x >= 3 - Opt_a, x <= 1];

% solve the outer problem
solvesdp(outer_constraint,outer_objective)

% voila
double(Opt_a)
double(x)

download code here
http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php
http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php?n=Solvers.MPT

Note that this high-level approach only is suitable for toy examples.
For larger problems, you should work explicitly with the complementary
conditions, either using a MIPQ approach, or by solving the
complementary conditions using a global nonlinear solver

/johan


golabidoon@gmail.com wrote:
> On Feb 27, 2:03 pm, Paul Rubin wrote:
>> (P1) min x^2 s.t. x >= 3 - a; x <= 1
>>
>> (P2) min a^2 s.t. a <= 2*x.
>
> Let's say (P2) is the inner problem. Since we can obtain closed form
> solution for this simple example, I just do that instead of using
> first order necessary condition.
> We must first solve the inner problem for a and treat x as a
> parameter. We get:
>
> a*=0 if x>=0
> a*=infeasible if x<0
>
> So we only have one feasible candidate. Plug a=0 and x>=0 in the outer
> problem and solve for x. You get " Min x^2 s.t. x>=3, x<=1, x>=0 "
> which is infeasible.
>
> A bit more interesting problem would be obtained if in (P2) "a<= 2*x"
> is replaced by "a>= 2*x". Then you get a*=0 when x<=0 and a*=2*x when
> x>0.
>
> Pluging the first case in (P1) yields infeasible, but for the second
> case we get "Min x^2 s.t. x >= 3 - 2*x; x <= 1 , x>=0" where x*=1 is
> the solution (and so a*=2).
>
> Now let me solve your problem with necessary condition. Returning to
> the inner problem (P2):
> 2*a+u=0
> a <= 2*x
> u*(a-2*x)=0
> u>=0
>
> Adding these constraints to P1 we get
> min x^2 s.t. x >= 3 - a; x <= 1 , 2*a+u=0 , a <= 2*x , u*(a-2*x)=0 ,
> u>=0 . As expected, the feasible set is empty.
>
> Now let's go over my modified P2:
> 2*a-u=0
> a>=2*x
> u*(2*x-a)=0
> u>=0
>
> Adding these constraints to P1 we get
> min x^2 s.t. x >= 3 - a; x <= 1 , 2*a-u=0 , a >= 2*x , u*(2*x-a)=0 ,
> u>=0 .
> The feasible set is only a point x=1, a=2, u=4 and hence x*=1 and
> a*=2, which is equal to what we obtained from closed form solution.
>
> I hope this could clarify the problem.
>
> Thanks
>
> G.D.
>
>
>
>
>