可分离凸优化问题的非精确平行分裂算法

针对一类可分离凸优化问题提出了一种非精确平行分裂算法.该算法充分利用了所求解问题的可分离结构,并对子问题进行非精确求解.在适当的条件下,证明了所提出的非精确平行分裂算法的全局收敛性,初步的数值实验说明了算法有效性.     

多重集非凸分裂可行问题的非精确均值投影算法

在本文中,我们引入了非精确均值投影算法来求解多重集非凸分裂可行问题,其中这些非凸集合为半代数邻近正则集合.通过借助著名的Kurdyka-Lojasiewicz不等式理论,我们建立了算法的收敛性.     

一类单调变分不等式的非精确交替方向法

交替方向法适合于求解大规模问题.该文对于一类变分不等式提出了一种新的交替方向法.在每步迭代计算中,新方法提出了易于计算的子问题,该子问题由强单调的线性变分不等式和良态的非线性方程系统构成.基于子问题的精确求解,该文证明了算法的收敛性.进一步,又提出了一类非精确交替方向法,每步迭代计算只需非精确求解子问题.在一定的非精确条件下,算法的收敛性得以证明.     

一类凸优化的混合下降算法

邻近点算法(PPA)是一类求解凸优化问题的经典算法, 但往往需要精确求解隐式子问题,于是近似邻近点算法(APPA)在满足一定的近似规则下非精确求解PPA的子问题, 降低了求解难度. 本文利用近似规则的历史信息和随机数扩张预测校正步产生了两个方向, 通过随机数组合两个方向获得了一类凸优化的混合下降算法.在近似规则满足的情况下, 给出了混合下降算法的收敛性证明. 一系列的数值试验表明了混合下降算法的有效性和效率性.     

凸优化和单调变分不等式收缩算法的统一框架

线性约束的凸优化问题可以转化成一个形式更一般的单调变分不等式.在变分不等式的框架下研究最优化问题的求解方法,就像微积分中利用导数求函数的极值,常常会带来很大的方便.求解单调变分不等式的投影收缩算法有一个预测-校正的统一框架,基于"孪生方向和相同步长"有两类花费几乎相当的算法,计算实践证明第二类算法效率往往更高.近年发展起来并被广泛采用的凸规划的分裂收缩算法属于一个更一般的框架,这个框架中的预测同样提供了一对孪生方向.迄今为止的凸规划的分裂收缩算法,都相当于变分不等式投影收缩算法中的第一类算法.本文指出,利用现有的步长法则,配上孪生方向中的另一个方向,同样可以构造相应的第二类算法.本文在统一框架下证明了两类算法的O(1/t)迭代复杂性.     

非光滑凸优化问题的一个非精确梯度镜面下降算法

本文提出一个求解非光滑凸优化问题非精确梯度镜面下降算法.该算法是Allen-Zhu2016年提出求解光滑凸优化问题梯度镜面下降算法的推广,而且该算法允许目标函数中光滑部分梯度计算和非光滑部分邻近算子计算都存在误差,并且在适当条件下分析了该算法函数值序列的O(1/(k²))收敛速度,这里k表示迭代数.最后关于Lasso问题和Logistic问题的数值结果表明该算法是有效的.     

我和乘子交替方向法20年

1997 年, 交通网络分析方面的问题把我引进乘子交替方向法(ADMM)的研究领域. 近10 年来, 原本用来求解变分不等式的ADMM在优化计算中被广泛采用, 影响越来越大. 这里总结了20 年来我们在ADMM 方面的工作, 特别是近10 年 ADMM 在凸优化分裂收缩算法方面的进展. 梳理主要结果, 说清来龙去脉. 文章利用变分不等式的形式研究凸优化的ADMM 类算法, 论及的所有方法都能纳入一个简单的预测-校正统一框架. 在统一框架下证明算法的收缩性质特别简单. 通读, 有利于了解ADMM类算法的概貌. 仔细阅读, 也许就掌握了根据实际问题需要构造分裂算法的基本技巧. 也要清醒地看到, ADMM类算法源自增广拉格朗日乘子法 (ALM) 和邻近点 (PPA)算法, 它只是便于利用问题的可分离结构, 并没有消除 ALM和PPA等一阶算法固有的缺点.     

