On Iteration Complexity of a First-Order Primal-Dual Method for Nonlinear Convex Cone Programming

doi:10.1007/s40305-021-00344-x

Abstract

Abstract: Nonlinear convex cone programming (NCCP) models have found many practical applications. In this paper, we introduce a flexible first-order primal-dual algorithm, called the variant auxiliary problem principle (VAPP), for solving NCCP problems when the objective function and constraints are convex but may be nonsmooth. At each iteration, VAPP generates a nonlinear approximation of the primal augmented Lagrangian model. The approximation incorporates both linearization and a distance-like proximal term, and then the iterations of VAPP are shown to possess a decomposition property for NCCP. Motivated by recent applications in big data analytics, there has been a growing interest in the convergence rate analysis of algorithms with parallel computing capabilities for large scale optimization problems. We establish O(1/t) convergence rate towards primal optimality, feasibility and dual optimality. By adaptively setting parameters at different iterations, we show an O(1/t²) rate for the strongly convex case. Finally, we discuss some issues in the implementation of VAPP.

Key words: Nonlinear convex cone programming, First-order method, Primal-dual method, Augmented Lagrangian function

CLC Number:

Lei Zhao, Dao-Li Zhu. On Iteration Complexity of a First-Order Primal-Dual Method for Nonlinear Convex Cone Programming[J]. Journal of the Operations Research Society of China, 2022, 10(1): 53-87.

TrendMD

References

