Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Does Strong Duality Imply Polynomial Time Solvability? <s> This paper presents a canonical duality theory for solving a general nonconvex quadratic minimization problem with nonconvex constraints. By using the canonical dual transformation developed by the first author, the nonconvex primal problem can be converted into a canonical dual problem with zero duality gap. A general analytical solution form is obtained. Both global and local extrema of the nonconvex problem can be identified by the triality theory associated with the canonical duality theory. Illustrative applications to quadratic minimization with multiple quadratic constraints, box/integer constraints, and general nonconvex polynomial constraints are discussed, along with insightful connections to classical Lagrangian duality. Criteria for the existence and uniqueness of optimal solutions are presented. Several numerical examples are provided. <s> BIB001 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Does Strong Duality Imply Polynomial Time Solvability? <s> We show that simple syntactic expressions such as existential second-order (ESO) universal Horn formulae can express NP-hard optimization problems. There is a significant difference between the expressibilities of decision problems and optimization problems. This is similar to the difference in computation times for the two classes of problems; for example, a 2SAT Horn formula can be satisfied in polynomial time, whereas the optimization version in NP-hard. It is known that all polynomially solvable decision problems can be expressed as ESO universal (Π1) Horn sentences in the presence of a successor relation. We show here that, on the other hand, if P ≠ NP, optimization problems defy such a characterisation, by demonstrating that even a Π0 (quantifier free) Horn formula is unable to guarantee polynomial time solvability. Finally, by connecting concepts in optimization duality with those in descriptive complexity, we will show a method by which optimization problems can be solved by a single call to a ‘de... <s> BIB002
At this time, such a proof (of whether a duality gap of zero implies polynomial time solvability of the primal and the dual problems) appears possible only for very simple problems, since estimating the duality gap appears extremely challenging for many problems. Some of the problems where this is true include Convex Programming (and in particular, Linear Programming), where both the primal and the dual problems are convex; the polynomial time algorithms are derived from interior point methods. For example, see the book by Nesterov and Nemirovskii  . In a recent paper BIB002 , we have demonstrated an additional computational benefit arising from strong duality. Primal-dual problem pairs that are polynomially solvable and obey strong duality can be solved by a single call to a decision Turing machine, that is, a Turing machine that provides a Yes/No answer (if the answer is yes, then it can provide a feasible solution which supports the Yes answer). Previously, it was only known that optimization problems require multiple calls to a decision Turing machine (for example, doing a binary search on the solution value to obtain an optimal solution). For more details, the reader is referred to BIB002 . More investigation is needed to answer the question Does Strong Duality Imply Polynomial Time Solvability? in a general setting. However, there have been some results recently using Canonical duality for certain types of quadratic programs   . Consider a standard quadratic programming (primal) problem: where A = A T ∈ R n×n , b i ∈ R n for 1 ≤ i ≤ m, and x ∈ R n . A is a symmetric matrix. We can write the Lagrangian function as The first order necessary condition among the Karush-Kuhn-Tucker (KKT) conditions yields λ i b i = 0, from which we get the value of x as assuming that A is an invertible matrix. Substituting this value of x back into the Lagrangian function yields We then get a dual problem, the canonical dual P d , as follows: Maximize Q(λ), subject to A ≻ 0 and λ ≥ 0. (The relation A ≻ 0 means the matrix A should be positive definite.) The positive definiteness of A has been found to be a sufficient condition. Whether it is a necessary condition is not known yet. Now, Q(λ) is a concave function, to be maximized in the dual variable λ; hence P d can be solved efficiently, since we are maximizing a concave function. Thus in general, we can get a lower bound for the primal problem quickly; and in some cases, we can get a strong dual with zero duality gap, which provides an optimal solution for the primal problem in polynomial time. Canonical duality was first developed to address the problem of (possibly large) duality gaps in Lagrangian duality in the context of problems in analytical mechanics BIB001 . Furthermore, large duality gaps can also be found while solving non-convex optimization problems using Fenchel-Morrow-Rockafellar duality. The so-called canonical dual transformation can be used to formulate a strong-dual problem (that is, one with a zero duality gap). Quoting from BIB001 , the primal problem can be made equal to its canonical dual in the sense that they have the same KKT points.