×

On convergence rates of linearized proximal algorithms for convex composite optimization with applications. (English) Zbl 1338.65159

Summary: In the present paper, we investigate a linearized proximal algorithm (LPA) for solving a convex composite optimization problem. Each iteration of the LPA is a proximal minimization of the convex composite function with the inner function being linearized at the current iterate. The LPA has the attractive computational advantage that the solution of each subproblem is a singleton, which avoids the difficulty as in the Gauss-Newton method (GNM) of finding a solution with minimum norm among the set of minima of its subproblem, while still maintaining the same local convergence rate as that of the GNM. Under the assumptions of local weak sharp minima of order \(p\) \((p \in [1,2])\) and a quasi-regularity condition, we establish a local superlinear convergence rate for the LPA. We also propose a globalization strategy for the LPA based on a backtracking line-search and an inexact version of the LPA. We further apply the LPA to solve a (possibly nonconvex) feasibility problem, as well as a sensor network localization problem. Our numerical results illustrate that the LPA meets the demand for an efficient and robust algorithm for the sensor network localization problem.

MSC:

65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization

Software:

SNLSDP
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] H. H. Bauschke and J. M. Borwein, {\it On projection algorithms for solving convex feasibility problems}, SIAM Rev., 38 (1996), pp. 367-426, http://dx.doi.org/10.1137/S0036144593251710. · Zbl 0865.47039
[2] A. Beck and M. Teboulle, {\it A fast iterative shrinkage-thresholding algorithm for linear inverse problems}, SIAM J. Imaging Sci., 2 (2009), pp. 183-202, http://dx.doi.org/10.1137/080716542. · Zbl 1175.94009
[3] D. P. Bertsekas, {\it Nonlinear Programming}, Athena Scientific, Cambridge, UK, 1999. · Zbl 1015.90077
[4] P. Biswas, T.-C. Liang, K.-C. Toh, Y. Ye, and T.-C. Wang, {\it Semidefinite programming approaches for sensor network localization with noisy distance measurements}, IEEE Trans. Automat. Sci. Engrg., 3 (2006), pp. 360-371.
[5] J. Bolte, A. Daniilidis, and A. S. Lewis, {\it Tame functions are semismooth}, Math. Program., 1-2 (2009), pp. 5-19. · Zbl 1158.49030
[6] J. F. Bonnans and A. Ioffe, {\it Second-order sufficiency and quadratic growth for nonisolated minima}, Math. Oper. Res., 20 (1995), pp. 801-817. · Zbl 0846.90095
[7] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, {\it Distributed optimization and statistical learning via the alternating direction method of multipliers}, Found. Trends Mach. Learning, 3 (2011), pp. 1-124. · Zbl 1229.90122
[8] J. V. Burke, {\it Descent methods for composite nondifferentiable optimization problems}, Math. Program., 33 (1985), pp. 260-279. · Zbl 0581.90084
[9] J. V. Burke, {\it Second order necessary and sufficient conditions for convex composite NDO}, Math. Program., 38 (1987), pp. 287-302. · Zbl 0641.49013
[10] J. V. Burke and M. C. Ferris, {\it A Gauss-Newton method for convex composite optimization}, Math. Program., 71 (1995), pp. 179-194. · Zbl 0846.90083
[11] J. V. Burke and S. Deng, {\it Weak sharp minima revisited, part I: Basic theory}, Control Cybern., 31 (2002), pp. 439-469. · Zbl 1105.90356
[12] J. V. Burke and M. C. Ferris, {\it Weak sharp minima in mathematical programming}, SIAM J. Control Optim., 31 (1993), pp. 1340-1359, http://dx.doi.org/10.1137/0331063. · Zbl 0791.90040
[13] R. Fletcher, {\it Practical Methods of Optimization}, Wiley, New York, 1987. · Zbl 0905.65002
[14] B. He and X. Yuan, {\it On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method}, SIAM J. Numer. Anal., 50 (2012), pp. 700-709, http://dx.doi.org/10.1137/110836936. · Zbl 1245.90084
[15] J.-B. Hiriart-Urruty and C. Lemaréchal, {\it Fundamentals of Convex Analysis}, Springer-Verlag, Berlin, 2001. · Zbl 0998.49001
[16] Y. H. Hu, X. Q. Yang, and C.-K. Sim, {\it Inexact subgradient methods for quasi-convex optimization problems}, European J. Oper. Res., 240 (2015), pp. 315-327. · Zbl 1357.90116
[17] A. S. Lewis and J. Malick, {\it Alternating projections on manifolds}, Math. Oper. Res., 33 (2008), pp. 216-234. · Zbl 1163.65040
[18] A. S. Lewis and S. J. Wright, {\it A Proximal Method for Composite Minimization}, tech. report, 2008. · Zbl 1345.49041
[19] C. Li and K. F. Ng, {\it Convergence analysis of the Gauss-Newton method for convex inclusion and convex-composite optimization problems}, J. Math. Anal. Appl., 389 (2012), pp. 469-485. · Zbl 1239.65036
[20] C. Li and K. F. Ng, {\it Majorizing functions and convergence of the Gauss-Newton method for convex composite optimization}, SIAM J. Optim., 18 (2007), pp. 613-642, http://dx.doi.org/10.1137/06065622X. · Zbl 1153.90012
[21] C. Li and X. Wang, {\it On convergence of the Gauss-Newton method for convex composite optimization}, Math. Program., 91 (2002), pp. 349-356. · Zbl 1049.90132
[22] Z.-Q. Luo, W.-K. Ma, A. M.-C. So, Y. Ye, and S. Zhang, {\it Semidefinite relaxation of quadratic optimization problems}, IEEE Signal Proc. Mag., 27 (2010), pp. 20-34.
[23] B. Martinet, {\it Regularisation d’indquations variationelles par approximations successives}, Rev. Francaise Inf. Rech. Oper., (1970), pp. 154-159. · Zbl 0215.21103
[24] J. J. Moré, {\it The Levenberg-Marquardt algorithm: Implementation and theory}, in Numerical Analysis, G. A. Watson, ed., Lecture Notes in Math. 630, Springer, Berlin, 1978, pp. 105-116.
[25] Yu. Nesterov, {\it Gradient methods for minimizing composite functions}, Math. Program., 140 (2013), pp. 125-161. · Zbl 1287.90067
[26] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, Springer Science+Business Media, New York, 2006. · Zbl 1104.65059
[27] J.-S. Pang, {\it Error bounds in mathematical programming}, Math. Program., 79 (1997), pp. 299-332. · Zbl 0887.90165
[28] L. Qi and J. Sun, {\it A nonsmooth version of Newton’s method}, Math. Program., 58 (1993), pp. 353-367. · Zbl 0780.90090
[29] S. M. Robinson, {\it Stability theory for systems of inequalities, part II. Differentiable nonlinear systems.}, SIAM J. Numer. Anal., 13 (1976), pp. 497-513, http://dx.doi.org/10.1137/0713043. · Zbl 0347.90050
[30] R. T. Rockafellar, {\it Monotone operators and the proximal point algorithm}, SIAM J. Control Optim., 14 (1976), pp. 877-898, http://dx.doi.org/10.1137/0314056. · Zbl 0358.90053
[31] R. T. Rockafellar, {\it First- and second-order epi-differentiability in nonlinear programming}, Trans. Amer. Math. Soc., 307 (1988), pp. 75-108. · Zbl 0655.49010
[32] C. Sagastizábal, {\it Composite proximal bundle method}, Math. Program., 140 (2013), pp. 189-233. · Zbl 1273.90163
[33] J. B. Saxe, {\it Embeddability of weighted graphs in \(k\)-space is strongly NP-hard}, in Proceedings of the 17th Annual Allerton Conference on Communication, Control, and Computing, 1979, pp. 480-489.
[34] Q. Shi, C. He, and L. Jiang, {\it Normalized incremental subgradient algorithm and its application}, IEEE Trans. Signal Process., 57 (2009), pp. 3759-3774. · Zbl 1391.90480
[35] M. Studniarski and D. E. Ward, {\it Weak sharp minima: Characterizations and sufficient conditions}, SIAM J. Control Optim., 38 (1999), pp. 219-236, http://dx.doi.org/10.1137/S0363012996301269. · Zbl 0946.49011
[36] W. Sun and Y.-X. Yuan, {\it Optimization Theory and Methods}, Springer Science+Business Media, New York, 2006.
[37] P. Tseng, {\it On Accelerated Proximal Gradient Methods for Convex-Concave Optimization}, tech. report, 2008.
[38] Z. Wang, S. Zheng, Y. Ye, and S. Boyd, {\it Further relaxations of the semidefinite programming approach to sensor network localization}, SIAM J. Optim., 19 (2008), pp. 655-673, http://dx.doi.org/10.1137/060669395. · Zbl 1173.90498
[39] R. S. Womersley, {\it Local properties of algorithms for minimizing nonsmooth composite functions}, Math. Program., 32 (1985), pp. 69-89. · Zbl 0571.90084
[40] L. Xiao and T. Zhang, {\it A proximal-gradient homotopy method for the sparse least-squares problem}, SIAM J. Optim., 23 (2013), pp. 1062-1091, http://dx.doi.org/10.1137/120869997. · Zbl 1280.65057
[41] Y. Ye, {\it Interior Point Algorithms: Theory and Analysis}, John Wiley & Sons, New York, 1987.
[42] Y.-X. Yuan, {\it Conditions for convergence of trust region algorithms for nonsmooth optimization}, Math. Program., 31 (1985), pp. 220-228. · Zbl 0576.90080
[43] X. Y. Zheng and K. F. Ng, {\it Strong KKT conditions and weak sharp solutions in convex-composite optimization}, Math. Program., 126 (2011), pp. 259-279. · Zbl 1229.90147
[44] X. Y. Zheng and X. Q. Yang, {\it Weak sharp minima for semi-infinite optimization problems with applications}, SIAM J. Optim., 18 (2007), pp. 573-588, http://dx.doi.org/10.1137/060670213. · Zbl 1190.90251
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.