Combinatorial structures in nonlinear programming
Nonconvexity in optimization problems can occur in two ways,
analytically through mixed curvature in smooth functions, and
structurally, through the use of combinatorial selections, operationalised
through "if" statements or finite "max" and "min" operations involving
otherwise smooth selection functions. The existing NLP framework caters
well for the analytic nonconvexity but is less suited to deal with the
structural nonconvexity induced by combinatorial selections, not least
since the latter induces the added complication of nonsmoothness. The lack
of interest in such problems is surprising, given the multitude of
practical problems which involve such functions.
We will give several examples of structurally nonconvex functions and
explain why smooth reformulations of the resulting NLPs will typically be
of limited use since they violate vital constraint qualifications. We
suggest an extension of NLP theory and methods to optimization problems
which involve such combinatorial, structurally non-convex, functions. Our
approach is simple and avoids the use of heavy nonsmooth analysis
machinery. We show that the familiar SQP algorithm can be extended to this
more general framework and that it maintains its local quadratic
convergence properties. We close with an outline research agenda for this
new area.
Chemnitz Workshop
Last modified: Thu Jul 8 20:00:00 CEST 2004