On the convergence rate for a penalty function method of exponential type

Recently, Kort and Bertsekas (Ref. 1) and Hartman (Ref. 2) presented independently a new penalty function algorithm of exponential type for solving inequality-constrained minimization problems. The main purpose of this work is to give a proof on the rate of convergence of a modification of the exponential penalty method proposed by these authors. We show that the sequence of points generated by the modified algorithm converges to the solution of the original nonconvex problem linearly and that the sequence of estimates of the optimal Lagrange multiplier converges to this multiplier superlinearly. The question of convergence of the modified method is discussed. The present paper hinges on ideas of Mangasarian (Ref. 3), but the case considered here is not covered by Mangasarian's theory.     

Convergence analysis of a proximal newton method 1

Recently Fukushima and Qi proposed a proximal Newton method for minimizating a nonsmooth convex function. An alternative global convergence proof for that method is presented in this paper. Global convergence was established without any additional assumption on the objective function. We also show that the infimum of a convex function is always equal to the infimun of its Moreau—Yosida regularization     

Some weak and strong laws of large numbers for D[0,1]-valued random variables

Pointwise Weak Law of Large Numbers and Weak Law of Large Numbers in the norm topology of D[0,l] are shown to be equivalent under uniform convex tightness and uniform integrability conditions for weighted sums of a sequence of random elements in D[0,1]. Uniform convex tightness and uniform integrability conditions are jointly characterized. Marcinkiewicz–Zygmund–Kolmogorov's and Brunk– Chung's Strong Laws of Large Numbers are derived in the setting of D[0,l]-space under uniform convex tightness and uniform integrability conditions. Equivalence of pointwise convergence, convergence in the Skorokhod topology and convergence in the norm topology f o r sequences in D[0,l] is studied     

度量投影的收敛性（英文）

讨论了赋范空间中度量投影的收敛性．得到了在局部紧集控制下，Chebyshev凸集序列的度量投影的收敛性与K－M收敛，Wijsman收敛和Kuratowski收敛都等价．本文的结论完善了M．Tsukada在[1]和[2]结果．     

Computing the region of convergence for power series in many real variables: A ratio-like test

We give an elementary proof that the region of convergence for a power series in many real variables is a star-convex domain but not, in general, a convex domain. In doing so, we deduce a natural higher-dimensional analog of the so-called ratio test from univariate power series. From the constructive proof of this result, we arrive at a method to approximate the region of convergence up to a desired accuracy. While most results in the literature are for rather specialized classes of multivariate power series, the method devised here is general. As far as applications are concerned, note that while theorems such as the Cauchy-Kowalevski theorem (and its generalizations to many variables) grant the existence of a region of convergence for a multivariate Taylor series to certain PDEs under appropriate restrictions, they do not give the actual region of convergence. The determination of the maximal region of convergence for such a series solution to a PDE is one application of our result.     

Kepler equation and accelerated Newton method

We study the efficiency of the accelerated Newton method (Garlach, SIAM Rev. 36 (1994) 272–276) for several orders of convergence versus Danby's method for the resolution of Kepler's equation; we find that the cited method of order three is competitive with Danby's method and the classical Newton's method. We also generalize the accelerated Newton method for the resolution of system of algebraic equations, obtaining a formula of order three and a proof of its convergence; its application to several examples shows that its efficiency is greater than Newton's method.     

Über Die Konvergenz von Einzelschrittverfahren zur Minimierung konvexer Funktionen

A first convergence proof for free steering minimization methods was given by SCHECHTER [3]. The function f to be minimized was assumed by him to be twice continously differentiable and strictly convex. These conditions were weakened by ELKIN [1], who considered continously differentiable and uniformly convex functions and who employed a slight modification of SCHECHTER's convergence proof. The following article gives a new proof for convergence of free steering methods. We assume f to be strictly convex and continously differentiable.

---

---

Aus Kap. I 1. der Dissertation des Verfassers [2].     

A first order method for finding minimal norm-like solutions of convex optimization problems

