sci.op-research

golabidoon@gmail.com wrote:
> Using first order necessary condition of the inner problem as an
> equality constraint for the outer problem is an interesting idea.
> However, I do not understand how to handle the daul variables. Let's
> go over a simple inner problem with only one variable (a):
> Min (c_1*a^2+c_2*a) s.t. a>=0
>
> where c_1 and c_2 are constant and c_1>0 to guarantee convexity.
>
> Now writing the KKT conditions gives:
> 2*c_1*a+c_2-u*a=0

Change u*a to just u here.

> a>=0
> u>=0
> a*u=0
>
> Now say the outer problem is Min (x^2+x) s.t. x>=a
> So I get:
> Min(x^2+x)
> x>=a
> 2*c_1*a+c_2-u*a=0

Again, u*a becomes u.

> a>=0
> u>=0
> a*u=0
>
> The variables here are both a and x. However, what should I do with
> the dual variable u? For example, if I want to feed this to a QP
> solver, how should I represent the u?

As just another variable. So you now have a problem with three
variables (a, x, u), one equality constraint, one inequality constraint,
one complementarity constraint and explicit sign restrictions on two of
the variables (implicitly x >= 0 as well).

> Do solvers have an option to
> explicitly define a dual variable like u besides the main variables x
> and a?

To the solver, it's not a "dual" variable, it's just another variable.

The complementarity constraint may be a problem. I've seen posts here
(I think) about solving complementarity problems, and it seems to me
that AMPL, for instance, has added some capabilities there (not sure
which solvers can exploit them). Honestly, though, I tend to tune out
when I see the word "complementarity", so someone else would be better
positioned to expand on that. All else failing, and assuming you don't
have a lot of these conditions, you can try all combinations. In the
simple example here, first set u = 0 and try to solve the reduced
problem (for x and a), then set a = 0 and try to solve what's left for x
and u. Note that either problem could be infeasible. For instance,
when you set u = 0, the equation constraint becomes c_1*a + c_2 = 0. If
the solution to that has a < 0, that version of the problem is infeasible.

/Paul