S-引理及其进展

doi:10.15960/j.cnki.issn.1007-6093.2023.04.002

Abstract

Abstract:

S-lemma is an important theorem in operations research and cybernetics. In this paper, starting from verifying the global asymptotic stability of a nonlinear control system, we draw S-procedure, S-lemma, and their relations and differences. Then the basic content of S-lemma and its latest advances are introduced. Moreover, several generalizations of S-lemma over the complex field and the quaternion set are discussed. Finally, some basic results corresponding to S-lemma are showed for any number of symmetric (or Hermitian) matrices.

Key words: S-procedure, S-lemma, Yuan's lemma, low-rank solutions

CLC Number:

Wenbao AI, Wei LIANG, Mengxiao ZHANG. S-lemma and its extension[J]. Operations Research Transactions, 2023, 27(4): 20-32.

References 34

1	Lur'e A I , Postnikov V N . On the theory of stability of control systems[J]. Prikladnaya Matamatika I Mekhanika, 1944, 8, 3- 13.
2	Aizerman M A , Gantmacher F R . Absolute Stability of Regulator Systems[M]. San Francisco: Holden-Day Series in Information Systems, 1964.
3	Yakubovich V A . S-procedure in nonlinear control theory[J]. Vestnik Leningradskogo Universiteta, 1971, 1, 62- 77.
4	Yakubovich V A . S-procedure in nonlinear control theory[J]. Vestnik Leningradskogo Universiteta, 1977, 4, 63- 93.
5	Yakubovich V A . Minimization of quadratic functionals under quadratic constraints and the necessity of a frequency condition in the quadratic criterion for absolute stability of nonlinear control systems[J]. Soviet Mathematics Doklady, 1973, 14 (2): 593- 597.
6	Megretsky A , Treil S . Power distribution in optimization and robustness of uncertain systems[J]. Journal of Mathematical Systems Estimation and Control, 1993, 3, 301- 319.
7	Boyd S , Ghaoui L E , Feron E , et al. Linear Matrix Inequalities in System and Control Theory[M]. Philadelphia: SIAM Studies in Applied Mathematics, 1994.
8	Lyapunov A M . The general problem of the stability of motion[J]. International Journal of Control, 1992, 55 (3): 531- 773. doi: 10.1080/00207179208934253
9	Finsler P . Über das vorkommen definiter und semidefiniter Formen in scharen quadratischer Formen[J]. Commentarii Mathematici Helvetici, 1937, 9, 188- 192.
10	Calabi E . Linear systems of real quadratic forms[J]. Proceedings of the American Mathematical Society, 1964, 15 (5): 844- 846. doi: 10.1090/S0002-9939-1964-0166203-7
11	Dines L L . On the mapping of quadratic forms[J]. Bulletin of the American Mathematical Society, 1941, 47, 494- 498. doi: 10.1090/S0002-9904-1941-07494-X
12	袁亚湘, 孙文瑜. 最优化理论与方法[M]. 北京: 科学出版社, 1997.
13	Derinkuyu K , Pınar M C . On the S-procedure and some variants[J]. Mathematical Methods of Operations Research, 2006, 64, 55- 77. doi: 10.1007/s00186-006-0070-8
14	Hu S L , Huang Z H . Theorems of the alternative for inequality systems of real polynomials[J]. Journal of Optimization Theory and Applications, 2012, 154 (1): 1- 16. doi: 10.1007/s10957-012-9993-9
15	Jeyakumar V , Lee G M , Li G Y . Alternative theorems for quadratic inequality systems and global quadratic optimization[J]. SIAM Journal on Optimization, 2009, 20 (2): 983- 1001. doi: 10.1137/080736090
16	Luo Z Q , Sturm J F , Zhang S Z . Multivariate nonegative quadratic mappings[J]. SIAM Journal on Optimization, 2004, 14, 1140- 1162. doi: 10.1137/S1052623403421498
17	P'olik I , Terlaky T . A survey of the S-lemma[J]. SIAM Review, 2007, 49 (3): 371- 418. doi: 10.1137/S003614450444614X
18	Sturm J F , Zhang S Z . On cones of nonnegative quadratic functions[J]. Mathematics of Operations Research, 2003, 28, 246- 267. doi: 10.1287/moor.28.2.246.14485
19	Yuan Y X . On a subproblem of trust region algorithms for constrained optimization[J]. Mathematical Programming, 1990, 47, 53- 63. doi: 10.1007/BF01580852
20	Xia Y , Wang S , Sheu R L . S-lemma with equality and its applications[J]. Mathematical Programming, 2016, 156 (1): 513- 547.
21	Peng J M , Yuan Y X . Optimality conditions for the minimization of a quadratic with two quadratic constraints[J]. SIAM Journal on Optimization, 1997, 7, 579- 594. doi: 10.1137/S1052623494261520
22	Polyak B T . Convexity of quadratic transformations and its use in control and optimization[J]. Journal of Optimization Theory and Applications, 1998, 99 (3): 553- 583. doi: 10.1023/A:1021798932766
23	Ai W, Liang W, Yuan J. On the tightness of an SDP relaxation for homogeneous QCQP with three real or four complex homogeneous constraints [J]. 2023, arXiv: 2304.04174.
24	Chen X , Yuan Y X . A note on quadratic forms[J]. Mathematical Programming, 1999, 86, 187- 197. doi: 10.1007/s101070050085
25	Brickman L. On the field of values of a matrix [C]// Proceedings of the American Mathematical Society, 1961: 61-66.
26	Fradkov A L , Yakubovich V A . The S-procedure and duality relations in nonconvex problems of quadratic programming[J]. Vestnik Leningrad University, Leningrad, Russia, 1979, 6, 101- 109.
27	Huang Y W , Zhang S Z . Complex matrix decomposition and quadratic programming[J]. Mathematics of Operations Research, 2007, 32 (3): 758- 768. doi: 10.1287/moor.1070.0268
28	He C , Jiang B , Zhu X H . Quaternion matrix decomposition and its theoretical implications[J]. Journal of Global Optimization, 2023, 87, 741- 758. doi: 10.1007/s10898-022-01210-7
29	Barvinok A . Problems of distance geometry and convex properties of quadartic maps[J]. Discrete and Computational Geometry, 1995, 12, 189- 202.
30	Pataki G. Cone-LP's and semidefinite programs: Geometry and a simplex-type method [C]// Proceedingof the International Conference on Integer Programming and Combinatorial Optimization, 1996: 162-174.
31	Barvinok A . A remark on the rank of positive semidefinite matrices subject to affine constraints[J]. Discrete and Computational Geometry, 2001, 25, 23- 31. doi: 10.1007/s004540010074
32	Bohnenblust F . Joint positiveness of matrices[J]. Unpublished manuscript, 1984,
33	Au-Yeung Y H , Poon Y T . A remark on the convexity and positive definiteness concerning Hermitian matrices[J]. Southeast Asian Bulletin of Mathematics, 1979, 3 (2): 85- 92.
34	Ai W B , Huang Y W , Zhang S Z . On the low rank solutions for linear matrix inequalities[J]. Mathematics of Operations Research, 2008, 33 (4): 965- 975. doi: 10.1287/moor.1080.0331

