半定规划问题

简介：
半定规划问题是数学优化的一个分支，涉及在对称矩阵的集合上定义的线性函数的最优化。它广泛应用于工程、经济和管理等领域，是解决复杂系统决策问题的重要工具。 L. Vandenberghe 和 S. Boyd 在 1996 年三月的《SIAM 审阅》杂志第38卷第一期（49-95页）上发表了关于半定规划的文章。这篇文章的一个早期版本，名为“Positive Definite Programming”，于1994年在《数学编程现状》，J. Birge 和 K. Murty 编辑的书中出版了。 半定优化问题中我们最小化一个线性函数，并且受限条件为对称矩阵的仿射组合是正半定。这种约束是非线性和非光滑，但它是凸性的，因此正定规划属于凸优化问题范畴。半定优化将几个标准的问题（如：线性与二次编程）统一起来，在工程领域中找到了广泛的应用。 尽管半定程序比线性程序更加通用，但是它们同样容易解决。大多数用于线性程序的内部点法已经被推广到半确定程序上。类似于在直线规划中的情况，这些方法具有多项式最坏情况下复杂度，并且实践表现很好。 本段落综述了关于半确定优化问题的理论及其应用，并介绍了求解这些问题的原始-对偶内点算法。