×

A general self-adaptive relaxed-PPA method for convex programming with linear constraints. (English) Zbl 1291.90170

Summary: We present an efficient method for solving linearly constrained convex programming. Our algorithmic framework employs an implementable proximal step by a slight relaxation to the subproblem of proximal point algorithm (PPA). In particular, the stepsize choice condition of our algorithm is weaker than some elegant PPA-type methods. This condition is flexible and effective. Self-adaptive strategies are proposed to improve the convergence in practice. We theoretically show under mild conditions that our method converges in a global sense. Finally, we discuss applications and perform numerical experiments which confirm the efficiency of the proposed method. Comparisons of our method with some state-of-the-art algorithms are also provided.

MSC:

90C25 Convex programming

Software:

TFOCS; PDCO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bruckstein, A. M.; Donoho, D. L.; Elad, M., From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Review, 51, 1, 34-81 (2009) · Zbl 1178.68619 · doi:10.1137/060657704
[2] Candès, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[3] Candès, E. J.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Transactions on Information Theory, 52, 12, 5406-5425 (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507
[4] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM Review, 43, 1, 129-159 (2001) · Zbl 0979.94010 · doi:10.1137/S003614450037906X
[5] Borsdorf, R.; Higham, N. J., A preconditioned Newton algorithm for the nearest correlation matrix, IMA Journal of Numerical Analysis, 30, 1, 94-107 (2010) · Zbl 1188.65055 · doi:10.1093/imanum/drn085
[6] Boyd, S.; Xiao, L., Least-squares covariance matrix adjustment, SIAM Journal on Matrix Analysis and Applications, 27, 2, 532-546 (2005) · Zbl 1099.65039 · doi:10.1137/040609902
[7] Higham, N. J., Computing the nearest correlation matrix-a problem from finance, IMA Journal of Numerical Analysis, 22, 3, 329-343 (2002) · Zbl 1006.65036 · doi:10.1093/imanum/22.3.329
[8] Cai, J.-F.; Candès, E. J.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20, 4, 1956-1982 (2010) · Zbl 1201.90155 · doi:10.1137/080738970
[9] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9, 6, 717-772 (2009) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[10] Candès, E. J.; Tao, T., The power of convex relaxation: near-optimal matrix completion, IEEE Transactions on Information Theory, 56, 5, 2053-2080 (2010) · Zbl 1366.15021 · doi:10.1109/TIT.2010.2044061
[11] Martinet, B., Régularisation d’inéquations variationnelles par approximations successives, Revue Franqaise dInformatique et de Recherche Operationelle, 4, 154-158 (1970) · Zbl 0215.21103
[12] Bnouhachem, A.; Noor, M. A., Inexact proximal point method for general variational inequalities, Journal of Mathematical Analysis and Applications, 324, 2, 1195-1212 (2006) · Zbl 1101.49026 · doi:10.1016/j.jmaa.2006.01.014
[13] Bnouhachem, A.; Noor, M. A., An interior proximal point algorithm for nonlinear complementarity problems, Nonlinear Analysis: Hybrid Systems, 4, 3, 371-380 (2010) · Zbl 1242.90256 · doi:10.1016/j.nahs.2009.09.010
[14] Burke, J. V.; Qian, M., A variable metric proximal point algorithm for monotone operators, SIAM Journal on Control and Optimization, 37, 2, 353-375 (1999) · Zbl 0918.90112 · doi:10.1137/S0363012992235547
[15] Eckstein, J., Approximate iterations in Bregman-function-based proximal algorithms, Mathematical Programming, 83, 1, 113-123 (1998) · Zbl 0920.90117 · doi:10.1016/S0025-5610(97)00105-6
[16] Eckstein, J.; Silva, P. J. S., Proximal methods for nonlinear programming: double regularization and inexact subproblems, Computational Optimization and Applications, 46, 2, 279-304 (2010) · Zbl 1220.90164 · doi:10.1007/s10589-009-9274-1
[17] Güler, O., On the convergence of the proximal point algorithm for convex minimization, SIAM Journal on Control and Optimization, 29, 2, 403-419 (1991) · Zbl 0737.90047 · doi:10.1137/0329022
[18] Hestenes, M. R., Multiplier and gradient methods, Journal of Optimization Theory and Applications, 4, 303-320 (1969) · Zbl 0174.20705 · doi:10.1007/BF00927673
[19] Rockafellar, R. T., Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14, 5, 877-898 (1976) · Zbl 0358.90053 · doi:10.1137/0314056
[20] Parikh, N.; Boyd, S., Proximal algorithms, Foundations and Trends in Optimization, 1, 3, 1-108 (2013)
[21] Rockafellar, R. T., Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research, 1, 2, 97-116 (1976) · Zbl 0402.90076 · doi:10.1287/moor.1.2.97
[22] Korpelevič, G. M., An extragradient method for finding saddle points and for other problems, Èkonomika i Matematicheskie Metody, 12, 4, 747-756 (1976) · Zbl 0342.90044
[23] He, B. S.; Yuan, X. M., A contraction method with implementable proximal regularization for linearly constrained convex programming, Optimization Online, 1-14 (2010)
[24] You, Y. F.; Fu, X. L.; He, B. S., Lagrangian PPA-based contractionmethods for linearly constrained convex optimization · Zbl 1310.90086
[25] He, B. S.; Fu, X. L.; Jiang, Z. K., Proximal-point algorithm using a linear proximal term, Journal of Optimization Theory and Applications, 141, 2, 299-319 (2009) · Zbl 1170.49008 · doi:10.1007/s10957-008-9493-0
[26] Rockafellar, R. T., Convex Analysis. Convex Analysis, Princeton Mathematical Series, no. 28, xviii+451 (1970), Princeton, NJ, USA: Princeton University Press, Princeton, NJ, USA · Zbl 0932.90001
[27] Facchinei, F.; Pang, J. S., Finite-Dimensional Variational Inequalities and Complementarity Problems (2003), New York, NY, USA: Springer, New York, NY, USA · Zbl 1062.90002
[28] He, B., A class of projection and contraction methods for monotone variational inequalities, Applied Mathematics and Optimization, 35, 1, 69-76 (1997) · Zbl 0865.90119 · doi:10.1007/s002459900037
[29] He, B. S.; Liao, L. Z., Improvements of some projection methods for monotone nonlinear variational inequalities, Journal of Optimization Theory and Applications, 112, 1, 111-128 (2002) · Zbl 1025.65036 · doi:10.1023/A:1013096613105
[30] He, B.; Yuan, X.; Zhang, J. J. Z., Comparison of two kinds of prediction-correction methods for monotone variational inequalities, Computational Optimization and Applications, 27, 3, 247-267 (2004) · Zbl 1061.90111 · doi:10.1023/B:COAP.0000013058.17185.90
[31] Fu, X.; He, B., Self-adaptive projection-based prediction-correction method for constrained variational inequalities, Frontiers of Mathematics in China, 5, 1, 3-21 (2010) · Zbl 1186.65083 · doi:10.1007/s11464-009-0045-1
[32] Becker, S. R.; Candès, E. J.; Grant, M. C., Templates for convex cone problems with applications to sparse signal recovery, Mathematical Programming Computation, 3, 3, 165-218 (2011) · Zbl 1257.90042 · doi:10.1007/s12532-011-0029-5
[33] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3, 1, 1-122 (2010) · Zbl 1229.90122 · doi:10.1561/2200000016
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.