[1]	Yonghong LIU, Congying HAN, Tiande GUO. Fingerprint orientation field estimation algorithm based on deep learning [J]. Operations Research Transactions, 2023, 27(4): 1-19.
[2]	SHAO Mengzhen, YU Changjun. A survey of direct methods for optimal control problems [J]. Operations Research Transactions, 2023, 27(4): 81-105.
[3]	WANG Xiangfeng, LI Wenhao. Machine learning-driven multi-agent pathfinding: An overview [J]. Operations Research Transactions, 2023, 27(4): 106-135.
[4]	JIANG Bo. On the theories, algorithms, and applications of optimization with nonnegative orthogonality constraints [J]. Operations Research Transactions, 2023, 27(4): 136-152.
[5]	WANG Xiao. Stochastic approximation methods for nonconvex constrained optimization [J]. Operations Research Transactions, 2023, 27(4): 153-165.
[6]	ZHANG Ying, JING Xinqi, WANG Changjun. A conjecture of optimal pricing for two matroids [J]. Operations Research Transactions, 2023, 27(4): 166-174.
[7]	Jing ZENG, Ruowen DING. Stability of solutions for a class of non-convex vector optimization problems with mapping differences [J]. Operations Research Transactions, 2023, 27(3): 121-128.
[8]	Yunwei ZHANG, Shuguang HAN. Research on city unmanned logistics distribution with simultaneous delivery and pickup [J]. Operations Research Transactions, 2023, 27(3): 53-67.
[9]	Ke SU, Xiaohui REN. A modified inventory pricing model with uncertainty demand [J]. Operations Research Transactions, 2023, 27(3): 21-36.
[10]	Wei XU, Yuefeng HUANG, Caihua CHEN. Charging and discharging scheduling for electric bus charging station with energy storage system [J]. Operations Research Transactions, 2023, 27(2): 95-109.
[11]	Maoran WANG, Xingju CAI, Zhongming WU, Deren HAN. First-order splitting algorithm for multi-model traffic equilibrium problems [J]. Operations Research Transactions, 2023, 27(2): 63-78.
[12]	Yun HUA, Xiangfeng WANG, Bo JIN. Multi-agent deep reinforcement learning-based urban traffic signal management [J]. Operations Research Transactions, 2023, 27(2): 49-62.
[13]	Hu SHAO, Yue ZHUO, Pengjie LIU, Feng SHAO. Operational research methods for urban traffic flow estimation [J]. Operations Research Transactions, 2023, 27(2): 27-48.
[14]	He WEI, Haofei LIU, Dandan XU, Xuehua HAN, Liang WANG, Xiaodong ZHANG. A systematic review of researches and applications of bi-level programming in the context of urban transport [J]. Operations Research Transactions, 2023, 27(2): 1-26.
[15]	Minglu YE, Huan DENG. A new projection and contraction algorithm for solving quasimonotone variational inequalities [J]. Operations Research Transactions, 2023, 27(1): 127-137.

S-lemma and its extension

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 34

Related Articles 15

Recommended Articles

Metrics

Comments