文档介绍：摘要研究现状,:柚谕狗治觯枪饣治龅仁Чぞ撸永砺凵隙杂谔卣髦涤呕侍图的最大二等分问题特征值优半定规划是线性规划的一种推广,近年来其理论和算法取得了很大的进展,并且在组合优化,系统工程和电子工程等领域得到了广泛的应用,已经成为数学规划领域中一个新的活跃的研究方向。本文首先介绍了半定规划的基本知识,包括半定规划的理论与算法,应用和ò攵ü婊淖钣判蕴跫;杀浞植坏仁剑ü蠼獗浞植坏仁降玫求解半定规划的一个新的投影算法,并给出了该算法的收敛性证明。数值实验表明了该方法的有效性。隽送嫉淖畲蠖确治侍獾恼婊P偷牡燃勰P图捌湫碌陌攵ü划松弛模型,利用低秩非线性规划算法求解该半定规划松弛模型,然后利用随机扰动算法求得原问题的次优解。数值实验表明该方法可以有效地求解大规模的图的最大二等分问题。进行了研究,这些有助于求解此类问题。关键词:半定规划组合优化变分不等式化问题凸分析非光滑分析
,..,,’甀,瑃琲:甜,,—
整垫迃月如日学位论文作者签名:托艳向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被西北大学学位论文知识产权声明书本人完全了解学校有关保护知识产权的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时,本人保证,毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北大学。保密论文待解密后适用本声明。学位论文作者签名:指导教师签名:年西北大学学位论文独创性声明本人声明:所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方外,本论文不包含其他人已经发表或撰写过的研究成果,也不包含为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。.辳年聓月日
第一章和淮喂乖炝恕ǜ霭攵ü婊侍狻=幼潘樟5囊恍┭д呦嗉萄芯苛税攵绪论偶理论,主要算法及其应用;接着阐述了半定规划的研究现状和意;最后简述问题转化成为一个特征值优化问题求瓣。在对这些实际问题的解决中半定规划的化、特征值优化、滤波器的设计【康攘煊蛴凶殴惴旱挠τ茫裕殉晌J§半定规蓟捌溲芯肯肿本章主要介绍芈定规划的基本知识,首先介绍了半定规划及其对偶模型,对了本文的内容提要和章节安排。§引言世纪年代,随着运筹学的产生和发展,在数学规划的领域内产生了许多新的问题,而已经存在的诸如线性规划和非线性规划的算法都不能有效地解决这些问题。世纪年代,半定规划产生并发展起来。在年由规划笔币渤谱骶卣蟛坏仁在控制领域中的应用。在年代的早期,和谖南譡俊,和谖南譡把一些难的图分割理论与算法得到了一定的发展。尤其在年代,和俊硝】首次把餸盯岢龅南咝怨婊哪诘闼惴ㄍ乒悴⒂τ玫桨攵ü婊上,使得半定规划获得了飞速的发展:另外,半定规划在系统控制论【俊⒔峁褂规划领域日益引人注目的研究方向,对它的研究意义相当深远。半定规划分为线性半定规划和非线性半定规划两类,由于对非线性半定规划的研究才刚刚开始,其理论与算法都很不完善,再加上它的应用目前远不如线性半定规划那样广泛,所以对它的研究还很少。笔者在本文中的研究只涉及线性半定规划问题。关于非线性半定规划的有关内容可参看文献,§.攵ü婊捌涠耘祭砺半定规划是线性规划的一种推广,它是在满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极大化的问题,这个约束是非线性、非光滑、凸的,因而半定规划是一个非光滑凸优化问题。半定规划的标准数学形式‘缦拢西北大学硕士学住论文
《删,,蔛”,坝∥,,一蛭表示0胝正定卣螅直鹩胹:硎拘小烈园胝正定埽蔛一,否则令’,爿,,,琲:琺即可。荩珺艫。∑珹,。事实上,当保珹其中,⋯,埘J凳啊ぁ被彳,表示诨吹矩阵的全体。珹为氖稻卣蟆2皇б话阈裕梢约偕令琤琤。,,矩阵表示矩阵淖V谩6訶∈保琒硎緉×聆实对称矩阵的全体,珺∈啊埃琑⋯为”阶实方阵的全体为了方便起见,我们引进线性算子篠”斗北硎狙形档呐芳咐锏空间陌樗嫠阕樱俏狝’:鄙隨“根据伴随算子定义,应满足:对任意利用方法可以得到半定规划的对偶模型西北大学硕士学位论文瓵.·,⋯,·\,,
竺恃性ド爿瑈,,猌妣÷Ⅳ令Ⅳ表示爿的零空间,爿,∈姆:Ⅳ∑,,∑V压,猌,力甪.≯¨∈,⋯,.∈半定规划是线性规划的推广,它有线性规曼嗨频亩耘祭砺踇”NA诵鹗定理㈣其中蔛”,蔙”。,