Primal-dual

Wright, S. J. Primal-Dual Interior-Point Methods. SIAM, Philadelphia, PA (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). 

In order to simplify the discussion, we consider, for a while, the primal-dual pair of SDPs Eqs. (l)-(2) instead of Eqs. (3)-(4). We also assume that the space S is formed by single block-diagonal symmetric matrices with size n x n. 

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. 

B. Borchers and J. Young, Implementation of a Primal—Dual Method for SDP on a Parallel Architecture, Research Report, 2005. Available at http //infohost.nmt. edu/ borchers/csdp.html. 

Simultaneous circle-packing representations of a map M and its dual M are called primal-dual circle representation of M if it holds ... 

See Figure 1.2 for an illustration of this feature and an example of a primal-dual circle representation. 

The edges, vertex circles and face circles of a primal-dual representation... 

Figure 1.2 Illustration of primal-dual circle representations...

A map M is called reduced (see [Moh97, Section 3]) if its universal cover is 3-connected and is a cell-complex. It is shown in [Moh97, Corollary 5.4] that reduced maps admit unique primal-dual circle packing representations on a Riemann surface of the same genus moreover, a polynomial time algorithm allows one to find the coordinates of those points relatively easily. This means that the combinatorics of the map determines the structure of the Riemann surface. 

For tori, we take their universal covers on the plane and use the primal-dual representation obtained from the program TorusDraw ([Dut04b]). For the projective plane F2, we take its universal cover, which is the sphere, and draw a circular frame,... 

---