《求解约束优化问题的filter型算法研究论文论文》由会员分享，可在线阅读，更多相关《求解约束优化问题的filter型算法研究论文论文（45页珍藏版）》请在金锄头文库上搜索。
1、论文题目：求解约束优化问题的 Filter 型算法研究作者姓名： 王鑫入学时间：2005 年 9 月专业名称： 应用数学研究方向： 数学模型与计算机算法研究指导教师： 贺国平职称： 教授论文提交日期：2008 年 5 月论文答辩日期：2008 年 6 月授予学位日期：STUDY OF FILTER-TYPE ALGORITHMS IN SOLVINGCONSTRAINED OPTIMIZATION PROBLEMSA Dissertation submitted in fulfillment of the requirements of the degree ofMASTER OF SCIEN
2、CEfromShandong University of Science and TechnologybyWang XinSupervisor: Professor He GuopingCollege of Information Science and EngineeringMay 2008声明本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所 公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交 于其它任何学术机关作鉴定。硕士生签名：日期：AFFIRMATIONI declare that this dissertation, submitted in ful
3、fillment of the requirements for the award of Master of Science in Shandong University of Science and Technology, is wholly my own work unless referenced of acknowledge. The document has not been submitted for qualification at any other academic institute.Signature:Date:山东科技大学硕士学位论文摘要摘要本文主要研究求解约束优化问
4、题的 Filter 型算法。论文共分五部分。在第一章中我们首先介绍了优化问题的模型、基本求解思路以及算法的收敛性和收敛速度等一系列概念。而后，文章着重对求解约束优化问题的罚函数法进行分析，指出其中存在的缺陷与不足，从而引出 Filter 型算法的研究背景、发展现状以及本文的主要工作。论文的第二部分主要以模式识别中的 SVM 分类问题为实际应用背景，以求解正定二次规划的内点算法为研究对象，通过引入 Filter 方法，给出了一个求解正定二次规划的 Filter 内点算法，与现有的大多数 SVM 算法相比，在一定条件下，该算法在理论上可获得全局收敛的良好性质。对算法的可行性和收敛性，文章给出了详细
5、的分析证明过程。论文的第三部分将 Filter 方法引入到半定规划问题，通过将半定规划问题序列非线性化，并结合求解非线性规划的 Filter-SQP 算法，给出求解半定规划的 Filter 型 算 法 ，在一定的假设条件下，证明了算法的全局收敛性。第四章以对策论中矩阵对策为实际应用背景，分析了内点算法在其中的应用。论文的最后一章对全文进行总结，指出文章的创新之处，并针对本文未解决的问题提出了进一步研究的方向。关键词：Filter 方法，正定二次规划，SVM，半定规划，内点算法山东科技大学硕士学位论文摘要AbstractIn this paper, we study the Filter-typ
6、e algorithms for constrained optimization problemsand the paper is divided into five parts.First, we introduce the model, the basic method of constrained optimization problems andsome concepts about the convergence of algorithms. Then we give an analysis on the penaltymethod and emphasize its shorta
7、ges. After that, we give a detailed introduction of thebackgrounds, current researches on the Filter-type algorithms and the main work of the paper.The second part of the paper chooses the SVM classification in pattern recognition as ourpractical background. Based on a definite qudratic programming
8、model and by combining theFilter method with the primal-dual interior-point algorithm, we construct the Filterinterior-point algorithm for definite qudratic programming. Compared with other SVM agorithms,under some assumptions, the Filter interior-point algorithm can convergent globally. As for thef
9、easibility and convergence of the algorithm, we also give detailed analyses.In the third part, we introduce the Filter method into a wide optimization model-thesemidefinite programming(SDP). By solving SDP problems throught a NLP, we construct anew Filter and give a Filter-SQP algorithm for SDP. Und
10、er some assumptions, we give adetailed proof on the global convergence of the algorithm.The fourth chapter of the paper chooses games theory as practical background. Byanalyzing the primal-dual path following short-step algorithm, we give a simple applicationof interior point method on the matrix ga
11、mes.The last chapter concludes the whole paper and points out the creativities. We also givesome prospects about further researches on Filter-type algorithms.Keywords: Filter, Definite Quadratic Programming, SVM, Semidefinite programming,Interior-Point algorithm山东科技大学硕士学位论文目录目录1 绪绪1.1 1.2 1.3论论 1引言 1 FILTER 算法的研究背 景 2 本文主要工作概 述 42 求解一类正定二次规划问题的求解一类正定二次规划问题的 FILTER 内点算法内点算法52.1 2.2 2.3 2.4研究背景SVM 分类问题5 FILTER 方法的引 入7 FILTER 内点算 法10 收敛性证明和算法分 析 153 求解半定规划的求解半定规划的 FILTER 型算型算法法203.1 3.2 3.3引言 20 FILTER-SQP 算 法21 收敛性证明和算法分 析 244 内点算法在对策论中的应用内点算法在对策论中的应用 284.1 4.2引言 28 算法应 用
