## Abstract

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.

This is a preview of subscription content, access via your institution.

## Notes

- 1.
(C2) and \(\lambda _n \le \alpha _n\)\((n\in {\mathbb {N}})\) imply (C1).

- 2.
Since \(\epsilon > 0\) is sufficiently small, we have that \(f(X) \approx - \mathrm {Tr}(X)\)\((X \in {\mathcal {S}}^{N + N_u})\) in the sense of the norm of \({\mathbb {R}}\). Hence, we can expect that the unique solution \(X^\star \) to problem (45) is almost the same as the unique minimizer of

*f*over \({\mathcal {C}}_g\).

## References

Attouch H (1996) Viscosity solutions of minimization problems. SIAM J Optim 6:769–806

Baillon JB, Haddad G (1977) Quelques propriétés des opérateurs angle-bornés et \(n\)-cycliquement monotones. Isr J Math 26:137–150

Bauschke HH, Combettes PL (2011) Convex analysis and monotone operator theory in Hilbert spaces. Springer, New York

Berinde V (2007) Iterative approximation of fixed points. Springer, Berlin

Bertsekas DP (2011) Incremental proximal methods for large scale convex optimization. Math Program 129:163–195

Bertsekas DP, Nedić A, Ozdaglar AE (2003) Convex analysis and optimization. Athena Scientific, Cambridge

Browder FE, Petryshyn WV (1967) Construction of fixed points of nonlinear mappings in Hilbert space. J Math Anal Appl 20:197–228

Cabot A (2005) Proximal point algorithm controlled by a slowly vanishing term: applications to hierarchical minimization. SIAM J Optim 15:555–572

Censor Y, Iusem AN, Zenios S (1998) An interior point method with Bregman functions for the variational inequality problem with paramonotone operators. Math Program 81:373–400

Chen S, Li X, Zhou XY (1998) Stochastic linear quadratic regulators with indefinite control weight costs. SIAM J Control Optim 36:1685–1702

Combettes PL (2003) A block-iterative surrogate constraint splitting method for quadratic signal recovery. IEEE Trans Signal Process 51:1771–1782

Combettes PL, Bondon P (1999) Hard-constrained inconsistent signal feasibility problems. IEEE Trans Signal Process 47:2460–2468

Cominetti R, Courdurier M (2005) Coupling general penalty schemes for convex programming with the steepest descent and the proximal point algorithm. SIAM J Optim 13:745–765

Ekeland I, Témam R (1999) Convex analysis and variational problems. Classics in applied mathematics, vol 28. SIAM, Philadelphia

Facchinei F, Pang JS (2003) Finite-dimensional variational inequalities and complementarity problems I. Springer, New York

Goebel K, Kirk WA (1990) Topics in metric fixed point theory. Cambridge studies in advanced mathematics. Cambridge University Press, New York

Grigoriadis KM, Skelton RE (1996) Alternating convex projection methods for discrete-time covariance control design. J Optim Theory Appl 88:399–432

Halpern B (1967) Fixed points of nonexpanding maps. Bull Am Math Soc 73:957–961

Helou Neto E, De Pierro A (2009) Incremental subgradients for constrained convex optimization: a unified framework and new methods. SIAM J Optim 20:1547–1572

Iiduka H (2011) Iterative algorithm for solving triple-hierarchical constrained optimization problem. J Optim Theory Appl 148:580–592

Iiduka H (2012) Fixed point optimization algorithm and its application to power control in CDMA data networks. Math Program 133:227–242

Iiduka H (2012) Iterative algorithm for triple-hierarchical constrained nonconvex optimization problem and its application to network bandwidth allocation. SIAM J Optim 22:862–878

Iiduka H (2013) Fixed point optimization algorithms for distributed optimization in networked systems. SIAM J Optim 23:1–26

Iiduka H (2015) Acceleration method for convex optimization over the fixed point set of a nonexpansive mapping. Math Program 149:131–165

Iiduka H (2016a) Convergence analysis of iterative methods for nonsmooth convex optimization over fixed point sets of quasi-nonexpansive mappings. Math Program 159:509–538

Iiduka H (2016b) Proximal point algorithms for nonsmooth convex optimization with fixed point constraints. Eur J Oper Res 253:503–513

Iiduka H (2018) Distributed optimization for network resource allocation with nonsmooth utility functions. IEEE Trans Control Netw Syst (accepted for publication)

Iiduka H, Hishinuma K (2014) Acceleration method combining broadcast and incremental distributed optimization algorithms. SIAM J Optim 24:1840–1863

