Solutions and optimality criteria to box constrained nonconvex minimization problems. (English) Zbl 1171.90504

Gao, David Yang

J. Ind. Manag. Optim. 3, No. 2, 293-304 (2007).

Summary: This paper presents a canonical duality theory for solving nonconvex polynomial programming problems subjected to box constraints. It is proved that under certain conditions, the constrained nonconvex problems can be converted to the so-called canonical (perfect) dual problems, which can be solved by deterministic methods. Both global and local extrema of the primal problems can be identified by a triality theory proposed by the author. Applications to nonconvex integer programming and Boolean least squares problems are discussed. Examples are illustrated. A conjecture on NP-hard problems is proposed.

MSC:

90C26	Nonconvex programming, global optimization
49N15	Duality theory (optimization)
49M37	Numerical methods based on nonlinear programming
90C20	Quadratic programming

Keywords:

global optimization; duality; integer programming; Boolean least squares problem; NP-hard problems