A Dynamic Penalization Framework for Online Rank-1 Semidefinite Programming Relaxations

We propose a unified framework for solving sequences of semidefinite programs (SDPs) with rank-one constraints—critical in domains such as combinatorial optimization and power systems. Enforcing rank−1 feasibility in SDP relaxations is especially challenging in dynamic environments where problem parameters evolve across time. To address this, our method operates on two complementary levels. At the per-task level, we introduce a two-phase optimization scheme: the decision phase solves a penalized SDP using a task-specific penalty matrix to approximate a rank−1 solution, while the learning phase updates this penalty matrix via subgradient-based feedback to progressively enforce rank−1 feasibility. At the meta level, we introduce a meta-learning framework that accelerates optimization across tasks by predicting effective initializations for the penalty matrix in each new task. The meta-model leverages historical solutions to produce informed penalty initializations, reducing the number of inner iterations needed per task. We provide theoretical guarantees showing that the task-averaged regret decreases with the number of tasks, with rates that improve under higher task similarity. Empirical results in real-world rank-constrained applications, including the Max-Cut problem and Optimal Power Flow (OPF), demonstrate that our method consistently recovers rank−1 solutions.