半定规划的解析中心割平面法

给出了半定规划的解析中心割平面算法,它可以用于求解较大规模的半定规划问题。这个算法在每一步迭代中解决对偶半定规划线性松弛问题,并以割平面的解析中心作为下一个迭代点。我们证明了算法的收敛性,并在最后给出了实际算例。     

基于Q0-1规划模型用分枝定界法求解最大团问题

搜索图的最大团是经典的NP-难题。通过运用二次0-1规划模型（简称Q0-1规划模型）寻得最大团问题的解法,所用的分枝定界法建立在此模型之上。通过一个命题推导出图的最大团求解问题与一类特殊Q0-1规划的等价性,借助于求解一般Q0-1规划的分枝定界法推演出求最大团问题的分枝定界规则,从而将图论中的经典问题转化成代数问题加以解决,并给出实例说明该算法的有效性。     

整凸二次规划

本文给出了一种求解整凸二次规划的分枝定界法，该算法把松弛问题转化为线性互补问题，由于求解线性互补问题时，充分地利用了前一分枝点所对应的线性互补问题解的信息，从而地减少了计算量。     

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

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

非线性半定规划问题的一种内点法及其在阵列信号处理中的应用

利用精确罚函数和信赖域全局优化技术给出非线性半定规划的一种内点法.该方法能用于求解较大规模的优化问题,是因为它处理的子问题比较简单.该算法的每步迭代需要解的子问题是一个二次半定规划问题,可以用已有的半定规划软件有效地求解.在某些假定条件下,证明了该算法是全局收敛的.建立起阵列信号处理中的近场多源定位问题的数学模型,并利用本文给出的内点法进行求解.利用该算法不需要对约束条件进行松弛,可以避免产生较大误差,从而能够得到更加精确的结果.     

求不定二次规划问题全局解的新的分支定界算法

提出了求解不定二次规划问题一个新的分支定界算法.利用D.C.分解和正定阵的Cholesky分解把问题转化为可分离形式,并导出Lagrangian对偶界,给出基于Lagrangian对偶界和矩形对分的分支定界算法,同时给出初步数值实验结果.     

一类不定二次规划问题的分枝定界法

研究一类特殊的不定二次规划问题的全局最优解.首先利用广义Cholesky分解对该类不定二次规划问题进行预处理,然后进行凹凸分离并用常见的分枝定界法进行求解.利用典型算例进行数值试验,并在试验过程中对分枝定界法采用新的剖分原则进行线性逼近,结果表明该算法是有效的并且运行时间和迭代次数都较少.     

凸二次规划SDP松弛解的存在性证明

针对利用CVX软件求解半定规划问题的有效性依赖于该半定规划问题的原始-对偶性,提出利用半定规划问题的强对偶定理和Gershgorin圆盘定理证明在箱子约束及单位球形约束下的凸二次规划问题的半定规划松弛模型解的存在性。该证明方法为嵌入了SeDuMi和SDPT3这两种内点算法的CVX软件提供了有效求解半定规划松弛模型的理论依据;一旦利用该方法证明了半定规划问题解的存在,必然可利用CVX软件有效求解。     

一类可分离的非线性0-1背包问题的分枝定界算法

构造出了一类可分离非线性0-1背包问题的分枝定界算法．分枝的过程是酱通的0-1变量分枝，用简单的取整启发式法确定更好的可行解；而在每个分枝结点处用线性松弛技术确定了它的子问题的一个线性规划松弛逼近。由此得到最优值的一个下界．数值结果表明所提出的算法是有效的．可以求解中等规模的问题．     

半定规划松弛求解新方法及在通信问题中的应用简

半定规划因其约束条件的合理性,比线性规划具有更强的实用性,也是诸多领域中广泛采用的优化算法.该文在传统半定规划数学模型的基础上,提出了一种新的松弛求解方法.并且为了解决多址通信干扰问题,该文构建了一种基于松弛求解的半定规划模型.实验结果证实提出的半定松弛模型降低了通信过程的误码率,可以有效地解决多址通信干扰问题.     

