Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Preliminary Results: Canonical Duality and the Complexity Classes NP and CoNP <s> We propose an algorithm for the problem of minimizing a quadratic function subject to an ellipsoidal constraint and show that this algorithm is guaranteed to produce a nearly optimal solution in a finite number of iterations. We also consider the use of this algorithm in a trust region Newton's method. In particular, we prove that under reasonable assumptions the sequence generated by Newton's method has a limit point which satisfies the first and second order necessary conditions for a minimizer of the objective function. Numerical results for GQTPAR, which is a Fortran implementaton of our algorithm, show that GQTPAR is quite successful in a trust region method. In our tests a call to GQTPAR only required 1.6 iterations on the average. <s> BIB001 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Preliminary Results: Canonical Duality and the Complexity Classes NP and CoNP <s> Primal-dual pairs of semidefinite programs provide a general framework for the theory and algorithms for the trust region subproblem (TRS). This latter problem consists in minimizing a general quadratic function subject to a convex quadratic constraint and, therefore, it is a generalization of the minimum eigenvalue problem. The importance of (TRS) is due to the fact that it provides the step in trust region minimization algorithms. The semidefinite framework is studied as an interesting instance of semidefinite programming as well as a tool for viewing known algorithms and deriving new algorithms for (TRS). In particular, a dual simplex type method is studied that solves (TRS) as a parametric eigenvalue problem. This method uses the Lanczos algorithm for the smallest eigenvalue as a black box. Therefore, the essential cost of the algorithm is the matrix-vector multiplication and, thus, sparsity can be exploited. A primal simplex type method provides steps for the so-called hard case. Extensive numerical tests for large sparse problems are discussed. These tests show that the cost of the algorithm is 1 +ź(n) times the cost of finding a minimum eigenvalue using the Lanczos algorithm, where 0 <s> BIB002 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Preliminary Results: Canonical Duality and the Complexity Classes NP and CoNP <s> In this paper, we present a new and more complete duality for Semidefinite Programming (SDP), with the following features: \begin{itemize} \item This dual is an explicit semidefinite program, whose number of variables and the coefficient bitlengths are polynomial in those of the primal. \item If the Primal is feasible, then it is bounded if and only if the dual is feasible. \item The duality gap, \ie the difference between the primal and the dual objective function values, is zero whenever the primal is feasible and bounded. Also, in this case, the dual attains its optimum \item It yields a precise Farkas Lemma for semidefinite feasibility systems, \ie characterization of the {\it infeasibility} of a semidefinite inequality in terms of the {\it feasibility} of another polynomial size semidefinite inequality. \end{itemize} Note that the standard duality for Linear Programming satisfies all of the above features, but no such duality theory was previously known for SDP, without Slater-like conditions being assumed. Then we apply the dual to derive certain complexity results for Semidefinite Programming Problems. The decision problem of Semidefinite Feasibility (SDFP), \ie that of determining if a given semidefinite inequality system is feasible, is the central problem of interest. The complexity of SDFP is unknown, but we show the following: 1) In the Turing machine model, SDFP is not NP-Complete unless NP=Co-NP; 2) In the real number model of Blum, Shub and Smale\cite{bss}, SDFP is in NP$\cap$Co-NP. We then give polynomial reductions from the following problems to SDFP: 1) Checking whether an SDP is bounded; 2) Checking whether a feasible and bounded SDP attains the optimum; 3) Checking the optimality of a feasible solution. <s> BIB003 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Preliminary Results: Canonical Duality and the Complexity Classes NP and CoNP <s> Quadratically constrained quadratic programs (QQPs) play an important modeling role for many diverse problems. These problems are in general NP hard and numerically intractable. Lagrangian relaxations often provide good approximate solutions to these hard problems. Such relaxations are equivalent to semidefinite programming relaxations. ::: For several special cases of QQP, e.g., convex programs and trust region subproblems, the Lagrangian relaxation provides the exact optimal value, i.e., there is a zero duality gap. However, this is not true for the general QQP, or even the QQP with two convex constraints, but a nonconvex objective. ::: In this paper we consider a certain QQP where the quadratic constraints correspond to the matrix orthogonality condition XXT=I. For this problem we show that the Lagrangian dual based on relaxing the constraints XXT=I and the seemingly redundant constraints XT X=I has a zero duality gap. This result has natural applications to quadratic assignment and graph partitioning problems, as well as the problem of minimizing the weighted sum of the largest eigenvalues of a matrix. We also show that the technique of relaxing quadratic matrix constraints can be used to obtain a strengthened semidefinite relaxation for the max-cut problem. <s> BIB004 </s> Duality Gap, Computational Complexity and NP Completeness: A Survey <s> Preliminary Results: Canonical Duality and the Complexity Classes NP and CoNP <s> 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. <s> BIB005
We consider quadratic programming 3 problems with a single quadratic constraint (QCQP)  . The primal problem P 0 is given by: where A and B are non-zero n × n symmetric matrices, f ∈ R n , and µ ∈ R. (A, B, f and µ are given.) Corresponding to the primal P 0 , the canonical dual problem P d is as follows: assuming that F is non-empty. To ensure that (A + σB) is invertible, we have assumed that A and B are symmetric and non-zero. Again, the positive definiteness of (A + σB) for the dual problem has been found to be a sufficient condition, and it is not known yet whether it is a necessary condition. The following theorem appeared in  : (11) is finite, strong duality between the primal problem P 0 and the dual problem P d holds, and the optimal solution for P 0 is given by However, the pair (P 0 , P d ) may not be tight duals (i.e., they may not belong to the class T D). To show that (P 0 , P d ) ∈ T D, it also needs to be shown that the dual of P d is P 0 . (Recall Remark 10.) Remark 23. We have not provided a detailed analysis of how the canonical problem can be derived. The interested reader is referred to  . Our goal is to illustrate an instance of a pair of primal and dual problems that obey strong duality, and where an optimal solution can be obtained efficiently (in polynomial time). Strong duality for a variation of QCQP was established by Moré and Sorensen in 1983 BIB001 (as described in BIB004 ); they call theirs as the Trust Region Problem (TRP). The problem is to minimize a quadratic function q 0 , subject to a norm constraint x T x ≤ δ 2 . This is an example of a non-convex problem where strong duality holds. Rendl and Wolkowicz BIB002 show that the TRP can be reformulated as an unconstrained concave maximization problem, and hence can be solved in polynomial time by using the interior point method  . Recall that decision problems are those with Yes/No answers. Combining Theorem 22 with Lemma 9 above, we can conclude that Remark 24. Decision versions of Problems P 0 in (10) and P d in (11) are members of the intersection class NP ∩ CoNP. Furthermore, from Theorem 3 in  , it is easy to see that problems P 0 and P d can be solved in polynomial time. The authors in  use what they call a "boundarification" technique which moves the analytical solutionx to a global minimizer x * on the boundary of the primal domain. This strengthens the conjecture that Conjecture 25. If two optimization problems P a and P b are such that one of them is the dual of the other, that is, they exhibit strong duality, then both are polynomially solvable. As hinted earlier, the canonical dual feasible space F in (11) may be empty. In such a case, strong duality still holds on a feasible domain in which the matrix (A + σB) is not definite. However, the question as to how to solve the canonical dual problem is still open. It is conjectured in BIB005 that the primal problem (from which the canonical dual problem is derived) could be NP-hard. The observations above are for quadratic programming problems with a single quadratic constraint. It would be interesting to see what happens for quadratic programming problems with two constraints, whether strong duality still holds, and whether both the primal and the dual are still polynomially solvable. Semidefinite Programming (SDP). Ramana BIB003 exhibited strong duality for the SDP problem. However, the complexity of SDP is unknown; it was shown in BIB003 that the decision version of SDP is NP-complete if and only if NP = CoNP. (Note: There have been some published papers which say that SDP is polynomial time solvable. This is NOT correct, as the above result in BIB003 shows.)