zbMATH — the first resource for mathematics

Decentralized hierarchical constrained convex optimization. (English) Zbl 1431.65086
Summary: This paper proposes a decentralized optimization algorithm for the triple-hierarchical constrained convex optimization problem of minimizing a sum of strongly convex functions subject to a paramonotone variational inequality constraint over an intersection of fixed point sets of nonexpansive mappings. The existing algorithms for solving this problem are centralized optimization algorithms using all the information in the problem, and these algorithms are effective, but only under certain additional restrictions. The main contribution of this paper is to present a convergence analysis of the proposed algorithm in order to show that the proposed algorithm using incremental gradients with diminishing step-size sequences converges to the solution to the problem without any additional restrictions. Another contribution of this paper is the elucidation of the practical applications of hierarchical constrained optimization in the form of network resource allocation and optimal control problems. In particular, it is shown that the proposed algorithm can be applied to decentralized network resource allocation with a triple-hierarchical structure.
MSC:
 65K05 Numerical mathematical programming methods 65K15 Numerical methods for variational inequalities and related problems 90C25 Convex programming
Pegasos
Full Text:
References:
 [1] Attouch, H., Viscosity solutions of minimization problems, SIAM J Optim, 6, 769-806 (1996) · Zbl 0859.65065 [2] Baillon, Jb; Haddad, G., Quelques propriétés des opérateurs angle-bornés et $$n$$-cycliquement monotones, Isr J Math, 26, 137-150 (1977) · Zbl 0352.47023 [3] Bauschke, Hh; Combettes, Pl, Convex analysis and monotone operator theory in Hilbert spaces (2011), New York: Springer, New York [4] Berinde, V., Iterative approximation of fixed points (2007), Berlin: Springer, Berlin · Zbl 1165.47047 [5] Bertsekas, Dp, Incremental proximal methods for large scale convex optimization, Math Program, 129, 163-195 (2011) · Zbl 1229.90121 [6] Bertsekas, Dp; Nedić, A.; Ozdaglar, Ae, Convex analysis and optimization (2003), Cambridge: Athena Scientific, Cambridge [7] Browder, Fe; Petryshyn, Wv, Construction of fixed points of nonlinear mappings in Hilbert space, J Math Anal Appl, 20, 197-228 (1967) · Zbl 0153.45701 [8] Cabot, A., Proximal point algorithm controlled by a slowly vanishing term: applications to hierarchical minimization, SIAM J Optim, 15, 555-572 (2005) · Zbl 1079.90098 [9] Censor, Y.; Iusem, An; Zenios, S., An interior point method with Bregman functions for the variational inequality problem with paramonotone operators, Math Program, 81, 373-400 (1998) · Zbl 0919.90123 [10] Chen, S.; Li, X.; Zhou, Xy, Stochastic linear quadratic regulators with indefinite control weight costs, SIAM J Control Optim, 36, 1685-1702 (1998) · Zbl 0916.93084 [11] Combettes, Pl, A block-iterative surrogate constraint splitting method for quadratic signal recovery, IEEE Trans Signal Process, 51, 1771-1782 (2003) · Zbl 1369.94121 [12] Combettes, Pl; Bondon, P., Hard-constrained inconsistent signal feasibility problems, IEEE Trans Signal Process, 47, 2460-2468 (1999) · Zbl 0979.94016 [13] Cominetti, R.; Courdurier, M., Coupling general penalty schemes for convex programming with the steepest descent and the proximal point algorithm, SIAM J Optim, 13, 745-765 (2005) · Zbl 1049.90056 [14] Ekeland, I.; Témam, R., Convex analysis and variational problems. Classics in applied mathematics (1999), Philadelphia: SIAM, Philadelphia · Zbl 0939.49002 [15] Facchinei, F.; Pang, Js, Finite-dimensional variational inequalities and complementarity problems I (2003), New York: Springer, New York [16] Goebel, K.; Kirk, Wa, Topics in metric fixed point theory. Cambridge studies in advanced mathematics (1990), New York: Cambridge University Press, New York [17] Grigoriadis, Km; Skelton, Re, Alternating convex projection methods for discrete-time covariance control design, J Optim Theory Appl, 88, 399-432 (1996) · Zbl 0854.93146 [18] Halpern, B., Fixed points of nonexpanding maps, Bull Am Math Soc, 73, 957-961 (1967) · Zbl 0177.19101 [19] Helou Neto, E.; De Pierro, A., Incremental subgradients for constrained convex optimization: a unified framework and new methods, SIAM J Optim, 20, 1547-1572 (2009) · Zbl 1207.65082 [20] Iiduka, H., Iterative algorithm for solving triple-hierarchical constrained optimization problem, J Optim Theory Appl, 148, 580-592 (2011) · Zbl 1216.90092 [21] Iiduka, H., Fixed point optimization algorithm and its application to power control in CDMA data networks, Math Program, 133, 227-242 (2012) · Zbl 1274.90428 [22] Iiduka, H., Iterative algorithm for triple-hierarchical constrained nonconvex optimization problem and its application to network bandwidth allocation, SIAM J Optim, 22, 862-878 (2012) · Zbl 1267.90139 [23] Iiduka, H., Fixed point optimization algorithms for distributed optimization in networked systems, SIAM J Optim, 23, 1-26 (2013) · Zbl 1266.49067 [24] Iiduka, H., Acceleration method for convex optimization over the fixed point set of a nonexpansive mapping, Math Program, 149, 131-165 (2015) · Zbl 1338.90301 [25] Iiduka, H., Convergence analysis of iterative methods for nonsmooth convex optimization over fixed point sets of quasi-nonexpansive mappings, Math Program, 159, 509-538 (2016) · Zbl 1351.65035 [26] Iiduka, H., Proximal point algorithms for nonsmooth convex optimization with fixed point constraints, Eur J Oper Res, 253, 503-513 (2016) · Zbl 1346.90663 [27] Iiduka H (2018) Distributed optimization for network resource allocation with nonsmooth utility functions. IEEE Trans Control Netw Syst (accepted for publication) [28] Iiduka, H.; Hishinuma, K., Acceleration method combining broadcast and incremental distributed optimization algorithms, SIAM J Optim, 24, 1840-1863 (2014) · Zbl 1317.49044 [29] Iiduka, H.; Uchida, M., Fixed point optimization algorithms for network bandwidth allocation problems with compoundable constraints, IEEE Commun Lett, 15, 596-598 (2011) [30] Iiduka, H.; Yamada, I., A use of conjugate gradient direction for the convex optimization problem over the fixed point set of a nonexpansive mapping, SIAM J Optim, 19, 1881-1893 (2009) · Zbl 1176.47064 [31] Iiduka, H.; Yamada, I., Computational method for solving a stochastic linear-quadratic control problem given an unsolvable stochastic algebraic Riccati equation, SIAM J Control Optim, 50, 2173-2192 (2012) · Zbl 1252.93134 [32] Kelly, Fp, Charging and rate control for elastic traffic, Eur Trans Telecommun, 8, 33-37 (1997) [33] Kinderlehrer, D.; Stampacchia, G., An introduction to variational inequalities and their applications. Classics in Applied Mathematics (2000), Philadelphia: SIAM, Philadelphia · Zbl 0988.49003 [34] Krasnosel’Skiĭ, Ma, Two remarks on the method of successive approximations, Usp Mat Nauk, 10, 123-127 (1955) [35] Maingé, Pe, The viscosity approximation process for quasi-nonexpansive mappings in Hilbert spaces, Comput Math Appl, 59, 74-79 (2010) · Zbl 1189.49011 [36] Maingé, Pe; Moudafi, A., Strong convergence of an iterative method for hierarchical fixed-point problems, Pac J Optim, 3, 529-538 (2007) · Zbl 1158.47057 [37] Mann, Wr, Mean value methods in iteration, Proc Am Math Soc, 4, 506-510 (1953) · Zbl 0050.11603 [38] Mo, J.; Walrand, J., Fair end-to-end window-based congestion control, IEEE/ACM Trans Netw, 8, 556-567 (2000) [39] Moudafi, A., Krasnoselski-Mann iteration for hierarchical fixed-point problems, Inverse Probl, 23, 1635-1640 (2007) · Zbl 1128.47060 [40] Nedić, A.; Bertsekas, Dp, Incremental sugradient methods for nondifferentiable optimization, SIAM J Optim, 12, 109-138 (2001) · Zbl 0991.90099 [41] Nedić, A.; Ozdaglar, A., Approximate primal solutions and rate analysis for dual subgradient methods, SIAM J Optim, 19, 1757-1780 (2009) · Zbl 1191.90037 [42] Rami, Ma; Zhou, Xy, Linear matrix inequalities, Riccati equations, and indefinite stochastic linear quadratic controls, IEEE Trans Autom Control, 45, 1131-1142 (2000) [43] Rockafellar, Rt, Convex analysis (1970), Princeton: Princeton University Press, Princeton [44] Shalev-Shwartz, S.; Singer, Y.; Srebro, N.; Cotter, A., Pegasos: primal estimated sub-gradient solver for SVM, Math Program, 127, 3-30 (2011) · Zbl 1211.90239 [45] Slavakis, K.; Yamada, I., Robust wideband beamforming by the hybrid steepest descent method, IEEE Trans Signal Process, 55, 4511-4522 (2007) · Zbl 1390.94416 [46] Srikant, R., The mathematics of internet congestion control (2004), Boston: Birkhauser, Boston · Zbl 1086.68018 [47] Takahashi, W., Nonlinear functional analysis (2000), Yokohama: Yokohama Publishers, Yokohama [48] Vasin, Vv; Ageev, Al, Ill-posed problems with a priori information (1995), Utrecht: V.S.P. Intl Science, Utrecht · Zbl 0840.65048 [49] Wittmann, R., Approximation of fixed points of nonexpansive mappings, Arch Math, 58, 486-491 (1992) · Zbl 0797.47036 [50] Wonham, Wm, On a matrix Riccati equation of stochastic control, SIAM J Control, 6, 681-697 (1968) · Zbl 0182.20803 [51] Yamada, I.; Butnariu, D.; Censor, Y.; Reich, S., The hybrid steepest descent method for the variational inequality problem over the intersection of fixed point sets of nonexpansive mappings, Inherently parallel algorithms for feasibility and optimization and their applications, 473-504 (2001), New York: Elsevier, New York · Zbl 1013.49005 [52] Yamagishi, M.; Yamada, I., Nonexpansiveness of a linearized augmented Lagrangian operator for hierarchical convex optimization, Inverse Probl, 33, 044003 (2017) · Zbl 06723364 [53] Yu, H.; Neely, Mj, A simple parallel algorithm with an $${O}(1/t)$$ convergence rate for general convex programs, SIAM J Optim, 27, 759-783 (2017) · Zbl 1365.90207 [54] Zeidler, E., Nonlinear functional analysis and its applications II/B. Nonlinear monotone operators (1985), New York: Springer, New York
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.