全局求解线性多乘积规划的分支定界算法

本文针对一类线性多乘积规划问题提出一种分支定界算法.首先将原问题转化为其等价形式,然后利用提出的线性松弛技术将等价问题松弛为线性规划问题,通过求解一系列线性规划问题得到原问题的全局最优解.最后给出算法的收敛性和计算复杂性.数值实验表明算法是有效的.     

一种整数线性乘积规划问题的分支定界算法

本文为了求解整数线性乘积规划(ILMP)问题的全局最优解,提出一种新的线性松弛分支定界算法.该算法利用对数函数的单调性及凹凸性,得到(ILMP)全局最小值的下界,并利用区域缩减技术以最大限度地删除不可行区域,加快该算法的收敛速度.最后数值实验表明,本文提出的算法是有效并且可行的.     

一类线性乘积规划问题的分支定界缩减方法

提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的.     

一类多乘积规划的加速算法

针对一类多乘积规划问题(MP),给出一个加速算法.首先导出一个与(MP)等价的逆凸问题(RCP),然后构造问题(RCP)的线性松弛化问题.算法的主要特点是提出了两个加速技巧,这些技巧可以用于改善算法的收敛速度.数值算例表明算法是可行的.     

一个新的求解广义几何规划问题的全局优化方法（英文）

为求解广义几何规划问题,提出一个新的线性化松弛技巧.在此基础上,给出一个新的分支定界算法.为进一步改进算法,构造一个新的删除技巧,该技巧可被用来提高算法收敛效率.理论上证明了算法的收敛性,数值试验显示本文方法是有效可行的.     

求解线性比式和问题的缩减分支定界算法[英文]

本文针对线性比式和问题给出一个缩减分支定界算法.在算法中,基于比式分母的输出空间,我们提出一个新的范围缩减方法.结合分支定界框架和输出空间范围缩减方法,建立一个缩减分支定界算法.并给出算法的收敛性,数值实验结果展示了本文算法的优点.     

一类DC规划问题的分支定界算法

本文针对一类带有箱子和线性不等式约束的特殊DC规划问题,提出了一种分支定界算法.首先将原问题转化为其等价问题,然后利用目标函数的特点将等价问题松弛为凸规划问题,通过求解一系列凸规划问题得到原问题的最优解,最后给出算法的收敛性证明.数值实验表明该算法是可行有效的.     

求解带指数凹多乘积规划问题的对偶界方法

对一类带指数的凹多乘积规划问题,给出一种求其全局最优解的分支定界算法.先利用对数函数性质将原问题进行等价转化,对于等价问题,利用Lagrange弱对偶定理将分支定界算法中关键的定下界操作转化为易于求解的线性规划问题,且这些线性规划的规模不随迭代而变化,利于编程计算.同时,分支操作采用单纯形作为分割元素,并使用对分法,既保证穷举性,又使得线性规划的规模更小.最后给出算法的收敛性证明和数值实验结果.     

求线性比试和问题的确定性全局优化算法

为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的.     

一种新的二次约束二次规划问题的分支定界算法

本文为了获得二次约束二次规划(QCQP)问题的全局最优解,提出一种新的参数化线性松弛分支定界算法.该算法利用参数化线性松弛技术,得到(QCQP)的全局最小值的下界,并利用区域缩减技术以最大限度地删除不可行区域,加快该算法的收敛速度.数值实验表明,本文提出的算法是有效并且可行的.     

求广义线性比试和问题全局解的新方法

为确定广义线性比式和规划问题(GFP)的全局最优解,提出一个新的分支定界方法.在算法中,分支过程采用单纯形对分规则,且界的估计通过一些线性规划问题的求解完成.给出算法的收敛性证明.数值试验结果显示算法是有效可行的.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

线性分式多乘积规划问题的多项式时间近似算法

本文首先将一般形式的线性分式多乘积规划问题(MP),转化为特殊形式的子问题.再根据子问题提出一种求解(MP)的完全多项式时间近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值算例也说明了算法是可行的.     

求线性比式和问题全局解的一个新方法

针对一般线性比式和问题的求解,给出一个新的分支定界算法.首先利用等价转换技巧和一个新的线性化技巧,建立等价问题的松弛线性化问题,将原始的非凸规划问题归结为一系列线性规划问题的求解;然后借助于这一系列松弛线性化问题的解确定出原问题的最优解.算法的收敛性理论上得以证明,数值算例表明算法是可行的.     

线性分式多乘积规划问题的完全多项式时间近似算法

本文针对线性分式多乘积规划问题,通过Charnes-Cooper转化将原问题转化为一个等价问题,借助此等价问题提出一个获得原问题全局近似最优解的算法,最终证明了算法的收敛性,且提供了算法运算时间的理论分析.     

广义线性多乘积问题的完全多项式时间近似算法

本文针对广义线性多乘积极小化问题,通过一系列的线性规划问题的解提出一种求其全局最优解的完全多项式时间近似算法,并给出该算法的计算复杂性,且数值算例验证该算法是可行的.     

一类广义线性多乘积问题的完全多项式时间近似算法

本文针对一类广义线性多乘积问题提出一种求其全局最优解的完全多项式时间近似算法,并给出算法的理论分析和计算复杂性,数值结果表明本文算法有效可行.     

求二次比式和问题全局解的一个新的确定性算法

本文研究一类二次比式和规划问题.首先,利用等价转换的方法把原问题转化为一个非线性规划问题,并且这个非线性规划问题的目标函数通项的分子和分母都分别是两项线性函数乘积和再加上一个线性函数的形式,再根据两项线性函数乘积和的特性,对目标函数进行线性松弛,以确定原问题最优值的下界,从而提出一个求解线性规划问题的分支定界算法,并证明该算法的收敛性.最后,数值结果表明所提出的算法是可行有效的.     

线性分式多乘积问题的?-近似算法

本文针对线性分式多乘积问题提出一个近似算法;该算法主要通过非均匀搜索网格结点,将等价问题转化为多项式个与结点参量相关的线性子问题,通过求解这些子问题获得原问题的全局近似最优解.本文不仅从理论上证明了算法的收敛性,且通过算例验证算法的可行性与有效性,最终给出算法的计算复杂度.     

求线性比式和问题全局解的输出空间分枝定界算法

基于对p-1维输出空间进行剖分的思想,提出了一种求解线性比式和问题的分枝定界算法.通过一种两阶段转换方法得到原问题的一个等价问题,该问题的非凸性主要体现在新增加的p-1个非线性等式约束上.利用双线性函数的凹凸包络对这些非线性约束进行凸化,这就为等价问题构造了凸松弛子问题.将凸松弛子问题中的冗余约束去掉并进行等价转换,从而获得了一个比凸松弛子问题规模更小、约束更少的线性规划问题.证明了算法的理论收敛性和计算复杂性.数值实验表明该算法是有效可行的.