求解一类变形变分不等式的投影收缩算法及其性质

对一类变形的变分不等式：求，使得提出了一类投影收缩算法，并得到了该算法的收敛性及相关性质．     

On the Monotone Error Rule for Parameter Choice in Iterative and Continuous Regularization Methods

We consider in Hilbert spaces linear ill-posed problems Ax = y with noisy data y satisfying y –y. Regularized approximations x _r to the minimum-norm solution x of Ax = y are constructed by continuous regularization methods or by iterative methods. For the choice of the regularization parameter r (the stopping index n in iterative methods) the following monotone error rule (ME rule) is used: we choose r = r _ME (n = n _ME) as the largest r-value with the guaranteed monotonical decrease of the error x _r – x for r [0, r _ME] (x _n – x <#60; x _n–1 – x for n = 1, 2, ..., n _ME). Main attention is paid to iterative methods of gradient type and to nonstationary implicit iteration methods. As shown, the ME rule leads for many methods to order optimal error bounds. Comparisons with other rules for the choice of the stopping index are made and numerical examples are given.This revised version was published online in October 2005 with corrections to the Cover Date.     

Lasso solution strategies for the vehicle routing problem with pickups and deliveries

This paper considers the vehicle routing problem with pickups and deliveries (VRPPD) where the same customer may require both a delivery and a pickup. This is the case, for instance, of breweries that deliver beer or mineral water bottles to a set of customers and collect empty bottles from the same customers. It is possible to relax the customary practice of performing a pickup when delivering at a customer, and postpone the pickup until the vehicle has sufficient free capacity. In the case of breweries, these solutions will often consist of routes in which bottles are first delivered until the vehicle is partly unloaded, then both pickup and delivery are performed at the remaining customers, and finally empty bottles are picked up from the first visited customers. These customers are revisited in reverse order, thus giving rise to lasso shaped solutions. Another possibility is to relax the traditional problem even more and allow customers to be visited twice either in two different routes or at different times on the same route, giving rise to a general solution. This article develops a tabu search algorithm capable of producing lasso solutions. A general solution can be reached by first duplicating each customer and generating a Hamiltonian solution on the extended set of customers. Test results show that while general solutions outperform other solution shapes in term of cost, their computation can be time consuming. The best lasso solution generated within a given time limit is generally better than the best general solution produced with the same computing effort.     

Preconditioned Iterative Methods for Algebraic Systems from Multiplicative Half-Quadratic Regularization Image Restorations

<正>Image restoration is often solved by minimizing an energy function consisting of a data-fidelity term and a regularization term.A regularized convex term can usually preserve the image edges well in the restored image.In this paper,we consider a class of convex and edge-preserving regularization functions,i.e.,multiplicative half-quadratic regularizations,and we use the Newton method to solve the correspondingly reduced systems of nonlinear equations.At each Newton iterate,the preconditioned conjugate gradient method,incorporated with a constraint preconditioner,is employed to solve the structured Newton equation that has a symmetric positive definite coefficient matrix. The eigenvalue bounds of the preconditioned matrix are deliberately derived,which can be used to estimate the convergence speed of the preconditioned conjugate gradient method.We use experimental results to demonstrate that this new approach is efficient, and the effect of image restoration is reasonably well.     

基于连分式重新推导的Newton迭代公式及其变体

基于Thiele连分式,重新建立了求解非线性方程的经典的Newton迭代公式.为了避免求导数运算,采用差商可以近似代替导数的办法,得到Newton迭代方法的几个变体并给出了其收敛的阶数.最后,数值实例证实了这些迭代格式是有效的.     

求解非线性方程的加权迭代方法

提出加速迭代收敛的新思想,构造出一类加权迭代格式.通过选取最优加权因子使得该迭代格式具有较小的渐近误差常数,且至少具有原有迭代格式的收敛阶,数值例子表明该方法具有较快的收敛速度.     

求解广义鞍点问题的混合并行迭代法(英文)

为了在高性能计算机上求解广义鞍点问题,对于合适的系数矩阵,本文提出混合并行迭代法及其加速形式.并详细讨论了新方法的收敛性.     

Convergence Properties of Projection and Contraction Methods for Variational Inequality Problems

In this paper we develop the convergence theory of a general class of projection and contraction algorithms (PC method), where an extended stepsize rule is used, for solving variational inequality (VI) problems. It is shown that, by defining a scaled projection residue, the PC method forces the sequence of the residues to zero. It is also shown that, by defining a projected function, the PC method forces the sequence of projected functions to zero. A consequence of this result is that if the PC method converges to a nondegenerate solution of the VI problem, then after a finite number of iterations, the optimal face is identified. Finally, we study local convergence behavior of the extragradient algorithm for solving the KKT system of the inequality constrained VI problem. \keywords{Variational inequality, Projection and contraction method, Predictor-corrector stepsize, Convergence property.} \amsclass{90C30, 90C33, 65K05.} Accepted 5 September 2000. Online publication 16 January 2001.     

An Efficient Algorithm for Computing the HHSVM and Its Generalizations

The hybrid Huberized support vector machine (HHSVM) has proved its advantages over the ?₁ support vector machine (SVM) in terms of classification and variable selection. Similar to the ?₁ SVM, the HHSVM enjoys a piecewise linear path property and can be computed by a least-angle regression (LARS)-type piecewise linear solution path algorithm. In this article, we propose a generalized coordinate descent (GCD) algorithm for computing the solution path of the HHSVM. The GCD algorithm takes advantage of a majorization–minimization trick to make each coordinatewise update simple and efficient. Extensive numerical experiments show that the GCD algorithm is much faster than the LARS-type path algorithm. We further extend the GCD algorithm to solve a class of elastic net penalized large margin classifiers, demonstrating the generality of the GCD algorithm. We have implemented the GCD algorithm in a publicly available R package gcdnet.     

On Lanczos Based Methods for the Regularization of Discrete Ill-Posed Problems

We study hybrid methods for the solution of linear ill-posed problems. Hybrid methods are based on he Lanczos process, which yields a sequence of small bidiagonal systems approximating the original ill-posed problem. In a second step, some additional regularization, typically the truncated SVD, is used to stabilize the iteration. We investigate two different hybrid methods and interpret these schemes as well-known projection methods, namely least-squares projection and the dual least-squares method. Numerical results are provided to illustrate the potential of these methods. This gives interesting insight in to the behavior of hybrid methods in practice.This revised version was published online in October 2005 with corrections to the Cover Date.     

Stokes方程的投影／方向分裂谱方法

我们提出和分析了一种求解Stokes方程的数值方法．新方法基于空间上的Legendre谱离散,时间上则采用投影／方向分裂格式．更确切地说,时间离散的出发点是旋度形式的压力校正投影法,在此基础上进一步应用方向分裂法,把速度和压力方程分裂为一系列一维的椭圆型子问题．然后生成的这些一维子问题用Legendre谱方法进行空间离散．另外,我们证明了全离散格式的稳定性．一些数值实验验证了收敛性和方法的有效性．     

非线性方程组的具有单边初值条件的分裂型单调迭代法

本文利用区间迭代法的思想，提出了一种使用单边初值条件的分裂型单调迭代方法，证明了该方法的收敛性，并且具体化到常见的单调迭代法。     

解第一类线性算子方程的多层次迭代法(英文)

In this paper we develop two multilevel iteration methods for solving linear systems resulting from the Galerkin method and Tikhonov regularization for linear ill-posed problems. The two algorithms and their convergence analyses are presented in an abstract framework.     

一类预条件AOR迭代法及其收敛性

给出了一类预条件的AOR迭代法及其收敛性,并给出了松驰因子ω与加速因子γ的选取对收敛速度的影响,同时通过数值实例验证了主要结果.     

Hilbert空间中涉及一类新的具误差迭代程序的平衡问题的黏性逼近法

In this paper, we introduce an iterative scheme with error by the viscosity approximation method for finding a common element of the set of solutions of an equilibrium problem and the set of fixed points of a nonexpansive mapping in a Hilbert space. A strong convergence theorem is given, which generalizes all the results obtained by S.Takahashi and W.Takahashi in 2007. In addition, some of the methods applied in this paper improve those of S.Takahashi and W.Takahashi.     

无约束最优化问题中一类新黄族及其性质

本文提出了一类新的用于解决无约束最优化问题的拟牛顿方法,并证明了这样的性质,在 精确线性搜索条件下,每一步该族所有方法所产生的迭代方向和迭代点列仅依赖于参数ρ.该方 法可视为拟牛顿方法中黄族的推广.     

Poisson方程差分格式迭代解法中一些最优参数的有理拟合方法(英文)

本文针对二维Poisson方程五点和九点差分格式,导出了求解这些格式的SOR方法中最优松弛因子与区域剖分数的有理拟合公式,给出了Jacobi结合Chebyshev加速方法中Jacobi迭代矩阵谱半径的有理拟合公式.实际计算表明这些公式计算效果良好.     

均衡问题和不动点问题的粘滞近似方法及其应用

用粘滞近似方法产生了一个新的迭代序列,并证明了该迭代序列强收敛于一个非扩张映射的不动点,同时该不动点也是一个变分不等式和一个均衡问题的共同解.作为应用,另外证明了一个关于非扩张映射和严格伪压缩映射的定理.     

关于PSD迭代法收敛的充分必要性定理

本文在线性方程组系数矩阵A为相容次序矩阵及A的Jacobi迭代矩阵的特征值μ_j均为实数且μ_j~2<1的条件下,得出了PSD迭代法收敛的充分必要性定理,并由此而得到了一个易于判别的PSD法收敛性定理。