Combinatorial structures in nonlinear programming

Dr Stefan Scholtes
Traditional optimisation theory and -methods on the basis of the Lagrangian function do not apply to objective or constraint functions which are defined by means of a combinatorial selection structure. Such selection structures can be explicit, for example in the case of "min", "max" or "if" statements in function evaluations, or implicit as in the case of inverse optimisation problems where the combinatorial structure is induced by the possible selections of active constraints. The resulting optimisation problems are typically neither convex nor smooth and do not fit into the standard framework of nonlinear optimisation. Users typically treat these problems either through a mixed-integer reformulation, which drastically reduces the size of tractable problems, or by employing nonsmooth optimisation methods, such as bundle methods, which are typically based on convex models and therefore only allow for weak convergence results. In this talk we argue that the classical Lagrangian theory and SQP methodology can be extended to a fairly general class of nonlinear programs with combinatorial constraints. The paper is available at
  • Computational Mathematics and Applications Seminar