sci.op-research

golabidoon@gmail.com wrote:
> Thank you for connecting complementarity constraints to a larger class
> for which solvers exist. The combinatorial nature still remains though
> and only a local opitmum can be guaranteed unfortunately.
>
> About your second question, you are right, I mistakenly gave an over
> simplified specification of my problem. In fact, the inner problem
> involves x_i's, but x_i's are treated as constants there and
> optimization happens only with respect to a_k's. Although I gave a
> wrong specification, your idea was general enough to capture that and
> so we are on the right track. Your hints about optimality conditions
> of the inner problem and the issue of complementarity were very
> helpful.
>

Ok, with that I agree that simultaneous optimization, finessing one of
the objective functions with first order conditions, makes sense. As I
understand the problem, both objectives (inner and outer) are quadratic
and convex, and all constraints are linear (other than the
complementarity constraints we introduced). Let me know if I'm wrong there.

Assuming I'm correct, I don't get what you mean by "only a local optimum
can be guaranteed". If the constraints are linear and the outer
objective is convex, any local optimum to the merged problem that meets
the complementarity conditions will be a global optimum.

I withdraw my earlier expression of concern regarding the bounding.
With all the complementarity conditions converted to SOS1 constraints,
the node relaxation will be a QP with some of the SOS1 constraints
relaxed, so it should produce a decent bound I think.

There may be another approach. As I (now) understand this, a solves a
QP (quadratic objective, linear constraints, I'll assume minimization)
in which x appears as constraint limits, and x solves another QP
(quadratic objective, linear constraints, and I'll again assume
minimization) in which the a appear as constraint limits. In
particular, I assume that x does not appear in the inner objective
function and a does not appear in the outer objective function. So you
could merge the constraints of the two problems (treating both a and x
as variables), and minimize a weighted sum of the objective functions
(which would again be quadratic). Any optimal solution (a*, x*) would
have to satisfy the two conditions that x* minimized the outer objective
given a = a* and a* minimized the inner objective given x = x*.

This sounds too easy, so perhaps I'm still misunderstanding something.

/Paul