S-引理及其进展

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

运筹学学报 ›› 2023, Vol. 27 ›› Issue (4): 20-32.doi: 10.15960/j.cnki.issn.1007-6093.2023.04.002

S-引理及其进展

艾文宝¹^,*(), 梁炜¹, 张梦晓¹

1. 北京邮电大学理学院, 数学与信息网络教育部重点实验室, 北京, 100876

收稿日期:2023-04-28 出版日期:2023-12-15 发布日期:2023-12-07
通讯作者: 艾文宝 E-mail:aiwb@bupt.edu.cn
作者简介:艾文宝, E-mail: aiwb@bupt.edu.cn
基金资助:
国家自然科学基金(12171052);国家自然科学基金(12171051);国家自然科学基金(11971073);北京市自然科学基金(Z220004)

S-lemma and its extension

Wenbao AI¹^,*(), Wei LIANG¹, Mengxiao ZHANG¹

1. Key Laboratory of Mathematics and Information Networks, Ministry of Education, School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received:2023-04-28 Online:2023-12-15 Published:2023-12-07
Contact: Wenbao AI E-mail:aiwb@bupt.edu.cn

摘要/Abstract

摘要：

S-引理是运筹学领域和控制论领域中一个十分重要的定理。本文首先从一个非线性控制系统的全局渐近稳定性分析出发，引出S-过程和S-引理，以及两者之间的联系与区别。接着我们介绍了S-引理的基本内容和最新进展，以及它在复数域和四元数集合上的推广。最后，我们介绍了将齐次型S-引理推广到任意多个对称(或厄米特)矩阵时的一些基本结果。

关键词: S-过程, S-引理, 袁氏引理, 低秩解

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

中图分类号:

艾文宝, 梁炜, 张梦晓. S-引理及其进展[J]. 运筹学学报, 2023, 27(4): 20-32.

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

参考文献 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]	刘永鸿, 韩丛英, 郭田德. 基于深度学习的指纹方向场提取算法[J]. 运筹学学报, 2023, 27(4): 1-19.
[2]	邵梦真, 余长君. 最优控制问题的直接法综述[J]. 运筹学学报, 2023, 27(4): 81-105.
[3]	王祥丰, 李文浩. 机器学习驱动的多智能体路径搜寻算法综述[J]. 运筹学学报, 2023, 27(4): 106-135.
[4]	姜波. 非负正交约束优化问题的理论、算法及应用[J]. 运筹学学报, 2023, 27(4): 136-152.
[5]	王晓. 非凸约束优化的随机近似算法[J]. 运筹学学报, 2023, 27(4): 153-165.
[6]	张莹, 敬新奇, 王长军. 一个双拟阵下的最优定价存在性猜想[J]. 运筹学学报, 2023, 27(4): 166-174.
[7]	曾静, 丁若文. 一类带映射差的非凸向量优化问题解的稳定性[J]. 运筹学学报, 2023, 27(3): 121-128.
[8]	张昀蔚, 韩曙光. 收送货同时的城市无人物流配送问题研究[J]. 运筹学学报, 2023, 27(3): 53-67.
[9]	苏珂, 任晓慧. 需求不确定的修正库存定价模型[J]. 运筹学学报, 2023, 27(3): 21-36.
[10]	徐薇, 黄悦丰, 陈彩华. 考虑配置储能系统的电动公交充电站充放电调度策略[J]. 运筹学学报, 2023, 27(2): 95-109.
[11]	王茂然, 蔡邢菊, 吴中明, 韩德仁. 多模式交通均衡问题的一阶分裂算法[J]. 运筹学学报, 2023, 27(2): 63-78.
[12]	华贇, 王祥丰, 金博. 面向城市交通信号优化的多智能体强化学习综述[J]. 运筹学学报, 2023, 27(2): 49-62.
[13]	邵虎, 卓越, 刘鹏杰, 邵枫. 城市交通流量估计的运筹学方法[J]. 运筹学学报, 2023, 27(2): 27-48.
[14]	魏贺, 刘昊飞, 许丹丹, 韩雪华, 王良, 张晓东. 双层规划在城市交通领域研究与应用的系统综述[J]. 运筹学学报, 2023, 27(2): 1-26.
[15]	叶明露, 邓欢. 一种新的求解拟单调变分不等式的压缩投影算法[J]. 运筹学学报, 2023, 27(1): 127-137.

S-引理及其进展

S-lemma and its extension

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 34

相关文章 15

编辑推荐

Metrics

本文评价