Proximal Point Methods and Nonconvex Optimization

The goal of this paper is to discover some possibilities for applying the proximal point method to nonconvex problems. It can be proved that – for a wide class of problems – proximal regularization performed with appropriate regularization parameters ensures convexity of the auxiliary problems and each accumulation point of the method satisfies the necessary optimality conditions.     

Steepest descent evolution equations: asymptotic behavior of solutions and rate of convergence

We study the asymptotic behavior of the solutions of evolution equations of the form , where is a one-parameter family of approximations of a convex function we wish to minimize. We investigate sufficient conditions on the parametrization ensuring that the integral curves converge when towards a particular minimizer of . The speed of convergence is also investigated, and a result concerning the continuity of the limit point with respect to the parametrization is established. The results are illustrated on different approximation methods. In particular, we present a detailed application to the logarithmic barrier in linear programming.

     

Steepest Descent Methods with Generalized Distances for Constrained Optimization

We consider the problem s.t. , where C is a closed and covex subset of with nonempty interior, and introduce a family of interior point methods for this problem, which can be seen as approximate versions of generalized proximal point methods. Each step consists of a one-dimensional search along either a curve or a segment in the interior of C. The information about the boundary of C is contained in a generalized distance which defines the segment of the curve, and whose gradient diverges at the boundary of C. The objective of the search is either f or f plus a regularizing term. When , the usual steepest descent method is a particular case of our general scheme, and we manage to extend known convergence results for the steepest descent method to our family: for nonregularized one-dimensional searches,under a level set boundedness assumption on f, the sequence is bounded, the difference between consecutive iterates converges to 0 and every cluster point of the sequence satisfies first-order optimality conditions for the problem, i.e. is a solution if f is convex. For the regularized search and convex f, no boundedness condition on f is needed and full and global convergence of the sequence to a solution of the problem is established.     

Auxiliary Problem Principle and Proximal Point Methods

An extension of the auxiliary problem principle to variational inequalities with non-symmetric multi-valued operators in Hilbert spaces is studied. This extension concerns the case that the operator is split into the sum of a single-valued operator , possessing a kind of pseudo Dunn property, and a maximal monotone operator . The current auxiliary problem is k constructed by fixing at the previous iterate, whereas (or its single-valued approximation ^k) k is considered at a variable point. Using auxiliary operators of the form ^k+ , with _k>0, the standard for the auxiliary problem principle assumption of the strong convexity of the function h can be weakened exploiting mutual properties of and h. Convergence of the general scheme is analyzed and some applications are sketched briefly.     

Proximal Point Algorithm On Riemannian Manifolds

Abstract

In this paper we consider the minimization problem with constraints. We will show that if the set of constraints is a Riemannian manifold of nonpositive sectional curvature, and the objective function is convex in this manifold, then the proximal point method in Euclidean space is naturally extended to solve that class of problems. We will prove that the sequence generated by our method is well defined and converge to a minimizer point. In particular we show how tools of Riemannian geometry, more specifically the convex analysis in Riemannian manifolds, can be used to solve nonconvex constrained problem in Euclidean, space.     

On Some Properties of Generalized Proximal Point Methods for Variational Inequalities

We discuss here generalized proximal point methods applied to variational inequality problems. These methods differ from the classical point method in that a so-called Bregman distance substitutes for the Euclidean distance and forces the sequence generated by the algorithm to remain in the interior of the feasible region, assumed to be nonempty. We consider here the case in which this region is a polyhedron (which includes linear and nonlinear programming, monotone linear complementarity problems, and also certain nonlinear complementarity problems), and present two alternatives to deal with linear equality constraints. We prove that the sequences generated by any of these alternatives, which in general are different, converge to the same point, namely the solution of the problem which is closest, in the sense of the Bregman distance, to the initial iterate, for a certain class of operators. This class consists essentially of point-to-point and differentiable operators such that their Jacobian matrices are positive semidefinite (not necessarily symmetric) and their kernels are constant in the feasible region and invariant through symmetrization. For these operators, the solution set of the problem is also a polyhedron. Thus, we extend a previous similar result which covered only linear operators with symmetric and positive-semidefinite matrices.     

一致凸Banach空间中渐近非扩张映射不动点的粘性逼近

在一致凸并具有一致G可微范数的Banach空间中,研究一类渐近非扩张映象迭代序列的收敛性,给出强收敛定理.     

Proximal Methods in View of Interior-Point Strategies

This paper deals with regularized penalty-barrier methods for convex programming problems. In the spirit of an iterative proximal regularization approach, an interior-point method is constructed, in which at each step a strongly convex function has to be minimized and the prox-term can be scaled by a variable scaling factor. The convergence of the method is studied for an axiomatically given class of barrier functions. According to the results, a wide class of barrier functions (in particular, logarithmic and exponential functions) can be applied to design special algorithms. For the method with a logarithmic barrier, the rate of convergence is investigated and assumptions that ensure linear convergence are given.     

极大单调算子的一个邻近点算法

