文档介绍：摘要
半定规划是线性规划的一种推广,近年来其理论和算法取得了很大的进展, 并且在组合优化,系统工程和电子工程等领域得到了广泛的应用,已经成为数学规划领域中一个新的活跃的研究方向。
本文首先介绍了半定规划的基本知识,包括半定规划的理论与算法,应用和
研究现状,:
,通过求解变分不等式得到求解半定规划的一个新的投影算法,并给出了该算法的收敛性证明。数值实验表明了该方法的有效性。
,利用低秩非线性规划算法求解该半定规划松弛模型,然后利用随机扰动算法求得原问题的次优解。数值实验表明该方法可以有效地求解大规模的图的最大二等分问题。
,非光滑分析等数学工具,从理论上对于特征值优化问题
进行了研究,这些有助于求解此类问题。
关键词:半定规划组合优化变分不等式 图的最大二等分问题特征值优
化问题凸分析非光滑分析
Master Degree Dissertation
Research of Semidefinite Programming and Its Application
CuiY-an
Directed by ProfoXing Zhidong
math.,Northwest University,Xi’an 710069
Abstract
Scmidefinltc programming is an extension of linear recent ye甜s
,the theory and algorithm for semidefinite programming have developed greatly,and its most important applications are found binatorial optimization,system engineering and electrical engineering。Semidefinite programming is a new and important research field in mathematical programming.
In the paper,we firstly summarize the theory,algorithm,application and recent msearch of semidefinlte programming,then,introduce our some work in algorithm and conclude them as follows:
optimal condition iS transformed to a variational new projective algorithm is proposed in order to obtain the solution of semidefinite programming by solving variational inequality,and the convergent result was given. The experiments show that the performance of oar method is effective.
equivalent integral programming model and a new semidefinite programming relaxation for the max-bisection problem are ,we solve the relaxation with a nonlinear programming of low- with the randomized method,an approximate solution of the max—bisection problem is numerical results show that the method call effectively solve the
problem.
mealls ofnonsmooth analysis and convexity,eigenvalue optimization prob—