We consider a general class of convex optimization problems in which one seeks to minimize a strongly convex function over a closed and convex set which is by itself an optimal set of another convex problem. We introduce a gradient-based method, called the minimal norm gradient method, for solving this class of problems, and establish the convergence of the sequence generated by the algorithm as well as a rate of convergence of the sequence of function values. The paper ends with several illustrating numerical examples.     

A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets

The method of projections onto convex sets to find a point in the intersection of a finite number of closed convex sets in a Euclidean space, may lead to slow convergence of the constructed sequence when that sequence enters some narrow “corridor” between two or more convex sets. A way to leave such corridor consists in taking a big step at different moments during the iteration, because in that way the monotoneous behaviour that is responsible for the slow convergence may be interrupted. In this paper we present a technique that may introduce interruption of the monotony for a sequential algorithm, but that at the same time guarantees convergence of the constructed sequence to a point in the intersection of the sets. We compare experimentally the behaviour concerning the speed of convergence of the new algorithm with that of an existing monotoneous algorithm.     

Spectral collocation and waveform relaxation methods for nonlinear delay partial differential equations

We investigate Chebyshev spectral collocation and waveform relaxation methods for nonlinear delay partial differential equations. Waveform relaxation methods allow to replace the system of nonlinear differential equations resulting from the application of spectral collocation methods by a sequence of linear problems which can be effectively integrated in a parallel computing environment by highly stable implicit methods. The effectiveness of this approach is illustrated by numerical experiments on the Hutchinson's equation. The boundedness of waveform relaxation iterations is proved for the Hutchinson's equation. This result is used in the proof of the superlinear convergence of the iterations.     

Convergence of a continuation method under the Hölder condition of the first derivative

The aim of this paper is to describe a continuation method combining the Chebyshev’s method and the convex acceleration of Newton’s method to solve nonlinear equations in Banach spaces. The semilocal convergence analysis of the method is established using recurrence relations under the assumption that the first Fréchet derivative satisfies the Hölder continuity condition. This condition is milder than the usual Lipschitz condition. The computation of second Fréchet derivative is also avoided. Two real valued functions and a real sequence are used to establish a convergence criterion of R-order (1+p), where p∈(0,1] is the order of the Hölder condition. An existence and uniqueness theorem along with the closed form of error bounds is derived in terms of a real parameter α∈[0,1]. Two numerical examples are worked out to demonstrate the efficacy of our convergence analysis. For both the examples, the convergence conditions hold for the Chebyshev’s method (α=0). However, for the convex acceleration of Newton’s method (α=1), these convergence conditions hold for the first example but fail for the second example. For particular values of α, our method reduces to the Chebyshev’s method (α=0) and the convex acceleration of Newton’s method (α=1).     

On Schwarz Alternating Methods for the Subsonic Full Potential Equation

The Schwarz alternating method can be used to solve elliptic boundary value problems on domains which consist of two or more overlapping subdomains. The solution is approximated by an infinite sequence of functions which results from solving a sequence of elliptic boundary value problems in each of the subdomains. The full potential equation is derived from the Navier–Stokes equations assuming the fluid is compressible, inviscid, irrotational and isentropic. It is being used by the aircraft industry to model flow over an airfoil or even an entire aircraft. This paper shows that the additive and multiplicative versions of the Schwarz alternating method, when applied to the full potential equation in three dimensions, converge to the true solution geometrically. The assumptions are that the initial guess and the true solution are everywhere subsonic. We use the convergence proof by Tai and Xu and modify it for certain closed convex subsets.     

均衡及约束凸优化问题公共解的一般迭代算法

梯度投影法在解决约束凸极小化问题中起到了重要的作用. 基于Tian的一般迭代算法, 本文将梯度投影法和平均算子方法相结合, 首次提出隐式和显式的复合迭代算法, 寻求均衡问题和约束凸极小化问题的公共解. 在适当条件下, 获得了强收敛定理.     

A formalization of Sambins's normalization for GL

