zbMATH — the first resource for mathematics

The theory of discrete Lagrange multipliers for nonlinear discrete optimization. (English) Zbl 0965.90051
Jaffar, Joxan (ed.), Principles and practice of constraint programming - CP ’99. 5th international conference, Alexandria, VA, USA, October 11-14, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1713, 28-42 (1999).
Summary: In this paper we present a Lagrange-multiplier formulation of discrete constrained optimization problems, the associated discrete-space first-order necessary and sufficient conditions for saddle points, and an efficient first-order search procedure that looks for saddle points in discrete space. Our new theory provides a strong mathematical foundation for solving general nonlinear discrete optimization problems. Specifically, we propose a new vector-based definition of descent directions in discrete space and show that the new definition does not obey the rules of calculus in continuous space. Starting from the concept of saddle points and using only vector calculus, we then prove the discrete-space first-order necessary and sufficient conditions for saddle points. Using well-defined transformations on the constraint functions, we further prove that the set of discrete-space saddle points is the same as the set of constrained local minima, leading to the first-order necessary and sufficient conditions for constrained local minima. Based on the first-order conditions, we propose a local-search method to look for saddle points that satisfy the first-order conditions.
For the entire collection see [Zbl 0929.00071].

90C30 Nonlinear programming
90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods