Convexifying Nonconvex Problems: SDP and SOCP Relaxations

This lecture by the instructor covers the concept of convexifying nonconvex problems using semidefinite programming (SDP) and second-order cone programming (SOCP) relaxations. The lecture starts by introducing the interpretation of problems as convex relaxations, focusing on the convex-cardinality problem and continuous relaxations. It then delves into examples of total variation reconstruction in 1D and 2D, illustrating the application of convex approximations. The lecture further explores convex-rank problems, lift-and-project methods, and the semidefinite relaxation of quadratically constrained quadratic programs (QCQPs). Finally, it discusses optimal power flow (OPF) in power systems, detailing the formulation, constraints, and the highly nonconvex nature of the OPF problem.