An Interior-Point Method for Convex Optimization over Non-symmetric Cones
summary
Describes an interior‑point predictor–corrector algorithm for convex optimization over non‑symmetric cones that uses only barrier gradient and Hessian (no need for closed‑form conjugate derivatives), achieves best‑known iteration complexity, and limits per‑step cost to solving Newton linear systems (~O(n^3). Provides a MATLAB implementation and corrects analysis flaws in a prior paper. Applies the method to SOS problems using an interpolant basis gives O(U^2) barrier computations, cuts memory/time vs SDP, and includes postprocessing that yields exact rational SOS certificates.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 0:30Motivations
- 1:56Why symmetrical programming
- 2:57Sum of squares optimization
- 4:02Nonkinetic comp programs
- 8:29Generalized power cones
- 11:04Algorithms
- 17:10MATLAB Implementation
- 18:45Feasibility Detection
- 20:57Notation
- 23:47Complexity
- 31:53Test Problems
- 35:57No SDPD
- 37:52Example
- 40:33Motivation
- 42:47Preliminary Results
- 44:35Conclusion
- 48:45Numerical Performance
related talks
27mTalk by Ali Kavis (UT Austin)
46mSmooth Nonconvex Min-Max Optimization
33mRobust Sketching for Large-Scale Multi-Instance Conic Optimization
46mCan Non-Convex Optimization be Robust?
01h 18mOptimization I
01h 11m(Hidden) Symmetries of Computational Problems (continued)
01h 04mLast-Iterate Convergence in Constrained Min-Max Optimization: SOS to the Rescue
01h 12mGeodesic Convexity and Optimization