近似邻近点算法收敛性的一个注记

近似邻近点算法在最优化理论与方法研究中具有重要作用.在不同误差准则下,近似邻近点算法具有不同的收敛性.利用极大单调算子等工具给出了一个具体的例子,解释了在一些误差准则下近似邻近点算法的收敛性.     

An inexact proximal point algorithm for maximal monotone vector fields on Hadamard manifolds

In this paper, an inexact proximal point algorithm concerned with the singularity of maximal monotone vector fields is introduced and studied on Hadamard manifolds, in which a relative error tolerance with squared summable error factors is considered. It is proved that the sequence generated by the proposed method is convergent to a solution of the problem. Moreover, an application to the optimization problem on Hadamard manifolds is given. The main results presented in this paper generalize and improve some corresponding known results given in the literature.     

On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators

This paper shows, by means of an operator called asplitting operator, that the Douglas—Rachford splitting method for finding a zero of the sum of two monotone operators is a special case of the proximal point algorithm. Therefore, applications of Douglas—Rachford splitting, such as the alternating direction method of multipliers for convex programming decomposition, are also special cases of the proximal point algorithm. This observation allows the unification and generalization of a variety of convex programming algorithms. By introducing a modified version of the proximal point algorithm, we derive a new,generalized alternating direction method of multipliers for convex programming. Advances of this sort illustrate the power and generality gained by adopting monotone operator theory as a conceptual framework.This paper is drawn largely from the dissertation research of the first author. The dissertation was performed at M.I.T. under the supervision of the second author, and was supported in part by the Army Research Office under grant number DAAL03-86-K-0171, and by the National Science Foundation under grant number ECS-8519058.     

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

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

New fixed point theorems and applications of mixed monotone operator

In this paper, we study the uniqueness and existence of fixed point of mixed monotone operators in the partially ordered Banach space. The results extend and improve recent related results.     

A proximal point algorithm for generalized fractional programs

In this paper, the problem of solving generalized fractional programs will be addressed. This problem has been extensively studied and several algorithms have been proposed. In this work, we propose an algorithm that combines the proximal point method with a continuous min–max formulation of discrete generalized fractional programs. The proposed method can handle non-differentiable convex problems with possibly unbounded feasible constraints set, and solves at each iteration a convex program with unique dual solution. It generates two sequences that approximate the optimal value of the considered problem from below and from above at each step. For a class of functions, including the linear case, the convergence rate is at least linear.     

Regularization inertial proximal point algorithm for common solutions of a finite family of inverse-strongly monotone equations

The aim of the paper is to propose an iterative regularization method of proximal point type for finding a common solution for a finite family of inverse-strongly monotone equations in Hilbert spaces.     

Generalized proximal point algorithm for convex optimization

Ha (Ref. 1) recently introduced a generalized proximal point algorithm for solving a generalized equation. In this note, we present a generalized proximal point algorithm for convex optimization problems based on Ha's work. The idea behind this algorithm is that, instead of adding a quadratic term to all the variables, we add a quadratic term to a subset of the variables. We extend the criteria for approximate solutions given by Rockafellar (Ref. 2) and Auslender (Ref. 3) and present convergence results. Finally, we show how this algorithm can be applied to solve block-angular linear and quadratic programming problems.     

A Relaxed Approximate Proximal Point Algorithm

For a maximal monotone operator T, a well-known overrelaxed point algorithm is often used to find the zeros of T. In this paper, we enhance the algorithm to find a point in , where is a given closed convex set. In the inexact case of our modified relaxed proximal point algorithm, we give a new criterion. The convergence analysis is quite easy to follow.     

Modified proximal point algorithm for extended linear-quadratic programming

