一种新的线性规划不可行内点算法

提出了一个新的求解线性规划问题的不可行内点算法,这个算法每一步只须解一个线性方程组,算法是基于路径跟踪算法思想,适当选取初始点,算法至多可在Ｏ（ｎｌ）迭代步获得ε－可行性和ε－互补性,算法具有每一步的计算量少的特点。     

凸规划的一个内点算法

对于含线性约束的凸规划问题，本文给出了一个内点算法，并且证明了算法经过Ｏ（ｎ￣（０．５）｜ｌｎε｜）步迭代后，原始一对偶间隙必小于ε，整个算法的复杂度为Ｏ（ｎ￣（３．５）｜ｌｎε｜）．特别的，如果目标函数为凸二次函数或者线性函数，则得到相应的多项式算法，其算法复杂度为Ｏ（ｎ￣（３．５）Ｌ），其中Ｌ为相应问题的输入长度．ε取做２￣（－Ｌ）．     

可分凸二次规划的不可行内点算法

给出了可分凸二次规划的不可行内点算法,并证明了该算法在Ｏ（ｎ＾２Ｌ次迭代之后,或收敛到问题的一个近似最优解,或说明该问题在某个较大区域内无最优解。     

线性规划的投影尺度内点算法

对标准线性规划问题给出了一个新的多项式时间的投影内点算法．该算法无需事先知道目标函数的一个初始下界,因此它优于同为投影类的ＴｏｄｄＢｕｒｅｌ算法和Ｇａｙ算法,是目前为止投影类内点算法方面的最好结果．     

基于L1范数和现代内点理论的电力系统潮流计算

利用L1范数把电力系统潮流方程的求解转化为对一个新的非线性规划模型L1LF的求解.在基于原问题的扰动Karush-Kuhn-Tucker(KKT)条件基础上,导出了求解L1LF模型的内点算法公式.仿真结果显示,L1LF模型结构简洁、直观,编程应用方便.新算法计算结果正确,收敛性好.和常规潮流算法相比,新模型和新算法有效解决了病态系统潮流计算发散的问题,为给定条件下的潮流问题是否有解提供了一个新的判断途径.     

求解线性互补问题的一种势下降内点算法

针对带半正定矩阵的线性互补问题提出了一个新的内点方法-势函数下降内点方法,并采用部分校正技术和Sherman-Morrison-Woodbury准则,从而得到问题的近似最优解.最后讨论了该算法的收敛性,证明了该算法为多项式算法,通过算例对算法进行了数值实验,数值结果表明本文提出的算法具有一定优越性     

内点算法的若干基本框架及其发展

近十几年来内点算法已经成为数学规划中非常活跃的研究方向,其收敛性和计算速度均优于单纯形算法.本文对此方向目前形成的三类主要算法:势函数投影算法,仿射尺度算法,路径跟踪算法的基本框架以及成为多项式算法的机理给予分析和阐述,并指出它们在数学规划和解决实际问题方面的扩展.     

凸二次规划的原-对偶内点算法数值实验初步

在线性规划原始对偶内点算法的基础上,进一步给出原始对偶内点算法在解凸二次规划问题中的应用, 并初步给出了该算法的数值例子, 作为对内点算法的一个重要补充.     

线性规划的一个宽邻域预估-矫正内点算法

在线性规划的内点算法中,宽邻域算法比窄邻域算法的数值效果好,但宽邻域算法的复杂性比窄邻域差.提出了求解线性规划问题的一个宽邻域预估-矫正内点算法,证明了该算法的迭代复杂性是O(n L),这是线性规划的内点算法中最好的复杂性结果.     

正定二次规划内点稳定算法

进一步讨论一种新二次规划的内点算法.该算法不同于传统的内点算法:它不含有原始或者对偶变量的逆,因而在靠近解集附近也有定义(well defined).证明了若目标函数的二次部分为标准正定二次型,则在计算迭代方向时,可以把对(m 2n)×(m 2n)阶KKT系统的求解转化为(n-m)×(n-m)阶KKT系统的求解,从而在很大程度上提高算法的效率.     

线性分式规划的多项式算法

Charnes—Cooper提出了一种线性分式规划的算法。本文在此基础上证明了线性分式规划与一种特定的线性规划等价。将Karmarkar算法用于该线性规划,我们得到了线性分式规划的多项式算法。     

