← All papers
First page of Formalization of Optimality Conditions for Smooth Constrained Optimization Problems

Formalization of Optimality Conditions for Smooth Constrained Optimization Problems

Chenyi Li, Shengyang Xu, Chumin Sun, Li Zhou, Zaiwen Wen

math.OC Mar 24, 2025 · v1
Formalizes the KKT first-order optimality conditions for smooth constrained optimization in Lean4, including the Farkas lemma and weak duality.
Optimality conditions are central to analysis of optimization problems, characterizing necessary criteria for local minima. Formalizing the optimality conditions within the type-theory-based proof assistant Lean4 provides a precise, robust, and reusable framework essential for rigorous verification in optimization theory. In this paper, we introduce a formalization of the first-order optimality conditions (also known as the Karush-Kuhn-Tucker (KKT) conditions) for smooth constrained optimization problems by beginning with concepts such as the Lagrangian function and constraint qualifications. The geometric optimality conditions are then formalized, offering insights into local minima through tangent cones. We also establish the critical equivalence between the tangent cone and linearized feasible directions under appropriate constraint qualifications. Building on these key elements, the formalization concludes the KKT conditions through the proof of the Farkas lemma. Additionally, this study provides a formalization of the dual problem and the weak duality property.

The first-order (KKT) optimality conditions for smooth constrained optimization had no formal treatment in a type-theory-based proof assistant.

Starting from the Lagrangian and constraint qualifications, the authors formalize geometric optimality via tangent cones in Lean4, establish the equivalence between the tangent cone and linearized feasible directions under suitable constraint qualifications, and conclude the KKT conditions through a proof of the Farkas lemma. They also formalize the dual problem and weak duality.

A reusable Lean4 framework for first-order optimality, covering the KKT conditions for smooth constrained problems, the Farkas lemma, and the weak duality property.