2011 Matrix optimization - searching between the first and second order methods (slide).pdf

bb b b b b b b b b b b b bb b b b b b b b b b b b b b b b b b b b b Matrix Optimization: Searching between the First and Second Order Methods Defeng Sun Department of Mathematics and Risk Management Institute National University of Singapore May 17, 2011 The Matrix Optimization Problem The SIAM Conference on Optimization 2011, Darmstadt NUS/SUN – 2 / 37 We consider the “standard” matrix optimization problem (MOP) and its dual: (P) min 〈c, x〉+ f(x) s.t. Ax = b and (D) max 〈b, y〉 ? f?(z) s.t. A?y ? c = z , where X is the Cartesian product of several finite dimensional real matrix spaces, symmetric or non-symmetric, A? is the adjoint of the linear operator A : X → ?m, c ∈ X , b ∈ ?m, f : X → (?∞,∞] is a closed proper convex function with its Fenchel conjugate f?. The SIAM Conference on Optimization 2011, Darmstadt NUS/SUN – 3 / 37 The Fenchel conjugate of f is defined by f?(z) := sup x∈X {〈z, x〉 ? f(x)} . In standard linear programming, f(x) = δ?n + (x), the indicator function over ?n+ and f ?(x) = δ(??n + )(x). In semidefinite programming (SDP), f(x) = δSn + , the indicator function over Sn+ and f ?(x) = δ(?Sn + )(x). Desirable Properties of f The SIAM Conference on Optimization 2011, Darmstadt NUS/SUN – 4 / 37 We need conditions on f . Specifically, we require ? The Moreau-Yosida regularization of f ψf (x) := min z∈X { f(z) + 1 2 ‖z ? x‖2 } has a closed form solution, denoted by Pf (x). ? We can easily compute the directional derivative of ?ψf(x) = x? Pf(x). ? The function ?ψf is (strongly) semismooth. The SIAM Conference on Optimization 2011, Darmstadt NUS/SUN – 5 / 37 Let us first look at one simple example with nonsymmetric matrices: min y∈?k ‖A0 ? ∑k i=1 yiAi‖2 , (1) where Ai are m by n matrices, ‖ · ‖2 is the spectral (operator) norm of matrices (the largest singular value). Use ‖ · ‖? to denote the nuclear norm (the sum of all singular values) and B1? to denote the unit nuclear norm ball. The SIAM Conference on Optimization 2011, Darmstadt NUS/SUN – 6 / 37 We c