求解分裂可行问题的次梯度投影松弛算法

在无限维Hilbert空间中，区别于现有许多算法中的正交投影，采用次梯度投影法，提出求解分裂可行问题的次梯度投影松弛算法，并利用次梯度算子的cutter性质以及分类讨论的思想，证明了次梯度投影松弛算法生成的序列弱收敛于分裂可行问题的解.     

解半定规划的投影收缩法

首先将一般的半定规划扰动成二次半定规划,而后者在其对偶空间等价于一投影方程,然后提出了求解半定规划问题的投影收缩方法并且给出了全局收敛性结果.     

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

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

基于半定规划的多约束图划分问题

提出一种递归的二分算法,用于求解带顶点权重约束的图划分问题.首先利用内点法求解不加顶点权重约束的半定规划松弛模型,然后利用超平面舍入算法得到满足顶点权重约束的初始可行解,再进一步设计启发式算法对初始可行划分进行局部改进,以得到更优的划分结果.实验结果表明,所设计的算法可在较短时间内得到多约束图划分问题的高质量解.     

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

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

求解非奇异■-张量方程的加速超松弛算法

■-张量方程在偏微分方程数值解中具有重要的应用。基于张量分裂技术提出求解非奇异■-张量方程的加速超松驰方法(简称AOR型方法),并证明该方法是线性收敛性的。数值实验表明,在某些情况下AOR型方法比Jacobi方法、G-S方法、SOR方法具有更快的收敛速度。     

求解最大割问题的分枝定界算法

最大割问题是图论中的一个典型的NP困难问题。文中基于最大割问题的半定规划松弛模型，给出了最大割问题的一种二次规划松弛模型，并且理论证明了提出的二次规划松弛模型要优于半定规划松弛模型。在谈模型的基础上，利用分枝定界算法求解最大割问题。对小规模和中等规模的最大割问题分别作数值实验。实验表明分枝定界算法能够给出最大割问题一个好的近似解，是求解中小规模最大割问题的有效方法。     

半定规划的改进的外梯度法

利用半定规划的最优性条件,对其进行有效变换,把求解半定规划问题转化为求解变分不等式问题,再给出一个改进的求解变分不等式问题的外梯度法,从而得到半定规划问题的最优解.结果表明:改进的算法是求解半定规划的有效方法.     

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

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

模系矩阵分裂迭代法定价机制转换下的美式Kou型跳扩散期权

【目的】研究机制转换下的美式Kou型跳扩散期权模型的数值解法。【方法】基于Crank-Nicolson拟合有限体积法离散得到的线性互补问题,引入高效的模系矩阵分裂迭代法进行求解。【结果】给出了H₊离散矩阵下算法的收敛性定理。【结论】数值实验验证了新方法的有效性、稳健性和收敛性,且模系矩阵分裂迭代法的计算效率优于投影超松弛迭代法。     

协同优化计算方法的分析与改进

针对协同优化算法对初始点选取敏感的问题,从保证系统级优化可行有解的角度,以一典型算例为研究对象,对已有的改进措施进行了分析与完善.当初始点在可行域内时,采用固定因子松弛法进行求解,并给出了动态松弛法失效的原因.当初始点在可行域外时,利用动态松弛因子和固定松弛法因子相结合的策略进行求解,并对动态松弛法优化结果精度不高,以及其值在可行域边界徘徊的情况,分别从系统级和学科级给出了相应的解释.最后,采用减速器优化算例,对所提出的优化策略进行了验证,得到了较为满意的结果.     

基于张量秩校正的图像恢复方法

针对医学图像和视频图像的恢复问题,基于张量表示,研究有限样本下的低秩张量数据恢复问题,在张量奇异值分解(t-SVD)理论的基础上,提出了张量秩校正模型和两阶段张量秩校正方法,第一阶段是用张量核范数最小化模型求得预估解,第二阶段,根据预估解,求解张量秩校正模型,获得更高精度的解.构建了求解张量秩校正模型和张量核范数最小化模型的张量近似点算法,使得可以在实数域上对张量直接进行计算,并且从理论上证明了该算法的收敛性.通过对医学图像和视频图像的数值仿真实验,验证了本文所提出模型和方法的有效性,实验结果显示,张量秩校正模型和方法能够取得更高的恢复精度.     

利用半无限规划的离散化方法求解半定规划问题

【目的】对半定规划的强对偶定理以及求解半定规划近似解的算法进行讨论。【方法】利用求解半无限规划的近似解的离散化思想,及线性规划的强对偶定理。【结果】得到了半定规划强对偶定理一种新的证明方法以及求解半定规划近似解的离散化算法,给出了该算法的数值实验结果。【结论】为半定规划问题提供了一种新的近似求解算法。
     

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

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

求解分裂可行问题的一种投影算法

分裂可行问题产生于工程实践,在信号处理领域有广泛的应用。基于求解线性变分不等式的投影方法,设计了一类求解分裂可行问题的新的投影算法。通过约束最优化问题与变分不等式问题的等价性理论进行问题转化。该算法不需计算矩阵逆和矩阵最大特征值,具有较好的稳定性。还证明了该算法的全局收敛性并进行了数值实验,实验结果表明该方法具有较快的收敛速度和良好的可行性。     

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

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

分裂等式问题的一种简单投影算法

本文主要给出了求解分裂等式问题的一种简单投影算法及其松弛算法,证明了算法的全局收敛性.与相关算法相比,该算法每一步的迭代步长都可直接计算出,避免了计算矩阵的谱半径.     

基于有限差分离散的模方法定价美式债券期权

针对美式债券期权定价模型的数值解法, 构造全隐式的有限差分格式, 并给出格式的稳定性证明. 采用模系矩阵分裂迭代法求解离散得到的线性互补问题, 并与投影超松弛迭代法进行比较. 数值实验验证了新方法的有效性和稳健性.     

球约束加权极大极小离差问题的SDP松弛的注记

【目的】研究利用CVX软件有效求解球约束下的加权极大极小离差问题的SDP松弛模型。【方法】应用半定规划的强对偶定理和Gershgorin圆盘定理。【结果】证明了Haines等人给出的球形约束下离差问题的SDP松弛的解的存在性;同时提出了另一个球形约束下的离差问题,并给出了它的SDP松弛模型的解的存在性证明。【结论】提出的新的证明方法为CVX中嵌入的SeDuMi和SDPT3这两种内点算法提供了有效求解SDP松弛模型的理论依据。     

求解最优潮流全局最优解的二阶半定规划方法

【目的】半定规划凸松弛方法是求取电力系统最优潮流(Optimal power flow, OPF)问题全局最优解的有效技术手段，但解的秩为1的条件难以满足，导致应用具有一定的局限性。针对这一求解困境，提出了一种新的半定规划凸松弛方法。【方法】基于变量扩展，将原变量对应的二阶单项式扩展为新的变量，扩展后可构造一阶及二阶的半正定扩展矩阵，在此基础上将不等式约束转化为矩阵不等式约束，从而形成二阶半定规划凸松弛模型。【结果】为验证所提方法的有效性，求解了常规半定规划方法应用失败的一些反例，结果表明：二阶半定规划松弛模型能更可靠地求得秩为1的扩展矩阵，从而直接获得原OPF问题精确的全局最优解。【结论】二阶半定规划松弛方法为电力系统OPF问题提供了一种更可靠的全局最优算法，具有更好的应用前景。