×

zbMATH — the first resource for mathematics

Applications of gauge duality in robust principal component analysis and semidefinite programming. (English) Zbl 1380.65106
The nonlinear gauge optimization problem is to minimize a closed gauge function \(\kappa\) over a closed convex set \(X \subset \mathbb{R}^n\), i.e. \(\min_x\{\kappa(x)|x\in X\}\). Its nonlinear gauge dual problem is defined as minimizing the polar function \(\kappa^\circ\) over the antipolar set \(X'\), i.e. \(\min_y\{\kappa^\circ(y)|y\in X'\}\), where \(\kappa^\circ(y)=\inf\{\mu>0|\langle x,y\rangle \leq \mu\kappa(x) \text{ for all } x\}\). The authors present new theoretical results on applying the gauge duality theory [R. M. Freund, Math. Program. 38, 47–67 (1987; Zbl 0632.90054)] to robust principal component analusis and general semidefinite programming [M. P. Friedlander and I. Macêdo, SIAM J. Sci. Comput. 38, No. 3, A1616–A1638 (2016; Zbl 1342.90115)]. For each considered problem, they give its gauge dual problem, characterize the optimality conditions for the primal-dual gauge pair and finally they validate a way to recover a primal optimal solution from a dual one.
MSC:
65K05 Numerical mathematical programming methods
90C25 Convex programming
90C22 Semidefinite programming
60H25 Random operators and equations (aspects of stochastic analysis)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Ben-Tal, A; Nemirovski, A, Non-Euclidean restricted memory level method for large-scale convex optimization, Math Program, 102, 407-456, (2005) · Zbl 1066.90079
[2] Candès, E J; Li, X; Ma, Y; etal., Robust principal component analysis?, J ACM, 58, 1-73, (2011) · Zbl 1327.62369
[3] Candès, E J; Strohmer, T; Voroninski, V, Phaselift: exact and stable signal recovery from magnitude measurements via convex programming, Comm Pure Appl Math, 66, 1241-1274, (2013) · Zbl 1335.94013
[4] Chandrasekaran, V; Sanghavi, S; Parrilo, P A; etal., Rank-sparsity incoherence for matrix decomposition, SIAM J Optim, 21, 572-596, (2011) · Zbl 1226.90067
[5] Frank, M; Wolfe, P, An algorithm for quadratic programming, Naval Res Logist Quart, 3, 95-110, (1956)
[6] Freund, R M, Dual gauge programs, with applications to quadratic programming and the minimum-norm problem, Math Program, 38, 47-67, (1987) · Zbl 0632.90054
[7] Friedlander, M P; Macêdo, I, Low-rank spectral optimization, (2016) · Zbl 1342.90115
[8] Friedlander, M P; Macêdo, I; Pong, T K, Gauge optimization and duality, SIAM J Optim, 24, 1999-2022, (2014) · Zbl 1333.90083
[9] Golub, G H; Ye, Q, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J Sci Comput, 2, 312-334, (2002) · Zbl 1016.65017
[10] Kiwiel, K C, Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities, Math Program, 69, 89-109, (1995) · Zbl 0857.90101
[11] Lemaréchal, C; Nemirovskii, A; Nesterov, Y, New variants of bundle methods, Math Program, 69, 111-147, (1995) · Zbl 0857.90102
[12] Levitin, E; Polyak, B, Constrained minimization methods, Ussr Comput Math Math Phys, 6, 1-50, (1956)
[13] Lewis, A S, The convex analysis of unitarily invariant matrix functions, J Convex Anal, 2, 173-183, (1995) · Zbl 0860.15026
[14] Mu C, Zhang Y, Wright J, et al. Scalable robust matrix recovery: Frank-wolfe meets proximal methods. ArXiv:1403. 7588, 2014
[15] Oliveira D E, Wolkowicz H, Xu Y. ADMM for the SDP relaxation of the QAP. ArXiv:1512.05448, 2015
[16] Renegar J. Efficient first-order methods for linear programming and semidefinite programming. ArXiv:1409.5832, 2014
[17] Rockafellar R T. Convex Analysis. Princeton: Princeton University Press, 1970 · Zbl 0193.18401
[18] Shen, Y; Wen, Z; Zhang, Y, Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Optim Methods Softw, 29, 239-263, (2014) · Zbl 1285.90068
[19] Shor N Z. Minimization Methods for Non-Diffrentiable Functions. New York: Springer-Verlag, 1985
[20] Wen, Z; Goldfarb, D; Yin, W, Alternating direction augmented Lagrangian methods for semidefinite programming, Math Program Comput, 2, 203-230, (2010) · Zbl 1206.90088
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.