sci.op-research

golabidoon@gmail.com wrote:

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

Ok. I was envisioning using a solver for MIQP (so that the bilinear
constraints would become SOS1, leaving only linear constraints.
>
>> 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.

First time I've seen that assertion. I routinely work with MILPs with
considerably more than 10 binary variables. Making the objective
quadratic rather than linear causes a bit of a performance hit, but I
suspect that you can still go well above 10 complementarity conditions.
It's not going to be as bad as a general MINLP (with a general convex
nonlinear objective). Quadratic is still relatively nice. As always
with BNB, how tight the bounding is and how good a solution you get
early will make a big difference in performance.

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

Sorry, scratch that statement; I forgot momentarily that x appeared in
the inner constraints. What I wrote is untrue in general.

Which brings me back to my normal state of confusion. Are you saying
that the solution x to the outer problem must be optimal for whatever a
that is optimal in the inner problem given that same x? If so, how do
you know a solution exists? One obvious problem is that the merger of
the inner and outer constraints might be infeasible, but even if there
are jointly feasible solutions, you can't be sure a joint optimum
exists. Consider the following pair of problems:

(P1) min x^2 s.t. x >= 3 - a; x <= 1

(P2) min a^2 s.t. a <= 2*x.

If you merge the two constraint sets, you find that x = 1, a = 2 is the
unique combination feasible in both problems. However, the optimal
solution of (P2) with x = 1 is a = 0, not a = 2.


/Paul