sci.op-research

On Feb 27, 10:22=A0am, Paul Rubin wrote:
> understand the problem, both objectives (inner and outer) are quadratic
> and convex, and all constraints are linear (other than the
> complementarity constraints we introduced). =A0Let me know if I'm wrong th=
ere.

You are right.

> Assuming I'm correct, I don't get what you mean by "only a local optimum
> can be guaranteed". =A0If 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.

The complementarity constraints are not convex (they are disjunctive
constraints). There are ways that you could express their disjunctive
property as some form that can be fed to a NLP solver, e.g:
u>=3D0
a>=3D0
a*u<=3D0

Note that this is equivalent to saying at least one of variables (a,u)
has to be zero (in practice you might want to replace zeros with some
small epsilon for numerical reasons). My point was that the constraint
a*u<=3D0 involves a bilinear term, which is not convex. You might apply
a typical NLP solver directly to this NLP problem, but it can only
guarantee you a local optimum solution due to non-convexity of a*u.
Alternatively, you might use some convex relaxation and then use a
convex solver, but again you have only solved an approximation of the
original problem and the solution is not guaranteed to be equal to the
solution of non-relaxed problem.

> 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.

Your reference to "node relaxation" seems to be referring to a branch
and bound technique (BNB). BNB's are NLP solvers that can guarantee a
global solution (upto a precision tolerance), but still the complexity
of a BNB is exponential in number of variables and in practice it
cannot be used for problems with more than 10 variables. On the other
hand, as you know, typical NLP solvers which take reasonable time use
some sort of local search around an initial guess and hence only
guarantee a local optimum.

> There may be another approach. =A0As 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. =A0In
> particular, I assume that x does not appear in the inner objective
> function and a does not appear in the outer objective function. =A0So 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). =A0Any optimal solution (a*, x*) would
> have to satisfy the two conditions that x* minimized the outer objective
> given a =3D a* and a* minimized the inner objective given x =3D x*.

This is very interesting too, but what if a and x both appear in both
objectives? In fact, I am not curious to know: what is the most
general setting under which you can merge two convex problems to one
(in that way that you said, i.e. adding up their objectives and using
constraints all together in a single problem) and still expect the
optimal solution (a*,x*) of the merged problem to be the optimal
solution of the nested problem?

Thanks

G.D.