11 papers
Benign Degeneracy for First-Order Methods in Exact Boolean Moment-SOS Relaxations
Shucheng Kang
Pseudo-Boolean optimization -- minimizing a polynomial over -- includes MAX-CUT, binary quadratic optimization, and Ising models. The moment-sum-of-squares (Moment-SO…
Spectral Deflation for Factorization-Free Matrix Filtering in Muon and Semidefinite Programming
Haoran Sun, Shucheng Kang, Heng Yang
GPU implementations of the Muon optimizer and of first-order semidefinite programming (SDP) solvers share one computational pattern: a matrix factorization is replaced by a fixed-d…
Afterimage Slow Regions in First-Order Methods for Linear Conic Programming
Shucheng Kang, Heng Yang
First-order methods for linear conic programming often stall on long plateaus. Existing analyses characterize when during a run or on which problem instances slow convergence occur…
Simplicial Regularizability of the Pseudo-Moment Cone and Carathéodory-Type Atomic Decomposition of Moment Matrices
Shucheng Kang, Heng Yang
We study the facial geometry of the homogeneous pseudo-moment cone \(Σ_{n,2d}^*\) and its implications for atomic decomposition of moment matrices. For fixed \(d \ge 2\), we show t…
Local Second-Order Limit Dynamics of the Alternating Direction Method of Multipliers for Semidefinite Programming
Shucheng Kang, Heng Yang
The alternating direction method of multipliers (ADMM) is widely used for solving large-scale semidefinite programs (SDPs), yet on instances with multiple primal-dual optimal solut…
Factorization-free Orthogonal Projection onto the Positive Semidefinite Cone with Composite Polynomial Filtering
Shucheng Kang, Haoyu Han, Antoine Groudiev +1
We propose a factorization-free method for orthogonal projection onto the positive semidefinite (PSD) cone, leveraging composite polynomial filtering. Inspired by recent advances i…
Local Linear Convergence of the Alternating Direction Method of Multipliers for Semidefinite Programming under Strict Complementarity
Shucheng Kang, Xin Jiang, Heng Yang
We investigate the local linear convergence properties of the Alternating Direction Method of Multipliers (ADMM) when applied to Semidefinite Programming (SDP). A longstanding beli…
Global Contact-Rich Planning with Sparsity-Rich Semidefinite Relaxations
Shucheng Kang, Guorui Liu, Heng Yang
We show that contact-rich motion planning is also sparsity-rich when viewed as polynomial optimization (POP). We can exploit not only the correlative and term sparsity patterns tha…
On the Surprising Robustness of Sequential Convex Optimization for Contact-Implicit Motion Planning
Yulin Li, Haoyu Han, Shucheng Kang +2
Contact-implicit motion planning-embedding contact sequencing as implicit complementarity constraints-holds the promise of leveraging continuous optimization to discover new contac…
Fast and Certifiable Trajectory Optimization
Shucheng Kang, Xiaoyang Xu, Jay Sarva +2
We propose semidefinite trajectory optimization (STROM), a framework that computes fast and certifiably optimal solutions for nonconvex trajectory optimization problems defined by…
Sparse Polynomial Optimization with Unbounded Sets
Lei Huang, Shucheng Kang, Jie Wang +1
This paper considers sparse polynomial optimization with unbounded sets. When the problem possesses correlative sparsity, we propose a sparse homogenized Moment-SOS hierarchy with…