Nonconvex structures in nonlinear programming

• 成果类型: Article
• 署名作者: Scholtes, S
• 署名单位: University of Cambridge
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1030.0102
• 发表日期: 2004
• 页码: 368-383
• 关键词: programming; nonlinear; nondifferentiable; COMPLEMENTARITY; mathematics; piecewise linear; combinatorics

摘要

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.