Guessing variable bounds for NLP
aquadoll
Is anyone aware of any research on setting variable bounds for unbounded
variables in a general NLP?
The context is as follows: I have noticed that there are algorithms like
projected gradient (PG) etc. for solving bound constrained problems, but
a requirement (I think) is that all the variables should have bounds. On
the other hand, we often face problems where some of the variables have
UB, some have LB and some have none. Are there any algorithms like PG,
which deal with these kind of problems? Or, are there modifications to
the PG algorithm which does this? If not, my original question would
help me put bounds on these variables, and then I can use the PG scheme.
Thanks.
Paul
It's been a long time since I did NLP, so I can't trust my memory, but
I don't recall the gradient projection method requiring bounded
variables, so long as the feasible region contains no recession
directions along which the objective improves forever.
In any event, if an algorithm does require bounded variables, and if
the problem is to minimize a convex objective function (or maximize a
concave objective function) over a convex feasible region, you should
be able to assert arbitrary bounds on each variable. If the algorithm
converges to a solution hitting one or more of your arbitrary bounds,
extend those bounds and resume iteration. You're imposing an
arbitrary hyperrectangle on the feasible region. If the true optimum
is inside the hyperrectangle, all is well. If it is outside the
hyperrectangle, the optimum for the over-constrained problem should be
on the boundary of the hyperrectangle (by convexity), in which case
you just shift the hyperrectangle to move that point into the interior
and iterate.
/Paul
A.L.
aquadoll
Thanks for all the replies.
Pual: I wasn't really thinking about convex programming problems, was
more concerned about the general non-convex approach. I will take a
closer look at the gradient projection however.
A.L.: Thanks for the link - that would seem to be a really useful one
for general NLP's. I will go through the theory and look at what is
being done.
Regards.
Leo Liberti
> Hello,
> Is anyone aware of any research on setting variable bounds for unbounded
> variables in a general NLP?
In the context of the spatial Branch-and-Bound (sBB) algorithm for
nonconvex NLPs and MINLPs there's two devices for tightening ranges
(including those that are set at [-infty, infty], although I never
tested them on problems where NO variable range was given):
Optimization Based Bounds Tightening (OBBT) and Feasibility-Based
Bounds Tightening (FBBT). The first is more costly and more efficient,
and is usually only done at the root node (or rarely). The second is
less efficient but (usually) much faster and can be carried out at
each sBB node.
Most sBB-related papers describe OBBT and FBBT. You can see
http://www.lix.polytechnique.fr/~liberti/couenne.pdf
http://www.lix.polytechnique.fr/~liberti/globoptsoftware.pdf
but also works by Sahinidis and Tawarmalani on BARON, Floudas et al.
on alphaBB, and others.
Ciao
Leo
aquadoll
Hello,
Did not see this reply. I think my sense of the question was different
than what you are suggesting. If I understand the papers in your links
correctly, these deals with algorithms for finding strong bounds for an
objective function (for use in node-pruning etc. in a branch-bound type
scenario). I am specifically looking for bound tightening algorithms on
variables in an optimization problem - and these are not in the same
context.
Thanks.