Session: Semidefinite Programming - Theory and Algorithms
Chair: Hao Hu
Cluster: Conic and Semidefinite Optimization
Talk 1: Tight error bounds for log-determinant cones without constraint qualifications
Speaker: Ting Kei Pong
Abstract: Log-determinant cone is the closure of the hypograph of the perspective function of the log-determinant function, and can be viewed as a spectral analogue of the exponential cone. In this talk, without requiring any constraint qualifications, we establish tight error bounds for the log-determinant cone. This error bound is obtained using the recently developed framework based on one-step facial residual functions, which has been successfully applied to deriving error bounds for the exponential cone. This is a joint work with Ying Lin, Scott B. Lindstrom and Bruno F. Lourenço.
Talk 2: Primal-dual interior point algorithms for nonsymmetric convex conic optimization
Speaker: Anita Varga
Abstract: In this talk, we present primal-dual interior point methods for nonsymmetric conic optimization. The proposed methods are of the path following type; we discuss different strategies for initialization and different neighborhoods to ensure fast convergence. We will also discuss some applications including sums-of-squares optimization, where the proposed methods can outperform the conventional semidefinite programming approach. We also share numerical results to illustrate the practical performance of our algorithms.
Talk 3: Ramana's exact dual for semidefinite programming, and elementary row operations
Speaker: Gabor Pataki
Abstract: Thirty years ago, in a seminal paper Ramana derived an exact dual for Semidefinite Programming (SDP). Ramana's dual has the following remarkable features: i) it assumes feasibility of the primal, but it does not make any regularity assumptions, such as strict feasibility ii) its optimal value is the same as the optimal value of the primal, so there is no duality gap. iii) it attains its optimal value when it is finite iv) it yields a number of complexity results in SDP, which are fundamental, and to date are still the best known. For example, it proves that SDP feasibility in the Turing model is not NP-complete, unless NP = co-NP. In this work we give a fairly complete analysis of Ramana's dual. First, we connect it to a seemingly very different way of inducing strong duality: reformulating the SDP into a rank revealing form using mostly elementary row operations. Second, we completely characterize the feasible set of Ramana's dual. As a corollary, we obtain a short and transparent derivation of Ramana's dual, which we hope is accessible to both the optimization and the theoretical computer science community. Our approach is combinatorial in the following sense: i) we use a minimum amount of continuous optimization theory ii) we show that feasible solutions in Ramana's dual are identified with regular facial reduction sequences, i.e., essentially discrete structures.
