An algorithmic analysis of multiquadratic and semidefinite programming problems
An algorithmic analysis of multiquadratic and semidefinite programming problems
复制标题
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
M. Ramana
中科院分区：
文献类型：
--
作者：
M. Ramana
解决了多峰编程（MQP）和半决赛编程（SDP）的问题。为SDP的某些可行性版本开发了两种算法，其中第一种被证明具有固定矩阵映射的尺寸时具有多项式时间复杂性。第二算法是应用于最小二乘惩罚函数的全球收敛牛顿样方法。从结构和复杂性理论的观点分析了用凸图像表征和识别二次图的问题。然后，对一类称为Spectrahedra的凸组的几何形状进行了研究，这些凸组是半决赛程序中的可行区域。最后，在第7章中，我们基于特征值不平等，为MQP开发了一些切割平面技术。
The problems of Multiquadratic Programming (MQP) and Semidefinite Programming (SDP) are addressed. Two algorithms are developed for certain feasibility versions of the SDP, and the first of these is shown to have polynomial time complexity when the dimension of the matrix map involved is fixed. The second algorithm is a globally convergent Newton-like method applied to a least-squares penalty function. The problem of characterizing and identifying quadratic maps with convex images is analyzed from both structural and complexity theoretic points of view. Then a study is made of the geometry of a class of convex sets called spectrahedra, which are the feasible regions in semidefinite programs. Finally, in Chapter 7, we develop some cutting plane techniques for MQP, based on eigenvalue inequalities.