sci.op-research

Hi Paul,

Thank you for the clarification, I now understand your idea. I googled
about "complementarity constraints" and gained some shallow knowledge.
It seems that problems with such constraints cannot be solved
efficiently because of combinatorial flavor of the constraints.

I think a naive approximation would be to write a complementarity
constrain between u and a as a>=3D0, u>=3D0 a*u<=3D0 (or a*unumerical reasons) and then replace a*x with convex envelope of the
bilinear term.

I also found a paper titled "A semidefinite programming heuristic for
quadratic programming problems with complementarity constraints",
which seems to be more efficient than my naive bilinear relaxation
idea.

I would be very thankful if someone who knows about complimentarity
constraints could confirm or correct my understanding about hardness
and lack of any efficient method for solving it.

P.S. Enumeration of all posibilities is not an option due to the large
number of variables and exponential growth of possibilities in # of
variables.

Thanks

G.D.


On Feb 26, 9:48=A0am, Paul Rubin wrote:
> golabid...@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>=3D0
>
> > 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=3D0
>
> Change u*a to just u here.
>
> > a>=3D0
> > u>=3D0
> > a*u=3D0
>
> > Now say the outer problem is Min (x^2+x) s.t. x>=3Da
> > So I get:
> > Min(x^2+x)
> > x>=3Da
> > 2*c_1*a+c_2-u*a=3D0
>
> Again, u*a becomes u.
>
> > a>=3D0
> > u>=3D0
> > a*u=3D0
>
> > 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. =A0So 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 >=3D 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. =A0I'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). =A0Honestly, though, I tend to tune out
> when I see the word "complementarity", so someone else would be better
> positioned to expand on that. =A0All else failing, and assuming you don't
> have a lot of these conditions, you can try all combinations. =A0In the
> simple example here, first set u =3D 0 and try to solve the reduced
> problem (for x and a), then set a =3D 0 and try to solve what's left for x=

> and u. =A0Note that either problem could be infeasible. =A0For instance,
> when you set u =3D 0, the equation constraint becomes c_1*a + c_2 =3D 0. =
=A0If
> the solution to that has a < 0, that version of the problem is infeasible.=

>
> /Paul