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

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.


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