关于单调变分不等式的不精确邻近点算法的收敛性分析

We consider a proximal point algorithm(PPA) for solving monotone variational inequalities. PPA generates a sequence by solving a sequence of strongly monotone subproblems .However,solving the subproblems is either expensive or impossible. Some inexact proximal point algorithms(IPPA) have been developed in many literatures. In this paper, we present a criterion for approximately solving subproblems. It only needs one simple additional work on the basis of original algorithm, and the convergence criterion becomes milder. We show that this method converges globally under new criterion provided that the solution set of the problem is nonempty.     

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

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

求解一类非对称单调变分不等式的非精确自适应交替方向法

本文研究了一类单调非对称变分不等式的非精确自适应交替方向法,证明了方法的收敛性.     

Enlargement of Monotone Operators with Applications to Variational Inequalities

Given a point-to-set operator T, we introduce the operator T defined as T(x)= {u: u – v, x – y – for all y Rn, v T(y)}. When T is maximal monotone T inherits most properties of the -subdifferential, e.g. it is bounded on bounded sets, T(x) contains the image through T of a sufficiently small ball around x, etc. We prove these and other relevant properties of T, and apply it to generate an inexact proximal point method with generalized distances for variational inequalities, whose subproblems consist of solving problems of the form 0 H(x), while the subproblems of the exact method are of the form 0 H(x). If k is the coefficient used in the kth iteration and the k's are summable, then the sequence generated by the inexact algorithm is still convergent to a solution of the original problem. If the original operator is well behaved enough, then the solution set of each subproblem contains a ball around the exact solution, and so each subproblem can be finitely solved.     

求解单调变分不等式的近似邻近点算法的收敛性分析

为了求解单调变分不等式,建立了一个新的误差准则,并且在不需要增加诸如投影,外梯度等步骤的情况下证明了邻近点算法的收敛性.     

求解结构型单调变分不等式的改进的邻近类分解方法

邻近类分解方法首先是由Chen和Teboulle（Math. Programming,1994,64(1):81-101）提出用来求解凸的极小化问题．在此基础上,该文提出一种新方法求解具有分离结构的单调变分不等式．其主要优点在于放松了算法中对某些参数的限制,使得新方法更加便于计算．在和原分解方法相同的假设下,可以证明新方法是全局收敛的．     

惩罚框架下求解广义Nash均衡问题的分解算法

广义Nash均衡问题(GNEP),是非合作博弈论中一类重要的问题,它在经济学、管理科学和交通规划等领域有着广泛的应用.本文主要提出一种新的惩罚算法来求解一般的广义Nash均衡问题,并根据罚函数的特殊结构,采用交替方向法求解子问题.在一定的条件下,本文证明新算法的全局收敛性.多个数值例子的试验结果表明算法是可行的,并且是有效的.     

Some proximal algorithms for linearly constrained general variational inequalities

Based on the classical proximal point algorithm (PPA), some PPA-based numerical algorithms for general variational inequalities (GVIs) have been developed recently. Inspired by these algorithms, in this article we propose some proximal algorithms for solving linearly constrained GVIs (LCGVIs). The resulted subproblems are regularized proximally, and they are allowed to be solved either exactly or approximately.     

Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities

The alternating direction method is one of the attractive approaches for solving linearly constrained separate monotone variational inequalities. Experience on applications has shown that the number of iterations depends significantly on the penalty parameter for the system of linear constraint equations. While the penalty parameter is a constant in the original method, in this paper we present a modified alternating direction method that adjusts the penalty parameter per iteration based on the iterate message. Preliminary numerical tests show that the self-adaptive adjustment technique is effective in practice.     

Alternating Direction Method for Maximum Entropy Subject to Simple Constraint Sets

The problem of maximizing the entropy subject to simple constraint sets is reformulated as a structured variational inequality problem by introducing dual variables. A new iterative alternating direction method is then developed that generates alternatively the dual and primal iterates. For some existing maximum entropy problems in the literature, the new dual iterate can be derived from a simple projection and then the new primal iterate can be obtained via solving approximately n separate one-dimensional strong monotone equations. Therefore, the proposed method is very easy to carry out. Preliminary numerical results show that the method is applicable.     

