求解凸规划及鞍点问题定制的PPA 算法及其收敛速率

线性约束的凸优化问题和鞍点问题的一阶最优性条件是一个单调变分不等式. 在变分不等式框架下求解这些问题, 选取适当的矩阵G, 采用G- 模下的PPA 算法, 会使迭代过程中的子问题求解变得相当容易. 本文证明这类定制的PPA 算法的误差界有1/k 的收敛速率.     

Quadratic estimates for the number of integer points in convex bodies

We give bounds for the mean square deviation with respect to arbitrary probability measures of the number of integer points in translated or dilated convex bodies. The proofs are based on Fourier analytic methods.     

On the convergence of a class of outer approximation algorithms for convex programs

This paper presents a new class of outer approximation methods for solving general convex programs. The methods solve at each iteration a subproblem whose constraints contain the feasible set of the original problem. Moreover, the methods employ quadratic objective functions in the subproblems by adding a simple quadratic term to the objective function of the original problem, while other outer approximation methods usually use the original objective function itself throughout the iterations. By this modification, convergence of the methods can be proved under mild conditions. Furthermore, it is shown that generalized versions of the cut construction schemes in Kelley-Cheney-Goldstein's cutting plane method and Veinott's supporting hyperplane method can be incorporated with the present methods and a cut generated at each iteration need not be retained in the succeeding iterations.     

The central limit problem for convex bodies

It is shown that every symmetric convex body which satisfies a kind of weak law of large numbers has the property that almost all its marginal distributions are approximately Gaussian. Several quite broad classes of bodies are shown to satisfy the condition.

     

Proximal point algorithms for solving convex minimization problem and common fixed points problem of asymptotically quasi-nonexpansive mappings in CAT(0) spaces with convergence analysis

In this paper, we introduce the modified proximal point algorithm for common fixed points of asymptotically quasi-nonexpansive mappings in CAT(0) spaces and also prove some convergence theorems of the proposed algorithm to a common fixed point of asymptotically quasi-nonexpansive mappings and a minimizer of a convex function. The main results in this paper improve and generalize the corresponding results given by some authors. Moreover, we then give numerical examples to illustrate and show efficiency of the proposed algorithm for supporting our main results.     

Incomplete projection algorithms for solving the convex feasibility problem

We present a general scheme for solving the convex feasibility problem and prove its convergence under mild conditions. Unlike previous schemes no exact projections are required. Moreover, we also introduce an acceleration factor, which we denote as the factor, that seems to play a fundamental role to improve the quality of convergence. Numerical tests on systems of linear inequalities randomly generated give impressive results in a multi-processing environment. The speedup is superlinear in some cases. New acceleration techniques are proposed, but no tests are reported here. As a by-product we obtain the rather surprising result that the relaxation factor, usually confined to the interval (0,2), gives better convergence results for values outside this interval.     

Linear convergence rates for extrapolated fixed point algorithms

ABSTRACT

We establish linear convergence rates for a certain class of extrapolated fixed point algorithms which are based on dynamic string-averaging methods in a real Hilbert space. This applies, in particular, to the extrapolated simultaneous and cyclic cutter methods. Our analysis covers the cases of both metric and subgradient projections.     

Generalizations of the Busemann-Petty problem for sections of convex bodies

We present generalizations of the Busemann-Petty problem for dual volumes of intermediate central sections of symmetric convex bodies. It is proved that the answer is negative when the dimension of the sections is greater than or equal to 4. For two- three-dimensional sections, both negative and positive answers are given depending on the orders of dual volumes involved, and certain cases remain open. For bodies of revolution, a complete solution is obtained in all dimensions.     

An exterior point method for the convex programming problem

This paper gives a proof of convergence of an iterative method for maximizing a concave function subject to inequality constraints involving convex functions. The linear programming problem is an important special case. The primary feature is that each iteration is very simple computationally, involving only one of the constraints. Although the paper is theoretical in nature, some numerical results are included.The author wishes to express his gratitude to Ms. A. Dunham, who provided a great deal of assistance in carrying out the computations presented in this paper.     

A convergence analysis result for constrained convex minimization problem

Abstract

Our purpose in this paper is to obtain strong convergence result for approximation of solution to constrained convex minimization problem using a new iterative scheme in a real Hilbert space. Furthermore, we give numerical analysis of our iterative scheme.     

Sections of convex bodies and splitting problem for selections

