A method of solving nonlinear variational problems by nonlinear transformation of the objective functional. Part II

Summary The method of transformation of the objective functional is extended to solve nonlinear variational problems with non-differentiable objective functionals. The method is applied to the Bingham flow problem.     

Some supplementary results on the 1+\sqrt 2 order method for the solution of nonlinear equations

Summary Recently an iterative method for the solution of systems of nonlinear equations having at leastR-order 1+ for simple roots has been investigated by the author [7]; this method uses as many function evaluations per step as the classical Newton method. In the present note we deal with several properties of the method such as monotone convergence, asymptotic inclusion of the solution and convergence in the case of multiple roots.     

Approximation of optimal distributed control problems governed by variational inequalities

Summary A method for approximating the optimal control and the optimal state for a class of distributed control problems governed by variational inequalities is given. It uses a Rayleigh-Ritz-Galerkin scheme, regularising techniques and a gradient algorithm. A numerical example is given.     

The nonlinear programming method of Wilson,Han, and Powell with an augmented Lagrangian type line search function

Summary The paper represents an outcome of an extensive comparative study of nonlinear optimization algorithms. This study indicates that quadratic approximation methods which are characterized by solving a sequence of quadratic subproblems recursively, belong to the most efficient and reliable nonlinear programming algorithms available at present. The purpose of this paper is to analyse the theoretical convergence properties and to investigate the numerical performance in more detail. In Part 1, the exactL ₁-penalty function of Han and Powell is replaced by a differentiable augmented Lagrange function for the line search computation to be able to prove the global convergence and to show that the steplength one is chosen in the neighbourhood of a solution. In Part 2, the quadratic subproblem is exchanged by a linear least squares problem to improve the efficiency, and to test the dependence of the performance from different solution methods for the quadratic or least squares subproblem.     

Numerical computation of branch points in nonlinear equations

Summary The numerical computation of branch points in systems of nonlinear equations is considered. A direct method is presented which requires the solution of one equation only. The branch points are indicated by suitable testfunctions. Numerical results of three examples are given.     

Optimal solution of nonlinear equations satisfying a Lipschitz condition

Summary For a given nonnegative we seek a pointx ^* such that |f(x ^*)| wheref is a nonlinear transformation of the cubeB=[0,1] ^m into (or ^p ,p>1) satisfying a Lipschitz condition with the constantK and having a zero inB.The information operator onf consists ofn values of arbitrary linear functionals which are computed adaptively. The pointx ^* is constructed by means of an algorithm which is a mapping depending on the information operator. We find an optimal algorithm, i.e., algorithm with the smallest error, which usesn function evaluations computed adaptively. We also exhibit nearly optimal information operators, i.e., the linear functionals for which the error of an optimal algorithm that uses them is almost minimal. Nearly optimal information operators consists ofn nonadaptive function evaluations at equispaced pointsx _j in the cubeB. This result exhibits the superiority of the T. Aird and J. Rice procedure ZSRCH (IMSL library [1]) over Sobol's approach [7] for solving nonlinear equations in our class of functions. We also prove that the simple search algorithm which yields a pointx ^*=x _k such that is nearly optimal. The complexity, i.e., the minimal cost of solving our problem is roughly equal to (K/) ^m .     

On the efficient solution of nonlinear finite element equations I

Summary On the efficient solution of nonlinear finite element equations. A fast numerical method is presented for the solution of nonlinear algebraic systems which arise from discretizations of elliptic boundary value problems. A simplified relaxation algorithm which needs no information about the Jacobian of the system is combined with a correspondingly modified conjugate gradient method. A global convergence proof is given and the number of operations required is compared with that of other algorithms which are equally applicable to a large class of problems. Numerical results verify the efficiency for some typical examples.     

Partitioned variable metric updates for large structured optimization problems

Summary This paper presents a minimization method based on the idea of partitioned updating of the Hessian matrix in the case where the objective function can be decomposed in a sum of convex element functions. This situation occurs in a large class of practical problems including nonlinear finite elements calculations. Some theoretical and algorithmic properties of the update are discussed and encouraging numerical results are presented.Work supported by a research grant of the Deutsche Forschungsgemeinschaft, Bonn, FRG     

Convergence of the multigrid full approximation scheme for a class of elliptic mildly nonlinear boundary value problems

Summary The multigrid full approximation scheme (FAS MG) is a well-known solver for nonlinear boundary value problems. In this paper we restrict ourselves to a class of second order elliptic mildly nonlinear problems and we give local conditions, e.g. a local Lipschitz condition on the derivative of the continuous operator, under which the FAS MG with suitably chosen parameters locally converges. We prove quantitative convergence statements and deduce explicit bounds for important quantities such as the radius of a ball of guaranteed convergence, the number of smoothings needed, the number of coarse grid corrections needed and the number of FAS MG iterations needed in a nested iteration. These bounds show well-known features of the FAS MG scheme.     

A pointwise quasi-Newton method for unconstrained optimal control problems

Summary For a class of unconstrained optimal control problems we propose a quasi-Newton method that exploits the structure of the problem. We define a new type of superlinear convergence for sequences in function spaces and prove superlinear convergence of the iterates generated by the quasi-Newton method in this sense.This author supported by NSF grants # DMS-8300841 and # DMS-8500844     

Chord techniques and Newton's method for discrete bifurcation problems

Summary The numerical treatment of discrete bifurcation problems (2) with chord methods or Newton's method is a question of constructing appropriate initial approximations to prevent the sequence from converging to the trivial solution. This problem is being discussed under conditions which are satisfied for quite a few examples arising in applications (see Sect. 3).     

