基于拉格朗日对偶的一类全局优化算法

针对带有非凸二次函数约束的非凸二次规划问题(NQP),提出了一个基于拉格朗日对偶的确定型全局优化算法,这类优化算法可广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中.为求解此问题,首先,应用拉格朗日对偶对原问题进行下界估计.其次,为克服拉格朗日对偶问题的非凸性,利用线性化方法,得到拉格朗日对偶问题的线性下界估计,并且由此建立了NQP拉格朗日对偶问题的松弛线性规划(RLP).如此通过对RLP可行域的细分和一系列RLP的求解过程,从理论上证明了算法收敛到NQP的全局最优解.数值算例应用结果表明,该方法是可行的.     

带有叉熵约束的最小叉熵优化问题的求解

研究了带有叉熵约束的最小叉熵优化问题的求解问题.根据对偶理论,提出了一个简单的几何规划,该方法把一个带有叉熵约束的叉熵优化问题转化成了一个对偶规划,而对偶规划是一个只需要解决一个带有线性约束的凸规划问题,比较容易计算.     

线性分式和规划问题的全局优化算法

提出一种求解线性分式和规划问题的分支定界算法.该算法首先利用等价转换技巧构造出原问题的等价问题,然后通过凹凸性包络技术建立等价问题中目标函数与约束函数的下逼近函数,得到其线性松弛规划,从而将原来的非凸规划问题转化为一系列线性规划问题,以确定原问题最优值的下界.从理论上证明了算法的收敛性,并用数值试验验证了算法的可行性和有效性.     

不定二次规划的全局优化算法

对不定二次规划问题提出了一个新的确定型全局优化算法,通过对目标函数和约束函数的线性下界估计,建立了不定二次规划的松弛线性规划.通过对松弛线性规划可行域的细分,以及一系列松弛线性规划的求解过程,并通过实例证明了算法能收敛到原问题的全局最优解.     

非凸二次规划的分支定界方法

通过构造二次函数的线性下界函数给出非凸二次约束二次规划问题(QP)的松弛线性规划,提出分支定界算法,数值计算表明算法是有效可行的.     

带有二次约束二次规划问题的全局最优化

根据带有二次约束二次规划模型的特殊结构,利用乘积的凸包络和凹包络,给出带有二次约束二次规划问题的松弛线性规划问题,以确定全局最优值的下界,使用超矩形缩减技术以加快分支定界算法的收敛速度,从而提出一个求解带有二次约束二次规划问题的全局最优化算法,证明该算法的收敛性,这个新算法实际上是把分支定界方法与外逼近方法有机地结合起来.数值算例表明所提出的算法是可行的.     

求非凸二次约束二次规划全局解的凸规划方法

针对非凸二次约束二次规划(QCQP)问题,将问题中二次函数的凸函数部分保留,达到所得松弛规划的可行域更加紧致的目的,得到原问题更好的下界.利用正交变换的方法得到原问题的一个凸规划松弛模型,再利用分支定界算法求其全局最优解.根据问题的最优性和可行性原则,提出一种能整体删除或缩小算法迭代过程中产生的分割子区域的区域删减策略...     

线性比式和问题的全局优化算法

为求解线性分式规划问题(P),提出一个分枝定界算法.首先通过转化技巧,导出问题(P)的等价问题(Q),然后利用线性化方法,得到(Q)的线性松弛规划问题(RLP).从而,初始非凸规划问题归结为一系列线性规划问题的求解.数值试验表明算法是可行的.     

一种求解QoS路由问题的半定规划算法

QoS路由的主要问题是求源节点到目的节点满足QoS多个约束的优化问题。由于半定规划在求解组合优化问题和NP-完全问题时具有收敛速度快,迭代步数少等优点。本文基于QoS路由问题的线性整数规划网络模型,利用半定规划方法研究了时延约束的代价最小问题。把QoS路由的一般模型松弛为半定规划的标准形式,利用半定规划内点方法进行求解,然后利用随机扰动方法得到原问题的近似最优解.数值试验表明了算法的有效性。     

求非凸二次规划全局最优解的分解线性化方法

对非凸二次规划(QP)问题提出新的确定性全局优化算法,该算法先对目标函数进行分解得到可分的等价问题,再根据相应函数的线性下估计建立原非凸二次规划的线性松弛规划,同时在分枝定界方法中使用区域删减准则来加速算法的收敛性.理论分析和数值计算表明提出的算法是收敛且有效的.