Let and be any convex-valued lower semicontinuous mappings and let be any linear surjection. The splitting problem is the problem of representation of any continuous selection f of the composite mapping L(F₁;F₂) in the form f=L(f₁;f₂), where f₁ and f₂ are some continuous selections of F₁ and F₂, respectively. We prove that the splitting problem always admits an approximate solution with fi being an ε-selection (Theorem 2.1). We also propose a special case of finding exact splittings, whose occurrence is stable with respect to continuous variations of the data (Theorem 3.1) and we show that, in general, exact splittings do not exist even for the finite-dimensional range.     

Improving the convergence of non-interior point algorithms for nonlinear complementarity problems

Recently, based upon the Chen-Harker-Kanzow-Smale smoothing function and the trajectory and the neighbourhood techniques, Hotta and Yoshise proposed a noninterior point algorithm for solving the nonlinear complementarity problem. Their algorithm is globally convergent under a relatively mild condition. In this paper, we modify their algorithm and combine it with the superlinear convergence theory for nonlinear equations. We provide a globally linearly convergent result for a slightly updated version of the Hotta-Yoshise algorithm and show that a further modified Hotta-Yoshise algorithm is globally and superlinearly convergent, with a convergence -order , under suitable conditions, where is an additional parameter.

     

Rate of convergence for proximal point algorithms on Hadamard manifolds

In this paper, an estimate of convergence rate concerned with an inexact proximal point algorithm for the singularity of maximal monotone vector fields on Hadamard manifolds is discussed. We introduce a weaker growth condition, which is an extension of that of Luque from Euclidean spaces to Hadamard manifolds. Under the growth condition, we prove that the inexact proximal point algorithm has linear/superlinear convergence rate. The main results presented in this paper generalize and improve some corresponding known results.     

On finite convergence of proximal point algorithms for variational inequalities

In this paper, we first characterize finite convergence of an arbitrary iterative algorithm for solving the variational inequality problem (VIP), where the finite convergence means that the algorithm can find an exact solution of the problem in a finite number of iterations. By using this result, we obtain that the well-known proximal point algorithm possesses finite convergence if the solution set of VIP is weakly sharp. As an extension, we show finite convergence of the inertial proximal method for solving the general variational inequality problem under the condition of weak g-sharpness.     

Exterior point algorithms for nearest points and convex quadratic programs

We consider the problem of finding the nearest point (by Euclidean distance) in a simplicial cone to a given point, and develop an exterior penalty algorithm for it. Each iteration in the algorithm consists of a single Newton step following a reduction in the value of the penalty parameter. Proofs of convergence of the algorithm are given. Various other versions of exterior penalty algorithms for nearest point problems in nonsimplicial polyhedral cones and for convex quadratic programs, all based on a single descent step following a reduction in the value of the penalty parameter per iteration, are discussed. The performance of these algorithms in large scale computational experiments is very encouraging. It shows that the number of iterations grows very slowly, if at all, with the dimension of the problem.Partially supported by NSF Grant No. ECS-8521183, and by the two universities.     

Strong convergence of projection algorithms for a family of relatively quasi-nonexpansive mappings and an equilibrium problem in Banach spaces

In this article, we introduce two kinds of new hybrid projection algorithms for finding a common element of the set of solutions of an equilibrium problem and the set of common fixed points of an infinitely countable family of relatively quasi-nonexpansive mappings in a Banach space. Our main results improve and extend the result obtained by Martinez-Yanes and Xu [Strong convergence of the CQ method for fixed point iteration processes, Nonlinear Anal. 64 (2006), pp. 2400–2411] and the corresponding results.     

On convergence criteria of generalized proximal point algorithms

We analyze some generalized proximal point algorithms which include the previously known proximal point algorithms as special cases. Weak and strong convergence of the proposed proximal point algorithms are proved under some mild conditions.     

Modified Busemann-Petty problem on sections of convex bodies

The Busemann-Petty problem asks whether convex origin-symmetric bodies in ℝ ⁿ with smaller central hyperplane sections necessarily have smallern-dimensional volume. It is known that the answer is affirmative ifn≤4 and negative ifn≥5. In this article we replace the assumptions of the original Busemann-Petty problem by certain conditions on the volumes of central hyperplane sections so that the answer becomes affirmative in all dimensions. The first-named author was supported in part by the NSF grant DMS-0136022 and by a grant from the University of Missouri Research Board.