求解稀疏逻辑回归问题的嵌套BB算法的分裂增广拉格朗日算法

逻辑回归是经典的分类方法,广泛应用于数据挖掘、机器学习和计算机视觉.现研究带有程。模约束的逻辑回归问题.这类问题广泛用于分类问题中的特征提取,且一般是NP-难的.为了求解这类问题,提出了嵌套BB(Barzilai and Borwein)算法的分裂增广拉格朗日算法(SALM-BB).该算法在迭代中交替地求解一个无约束凸优化问题和一个带程。模约束的二次优化问题.然后借助BB算法求解无约束凸优化问题.通过简单的等价变形直接得到带程。模约束二次优化问题的精确解,并且给出了算法的收敛性定理.最后通过数值实验来测试SALM-BB算法对稀疏逻辑回归问题的计算精确性.数据来源包括真实的UCI数据和模拟数据.数值实验表明,相对于一阶算法SLEP,SALM-BB能够得到更低的平均逻辑损失和错分率.     

一种求解两两合作轮流博弈问题的混合分裂算法

提出了一种求解两两合作轮流博弈的四人博弈问题的混合分裂算法.为了模拟实际博弈过程,该算法由两个组内平行分裂算法和一个组间交替极小化算法构成.算法允许对博弈子问题非精确求解,反映了实际博弈中参与人的有限理性,即允许参与人在博弈过程中出现满足一定条件的误差.在适当条件下,证明了所提出的混合分裂算法全局地收敛到所考虑博弈的Nash平衡.     

与渐近非扩张半群不动点问题相关的分裂等式混合均衡问题及其应用

研究了与渐近非扩张半群不动点问题相关的分裂等式混合均衡问题.在等式约束下,为同时逼近两个空间中混合均衡问题和渐近非扩张半群不动点问题的公共解,借助收缩投影方法引出了一种迭代程序.在适当条件下,该迭代算法的强收敛性被证明.文末还把所得结果应用于分裂等式混合变分不等式问题和分裂等式凸极小化问题.     

On the numerical solution of Korteweg-de Vries equation by the iterative splitting method

In this paper, we apply the method of iterative operator splitting on the Korteweg-de Vries (KdV) equation. The method is based on first, splitting the complex problem into simpler sub-problems. Then each sub-equation is combined with iterative schemes and solved with suitable integrators. Von Neumann analysis is performed to achieve stability criteria for the proposed method applied to the KdV equation. The numerical results obtained by iterative splitting method for various initial conditions are compared with the exact solutions. It is seen that they are in a good agreement with each other.     

Splitting method for an inverse source problem in parabolic differential equations: Error analysis and applications

In this work, we present a numerical method based on a splitting algorithm to find the solution of an inverse source problem with the integral condition. The source term is reconstructed by using the specified data and by employing the Lie splitting method, we decompose the equation into linear and nonlinear parts. Each subproblem is solved by the Fourier transform and then by combining the solutions of subproblems, the solution of the original problem is computed. Moreover, the framework of strongly continuous semigroup (or C₀-semigroup) is employed in error analysis of operator splitting method for the inverse problem. The convergence of the proposed method is also investigated and proved. Finally, some numerical examples in one, two, and three-dimensional spaces are provided to confirm the efficiency and capability of our work compared with some other well-known methods.     

A Fast Augmented Lagrangian Method for Euler's Elastica Models