Extended linear-quadratic programming arises as a flexible modeling scheme in dynamic and stochastic optimization, which allows for penalty terms and facilitates the use of duality. Computationally it raises new challenges as well as new possibilities in large-scale applications. Recent efforts have been focused on the fully quadratic case ([15] and [23]), while relying on the fundamental proximal point algorithm (PPA) as a shell of outer iterations when the problem is not fully quadratic. In this paper, we focus on the nonfully quadratic cases by proposing some new variants of the fundamental PPA. We first construct a continuously differentiable saddle function S(u, v) through infimal convolution in such a way that the optimal primal-dual pairs of the original problem are just the saddle points of S(u, v) on the whole space. Then the original extended linear-quadratic-programming problem reduces to solving the nonlinear equation S(u, v)=0. We then embed the fundamental PPA and some of its previous variants in the framework of a Newton-like iteration for this equation. After revealing the local quadratic structure of S near the solution, we derive new extensions of the fundamental PPA. In numerical tests, the modified iteration scheme based on the quasi-Newton update formula outperforms the fundamental PPA considerably.     

Some eigenvalue results for maximal monotone operators

We study the eigenvalue problem of the form

0∈Tx−λCx,     

Essential approximate point spectra and Weyl's theorem for operator matrices

When A∈B(H) and B∈B(K) are given, we denote by MC the operator acting on the infinite dimensional separable Hilbert space H⊕K of the form . In this paper, it is shown that a 2×2 operator matrix MC is upper semi-Fredholm and ind(MC)?0 for some C∈B(K,H) if and only if A is upper semi-Fredholm and

     

Interior proximal point algorithm for linear programs

An interior proximal point algorithm for finding a solution of a linear program is presented. The distinguishing feature of this algorithm is the addition of a quadratic proximal term to the linear objective function. This perturbation has allowed us to obtain solutions with better feasibility. Implementation of this algorithm shows that the algorithms. We also establish global convergence and local linear convergence of the algorithm.This research was supported by National Science Foundation Grants DCR-85-21228 and CCR-87-23091 and by Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-89-0410. It was conducted while the author was a Graduate Student at the Computer Sciences Department, University of Wisconsin, Madison, Wisconsin.     

A new logarithmic-quadratic proximal method for nonlinear complementarity problems

In this paper, we propose a new modified logarithmic-quadratic proximal (LQP) method for solving nonlinear complementarity problems (NCP). We suggest using a prediction-correction method to solve NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed accuracy criterion and the new iterate is computed by using a new step size α_k. Under suitable conditions, we prove that the new method is globally convergent. We report preliminary computational results to illustrate the efficiency of the proposed method. This new method can be considered as a significant refinement of the previously known methods for solving nonlinear complementarity problems.     

Finite termination of the proximal point algorithm

This paper concerns the notion of a sharp minimum on a set and its relationship to the proximal point algorithm. We give several equivalent definitions of the property and use the notion to prove finite termination of the proximal point algorithm.This material is based on research supported by National Science Foundation Grants DCR-8521228 and CCR-8723091, and Air Force Office of Scientific Research Grant AFOSR-86-0172.     

一个新的BUNDLE近似点算法及其收敛性质

提出了一类修正的近似点算法并讨论了算法的收敛性质及其Ｂｕｄｌｅ变形的收敛性质。     

A note on the existence of zeroes of convexly regularized sums of maximal monotone operators

Many algorithms for solving the problem of finding zeroes of a sum of two maximal monotone operators T₁ and T₂, have regularized subproblems of the kind 0T₁(x)+T₂(x)+∂D(x), where D is a convex function. We develop an unified analysis for existence of solutions of these subproblems, through the introduction of the concept of convex regularization, which includes several well-known cases in the literature. Finally, we establish conditions, either on D or on the operators, which assure solvability of the subproblems.     

An explicit algorithm for monotone variational inequalities

We introduce a fully explicit method for solving monotone variational inequalities in Hilbert spaces, where orthogonal projections onto the feasible set are replaced by projections onto suitable hyperplanes. We prove weak convergence of the whole generated sequence to a solution of the problem, under only the assumptions of continuity and monotonicity of the operator and existence of solutions.     

Convergence of stationary sequences for variational inequalities with maximal monotone operators

LetT be a maximal monotone operator defined on ^N . In this paper we consider the associated variational inequality 0 T(x ^*) and stationary sequences {x _k ^* for this operator, i.e., satisfyingT(x _k ^* 0. The aim of this paper is to give sufficient conditions ensuring that these sequences converge to the solution setT ^–1(0) especially when they are unbounded. For this we generalize and improve the directionally local boundedness theorem of Rockafellar to maximal monotone operatorsT defined on ^N .