×

Efficient iterative method for SOAV minimization problem with linear equality and box constraints and its linear convergence. (English) Zbl 07507117

Summary: This study proposes an efficient algorithm for the sum-of-absolute-values (SOAV) minimization problem with linear equality and box constraints by exploiting alternating direction method of multipliers (ADMM). In the iteration of ADMM, efficient algorithms for the calculations of proximal points, which are the solutions of sub-problems and have great effects on the computation efficiency, are employed. By focusing on the dynamical structure of the iteration, the linear convergence of the proposed algorithm is proven. Furthermore, a practical application for mechanical system control with discrete-valued control illustrates the advantages of the proposed methods.

MSC:

49-XX Calculus of variations and optimal control; optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Branicky, M. S.; Borkar, V. S.; Mitter, S. K., A unified framework for hybrid control: model and optimal control theory, IEEE Trans. Autom. Control, 43, 1, 31-45 (1998) · Zbl 0951.93002
[2] Bemporad, A.; Morari, M., Control of systems integrating logic, dynamics, and constraints, Automatica, 35, 3, 407-427 (1999) · Zbl 1049.93514
[3] Hespanhol, P.; Quirynen, R.; Di Cairano, S., A structure exploiting branch-and-bound algorithm for mixed-integer model predictive control, Proceedings of the 2019 18th European Control Conference (ECC), 2763-2768 (2019)
[4] Axehill, D.; Hansson, A., A mixed integer dual quadratic programming algorithm tailored for MPC, Proceedings of the 45th IEEE Conference on Decision and Control, 5693-5698 (2006)
[5] Ikeda, T.; Nagahara, M.; Ono, S., Discrete-valued control of linear time-invariant systems by sum-of-absolute-values optimization, IEEE Trans. Autom. Control, 62, 6, 2750-2763 (2017) · Zbl 1369.49048
[6] Aguilera, R. P.; Urrutia, G.; Delgado, R. A.; Dolz, D.; Agüero, J. C., Quadratic model predictive control including input cardinality constraints, IEEE Trans. Autom. Control, 62, 6, 3068-3075 (2017) · Zbl 1369.93328
[7] Giselsson, P.; Boyd, S., Linear convergence and metric selection for Douglas-Rachford splitting and ADMM, IEEE Trans. Autom. Control, 62, 2, 532-544 (2017) · Zbl 1364.90256
[8] Giarré, L.; Argenti, F., Mixed \(\ell_2\) and \(\ell_1\)-norm regularization for adaptive detrending with ARMA modeling, J Franklin Inst., 355, 3, 1493-1511 (2018) · Zbl 1393.93084
[9] Banjac, G.; Goulart, P. J., Tight global linear convergence rate bounds for operator splitting methods, IEEE Trans. Autom. Control, 63, 12, 4126-4139 (2018) · Zbl 1423.90175
[10] Tian, T.; Wu, F.-Y.; Yang, K., Block-sparsity regularized maximum correntropy criterion for structured-sparse system identification, J. Franklin Inst., 357, 17, 12960-12985 (2020) · Zbl 1454.93055
[11] Wang, Y.; Li, Y.; Yang, R., Sparse adaptive channel estimation based on mixed controlled \(l_2\) and \(l_p\)-norm error criterion, J. Franklin Inst., 354, 15, 7215-7239 (2017) · Zbl 1373.93333
[12] Uchida, K.; Yamada, I., An \(\ell_1\)-penalized adaptive normalized quasi-newton algorithm for sparsity-aware generalized eigen-subspace tracking, J. Franklin Inst., 357, 8, 5033-5057 (2020) · Zbl 1437.93041
[13] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1, 1-122 (2011) · Zbl 1229.90122
[14] Lorenz, D. A.; Pfetsch, M. E.; Tillmann, A. M., Solving basis pursuit: heuristic optimality check and solver comparison, ACM Trans. Math. Softw., 41, 2, 1-29 (2015) · Zbl 1371.65055
[15] 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) · Zbl 1245.90084
[16] Toyoda, M.; Tanaka, M., Local R-linear convergence of ADMM-based algorithm for \(\ell_1\)-norm minimization with linear and box constraints, Syst. Control Lett., 146, 104824 (2020) · Zbl 1456.90159
[17] Eckstein, J.; Bertsekas, D. P., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 1, 293-318 (1992) · Zbl 0765.90073
[18] http://www.athenasc.com/convexduality.html · Zbl 1242.90001
[19] http://jmlr.org/papers/v15/wang14a.html · Zbl 1319.90051
[20] Necoara, I.; Nesterov, Y.; Glineur, F., Linear convergence of first order methods for non-strongly convex optimization, Math. Program., 175, 1, 69-107 (2019) · Zbl 1412.90111
[21] Bolte, J.; Nguyen, T. P.; Peypouquet, J.; Suter, B. W., From error bounds to the complexity of first-order descent methods for convex functions, Math. Program., 165, 2, 471-507 (2017) · Zbl 1373.90076
[22] Beck, A.; Shtern, S., Linearly convergent away-step conditional gradient for non-strongly convex functions, Math. Program., 164, 1, 1-27 (2017) · Zbl 1370.90010
[23] Hong, M.; Luo, Z. Q., On the linear convergence of the alternating direction method of multipliers, Math. Program., 162, 1, 165-199 (2017) · Zbl 1362.90313
[24] https://doi.org/10.1007/s10589-013-9616-x · Zbl 1303.90080
[25] B. He, X. Yuan, Balanced augmented lagrangian method for convex programming, 2021, arXiv preprint arXiv:2108.08554.
[26] https://epubs.siam.org/doi/book/10.1137/1.9781611970944 · Zbl 0832.65046
[27] Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P., Numerical Recipes 3rd Edition: The Art of Scientific Computing (2007), Cambridge University Press: Cambridge University Press USA · Zbl 1132.65001
[28] http://jmlr.org/papers/v18/16-274.html · Zbl 1433.68351
[29] Olshanskii, M. A.; Tyrtyshnikov, E. E., Iterative methods for linear systems: theory and applications, Society for Industrial and Applied Mathematics, USA (2014) · Zbl 1320.65050
[30] Jiao, X.; Zhang, J.; Shen, T., An adaptive servo control strategy for automotive electronic throttle and experimental validation, IEEE Trans. Ind. Electron., 61, 11, 6275-6284 (2014)
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.