Sambin [6] proved the normalization theorem (Hauptsatz) for GL, the modal logic of provability, in a sequent calculus version called by him GLS. His proof does not take into account the concept of reduction, commonly used in normalization proofs. Bellini [1], on the other hand, gave a normalization proof for GL using reductions. Indeed, Sambin's proof is a decision procedure which builds cut-free proofs. In this work we formalize this procedure as a recursive function and prove its recursiveness in an arithmetically formalizable way, concluding that the normalization of GL can be formalized in PA. MSC: 03F05, 03B35, 03B45.     

Finite Convergence of the Partial Inverse Algorithm

In Refs. 1–2, Lefebvre and Michelot proved the finite convergence of the partial inverse algorithm applied to a polyhedral convex function by means of some suitable tools of convex analysis. They obtained their result under some assumptions on the primal and dual solution sets. The aim of this note is to show that the proof can be extended to remove the nasty assumption on the dual solution set. The result is in conformity with the proof given in Ref. 3, which has been obtained using the concept of folding.     

Minimization of some non-differentiable functionals by the Augmented Lagrangian Method of Hestenes and Powell

The Augmented Lagrangian Method of Hestenes and Powell is presented here in a more general case, including Fenchel's duality, using some recent results of R. T. Rockafellar which are here extended. It is shown that for some functionals which contain a non-differentiable term which is the support function of a convex set, the Augmented Lagrangian Method provides a natural way to marry standard duality techniques and regularisation techniques. An application to visco-plastic flows is presented and numerical results are given. A convergence proof is given for the algorithm used. Another application to elasto-plastic torsion is also signaled.     

Quadratic Convergence of Newton's Method for Convex Interpolation and Smoothing

Abstract. In this paper, we prove that Newton's method for convex best interpolation is locally quadratically convergent, giving an answer to a question of Irvine, Marin, and Smith [7] and strengthening a result of Andersson and Elfving [1] and our previous work [5]. A damped Newton-type method is presented which has global quadratic convergence. Analogous results are obtained for the convex smoothing problem. Numerical examples are presented.     

Dykstras algorithm with bregman projections: A convergence proof

Dykstra’s algorithm and the method of cyclic Bregman projections are often employed to solve best approximation and convex feasibility problems, which are fundamental in mathematics and the physical sciences. Censor and Reich very recently suggested a synthesis of these methods, Dykstra’s algorithm with Bregman projections, to tackle a non-orthogonal best approximation problem, They obtained convergence when each constraint is a halfspace. It is shown here that this new algorithm works for general closed convex constraints; this complements Censor and Reich’s result and relates to a framework by Tseng. The proof rests on Boyle and Dykstra’s original work and on strong properties of Bregman distances corresponding to Legendre functions. Special cases and observations simplifying the implementation of the algorithm are aiso discussed     

Decomposition theorems

The countable-decomposition theorem for linear functionals has become a useful tool in the theory of representing measures (see [4–7]). The original proof of this theorem was based on a rather involved study of extreme points in the state space of a convex cone. Recently M. Neumann [9] gave an independent proof using a refined form of Simons convergence lemma and Choquet's theorem. In this paper a (relatively) short proof of an extension (to a more abstract situation) of the countable-decomposition theorem is given. Furthermore a decomposition criterion is obtained which even works in the case when not all states are decomposable. All the work is based on a complete characterization of those states which are partially decomposable with respect to a given sequence of sublinear functionals.     

Fixed-point theorems for set-valued mappings and existence of best approximants

The paper gives a proof of the following existence result in best approximation. Let M be a compact, convex, and non-empty subset of a normed space E and let g be a continuous almost affine mapping of M onto M. For each continuous mapping f from M into E there exists a point x in M such that g(x) is a best M- approximation to f(x). The proof uses Bohnenblust and Karlin's extension to normed spaces of Kakutani's Fixed Point Theorem for set-valued mappings on compact, convex, and non-empty subsets of Euclidean n-space.