Dealing with Linear Constraints via Random Permutation

Explore a lecture on optimization techniques focusing on dealing with linear constraints through random permutation. Delve into advanced concepts like multi-block ADMM variants, randomization tricks, and their applications in solving large-scale problems. Learn about the divergence of cyclic ADMM, spectral analysis of switched linear systems, and novel randomization rules. Examine the comparison of various algorithms, including cyclic coordinate descent, and their convergence rates. Gain insights into the relationship between different optimization methods and discover a new variant of the matrix AM-GM inequality.

Intro
Optimization for Large-scale Problems
Go Beyond Unconstrained Optimization
Random Permutation Helps
Outline
Variants of multi-block ADMM
Apply Randomization Trick to ADMM
Summarize ADMM Variants
Numerical Experiments: Cyc-ADMM Often Diverges
Remarks on Divergence of Cyclic ADMM
Solve Linear System
Why Spectral Analysis?
Switched Linear System
Theorem 2: a Pure Linear Algebra Problem
Proof Sketch of Lemma 2
Interesting Byproduct: New Randomization Rule
Another Way to Apply Decomposition to Constraints
Comparison of Algorithms (cont'd)
Convergence Rate of Cyclic CD
Relation to Other Methods
Another variant of matrix AM-GM inequality