In this paper, a fast algorithm for Euler's elastica functional is proposed, in which the Euler's elastica functional is reformulated as a constrained minimization problem. Combining the augmented Lagrangian method and operator splitting techniques, the resulting saddle-point problem is solved by a serial of subproblems. To tackle the nonlinear constraints arising in the model, a novel fixed-point-based approach is proposed so that all the subproblems either is a linear problem or has a closed-form solution. We show the good performance of our approach in terms of speed and reliability using numerous numerical examples on synthetic, real-world and medical images for image denoising, image inpainting and image zooming problems.     

A Direct Splitting Method for Nonsmooth Variational Inequalities

We propose a direct splitting method for solving a nonsmooth variational inequality in Hilbert spaces. The weak convergence is established when the operator is the sum of two point-to-set and monotone operators. The proposed method is a natural extension of the incremental subgradient method for nondifferentiable optimization, which strongly explores the structure of the operator using projected subgradient-like techniques. The advantage of our method is that any nontrivial subproblem must be solved, like the evaluation of the resolvent operator. The necessity to compute proximal iterations is the main difficulty of other schemes for solving this kind of problem.     

A projection method based on the splitting Bregman iteration for the image denoising

By analyzing the connection between the projection operator and the shrink operator, we propose a projection method based on the splitting Bregman iteration for image denoising problem in this paper. Compared with the splitting Bregman method, the proposed method has a more compact form so that it is more fast and efficient. Following from the operator theory, the convergence of the proposed method is proved. Some numerical comparisons between the proposed method and the splitting Bregman method are arranged for solving two basic image denoising models.     

Quasiperiodic solutions of variational problems of motion in a central force field

A method is proposed for computing nearly optimal trajectories of dynamic systems with a small parameter by splitting the original variational problem into two separate problems for "fast" and "slow" variables. The problem for "fast" variables is solved by improving the zeroth approximation — the extremals of the linearized problem — by the Ritz method. The solution of the problem for "slow" variables is constructed by passing from a discrete argument — the number of revolutions around the attracting center— to a continuous argument. The proposed method does not require numerical integration of systems of differential equations and produces a highly accurate approximate solution of the problem.Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 68, pp. 113–118, 1989.     

具有模糊信息的多目标运输问题求解

提出一种求解具有模糊信息的多目标运输问题的方法。利用专家意见通过模糊算法集给从各产地到各目的地运送单位物资的模糊综合指标值,运用一种对模糊数排序的方法,将模糊多目标运输问题转化为单目标的运输问题进行求解,最后给出了一个数值例子。     

The splitting finite-difference time-domain methods for Maxwell's equations in two dimensions

In this paper, we consider splitting methods for Maxwell's equations in two dimensions. A new kind of splitting finite-difference time-domain methods on a staggered grid is developed. The corresponding schemes consist of only two stages for each time step, which are very simple in computation. The rigorous analysis of the schemes is given. By the energy method, it is proved that the scheme is unconditionally stable and convergent for the problems with perfectly conducting boundary conditions. Numerical dispersion analysis and numerical experiments are presented to show the efficient performance of the proposed methods. Furthermore, the methods are also applied to solve a scattering problem successfully.     

A distributed Douglas-Rachford splitting method for multi-block convex minimization problems

A customized Douglas-Rachford splitting method (DRSM) was recently proposed to solve two-block separable convex optimization problems with linear constraints and simple abstract constraints. The algorithm has advantage over the well-known alternating direction method of multipliers (ADMM), the dual application of DRSM to the two-block convex minimization problem, in the sense that the subproblems can have larger opportunity of possessing closed-form solutions since they are unconstrained. In this paper, we further study along this way by considering the primal application of DRSM for the general case m≥3, i.e., we consider the multi-block separable convex minimization problem with linear constraints where the objective function is separable into m individual convex functions without coupled variables. The resulting method fully exploits the separable structure and enjoys decoupled subproblems which can be solved simultaneously. Both the exact and inexact versions of the new method are presented in a unified framework. Under mild conditions, we manage to prove the global convergence of the algorithm. Preliminary numerical experiments for extracting the background from corrupted surveillance video verify the encouraging efficiency of the new algorithm.