Henry Wolkowicz

Yuen-Lam Cheung, Dmitriy Drusvyatskiy, Chi-Kwong Li et al.

We consider the problem of constructing quantum operations or channels, if they exist, that transform a given set of quantum states $\{ρ_1, \dots, ρ_k\}$ to another such set $\{\hatρ_1, \dots, \hatρ_k\}$. In other words, we must find a {\em completely positive linear map}, if it exists, that maps a given set of density matrices to another given set of density matrices. This problem, in turn, is an instance of a positive semi-definite feasibility problem, but with highly structured constraints. The nature of the constraints makes projection based algorithms very appealing when the number of variables is huge and standard interior point-methods for semi-definite programming are not applicable. We provide emperical evidence to this effect. We moreover present heuristics for finding both high rank and low rank solutions. Our experiments are based on the \emph{method of alternating projections} and the \emph{Douglas-Rachford} reflection method.

Saeed Ghadimi, Woosuk L. Jung, Arnesh Sujanani et al.

Preconditioning (scaling) is essential in many areas of mathematics, and in particular in optimization. In this work, we study the problem of finding an optimal diagonal preconditioner. We focus on minimizing two different notions of condition number: the classical, worst-case type, $κ$-condition number, and the more averaging motivated $ω$-condition number. We provide affine based pseudoconvex reformulations of both optimization problems. The advantage of our formulations is that the gradient of the objective is inexpensive to compute and the optimization variable is just an $n\times 1$ vector. We also provide elegant characterizations of the optimality conditions of both problems. We develop a competitive subgradient method, with convergence guarantees, for $κ$-optimal diagonal preconditioning that scales much better and is more efficient than existing SDP-based approaches. We also show that the preconditioners found by our subgradient method leads to better PCG performance for solving linear systems than other approaches. Finally, we show the interesting phenomenon that we can apply the $ω$-optimal preconditioner to the exact $κ$-optimally diagonally preconditioned matrix $A$ and get consistent, significantly improved convergence results for PCG methods.

Greg Reid, Fei Wang, Henry Wolkowicz et al.

The real radical ideal of a system of polynomials with finitely many complex roots is generated by a system of real polynomials having only real roots and free of multiplicities. It is a central object in computational real algebraic geometry and important as a preconditioner for numerical solvers. Lasserre and co-workers have shown that the real radical ideal of real polynomial systems with finitely many real solutions can be determined by a combination of semi-definite programming (SDP) and geometric involution techniques. A conjectured extension of such methods to positive dimensional polynomial systems has been given recently by Ma, Wang and Zhi. We show that regularity in the form of the Slater constraint qualification (strict feasibility) fails for the resulting SDP feasibility problems. Facial reduction is then a popular technique whereby SDP problems that fail strict feasibility can be regularized by projecting onto a face of the convex cone of semi-definite problems. In this paper we introduce a framework for combining facial reduction with such SDP methods for analyzing $0$ and positive dimensional real ideals of real polynomial systems. The SDP methods are implemented in MATLAB and our geometric involutive form is implemented in Maple. We use two approaches to find a feasible moment matrix. We use an interior point method within the CVX package for MATLAB and also the Douglas-Rachford (DR) projection-reflection method. Illustrative examples show the advantages of the DR approach for some problems over standard interior point methods. We also see the advantage of facial reduction both in regularizing the problem and also in reducing the dimension of the moment matrices. Problems requiring more than one facial reduction are also presented.