×

Nonconvex structures in nonlinear programming. (English) Zbl 1165.90597

Summary: 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.

MSC:

90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C55 Methods of successive quadratic programming type
90C56 Derivative-free methods and methods using generalized derivatives
PDFBibTeX XMLCite
Full Text: DOI