Convergence Analysis of Some Methods for Minimizing a Nonsmooth Convex Function

In this paper, we analyze a class of methods for minimizing a proper lower semicontinuous extended-valued convex function . Instead of the original objective function f, we employ a convex approximation f _{k + 1} at the kth iteration. Some global convergence rate estimates are obtained. We illustrate our approach by proposing (i) a new family of proximal point algorithms which possesses the global convergence rate estimate even it the iteration points are calculated approximately, where are the proximal parameters, and (ii) a variant proximal bundle method. Applications to stochastic programs are discussed.     

一种求解单调变分不等式的部分并行分裂LQP交替方向法

LQP交替方向法是求解可分离结构型单调变分不等式问题的一种非常有效的方法.它不仅可以充分地利用目标函数的可分结构,将原问题分解为多个更易求解的子问题,还更适合求解大规模问题.对于带有三个可分离算子的单调变分不等式问题,结合增广拉格朗日算法和LQP交替方向法提出了一种部分并行分裂LQP交替方向法,构造了新算法的两个下降方向,结合这两个下降方向得到了一个新的下降方向,沿着这个新的下降方向给出了最优步长.并在较弱的假设条件下,证明了新算法的全局收敛性.     

PPA BASED PREDICTION-CORRECTION METHODS FOR MONOTONE VARIATIONAL INEQUALITIES

In this paper we study the proximal point algorithm (PPA) based prediction-correction (PC) methods for monotone variational inequalities. Each iteration of these methods consists of a prediction and a correction. The predictors are produced by inexact PPA steps. The new iterates are then updated by a correction using the PPA formula. We present two profit functions which serve two purposes: First we show that the profit functions are tight lower bounds of the improvements obtained in each iteration. Based on this conclusion we obtain the convergence inexactness restrictions for the prediction step. Second we show that the profit functions are quadratically dependent upon the step lengths, thus the optimal step lengths are obtained in the correction step. In the last part of the paper we compare the strengths of different methods based on their inexactness restrictions.     

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

对一类非对称变分不等式问题提出了交替方向法。推广了交替方向仅适用于等式约束或不等约束的情形，得出了迭代序列的一些性质及收敛性．     

Primal-dual proximal point algorithm for linearly constrained convex programming problems

A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs.     

A method of local convex majorants for solving variational-like inequalities

A numerical method based on convex approximations that locally majorize a gap function is proposed for solving a variational-like inequality. The algorithm is theoretically validated and the results of comparison of its numerical efficiency to that of the conventional methods are presented.     

On the proximal point method for equilibrium problems in Hilbert spaces

We analyse a proximal point method for equilibrium problems in Hilbert spaces, improving upon previously known convergence results. We prove global weak convergence of the generated sequence to a solution of the problem, assuming existence of solutions and rather mild monotonicity properties of the bifunction which defines the equilibrium problem, and we establish existence of solutions of the proximal subproblems. We also present a new reformulation of equilibrium problems as variational inequalities ones.     

Proximal-Point Algorithm Using a Linear Proximal Term

Proximal-point algorithms (PPAs) are classical solvers for convex optimization problems and monotone variational inequalities (VIs). The proximal term in existing PPAs usually is the gradient of a certain function. This paper presents a class of PPA-based methods for monotone VIs. For a given current point, a proximal point is obtained via solving a PPA-like subproblem whose proximal term is linear but may not be the gradient of any functions. The new iterate is updated via an additional slight calculation. Global convergence of the method is proved under the same mild assumptions as the original PPA. Finally, profiting from the less restrictions on the linear proximal terms, we propose some parallel splitting augmented Lagrangian methods for structured variational inequalities with separable operators. B.S. He was supported by NSFC Grant 10571083 and Jiangsu NSF Grant BK2008255.