We consider the matrix completion problem for special classes of matrices. This includes EDM, low rank, robust PCA, and Toeplitz. We consider both the exact and noisy cases. We include theoretical results as well as efficient numerical techniques. Our tools are semidefinite programming, facial reduction, and trust region subproblems.
joint work with Martin Stoll, Margherita Porcelli, Francesco Rinaldi
We present a novel Improved Penalty Algorithm (IPA) designed for large-scale problems. The Algorithm utilizes the framework of an existing Exact Penalty Algorithm to correctly increase the penalization throughout its iteration, while, in each iteration, it tries to find an iterate that decreases the current objective function value. Such a decrease can be achieved via a problem-specific perturbation strategy. Based on a numerical toy problem, we will compare the IPA to existing penalization strategies, simple rounding schemes, and a Branch and Bound routine of Cplex.
We consider the solution of binary quadratic programming (BQP) problems in the standard branch-and-bound framework. The idempotency of binary variables allows for regularization of the objective function without altering the set of optimal solutions. Such regularization can serve two purposes. First, it can be applied to ensure the convexity of the continuous relaxation, and secondly to strengthen the root relaxation of (convex) BQP problems. Computing such a regularization can be achieved by the solution of an auxiliary SDP, for which we compare different computational techniques.