【摘 要】
：
半定规划(SDP)是由线性规划(LP)推广而来的，同时，它也是数学规划邻域中一类重要的规划问题.由于，SDP在通信、工程设计、组合优化等邻域有十分广泛的应用，因此，对它的研究是十分必
论文部分内容阅读
半定规划(SDP)是由线性规划(LP)推广而来的，同时，它也是数学规划邻域中一类重要的规划问题.由于，SDP在通信、工程设计、组合优化等邻域有十分广泛的应用，因此，对它的研究是十分必要.本文研究的主要内容是在SDP中，基于弧搜索的内点算法和中心参数不固定的有效内点算法，分析了它们所具有的多项式复杂度，且作了数值实验进行比较. 本文基于原对偶内点算法在SDP的应用主要完成了以下的工作： 首先，概括了SDP的研究背景及进展，然后简要介绍了SDP的基础概念与求解SDP问题所应用的主要算法，接着举了几个可以转化为SDP问题求解的例子，最后说明本论文的主要工作和内容安排. 其次，基于弧搜索内点算法在LP理论上存在较好的复杂性，并且表明沿椭圆的弧搜索内点算法比一维线性搜索好，因此，本文将文献中所提出的LP的弧搜索内点算法推广到了SDP中，且应用MTY型预估矫正算法，采用连续两步迭代分别实现改进中心性和改进最优性，并利用其中的矫正步来沿着椭圆逼近中心路径，从而寻求到最优解.在初始点是可行的情况下，本文证明了该算法所具有迭代复杂性与目前SDP中具有的最好复杂性是一致的. 最后，由于在SDP的内点算法中，中心参数的选择对于理论上证明算法复杂度与实际中有效性是至关重要的，所以，把文献中提出的 LP有效内点算法进一步推广到了SDP上.基于宽邻域，提出了SDP上的一种有效的可行内点算法，使中心参数与步长之间有多项式的关系，从而，中心参数会随着步长而改变，同时，也是所要找的最优参数.基于NT方向，证明了这种算法无论是在理论上还是在实际中都是非常有效的，并作了数值实验进行比较.
其他文献
软件质量评估是保障软件可信性的关键技术之一，软件质量评估技术主要包括质量模型和评价方法。国际标准化组织1991年颁布了ISO9126-1991标准《软件产品评价-质量特性及其使用
摄像机的标定是计算机立体视觉中最重要的步骤之一，目前已经成为计算机立体视觉研究领域中的热门。因此要利用拍摄到的二维图像精确地构造三维物体，或是应用在精密测量以及空间
不确定推理是人工智能的重要研究领域,其中基于统计关系模型的不确定推理方法是不确定推理中的一个重要研究分支。马尔科夫逻辑网作为一种新的统计关系模型,它具有能进行逻辑
为使B2B应用或者其他涉及多个独立参与方的Web应用能完成一个共同的业务目标,参与方服务之间的正确交互是至关重要的,各方必须在开发自己的服务系统之前在交互协议上达成一致
新媒体环境下,人们的生活、学习、工作虽然更加便利、快捷,但是也出现道德意识的匮乏与社会责任的缺失现象。新媒体环境下道德危机的出现,不仅影响新媒体时代的发展秩序,也对
指派问题是一个比较经典的最优化问题，一直以来都吸引着很多人对其进行研究。本论文考虑max-min型限制性指派问题，简称为max-minCAP。该问题是这样描述的：有n项工作U=｛u1,u2，…，un｝，
课堂教学是对学生进行“素质教育”的主渠道,精心设计课堂提问也是优化课堂教学的一个重要方面。尽管设问灵活多样,但目的都是让学生掌握知识、提高创造能力。盲目的、漫无目
本文的研究内容主要围绕着匹配与特征的主线来展开,包括指纹匹配、点集匹配、特征提取等。研究工作分为两个方面,一是对指纹自动识别算法中的核心问题的研究,主要包括指纹切
本文分为四章.第一章是综述.简要介绍了本文的背景知识,并且总结了本文的一些主要结果.第二章是本文的理论基础.我们研究了一般 Q过程的经典对偶,给出在对偶变换下对应特征值
随着多媒体技术和计算机网络的迅速发展,越来越多的数字信息产品通过网络广泛传播。在这一背景下,数字水印作为图像的内容认证中的应用主要手段,正得到广泛研究与应用,本论文