设E是自反的Banach空间,T∶E→2E是极大单调算子.T-10≠.令x0∈E,yn=(J λnT)-1xn en,xn 1=J-1(αnJxn (1-αn)Jyn),n≥0,λn>0,αn∈[0,1],本文研究了{xn}收敛性.     

Efficiency of Proximal Bundle Methods

We give efficiency estimates for proximal bundle methods for finding f_*min_Xf, where f and X are convex. We show that, for any accuracy <0, these methods find a point x^kX such that f(x^k)–f^* after at most k=O(1/³) objective and subgradient evaluations.     

Two Facts on the Convergence of the Cauchy Algorithm

We discuss two issues related to the Cauchy algorithm. First, we use anArmijo search with constant 0.5 and show that the sequence isFejer convergent to the optimal set, and hence convergent. Second, we useexact line searches and show an example in which the sequence fails toconverge.     

Strong Convergence of an Inexact Proximal Point Algorithm for Equilibrium Problems in Banach Spaces

We develop an inexact proximal point algorithm for solving equilibrium problems in Banach spaces which consists of two principal steps and admits an interesting geometric interpretation. At a certain iterate, first we solve an inexact regularized equilibrium problem with a flexible error criterion to obtain an axillary point. Using this axillary point and the inexact solution of the previous iterate, we construct two appropriate hyperplanes which separate the current iterate from the solution set of the given problem. Then the next iterate is defined as the Bregman projection of the initial point onto the intersection of two halfspaces obtained from the two constructed hyperplanes containing the solution set of the original problem. Assuming standard hypotheses, we present a convergence analysis for our algorithm, establishing that the generated sequence strongly and globally converges to a solution of the problem which is the closest one to the starting point of the algorithm.     

Inexact Proximal Point Methods for Equilibrium Problems in Banach Spaces

We introduce two inexact proximal-like methods for solving equilibrium problems in reflexive Banach spaces and establish their convergence properties, proving that the sequence generated by each one of them converges to a solution of the equilibrium problem under reasonable assumptions.     

非扩张映射不动点的粘性逼近方法

在具有一致Gateaux可微范数的Banach空间中,建立了一个改进的非扩张映射不动点的粘性逼近方法,并在一定条件下证明了该方法所得到的迭代序列的强收性.本文所得结果扩展并统一了部分文献的结果.     

论强单调算子下的邻点算法

考虑强单调算子下的邻点算法.证明了它容许弱于可和性条件的绝对误差以及每个松弛因子不超过某个较小正数的相对误差.     

对广义强非线性拟变分包含带有误差的近似点算法

本文研究了一类广义强非线性拟变分包含.在Hilbert空间内利用与极大单调映象相联系的预解算子的性质,对广义强非线性拟变分包含建立了解的存在性定理和建议了一个新的寻求近似解的带有误差的近似总算法,证明了近似解序列强收敛于精确解.作为特例,在此领域内的某些已知结果也被讨论.     

A Regularization Method for the Proximal Point Algorithm

A regularization method for the proximal point algorithm of finding a zero for a maximal monotone operator in a Hilbert space is proposed. Strong convergence of this algorithm is proved.Hong-Kun Xu: Supported in part by NRF     

Proximal Point Algorithms for General Variational Inequalities

This paper presents a unified framework of proximal point algorithms (PPAs) for solving general variational inequalities (GVIs). Some existing PPAs for classical variational inequalities, including both the exact and inexact versions, are extended to solving GVIs. Consequently, several new PPA-based algorithms are proposed. M. Li was supported by NSFC Grant 10571083 and SRFDP Grant 200802861031. L.Z. Liao was supported in part by grants from Hong Kong Baptist University and the Research Grant Council of Hong Kong. X.M. Yuan was supported in part by FRG/08-09/II-40 from Hong Kong Baptist University and NSFC Grant 10701055.     

关于极大强单调算子的不精确邻近点算法的收敛性分析

该文研究集值映象方程0∈T(z)的解的迭代逼近，其中T是极大强单调算子．设{x^k}与{e^k}是由不精确邻近点算法x^{k+1}+c_kT(x^{k+1})> x^k+e^{k+1}生成的序列，满足‖e^{k+1}‖≤η_k‖x^{k+1}_x^k‖, ∑^∞_{k=0}(η_k-1)<+∞且inf_(k≥0) η_k=μ≥1.在适当的限制下证明了，{x^k}收敛到T的一个根当且仅当 lim inf_{k→+∞} d(x^k,Z)=0，其中Z是方程0∈T(z)的解集     

A dynamic gradient approach to Pareto optimization with nonsmooth convex objective functions

In a general Hilbert framework, we consider continuous gradient-like dynamical systems for constrained multiobjective optimization involving nonsmooth convex objective functions. Based on the Yosida regularization of the subdifferential operators involved in the system, we obtain the existence of strong global trajectories. We prove a descent property for each objective function, and the convergence of trajectories to weak Pareto minima. This approach provides a dynamical endogenous weighting of the objective functions, a key property for applications in cooperative games, inverse problems, and numerical multiobjective optimization.