[1] Goberna, M.A., López, M.A.:Linear Semi-infinite Optimization, vol. 2. Wiley, London (1998)
[2] López, M., Still, G.:Semi-infinite programming. Eur. J. Oper. Res. 180(2), 491-518(2007)
[3] Shapiro, A.:Semi-infinite programming, duality, discretization and optimality conditions. Optimization 58(2), 133-161(2009)
[4] Alizadeh, F., Goldfarb, D.:Second-order cone programming. Math. Program. 95(1), 3-51(2003)
[5] Fukuda, E.H., Silva, P.J., Fukushima,M.:Differentiable exact penalty functions for nonlinear secondorder cone programs. SIAM J. Optim. 22(4), 1607-1633(2012)
[6] Kanzow, C., Ferenczi, I., Fukushima, M.:On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity. SIAM J. Optim. 20(1), 297-320(2009)
[7] Kato, H., Fukushima,M.:An SQP-type algorithm for nonlinear second-order cone programs. Optim. Lett. 1(2), 129-144(2007)
[8] Yamashita, H., Yabe, H.:A primal-dual interior point method for nonlinear optimization over secondorder cones. Optim. Methods Softw. 24(3), 407-426(2009)
[9] Ben-Tal, A., Nemirovski, A.:Robust convex optimization. Math. Oper. Res. 23(4), 769-805(1998)
[10] Ben-Tal, A., El Ghaoui, L., Nemirovski, A.:Robust Optimization. Princeton University Press, Princeton (2009)
[11] Lobo, M.S.,Vandenberghe, L., Boyd, S., Lebret, H.:Applications of second-order cone programming. Linear Algebra Appl. 284(1), 193-228(1998)
[12] Wu, S.P., Boyd, S., Vandenberghe, L.:FIR filter design via semidefinite programming and spectral factorization. In:Proceedings of the 35th IEEE Conference on Decision and Control, vol. 1, pp. 271-276. IEEE (1996)
[13] Candés, E.J., Romberg, J., Tao, T.:Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489-509(2006)
[14] Patriksson, M.:A survey on the continuous nonlinear resource allocation problem. Eur. J. Oper. Res. 185(1), 1-46(2008)
[15] Donoho, D.L.:Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289-1306(2006)
[16] Patriksson, M., Strömberg, C.:Algorithms for the continuous nonlinear resource allocation problem-new implementations and numerical studies. Eur. J. Oper. Res. 243(3), 703-722(2015)
[17] Hestenes, M.R.:Multiplier and gradient methods. J. Optim. Theory Appl. 4(5), 303-320(1969)
[18] Powell, M.J.D.:A method for nonlinear constraints in minimization problems. In:Fletcher, R. (ed.) Optimization. Academic Press, London (1969)
[19] Buys, J.D.:Dual algorithms for constrained optimization problems. Brondder-Offset (1972)
[20] Rockafellar, R.T.:Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97-116(1976)
[21] Shapiro, A., Sun, J.:Some properties of the augmented Lagrangian in cone constrained optimization. Math. Oper. Res. 29(3), 479-491(2004)
[22] Fortin, M., Glowinski, R.:Chapter III on decomposition-coordination methods using an augmented Lagrangian. Stud. Math. Its Appl. 15, 97-146(1983)
[23] Stellato, B., Banjac, G., Goulart, P., Bemporad, A., Boyd, S.:OSQP:An operator splitting solver for quadratic programs. In:2018 UKACC 12th International Conference on Control (CONTROL), pp. 339-339. IEEE (2018)
[24] Cohen, G., Zhu, D.L.:Decomposition coordination methods in large scale optimization problems. The nondifferentiable case and the use of augmented Lagrangians. Adv. Large Scale Syst. 1, 203-266(1984)
[25] Contreras, J., Losi, A., Russo, M., Wu, F.F.:DistOpt:a software framework for modeling and evaluating optimization problem solutions in distributed environments. J. Parallel Distrib. Comput. 60(6), 741-763(2000)
[26] Losi, A., Russo, M.:On the application of the auxiliary problem principle. J. Optim. Theory Appl. 117(2), 377-396(2003)
[27] Kim, B.H., Baldick, R.:Coarse-grained distributed optimal power flow. IEEE Trans. Power Syst. 12(2), 932-939(1997)
[28] Kim, B.H., Baldick, R.:A comparison of distributed optimal power flow algorithms. IEEE Trans. Power Syst. 15(2), 599-604(2000)
[29] Renaud, A.:Daily generation management at Electricité de France:from planning towards real time. IEEE Trans. Autom. Control 38(7), 1080-1093(1993)
[30] Cao, L., Sun, Y., Cheng, X., Qi, B., Li, Q.:Research on the convergent performance of the auxiliary problem principle based distributed and parallel optimization algorithm. In:2007 IEEE International Conference on Automation and Logistics, pp. 1083-1088. IEEE (2007)
[31] Hur, D., Park, J.K., Kim, B.H.:On the convergence rate improvement of mathematical decomposition technique on distributed optimal power flow. Int. J. Electr. Power Energy Syst. 25(1), 31-39(2003)
[32] Gabay, D., Mercier, B.:A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. With Appl. 2(1), 17-40(1976)
[33] Aybat, N.S., Hamedani, E.Y.:A distributed ADMM-like method for resource sharing under conic constraints over time-varying networks. arXiv:1611.07393(2016)
[34] Li,M., Sun, D., Toh, K.C.:Amajorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization. SIAM J. Optim. 26(2), 922-950(2016)
[35] He, B., Yuan, X.:On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J. Numer. Anal. 50(2), 700-709(2012)
[36] Monteiro, R.D., Svaiter, B.F.:Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23(1), 475-507(2013)
[37] Gao, X., Zhang, S.Z.:First-order algorithms for convex optimization with nonseparable objective and coupled constraints. J. Oper. Res. Soc. China 5(2), 131-159(2017)
[38] Deng, W., Yin, W.:On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889-916(2016)
[39] Hong, M., Luo, Z.Q.:On the linear convergence of the alternating direction method of multipliers. Math. Program. 162(1-2), 165-199(2017)
[40] Lin, T.,Ma, S., Zhang, S.:On the global linear convergence of the ADMM with multiblock variables. SIAM J. Optim. 25(3), 1478-1497(2015)
[41] Liu, Y., Yuan, X., Zeng, S., Zhang, J.:Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers. SIAM J. Numer. Anal. 56(4), 2095-2123(2018)
[42] Chen, G., Teboulle, M.:A proximal-based decomposition method for convex minimization problems. Math. Program. 64(1-3), 81-101(1994)
[43] Zhang, X., Burger, M., Osher, S.:A unified primal-dual algorithm framework based on Bregman iteration. J. Sci. Comput. 46(1), 20-46(2011)
[44] Deng,W., Lai, M.J., Peng, Z., Yin,W.:Parallel multi-block ADMM with o(1/k) convergence. J. Sci. Comput. 71(2), 712-736(2017)
[45] Börgens, E., Kanzow, C.:Regularized Jacobi-type ADMM-methods for a class of separable convex optimization problems in Hilbert spaces. Comput. Optim. Appl. 73(3), 755-790(2019)
[46] Chambolle, A., Pock, T.:A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120-145(2011)
[47] Chambolle, A., Pock, T.:On the ergodic convergence rates of a first-order primal-dual algorithm. Math. Program. 159(1-2), 253-287(2016)
[48] Nemirovski, A.:Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1), 229-251(2004)
[49] He, N., Juditsky, A., Nemirovski, A.:Mirror prox algorithm for multi-term composite minimization and semi-separable problems. Comput. Optim. Appl. 61(2), 275-319(2015)
[50] Juditsky, A., Nemirovski, A.:First order methods for nonsmooth convex large-scale optimization, ii:utilizing problems structure. Optim. Mach. Learn. 30(9), 149-183(2011)
[51] Hamedani, E.Y., Aybat, N.S.:A primal-dual algorithm for general convex-concave saddle point problems. arXiv:1803.01401(2018)
[52] Fang, Z.,Li,Y.,Liu,C., Zhu,W.,Zhang,Y.,Zhou,W.:Large-scale personalized delivery for guaranteed display advertising with real-time pacing. IEEE Int. Conf. Data Min. (ICDM) 2019, 190-199(2019)
[53] Hojjat, A., Turner, J., Cetintas, S., Yang, J.:A unified framework for the scheduling of guaranteed targeted display advertising under reach and frequency requirements. Oper. Res. 65(2), 289-313(2017)
[54] Turner, J.:The planning of guaranteed targeted display advertising. Oper. Res. 60(1), 18-33(2012)
[55] Turner, J., Hojjat, A., Cetintas, S., Yang, J.:Delivering guaranteed display ADS under reach and frequency requirements. In:Twenty-Eighth AAAI Conference on Artificial Intelligence. AAAI Press (2014)
[56] Slawski, M., Zu Castell,W., Tutz, G.:Feature selection guided by structural information. Ann. Appl. Stat. 4, 1056-1080(2010)
[57] Slawski, M.:The structured elastic net for quantile regression and support vector classification. Stat. Comput. 22(1), 153-168(2012)
[58] Ortega, J.M., Rheinboldt, W.C.:Iterative Solution of Nonlinear Equations in Several Variables, vol. 30. SIAM, Philadelphia (1970)
[59] Shapiro, A., Scheinberg, K.:Duality and optimality conditions. Handbook of Semidefinite Programming, pp. 67-110(2000)
[60] Cheney, W., Goldstein, A.A.:Proximity maps for convex sets. Proc. Am. Math. Soc. 10(3), 448-450(1959)
[61] Wierzbicki, A.P., Kurcyusz, S.:Projection on a cone, penalty functionals and duality theory for problems with inequaltity constraints in Hilbert space. SIAM J. Control Optim. 15(1), 25-56(1977)
[62] Beck, A., Teboulle, M.:Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3), 167-175(2003)
[63] Boyd, S., Vandenberghe, L.:Convex Optimization. Cambridge University Press, Cambridge (2004)
[64] Hiriart-Urruty, J.B., Lemaréchal, C.:ConvexAnalysis and MinimizationAlgorithms I:Fundamentals, vol. 305. Springer, Berlin (2013)
[65] Aybat, N.S., Iyengar, G.:Aunified approach for minimizing composite norms.Math. Program. 144(1-2), 181-226(2014)
[66] Vapnik, V.:Statistical Learning Theory, vol. 3. Wiley, New York (1998)
[67] Bi, J., Vapnik, V.N.:Learning with rigorous support vector machines. In:Learning Theory and Kernel Machines, pp. 243-257. Springer, Berlin (2003)
[68] Oneto, L., Ridella, S., Anguita, D.:Tikhonov, Ivanov and Morozov regularization for support vector machine learning. Mach. Learn. 103(1), 103-136(2016)
[69] Zhao, L., Zhu, D.:First-order primal-dualmethod for nonlinear convex cone programs. arXiv preprint arXiv:1801.00261v5(2019) 123