文档介绍：西安电子科技大学
博士学位论文
半定规划及其应用
姓名:刘红卫
申请学位级别:博士
专业:应用数学
指导教师:刘三阳
20020901
中文摘要
半定规划,特别线性半定规划,线性规划的一种推广,是在满足约束“对称矩阵
的仿射组合半正定”的条件下使线性函数极大极小化的问题,这个约束是非线
性、非光滑、凸的,因而线性半定规划是一个非光滑凸优化问题近十几年内,半定
规划已成为数学规划领域中一个非常活跃的研究方向半定规划之所以引起人们
如此大的兴趣主要源于两方面的原因。第一,半定规划有广泛的应用领域例如在
统计学、结构设计、电子工程滤波器的设计和移动通信等、组合优化等领域的
应用。第二,线性规划的内点算法被成功地推广到半定规划上,使半定规划的内点
算法日趋成熟,并且己证明内点算法是求解中小规模问题的可靠有效算法,这对半
定规划的研究具有重要的理论意义和应用价值正如所述。“对半定规划的
研究不仅在现在,而且在将来的一段时间里都是一个引人关注的方向,我们可以在
这一领域内得到精妙的结果、有效的算法以及广泛的应用”本文首先概述了线性
半定规划的理论、主要算法和半定规划的研究现状,其次是本人攻读博士期间,在
导师刘三阳教授的指导下关于半定规划的理论和应用所做的一些工作,具体内容如
下
提出了卜二次约束二次整数规划的强化半定规划松弛模型‘和已有的半
定规划模型相比该模型能为原问题提供更强的界,并将该模型应用到最大割问题、
二次背包问题中,数值实验表明该方法是非常有效的,特别对具有非负权的随机完
全图的最大割问题,强化半定规划松弛模型往往会提供原问题的最优解,同时还研
究了强化半定规划松弛模型可行域的性质,特别在最大割问题中通过举例和证明得
出了比较好的结果
提出了线性约束二次整数规划的半定规划定界技术,导出了非线性半定
规划模型,同时设计了该非线性半定规划模型的谱向量丛算法,并应用到二次背包
问题中,数值实验表明该定界技术是非常有效的,利用该技术在一定规模下能有效
地求解二次背包问题,限制迭代次数后会给出二次背包问题很好的次优解最后,利
用半定规划定界技术的思想,提出了最大割问题基于半定规划的二次规划松弛模型
数值实验表明以该二次规划松弛模型为基础,利用分枝定界技术在一定规模下能有
效地求解最大割问题
发展了和对图的最大割问题及最大
二等分问题提出的秩半定规划方法对二次整数规划问题提出了秩半定
规划松弛模型,研究了该模型的性质,利用该性质设计了仁二次整数规划问题的
启发式算法,并将它分别应用到极大似然多用户检测问题和离散系数的数字
滤波器的设计中,数值实验表明该方法是解决仁二次整数规划行之有效的方法
之一在极大似然多用户检测问题中,和已有的半定规划方法相比它们的误码
率性能没有明显的差异,都接近单用户的误码率,对远近问题误码率性能也没有明
显的差异,但计算时间远远低于己有的半定规划松弛方法的计算时间在离散系数
的数字滤波器的设计中,和己有的半定规划方法相比它的误差性能基本一致,而计
算时间也远远低于己有的半定规划松弛方法的计算时间
研究了非线性半定规划的凸性,主要是通过反例否定了关于矩阵
值函数最大特征值凸性的猜想及关于长方形矩阵值函数奇异值凸性的猜
想
研究了图的最大二等分问题的半定规划方法,首先提出了图的最大二等分问
题新的吞二次整数规划模型及图的最大二等分问题新的半定规划松弛模型,利
用该模型设计了图的最大二等分问题的坐标上升算法,并用数值实验说明了该算法
的有效性其次,对非负赋权图的最大二等分问题利用具有严格可行解的半定规划
松弛模型提出了新的。算法,在一定意义上改进的工作一最后,定义了
一类较一般的图,提出了该类图的最大二等分问题的。算法,并用例子说明了具
有非负权的图真包含于该类图中
半非光滑优化凸规组合优化多用户检测滤波器设计
运
,
此抽奴
伽
脚
小
第一章绪论
第一章绪论
本章主要介绍了线性半定规划及其对偶模型、对偶理论和主要算法最后是半
定规划的研究现状和本文的内容安排
互引言
线性半定规划是线性规划的一种推广,它是在满足约束“对称矩阵的仿射组
合半正定”的条件下使线性函数极大极小化的问题,这个约束是非线性、非光
滑、凸的,因而线性半定规划是一个非光滑凸优化问题近年来,由于线性半定规
划的理论和算法取得了很大进展,以及它在控制论、系统论、结构优化、组合优
化滤波器的设计和移动通信等领域的广泛应