On duality gap with polynomial multipliers for polynomial optimization problems. (2nd January 2023)

• Record Type: Journal Article
• Authors: Chuong, Thai Doan
• Is Part Of: Optimization. Volume 72:Number 1(2023)
• Page Start: 107
• Page End: 134
• Publication Date: 2023-01-02
• Subjects: Non-convex polynomial program -- SOS-convexity -- semidefinite programming relaxation -- sum of squares certificate -- convergent relaxation; 49K99 -- 65K10 -- 90C29 -- 90C46; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2023.2168479
• Languages: English
• ISSNs: 0233-1934

Abstract

Abstract : In this paper, we examine a zero-duality gap with polynomial multipliers between a non-convex polynomial program and its associated generalized Lagrangian dual problem. To this end, we introduce a sum of squares certificate of non-negativity, abbreviated as (SC), that allows us to verify the non-negativity of a polynomial over a feasible set of a system of given polynomials. With the help of (SC), we show that the zero-duality gap with polynomial multipliers coincides with the convergent Lasserre hierarchy of semidefinite programming relaxations. This zero-duality gap with polynomial multipliers reduces to the classical zero-duality gap with constant multipliers when considering it in the setting of SOS-convex polynomial programs or quadratic programs with the hidden convexity. We also show that, in the framework of truncated polynomial systems, the zero-duality gap with polynomial multipliers can be checked via the classical Karush–Kuhn–Tucker condition under an additional convexity condition.