Session: Optimization for Approximation, Estimation, and Control
Chair: Martin Andersen
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)
Talk 1: Fast and Certifiable Nonconvex Optimal Control with Sparse Moment-SOS Relaxations
Speaker: Heng Yang
Abstract: Direct methods for optimal control, also known as trajectory optimization, is a workhorse for optimization-based control in robotics and beyond. Nonlinear programming with engineered initializations has been the de-facto approach for trajectory optimization, which however, can suffer from undesired local optimality. In this talk, I will first show that, using the machinery of sparse moment and sums-of-squares (SOS) relaxations, many nonconvex trajectory optimization problems can be solved to certifiable global optimality. That is, globally optimal solutions of the original nonconvex problems can be computed by solving convex semidefinite programs (SDPs) together with optimality certificates. I will then present a specialized SDP solver implemented in CUDA (C++) and runs in GPUs that exploits the structures of the problems to solve the convex SDPs at a scale far beyond existing solvers.
Talk 2: Optimal diagonal preconditioner and how to find it
Speaker: Zhaonan Qu
Abstract: Preconditioning has long been a staple technique in optimization, often applied to reduce the condition number of a matrix and speed up the convergence of algorithms. Although there are many popular preconditioning techniques in practice, most lack guarantees on reductions in condition number. Moreover, the degree to which we can improve over existing heuristic preconditioners remains an important practical question. In this talk, we discuss the problem of optimal diagonal preconditioning that achieves maximal reduction in the condition number of any full-rank matrix by scaling its rows and/or columns. We reformulate the problem as a quasi-convex optimization problem and design interior point method to solve it with O(log(1/ϵ)) iteration complexity. Next, we specialize to one-sided optimal diagonal preconditioning problems, and demonstrate that they can be formulated as standard dual SDP problems. Based on the SDP formulation, several computational techniques are applicable, and can greatly accelerate finding a good diagonal preconditioner with theoretical guarantees. Our experiments suggest that optimal diagonal preconditioners can significantly improve upon existing heuristic-based diagonal preconditioners at reducing condition numbers and speeding up iterative methods.
Talk 3: Power System State Estimation by Phase Synchronization and Eigenvectors
Speaker: Iven Guzel
Abstract: To estimate accurate voltage phasors from inaccurate voltage magnitude and complex power measurements, the standard approach is to iteratively refine a good initial guess using the Gauss-Newton method. But the nonconvexity of the estimation makes the Gauss-Newton method sensitive to its initial guess, so human intervention is needed to detect convergence to plausible but ultimately spurious estimates. This paper makes a novel connection between the angle estimation subproblem and phase synchronization to yield two key benefits: (1) an exceptionally high quality initial guess over the angles, known as a spectral initialization; (2) a correctness guarantee for the estimated angles, known as a global optimality certificate. These are formulated as sparse eigenvalue-eigenvector problems, which we efficiently compute in time comparable to a few Gauss-Newton iterations. Our experiments on the complete set of Polish, PEGASE, and RTE models show, where voltage magnitudes are already reasonably accurate, that spectral initialization provides an almost-perfect single-shot estimation of angles from moderately noisy bus power measurements (i.e. pairs of PQ measurements), whose correctness becomes guaranteed after a single Gauss--Newton iteration. For less accurate voltage magnitudes, the performance of the method degrades gracefully; even with moderate voltage magnitude errors, the estimated voltage angles remain surprisingly accurate.
