Interior point methods

If the matrix Q is positive semidefinite (positive definite) when projected into the null space of the active constraints, then (3-98) is (strictly) convex and the QP is a global (and unique) minimum. Otherwise, local solutions exist for (3-98), and more extensive global optimization methods are needed to obtain the global solution. Like LPs, convex QPs can be solved in a finite number of steps. However, as seen in Fig. 3-57, these optimal solutions can lie on a vertex, on a constraint boundary, or in the interior. A number of active set strategies have been created that solve the KKT conditions of the QP and incorporate efficient updates of active constraints. Popular methods include null space algorithms, range space methods, and Schur complement methods. As with LPs, QP problems can also be solved with interior point methods [see Wright (1996)]. 

Wright, S. J. Primal-Dual Interior-Point Methods. SIAM, Philadelphia, PA (1999). 

Bhatia, T. K. and L. T. Biegler. Multiperiod Design and Planning with Interior Point Methods. Comp Chem Engin 23 919 (1999). 

SEMIDEFINITE PROGRAMMING FORMULATIONS AND PRIMAL-DUAL INTERIOR-POINT METHODS... 

Considering such recent relevance of SDP in quantum chemistry, this chapter discusses some practical aspects of this variational calculation of the 2-RDM formulated as an SDP problem. We first present the definition of an SDP problem, and then the primal and dual SDP formulations of the variational calculation of the 2-RDM as SDP problems (Section II), an efficient algorithm to solve the SDP problems the primal-dual interior-point method (Section III), a brief section about alternative and also efficient augmented Lagrangian methods (Section IV), and some computational aspects when solving the SDP problems (Section V). 

Interior-point methods for SDPs were independently proposed by Nesterov and Nemirovsldi [19] and Alizadeh [20] in the early 1990s. These methods were primal or dual only interior-point methods. Several variants of interior-point methods have been proposed so far, but after a decade of theoretical maturation... 

Finally, the general algorithm framework of the infeasible primal-dual path-following Mehrotra-type predictor-corrector interior-point method is the following. 

Primal-Dual interior-point methods always compute the desired solution within a guaranteed time complexity framework. Moreover, we can always... 

The success of Primal-Dual interior-point methods is due to its feature of computing reliable and highly precise solutions in a guaranteed time framework, although its computational cost can become prohibitively expensive for large-scale SDP problems. 

For the SDP problems arising from the variational calculation, in which we are interested, the theoretical number of floating-point operations required by parallel Primal-Dual interior-point method-based software scales as... 

Theoretical Number of Floating-Point Operations per Iteration (FLOPI), Maximum Number of Major Iterations, and Memory Usage for the Parallel Primal-Dual Interior-Point Method (pPDIPM) and for the First-Order Method (RRSDP) Applied to Primal and Dual SDP Formulations". 

From the table, we can see that the first-order method usually requires fewer floating-point operations and memory storage if compared with the Primal-Dual interior-point method. The unique drawback of the former method is that we cannot guarantee a convergence of the method in a certain time frame. 

We can also conclude that if we employ the Primal-Dual interior-point method, the dual SDP formulation provides a more reduced mathematical description of the variational calculation of the 2-RDM than employing the primal SDP formulation. The former formulation also allows us to reach a faster computational solution. On the other hand, the number of floating-point operations and the memory storage of RRSDP do not depend on the primal or dual SDP formulations. 

---