Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Lack of Strong Duality results in NP hardness <s> In continuous variable, smooth, nonconvex nonlinear programming, we analyze the complexity of checking whether(a)a given feasible solution is not a local minimum, and(b)the objective function is not bounded below on the set of feasible solutions. ::: ::: We construct a special class of indefinite quadratic programs, with simple constraints and integer data, and show that checking (a) or (b) on this class is NP-complete. As a corollary, we show that checking whether a given integer square matrix is not copositive, is NP-complete. <s> BIB001 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Lack of Strong Duality results in NP hardness <s> We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems), we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints, which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent convex programs. <s> BIB002 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Lack of Strong Duality results in NP hardness <s> We establish several convexity results which are concerned with nonconvex quadratic matrix (QM) functions: strong duality of quadratic matrix programming problems, convexity of the image of mappings comprised of several QM functions and existence of a corresponding S-lemma. As a consequence of our results, we prove that a class of quadratic problems involving several functions with similar matrix terms has a zero duality gap. We present applications to robust optimization, to solution of linear systems immune to implementation errors and to the problem of computing the Chebyshev center of an intersection of balls. <s> BIB003 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Lack of Strong Duality results in NP hardness <s> Copositive programming is a relatively young field in mathematical optimization. It can be seen as a generalization of semidefinite programming, since it means optimizing over the cone of so called copositive matrices. Like semidefinite programming, it has proved particularly useful in combinatorial and quadratic optimization. The purpose of this survey is to introduce the field to interested readers in the optimization community who wish to get an understanding of the basic concepts and recent developments in copositive programming, including modeling issues and applications, the connection to semidefinite programming and sum-of-squares approaches, as well as algorithmic solution approaches for copositive programs. <s> BIB004
In this section, we will review results from the literature, which show that the lack of strong duality imply that the optimization problem in question is NP-hard, assuming that the primal problem obeys the constraint qualification assumption as stated below in Def. 14. Here we work with Lagrangian duality. Results for other types of duality such as Fenchel, geometric and canonical dualities require further investigation. Let us define what we mean by weak duality (as opposed to tight duality and strong duality): Definition 11. Given a primal problem P 1 and a dual problem P 2 , as defined in Def. 3, the pair (P 1 , P 2 ) is said to obey weak duality if θ(u, v) ≤ f (x), for every feasible solution x to the primal and every feasible solution (u, v) to the dual. Definition 12. In Def. (11), if (i) the inequality is replaced by an equality, and (ii) there exist a primal feasible solutionx and a dual feasible solution (ū,v) such that the equality in (i) holds, then the pair (P 1 , P 2 ) is said to be obey strong duality. The following theorem from  guarantees that the feasible solutions to Lagrangian dual problems (1) and (2) indeed obey weak duality: . If x is a feasible solution to the primal problem in (1) and (u, v) is a feasible solution to the dual problem in (2), then f (x) ≥ θ(u, v). We shall now define a special type of convex program, called a convex program with constraint qualification, which is one with an assumption about the existence of a feasible solution in the interior of the domain. To do. Minimize f (x), subject to g(x) ≤ 0, h(x) = 0 and x ∈ X. Definition 15. Convex program with constraint qualification. Same as the optimization problem in Def. 14, except that we include the following constraint qualification assumption. There is an x 0 ∈ X such that g(x 0 ) < 0, h(x 0 ) = 0, and 0 ∈ int h(X), where h(X) = x∈X h(x). (Note: Of course, the functions above can be written in the same form as in Def. 1 and 2. In such a case, we can define (g(x) − b) to be a convex function and (h(x) − c) to be an affine function, where b ∈ R m 1 and c ∈ R m 2 .) Definition 16. In Def. 14, if any of the (m + 1) functions f (x) : R n → R and g(x) : R n → R m 1 is not convex, then the optimization problem is said to non-convex. For the remainder of this section, we will assume primal constraint qualification; that is, we assume that constraint qualification is applied to the primal optimization problem. The following theorem provides sufficient conditions under which strong duality can occur: Theorem 17. Strong Duality  . If (i) the primal problem is given as in Def. 14, and (ii) the primal and dual problems have feasible solutions, then the primal and dual optimal solution values are equal (that is, the duality gap is zero): where θ(u, v) is the dual objective function. Using the contrapositive statement of Theorem 17, we get the following result: Corollary 18. (to Theorem 17) If there exists a duality gap using Lagrangian duals, then either the primal or the dual is not a convex optimization problem. (Remember, we are assuming constraint qualification.) The Subset Sum problem is defined as follows: Given a set S of positive integers {d 1 , d 2 , · · · , d k } and another positive integer d 0 , is there a subset P of S, such that the sum of the integers in P equals d 0 ? Using a polynomial time reduction from the Subset Sum problem to a non-convex optimization problem (see Def. 16), BIB001 showed the following: If an optimization problem is non-convex, it is NP-hard. In certain cases, non-convex problems have an equivalent convex formulation, for example, through strong duality. Such a dual transformation, where a convex problem B is a dual of a non-convex problem A such that the duality gap between them is zero, is called hidden convexity BIB003 BIB002 . In such cases, the reformulated convex problem is also NP-hard; otherwise the primal non-convex problem can be solved efficiently, thus violating Theorem 19. Definition 20. Standard Quadratic Program (SQP)  . Minimize the function x T Qx, where x ∈ ∆ (the standard simplex in R n + ). The n vertices of ∆ are at a unit distance (in the positive direction) along each of the n axes of R n . Q is a given symmetric matrix in R n×n . The converse of Theorem 19 is not true. A convex optimization problem in general is NP-hard, SQP being an example. SQP is non-convex; however in  , Bomze and de Clerk prove that it has an exact convex reformulation as a copositive programming problem. SQP is known to be NP-hard, since its decision version contains the max-clique problem in graphs as a special case. From this, it follows that copositive programming is also NP-hard; see BIB004 for more on this topic.