基于半定规划的{0,1}-经济调度

基于内点半定规划,提出一种直接求解{0,1}-经济调度问题({0,1}-ED)的新方法。通过引入辅助变量,该方法将原整数变量约束转化为凸二次约束,进而将{0,1}-ED问题转化为半定规划问题,并用内点法进行求解。对于大系统整数变量的微小偏差,应用简单的启发式技术调整。ED-420等9个测试系统的仿真结果表明,所提方法能够有效地处理{0,1}-经济调度,对于大多数问题都可以得到较精确的结果,计算时间具有多项式复杂性。

半定规划的一个扰动问题

构造半定规划的一个扰动问题。相比半定规划的标准问题,该扰动问题具有严格可行解。这对于设计和分析半定规划的不可行内点算法具有重要作用。

半定规划

半定规划是指线性函数在对称矩阵的仿射组合半正定的约束下的极小问题 ,它实际上是凸优化问题 ,在最近的十几年中得到突飞猛进的发展 ,目前已成为优化方面最热门的领域 .这一研究活动之所以被激发起来 ,是由于半定规划在一些领域的新应用的发现以及新的有效算法的产生 .

一个新的求解半正定规划问题的原始对偶内点算法(英文)

选择合适的核函数对设计求解线性规划与半正定规划的原始对偶内点算法以及复杂性分析都十分重要.Bai等针对线性规划提出三种核函数,并给出求解线性规划的大步迭代复杂界,但未给出数值算例验证算法的实际效果(Bai Y Q,Xie W,Zhang J.New parameterizedkernel functions for linear optimization.J Global Optim,2012.DOI 10.1007/s10898-012-9934-z).基于这三种核函数设计了新的求解半正定规划问题的原始对偶内点算法.进一步分析了算法关于大步方法的计算复杂性界,同时通过数值算例验证了算法的有效性和核函数所带参数对计算复杂性的影响.

半定规划的一种修正原对偶内点算法研究

提出了半定规划(SDP)的一种修正的原对偶内点算法,对初始点的选取进行了改进,提高了算法的计算效率,并证明了新算法的迭代复杂性是O(n).