二次背包问题的秩二松驰

把对最大割问题进行秩二松驰的思想应用到二次背包问题上,得到二次背包问题的秩二松驰模型.应用罚函数法求得该模型的最优解,再利用扰动算法将该最优解转化成二次背包问题的解.     

求解约束最小二乘半正定规划问题的L-BFGS方法

对带等式和不等式约束的最小二乘半正定规划问题的求解进行了研究。在Slater约束规范条件下,对偶问题的最优解与原问题最优解相等。因此,考虑将最小二乘半正定规划问题转化为相应的对偶问题,通过求解对偶问题达到求解原问题的目的。针对最小二乘半正定规划问题的对偶问题,首先构造相应的二次模型,沿负梯度方向最小化该二次模型得到柯西点,在此基础上,利用积极约束技巧,划分积极约束集与非积极约束集,然后应用L-BFGS技巧对自由变量进行加速,从而求得对偶问题的最优解。最后,从理论上证明了算法的全局收敛性,并进行了初步的数值实验,将该算法与光滑化牛顿法作对比,结果表明该算法在计算时间上有一定的优势。     

解半定规划的带筛子的正则化方法

研究了求解半定规划问题的一个带有筛子的正则化方法,该方法是基于经典的二次正则化方法,将半定规划问题转化为目标函数为凸的、可微的无约束优化问题。利用筛选信赖域方法来解这个无约束优化问题,并给出算法及其收敛性分析。     

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

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

半定规划问题基于方向分解的筛选算法

目的寻求半定规划问题新的理论算法。方法采用低秩分解技术将一般的半定规划问题转化为与其等价的非线性规划问题,利用基于方向分解的筛选算法,通过对搜索方向进行切线步和垂直步的分解来分别寻求最优解方向和不可行性改善的方向,构造了半定规划问题的筛选算法。结果通过证明得到算法具有可行性。结论最后给出了算法的收敛性分析。     

求解半定互补问题的一种非内点连续算法

基于光滑FB函数理论和中心路径原则,提出求解半定互补问题的一种非内点连续算法,在适当的条件下证得其全局线性收敛性和局部二次收敛性,并通过数值试验验证了算法可行性和有效性。     

基于弹性接触的共轭梯度算法

为了解决有约束的基于共轭梯度二次规划算法的多次迭代问题,结合共轭梯度算法和有效集策略,提出了一个新的算法模型,通过对变量的截取(使用Polak-Bibiere公式)来避免重新开始共轭梯度算法,在大规模的弹性接触问题中,大量的结果表明了这个算法的有效性。     

带有基数限制的离散多因素投资组合模型

研究带有基数限制的离散多因素投资组合模型.与传统的投资组合模型不同的是,该模型中投资组合的决策变量是交易手数(整数),且限制资产投资的最大数目,其最优化模型是一个非线性整数规划问题.分别用随机产生的一组数据和来自纳斯达克的40只股票数据,利用拉格朗日松弛的混合分枝定界算法求解此模型,并用FORTRAN语言编程,数值结果表明该算法能有效求解此模型.     

Convex quadratic programming relaxations for parallel machine scheduling with controllable processing times subject to release times

Scheduling unrelated parallel machines with controllable processing times subject to release times is investigated. Based on the convex quadratic programming relaxation and the randomized rounding strategy, a 2-approximation algorithm is obtained for a special case with the all-or-none property and then a 3-approximation algorithm is presented for general problem.     

一类二次半定规划内点算法的K..S..H搜索方向的存在唯一性

在对偶理论的基础上,将半定规划(SDP)的原始对偶内点算法推广到一类二次半定规划(QSDP),利用优化理论中经典的牛顿法通过求解非线性方程组得到K..S..H方向,并证明了K..S..H搜索方向的存在唯一性.