Iiduka H, Uchida M (2011) Fixed point optimization algorithms for network bandwidth allocation problems with compoundable constraints. IEEE Commun Lett 15:596–598

Iiduka H, Yamada I (2009) 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

Iiduka H, Yamada I (2012) Computational method for solving a stochastic linear-quadratic control problem given an unsolvable stochastic algebraic Riccati equation. SIAM J Control Optim 50:2173–2192

Kelly FP (1997) Charging and rate control for elastic traffic. Eur Trans Telecommun 8:33–37

Kinderlehrer D, Stampacchia G (2000) An introduction to variational inequalities and their applications. Classics in Applied Mathematics, vol 31. SIAM, Philadelphia

Krasnosel’skiĭ MA (1955) Two remarks on the method of successive approximations. Usp Mat Nauk 10:123–127

Maingé PE (2010) The viscosity approximation process for quasi-nonexpansive mappings in Hilbert spaces. Comput Math Appl 59:74–79

Maingé PE, Moudafi A (2007) Strong convergence of an iterative method for hierarchical fixed-point problems. Pac J Optim 3:529–538

Mann WR (1953) Mean value methods in iteration. Proc Am Math Soc 4:506–510

Mo J, Walrand J (2000) Fair end-to-end window-based congestion control. IEEE/ACM Trans Netw 8:556–567

Moudafi A (2007) Krasnoselski–Mann iteration for hierarchical fixed-point problems. Inverse Probl 23:1635–1640

Nedić A, Bertsekas DP (2001) Incremental sugradient methods for nondifferentiable optimization. SIAM J Optim 12:109–138

Nedić A, Ozdaglar A (2009) Approximate primal solutions and rate analysis for dual subgradient methods. SIAM J Optim 19:1757–1780

Rami MA, Zhou XY (2000) Linear matrix inequalities, Riccati equations, and indefinite stochastic linear quadratic controls. IEEE Trans Autom Control 45:1131–1142

Rockafellar RT (1970) Convex analysis. Princeton University Press, Princeton

Shalev-Shwartz S, Singer Y, Srebro N, Cotter A (2011) Pegasos: primal estimated sub-gradient solver for SVM. Math Program 127:3–30

Slavakis K, Yamada I (2007) Robust wideband beamforming by the hybrid steepest descent method. IEEE Trans Signal Process 55:4511–4522

Srikant R (2004) The mathematics of internet congestion control. Birkhauser, Boston

Takahashi W (2000) Nonlinear functional analysis. Yokohama Publishers, Yokohama

Vasin VV, Ageev AL (1995) Ill-posed problems with a priori information. V.S.P. Intl Science, Utrecht

Wittmann R (1992) Approximation of fixed points of nonexpansive mappings. Arch Math 58:486–491

Wonham WM (1968) On a matrix Riccati equation of stochastic control. SIAM J Control 6:681–697

Yamada I (2001) The hybrid steepest descent method for the variational inequality problem over the intersection of fixed point sets of nonexpansive mappings. In: Butnariu D, Censor Y, Reich S (eds) Inherently parallel algorithms for feasibility and optimization and their applications. Elsevier, New York, pp 473–504

Yamagishi M, Yamada I (2017) Nonexpansiveness of a linearized augmented Lagrangian operator for hierarchical convex optimization. Inverse Probl 33:044003

Yu H, Neely MJ (2017) A simple parallel algorithm with an \({O}(1/t)\) convergence rate for general convex programs. SIAM J Optim 27:759–783

Zeidler E (1985) Nonlinear functional analysis and its applications II/B. Nonlinear monotone operators. Springer, New York

## Acknowledgements

The author is sincerely grateful to the anonymous referees for helping him improve the original manuscript.

## Author information

### Affiliations

### Corresponding author

## Ethics declarations

### Conflicts of interest

The author declares that he has no conflict of interest.

## Additional information

### Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work was supported by JSPS KAKENHI Grant Number JP18K11184.

## Rights and permissions

## About this article

### Cite this article

Iiduka, H. Decentralized hierarchical constrained convex optimization.
*Optim Eng* **21, **181–213 (2020). https://doi.org/10.1007/s11081-019-09440-7

Received:

Revised:

Accepted:

Published:

Issue Date:

### Keywords

- Decentralized optimization
- Fixed point
- Hierarchical constrained convex optimization
- Incremental optimization algorithm
- Network resource allocation
- Nonexpansive mapping
- Optimal control
- Paramonotone

### Mathematics Subject Classification

- 65K05
- 65K15
- 90C25