一种基于内点算法的三重目标过滤器优化算法的研究与仿真

 大规模非线性最优化一直是规划中的研究热点.内点算法是一种有效的求解大规模不等式约束问题的算法,然而大多数过滤内点算法仅考虑了可行性和稳定性,忽略了辅助性对算法性能的影响,为此本文在综合过滤器法和内点算法特点的基础之上,提出了一种新的适用于大规模非线性优化的基于内点算法的三重目标过滤器法.新算法依据内点算法的卡罗需-库恩-塔克(KKT)条件,以可行性、辅助性和稳定性作为搜索步长的目标,将等式约束违反量,障碍目标函数和辅助条件作为过滤器选项计算搜索步长.通过搭建计算机仿真环境进行数值测试,从迭代次数、函数估计次数和运行时间3方面与基本过滤器法相比.测试结果表明,相同条件下三重目标过滤器法可以获得更大的搜索步长,实现快速收敛的目的.该算法具有良好的全局收敛性、鲁棒性和有效性.     

关于一个求解凸二次规划改进内点算法的全局收敛性

对一类利用对数障碍函数法求解凸二次规划问题的内点算法给出了全局收敛定理的证明,同时指出该算法并没有考虑到避免Maratos效应,因此很难有超线性收敛的结论,但是由于该算法简单,计算量少,故对小规模问题依然是有效的。     

凸二次规划的不可行内点算法

给出了一个求解凸二次规划的不可行点内点算法，算法的初始迭代点为非负不可行内 ，证明了算法的全局收敛性。该算 法可以看作是Ｋｏｊｉｍａ算人关于线性规划算法的推广，也可以看作是Ｍｏｎｔｅｉｒｏ等人关于可行内点算法的推广。     

基于遗传算法的室内装饰材料色彩合理搭配方法

为了解决传统方法计算过程极为复杂对专业知识的采集信息不完整,无法覆盖整个色彩搭配领域,无唯一最优解的弊端,通过遗传算法研究了室内装饰材料色彩合理搭配方法。通过三维部件与色彩构成遗传算法中染色体进行遗传编码。将RGB转变成HSL,计算色彩不和谐系数,充分分析了室内装饰材料色彩搭配时的调和度,求出视觉舒适度。通过色彩搭配和谐度、色彩搭配调和度和视觉舒适度三部分加权组成室内装饰材料色彩搭配适应度函数。利用遗传算法的选择、交叉和变异操作获取适应度最高的个体,设置停止迭代条件,得到室内装饰材料色彩合理搭配结果。结果表明:所提方法色彩搭配结果有更好的色彩舒适性;通过色彩搭配结果评价调查发现,大部分顾客对采用所提方法得到的室内装饰材料色彩搭配方案的评价结果为非常满意或满意,方法操作简单。可见所提方法搭配色彩合理,性能优越。     

求解线性规划的几种方法

线性规划是运筹学中应用最广泛的一个分支,详细地分析了线性规划的非多项式算法和多项式算法;给出了求解线性规划问题常用的数学软件,并对这些软件做了介绍。最后给出了线性规划问题的原-对偶内点算法,数值实验表明该算法具有很好的收敛性与稳定性。     

一类二次半定规划问题及其内点算法

讨论一类二次半定规划对偶性理论及与半定最小二乘问题的联系,并在对偶理论基础上讨论该规划的原始对偶内点算法,同时给出了基于NT方向的唯一性证明.     

框式线性规划的不可行内点算法

对框式线性规划提出了一个原始-对偶不可行内点算法,并证明了该算法的迭代复杂性为多项式时间性.     

线性规划的原-对偶内点算法数值实验初步

利用原-对偶内点算法的思想,初步给出了该算法的数值例子,对已有结果做了一个重要的补充。     

绝对值方程的一种严格可行内点算法

给出绝对值方程的一种新算法. 先把绝对值方程转化为线性互补问题, 再结合牛顿方向和中心路径方向, 通过求解一个线性方程组得到搜索方向.  获得了求解绝对值方程的一种严格可行内点算法, 并证明了该算法经过有限次迭代后收敛到原问题的一个最优解, 数值实验表明方法是有效的.