Starlike domains of convergence for Newton's method at singularities

Summary Given a solutionx ^* of a system of nonlinear equationsf with singular Jacobian f(x ^*) we construct an open starlike domainR of initial points, from which Newton's method converges linearly tox ^*. Under certain conditions the union of those straight lines throughx ^*, that do not intersect withR is shown to form a closed set of measure zero, which is necessarily disjoint from any starlike domain of convergence. The results apply to first and higher order singularities.     

A projected Newton method for minimization problems with nonlinear inequality constraints

Summary Recently developed projected Newton methods for minimization problems in polyhedrons and Cartesian products of Euclidean balls are extended here to general convex feasible sets defined by finitely many smooth nonlinear inequalities. Iterate sequences generated by this scheme are shown to be locally superlinearly convergent to nonsingular extremals , and more specifically, to local minimizers satisfying the standard second order Kuhn-Tucker sufficient conditions; moreover, all such convergent iterate sequences eventually enter and remain within the smooth manifold defined by the active constraints at . Implementation issues are considered for large scale specially structured nonlinear programs, and in particular, for multistage discrete-time optimal control problems; in the latter case, overall per iteration computational costs will typically increase only linearly with the number of stages. Sample calculations are presented for nonlinear programs in a right circular cylinder in ³.Investigation supported by NSF Research Grant #DMS-85-03746     

A series method for solving nonlinear two-point boundary value problems

Summary A new method for solving nonlinear boundary value problems based on Taylor-type expansions generated by the use of Lie series is derived and applied to a set of test examples. A detailed discussion is given of the comparative performance of this method under various conditions. The method is of theoretical interest but is not applicable, in its present form, to real life problems; in particular, because of the algebraic complexity of the expressions involved, only scalar second order equations have been discussed, though in principle systems of equations could be similarly treated. A continuation procedure based on this method is suggested for future investigation.     

On the approximate solution of nonlinear variational inequalities

Summary Nonlinear locally coercive variational inequalities are considered and especially the minimal surface over an obstacle. Optimal or nearly optimal error estimates are proved for a direct discretization of the problem with linear finite elements on a regular triangulation of the not necessarily convex domain. It is shown that the solution may be computed by a globally convergent relaxation method. Some numerical results are presented.     

Algorithmes mixtes asynchrones. Etude de convergence monotone

Summary In this paper we introduce two classes of iterative algorithms which we call Asynchronous mixed algorithms and we study their convergence under partial ordering. These algorithms can be implemented just as well on monoprocessors as on multiprocessors, and, along with their convergence study, constitute a generalization of the mixed classical Newton-relaxation algorithms.

---

Résumé Nous introduisons dans cet article deux classes d'algorithmes itératifs que nous appelons «Algorithmes mixtes asynchrones» et nous en étudierons la convergence selon un ordre partiel. Ces algorithmes sont implémentables aussi bien sur les monoprocesseurs que sur les multiprocesseurs, et avec leur étude de convergence constituent une généralisation des algorithmes mixtes classiques «Newton-relaxation».

     

A generalized conjugate gradient algorithm for minimization

Summary A generalized conjugate gradient algorithm which is invariant to a nonlinear scaling of a strictly convex quadratic function is described, which terminates after at mostn steps when applied to scaled quadratic functionsf: R _n R₁ of the formf(x)=h(F(x)) withF(x) strictly convex quadratic andhC ¹ (R₁) an arbitrary strictly monotone functionh. The algorithm does not suppose the knowledge ofh orF but only off(x) and its gradientg(x).     

On the efficient solution of nonlinear finite element equations. II

Summary We consider nonlinear variational inequalities corresponding to a locally convex minimization problem with linear constraints of obstacle type. An efficient method for the solution of the discretized problem is obtained by combining a slightly modified projected SOR-Newton method with the projected version of thec g-accelerated relaxation method presented in a preceding paper. The first algorithm is used to approximately reach in relatively few steps the proper subspace of active constraints. In the second phase a Kuhn-Tucker point is found to prescribed accuracy. Global convergence is proved and some numerical results are presented.     

A parallel projection method for solving generalized linear least-squares problems

Summary A parallel projection algorithm is proposed to solve the generalized linear least-squares problem: find a vector to minimize the 2-norm distance from its image under an affine mapping to a closed convex cone. In each iteration of the algorithm the problem is decomposed into several independent small problems of finding projections onto subspaces, which are simple and can be tackled parallelly. The algorithm can be viewed as a dual version of the algorithm proposed by Han and Lou [8]. For the special problem under consideration, stronger convergence results are established. The algorithm is also related to the block iterative methods of Elfving [6], Dennis and Steihaug [5], and the primal-dual method of Springarn [14].This material is based on work supported in part by the National Science foundation under Grant DMS-8602416 and by the Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign     

On the relation between quadratic termination and convergence properties of minimization algorithms

Summary It is shown that the theory developed in part I of this paper [22] can be applied to some well-known minimization algorithms with the quadratic termination property to prove theirn-step quadratic convergence. In particular, some conjugate gradient methods, the rank-1-methods of Pearson and McCormick (see Pearson [18]) and the large class of rank-2-methods described by Oren and Luenberger [16, 17] are investigated.This work was supported in part at Stanford University, Stanford, California, under Energy Research and Development Administration, Contract E(04-3) 326 PA No. 30, and National Science Foundation Grant DCR 71-01996 A04 and in part by the Deutsche Forschungsgemeinschaft