×

Quadratic maximization of reachable values of affine systems with diagonalizable matrix. (English) Zbl 1470.90062

Summary: In this paper, we solve a maximization problem where the objective function is quadratic and convex or concave and the constraints set is the reachable values set of a convergent discrete-time affine system. Moreover, we assume that the matrix defining the system is diagonalizable. The difficulty of the problem lies in the treatment of infinite sequences belonging to the constraint set. Equivalently, the problem requires to solve an infinite number of quadratic programs. Therefore, the main idea is to extract a finite number of them and to guarantee that the resolution of the extracted problems provides the optimal value and a maximizer for the initial problem. The number of quadratic programs to solve has to be the smallest possible. Actually, we construct a family of integers that over-approximate the exact number of quadratic programs to solve using basic ideas of linear algebra. This family of integers is used in the final algorithm. A new computation of an integer of the family within the algorithm ensures a reduction of the number of iterations. The method proposed in the paper is illustrated on small academic examples. Finally, the algorithm is experimented on randomly generated instances of the problem.

MSC:

90C20 Quadratic programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adjé, A.; Bogomolov, S.; Martel, M.; Prabhakar, P., Proving properties on PWA systems using copositive and semidefinite programming, Numerical Software Verification, 15-30 (2017), Cham: Springer, Cham · Zbl 1429.68138 · doi:10.1007/978-3-319-54292-8_2
[2] Adjé, A., Garoche, P.L., Magron, V.: Property-based polynomial invariant generation using sums-of-squares optimization. In: International Symposium On Static Analysis (SAS), pp. 235-251. Springer, New York (2015)
[3] Saberi, A., Stoorvogel, A., Sannuti, P.: H2 Optimal Control with an Output Regulation Constraint - Discrete-Time Systems, pp. 303-315. Springer, London (2000). doi:10.1007/978-1-4471-0727-9_9 · Zbl 0977.93001
[4] Kiumarsi, B.; Lewis, FL; Naghibi-Sistani, M.; Karimpour, A., Optimal tracking control of unknown discrete-time linear systems using input-output measured data, IEEE Trans. Cybern., 45, 12, 2770-2779 (2015) · doi:10.1109/TCYB.2014.2384016
[5] Petersen, IR; McFarlane, DC; Rotea, MA, Optimal guaranteed cost control of discrete-time uncertain linear systems, Int. J. Robust Nonlinear Control, 8, 8, 649-657 (1998) · Zbl 0911.93048 · doi:10.1002/(SICI)1099-1239(19980715)8:8<649::AID-RNC334>3.0.CO;2-6
[6] Iwasaki, T., Robust performance analysis for systems with structured uncertainty, Int. J. Robust Nonlinear Control, 6, 2, 85-99 (1996) · Zbl 0848.93015 · doi:10.1002/(SICI)1099-1239(199603)6:2<85::AID-RNC137>3.0.CO;2-Z
[7] Zhang, H.; Umenberger, J.; Hu, X., Inverse optimal control for discrete-time finite-horizon linear quadratic regulators, Automatica (2019) · Zbl 1429.93217 · doi:10.1016/j.automatica.2019.108593
[8] Ahiyevichh, V., Parsegov, S., Shcherbakov, P.: Upper bounds on peaks in discrete-time linear systems. Automatic Remote Control (2018). doi:10.31857/S000523100002775-6 · Zbl 1406.93193
[9] Balakrishnan, V.; Boyd, S., On computing the worst-case peak gain of linear systems, Syst. Control Lett., 19, 4, 265-269 (1992) · Zbl 0778.93072 · doi:10.1016/0167-6911(92)90064-Y
[10] Ghosh, B.; Duggirala, PS, Robust reachable set: accounting for uncertainties in linear dynamical systems, ACM Trans. Embed. Comput. Syst. (TECS), 18, 5, 1-22 (2019) · doi:10.1145/3358229
[11] Kong, H., Bartocci, E., Henzinger, T.A.: Reachable Set Over-Approximation for Nonlinear Systems using Piecewise Barrier Tubes. In: International Conference on Computer Aided Verification, pp. 449-467. Springer (2018) · Zbl 1511.68159
[12] Belta, C.; Yordanov, B.; Gol, EA, Formal Methods for Discrete-time Dynamical Systems (2017), New York: Springer, New York · Zbl 1409.93003 · doi:10.1007/978-3-319-50763-7
[13] Wolkowicz, H.; Saigal, R.; Vandenberghe, L., Handbook of Semidefinite Programming: Theory, Algorithms, and Applications (2012), New York: Springer, New York · Zbl 0962.90001
[14] Adjé, A.: Optimal analysis of discrete-time affine systems (2018)
[15] Ahmadi, A.A., Günlük, O.: Robust-to-dynamics linear programming. In: Proceedings of the 2015 54th IEEE Conference on Decision and Control (CDC), pp. 5915-5919 (2015). doi:10.1109/CDC.2015.7403149
[16] Ahmadi, A.A., Günlük, O.: Robust-to-Dynamics Optimization. arXiv preprint arXiv:1805.03682 (2018)
[17] Sun, Z., Switched Linear Systems: Control and Design (2006), New York: Springer, New York
[18] Fijalkow, N., Ouaknine, J., Pouly, A., Sousa-Pinto, J., Worrell, J.: On the decidability of reachability in linear time-invariant systems. In: Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control (HSCC), pp. 77-86 (2019) · Zbl 07120143
[19] Ouaknine, J., Worrell, J.: On the positivity problem for simple linear recurrence sequences. In: International Colloquium on Automata, Languages, and Programming (ICALP), pp. 318-329. Springer, New York (2014) · Zbl 1410.11134
[20] Horn, RA; Johnson, CR, Matrix Analysis (1990), Cambridge: Cambridge University Press, Cambridge · Zbl 0704.15002
[21] Furini, F.; Traversi, E.; Belotti, P.; Frangioni, A.; Gleixner, A.; Gould, N.; Liberti, L.; Lodi, A.; Misener, R.; Mittelmann, H., Qplib: a library of quadratic programming instances, Math. Program. Comput., 11, 2, 237-265 (2019) · Zbl 1435.90099 · doi:10.1007/s12532-018-0147-4
[22] Floudas, C.; Visweswaran, V., A global optimization algorithm (GOP) for certain classes of nonconvex NLPs-I. Theory, Comput. Chem. Eng., 14, 12, 1397-1417 (1990) · doi:10.1016/0098-1354(90)80020-C
[23] Burer, S.; Vandenbussche, D., A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Math. Program., 113, 2, 259-282 (2008) · Zbl 1135.90034 · doi:10.1007/s10107-006-0080-6
[24] Absil, PA; Tits, AL, Newton-KKT interior-point methods for indefinite quadratic programming, Comput. Optim. Appl., 36, 1, 5-41 (2007) · Zbl 1278.90288 · doi:10.1007/s10589-006-8717-1
[25] Huyer, W.; Neumaier, A., MINQ8: general definite and bound constrained indefinite quadratic programming, Comput. Optim. Appl., 69, 2, 351-381 (2018) · Zbl 1400.90240 · doi:10.1007/s10589-017-9949-y
[26] Zhang, S., Quadratic maximization and semidefinite relaxation, Math. Program., 87, 3, 453-465 (2000) · Zbl 1009.90080 · doi:10.1007/s101070050006
[27] Kim, S.; Kojima, M., Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations, Comput. Optim. Appl., 26, 2, 143-154 (2003) · Zbl 1043.90060 · doi:10.1023/A:1025794313696
[28] Burer, S., Ye, Y.: Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs. Math. Program. pp. 1-17 (2019) · Zbl 1445.90073
[29] Vanderbei, RJ, LOQO: an interior-point code for quadratic programming, Optim. Methods Softw., 11, 1-4, 451-484 (1999) · Zbl 0973.90518 · doi:10.1080/10556789908805759
[30] Friedlander, MP; Orban, D., A primal-dual regularized interior-point method for convex quadratic programs, Math. Program. Comput., 4, 1, 71-107 (2012) · Zbl 1279.90193 · doi:10.1007/s12532-012-0035-2
[31] Tian, DG, An exterior point polynomial-time algorithm for convex quadratic programming, Comput. Optim. Appl., 61, 51-78 (2015) · Zbl 1311.90088 · doi:10.1007/s10589-014-9710-8
[32] Curtis, FE; Han, Z.; Robinson, DP, A globally convergent primal-dual active-set framework for large-scale convex quadratic optimization, Comput. Optim. Appl., 60, 2, 311-341 (2015) · Zbl 1309.90072 · doi:10.1007/s10589-014-9681-9
[33] Forsgren, A.; Gill, PE; Wong, E., Primal and dual active-set methods for convex quadratic programming, Math. Program., 159, 1-2, 469-508 (2016) · Zbl 1346.90652 · doi:10.1007/s10107-015-0966-2
[34] Tuy, H., Nonconvex Quadratic Programming, 337-390 (2016), Cham: Springer, Cham · doi:10.1007/978-3-319-31484-6_10
[35] Konno, H., Maximization of a convex quadratic function under linear constraints, Math. Program., 11, 1, 117-127 (1976) · Zbl 0355.90052 · doi:10.1007/BF01580380
[36] Floudas, C. A.; Visweswaran, V., Quadratic Optimization, 217-269 (1995), Boston: Springer, Boston · Zbl 0833.90091 · doi:10.1007/978-1-4615-2025-2_5
[37] Bezanson, J.; Edelman, A.; Karpinski, S.; Shah, VB, Julia: a fresh approach to numerical computing, SIAM Rev., 59, 1, 65-98 (2017) · Zbl 1356.68030 · doi:10.1137/141000671
[38] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
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.