This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Scholtes, S. Search for Related Content

Nonconvex Structures in Nonlinear Programming

Judge Institute of Management, University of Cambridge, Cambridge CB2 1AG, United Kingdom
s.scholtes{at}jims.cam.ac.uk

Nonsmoothness and nonconvexity in optimization problems often arise because a combinatorial structure is imposed on smooth or convex data. The combinatorial aspect can be explicit, e.g., through the use of "max," "min," or "if" statements in a model; or implicit, as in the case of bilevel optimization, where the combinatorial structure arises from the possible choices of active constraints in the lower-level problem. In analyzing such problems, it is desirable to decouple the combinatorial aspect from the nonlinear aspect and deal with them separately. This paper suggests a problem formulation that explicitly decouples the two aspects. A suitable generalization of the traditional Lagrangian framework allows an extension of the popular sequential quadratic programming (SQP) methodology to such structurally nonconvex nonlinear programs. We show that the favorable local convergence properties of SQP are retained in this setting and illustrate the potential of the approach in the context of optimization problems with max-min constraints that arise, for example, in robust optimization.

Subject classifications: programming; nonlinear; nondifferentiable; complementarity; mathematics; piecewise linear; combinatorics.
History: Received May 2002; revision received April 2003; accepted May 2003.