Convergence of the Gauss-Newton method for convex composite optimization problems under majorant condition on Riemannian manifolds

In this paper, we consider convex composite optimization problems on Riemannian manifolds, and discuss the semi-local convergence of the Gauss-Newton method with quasi-regular initial point and under the majorant condition. As special cases, we also discuss the convergence of the sequence generated by the Gauss-Newton method under Lipschitz-type condition, or under γ-condition.     

A Memoryless Augmented Gauss-Newton Method for Nonlinear Least-Squares Problems

In this paper, we develop, analyze, and test a new algorithm for nonlinear least-squares problems. The algorithm uses a BFGS update of the Gauss-Newton Hessian when some heuristics indicate that the Gauss-Newton method may not make a good step. Some important elements are that the secant or quasi-Newton equations considered are not the obvious ones, and the method does not build up a Hessian approximation over several steps. The algorithm can be implemented easily as a modification of any Gauss-Newton code, and it seems to be useful for large residual problems.     

Efficient computation of the Gauss-Newton direction when fitting NURBS using ODR

We consider a subproblem in parameter estimation using the Gauss-Newton algorithm with regularization for NURBS curve fitting. The NURBS curve is fitted to a set of data points in least-squares sense, where the sum of squared orthogonal distances is minimized. Control-points and weights are estimated. The knot-vector and the degree of the NURBS curve are kept constant. In the Gauss-Newton algorithm, a search direction is obtained from a linear overdetermined system with a Jacobian and a residual vector. Because of the properties of our problem, the Jacobian has a particular sparse structure which is suitable for performing a splitting of variables. We are handling the computational problems and report the obtained accuracy using different methods, and the elapsed real computational time. The splitting of variables is a two times faster method than using plain normal equations.     

Conditional Stability Estimates for Ill-Posed PDE Problems by Using Interpolation

The focus of this article is on conditional stability estimates for ill-posed inverse problems in partial differential equations. Conditional stability estimates have been obtained in related literature by a couple different methods. In this article, we propose a method called interpolation method, which is based on interpolation in variable Hilbert scales. We provide the theoretical background of this method and show that optimal conditional stability estimates are obtained. The capabilities of our method are illustrated by a comprehensive collection of different inverse and ill-posed PDE problems containing elliptic and parabolic problems, one source problem and the problem of analytic continuation.     

Use of the Minimum-Norm Search Direction in a Nonmonotone Version of the Gauss-Newton Method

In this work, a new stabilization scheme for the Gauss-Newton method is defined, where the minimum norm solution of the linear least-squares problem is normally taken as search direction and the standard Gauss-Newton equation is suitably modified only at a subsequence of the iterates. Moreover, the stepsize is computed by means of a nonmonotone line search technique. The global convergence of the proposed algorithm model is proved under standard assumptions and the superlinear rate of convergence is ensured for the zero-residual case. A specific implementation algorithm is described, where the use of the pure Gauss-Newton iteration is conditioned to the progress made in the minimization process by controlling the stepsize. The results of a computational experimentation performed on a set of standard test problems are reported.     

The Incremental Gauss-Newton Algorithm with Adaptive Stepsize Rule

In this paper, we consider the Extended Kalman Filter (EKF) for solving nonlinear least squares problems. EKF is an incremental iterative method based on Gauss-Newton method that has nice convergence properties. Although EKF has the global convergence property under some conditions, the convergence rate is only sublinear under the same conditions. One of the reasons why EKF shows slow convergence is the lack of explicit stepsize. In the paper, we propose a stepsize rule for EKF and establish global convergence of the algorithm under the boundedness of the generated sequence and appropriate assumptions on the objective function. A notable feature of the stepsize rule is that the stepsize is kept greater than or equal to 1 at each iteration, and increases at a linear rate of k under an additional condition. Therefore, we can expect that the proposed method converges faster than the original EKF. We report some numerical results, which demonstrate that the proposed method is promising.     

Local convergence analysis of inexact Gauss-Newton like methods under majorant condition

In this paper, we present a local convergence analysis of inexact Gauss-Newton like methods for solving nonlinear least squares problems. Under the hypothesis that the derivative of the function associated with the least squares problem satisfies a majorant condition, we obtain that the method is well-defined and converges. Our analysis provides a clear relationship between the majorant function and the function associated with the least squares problem. It also allows us to obtain an estimate of convergence ball for inexact Gauss-Newton like methods and some important, special cases.     

Approximate solution methods in mechanics analysis of a class of nonlinear seepage problems by a finite-element method

We analyze the nonlinear boundary-value problem of seepage under a subsurface hydrotechnical construction over an inclined rectilinear aquifer. The method of inverse boundary-value problems is applied, using the velocity hodograph plane in which the original problem is reduced to a linear problem. The linear problem is solved in the general case using the finite-element method. A computer program realizing the proposed algorithms has been developed. We have used this program to run a series of numerical experiments, reaching certain conclusions about the behavior of the main seepage characteristics.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 55, pp. 75–80, 1985.     

A Truncated Nonmonotone Gauss-Newton Method for Large-Scale Nonlinear Least-Squares Problems

In this paper, a Gauss-Newton method is proposed for the solution of large-scale nonlinear least-squares problems, by introducing a truncation strategy in the method presented in [9]. First, sufficient conditions are established for ensuring the convergence of an iterative method employing a truncation scheme for computing the search direction, as approximate solution of a Gauss-Newton type equation. Then, a specific truncated Gauss-Newton algorithm is described, whose global convergence is ensured under standard assumptions, together with the superlinear convergence rate in the zero-residual case. The results of a computational experimentation on a set of standard test problems are reported.     

Study of optimal control problems on the half-line by the averaging method

We justify the application of the averaging method to optimal control problems for systems of differential equations on the half-line. For optimal control problems for systems of differential equations linear in the control, we prove the existence of optimal controls for the exact and averaged problems. We show that an optimal control in the averaged problem is ɛ-optimal in the exact problem.     

Local analysis of a spectral correction for the Gauss-Newton model applied to quadratic residual problems

A simple spectral correction for the Gauss-Newton model applied to nonlinear least squares problems is presented. Such a correction consists in adding a sign-free multiple of the identity to the Hessian of the Gauss-Newton model, being the multiple based on spectral approximations for the Hessians of the residual functions. A detailed local convergence analysis is provided for the resulting method applied to the class of quadratic residual problems. Under mild assumptions, the proposed method is proved to be convergent for problems for which the convergence of the Gauss-Newton method might not be ensured. Moreover, the rate of linear convergence is proved to be better than the Gauss-Newton’s one for a class of non-zero residue problems. These theoretical results are illustrated by numerical examples with quadratic and non-quadratic residual problems.     

On convergence of the Gauss-Newton method for convex composite optimization

The local quadratic convergence of the Gauss-Newton method for convex composite optimization f=h∘F is established for any convex function h with the minima set C, extending Burke and Ferris’ results in the case when C is a set of weak sharp minima for h. Received: July 24, 1998 / Accepted: November 29, 2000?Published online September 3, 2001     

Nonlinear nonaxisymmetric deformation of composite shells of revolution

We discuss the results of the determination of the stress and displacement fields in nonaxisymmetrically loaded nonlinear-elastic shells of revolution. The original nonlinear system of equations is linearized in accordance with the method of variation of elastic parameters. The two-dimensional linear boundary-value problem is reduced to a sequence of one-dimensional problems, which are solved using a numerical method. We carry out an analysis of the stress-strain state of a conical shell made of a composite material of granular structure. Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, No. 37, 1994, pp. 80–83.     

Matrix decomposition algorithms for elliptic boundary value problems: a survey

We provide an overview of matrix decomposition algorithms (MDAs) for the solution of systems of linear equations arising when various discretization techniques are applied in the numerical solution of certain separable elliptic boundary value problems in the unit square. An MDA is a direct method which reduces the algebraic problem to one of solving a set of independent one-dimensional problems which are generally banded, block tridiagonal, or almost block diagonal. Often, fast Fourier transforms (FFTs) can be employed in an MDA with a resulting computational cost of O(N ² logN) on an N × N uniform partition of the unit square. To formulate MDAs, we require knowledge of the eigenvalues and eigenvectors of matrices arising in corresponding two–point boundary value problems in one space dimension. In many important cases, these eigensystems are known explicitly, while in others, they must be computed. The first MDAs were formulated almost fifty years ago, for finite difference methods. Herein, we discuss more recent developments in the formulation and application of MDAs in spline collocation, finite element Galerkin and spectral methods, and the method of fundamental solutions. For ease of exposition, we focus primarily on the Dirichlet problem for Poisson’s equation in the unit square, sketch extensions to other boundary conditions and to more involved elliptic problems, including the biharmonic Dirichlet problem, and report extensions to three dimensional problems in a cube. MDAs have also been used extensively as preconditioners in iterative methods for solving linear systems arising from discretizations of non-separable boundary value problems.     

Linear versus Non-Linear Acquisition of Step-Functions

We address in this article the following two closely related problems. 1. How to represent functions with singularities (up to a prescribed accuracy) in a compact way. 2. How to reconstruct such functions from a small number of measurements. The stress is on a comparison of linear and non-linear approaches. As a model case, we use piecewise-constant functions on [0,1], in particular, the Heaviside jump function ℋ _t =χ _[0,t]. Considered as a curve in the Hilbert space L ²([0,1]) it is completely characterized by the fact that any two its disjoint chords are orthogonal. We reinterpret this fact in a context of step-functions in one or two variables. Next, we study the limitations on representability and reconstruction of piecewise-constant functions by linear and semi-linear methods. Our main tools in this problem are Kolmogorov’s n-width and ε-entropy, as well as Temlyakov’s (N,m)-width. On the positive side, we show that a very accurate non-linear reconstruction is possible. It goes through a solution of certain specific non-linear systems of algebraic equations. We discuss the form of these systems and methods of their solution, stressing their relation to Moment Theory and Complex Analysis. Finally, we informally discuss two problems in Computer Imaging which are parallel to problems 1 and 2 above: compression of still images and video-sequences on one side, and image reconstruction from indirect measurement (for example, in Computer Tomography), on the other. This research was supported by the ISF, Grant No. 304/05, and by the Minerva Foundation.     

Convergence analysis of a proximal Gauss-Newton method

An extension of the Gauss-Newton algorithm is proposed to find local minimizers of penalized nonlinear least squares problems, under generalized Lipschitz assumptions. Convergence results of local type are obtained, as well as an estimate of the radius of the convergence ball. Some applications for solving constrained nonlinear equations are discussed and the numerical performance of the method is assessed on some significant test problems.     

Inverse problem of groundwater modeling by iteratively regularized Gauss-Newton method with a nonlinear regularization term

A nonlinear minimization problem ‖F(d)−u‖?min, ‖u−u_δ‖≤δ, is a typical mathematical model of various applied inverse problems. In order to solve this problem numerically in the lack of regularity, we introduce iteratively regularized Gauss-Newton procedure with a nonlinear regularization term (IRGN-NRT). The new algorithm combines two very powerful features: iterative regularization and the most general stabilizing term that can be updated at every step of the iterative process. The convergence analysis is carried out in the presence of noise in the data and in the modified source condition. Numerical simulations for a parameter identification ill-posed problem arising in groundwater modeling demonstrate the efficiency of the proposed method.     

A multiplicative Gauss-Newton minimization algorithm:Theory and application to exponential functions

Multiplicative calculus(MUC) measures the rate of change of function in terms of ratios, which makes the exponential functions significantly linear in the framework of MUC.Therefore, a generally non-linear optimization problem containing exponential functions becomes a linear problem in MUC. Taking this as motivation, this paper lays mathematical foundation of well-known classical Gauss-Newton minimization(CGNM) algorithm in the framework of MUC. This paper formulates the mathematical derivation of proposed method named as multiplicative Gauss-Newton minimization(MGNM) method along with its convergence properties.The proposed method is generalized for n number of variables, and all its theoretical concepts are authenticated by simulation results. Two case studies have been conducted incorporating multiplicatively-linear and non-linear exponential functions. From simulation results, it has been observed that proposed MGNM method converges for 12972 points, out of 19600 points considered while optimizing multiplicatively-linear exponential function, whereas CGNM and multiplicative Newton minimization methods converge for only 2111 and 9922 points, respectively. Furthermore, for a given set of initial value, the proposed MGNM converges only after 2 iterations as compared to 5 iterations taken by other methods. A similar pattern is observed for multiplicatively-non-linear exponential function. Therefore, it can be said that proposed method converges faster and for large range of initial values as compared to conventional methods.     

Approximate Gauss-Newton Method for Robust Parameter Estimation

We consider robust parameter estimation problems in which either the l1 norm or the Huber function of a measurement error vector used as cost functionals. In order to avoid high computational effort of computing exact derivatives needed for the solution of these problems with the Gauss-Newton method, we suggest to use approximations of the derivatives in the occurring linearized subproblems. We show how the error introduced by using only approximated derivatives can be compensated by adding a correction term to the objective function of the linearized problems. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Solvability of Cauchy Problem for a Differential-Algebraic System with Concentrated Delay

We study the Cauchy problem for a linear differential-algebraic system of equations with concentrated delay. Our research continues investigation of solvability of linear Noether boundary value problems for systems of functional-differential equations given in the monographs by A.D. Myshkis, N.V. Azbelev, V.P. Maksimov, L.F. Rakhmatullina, A.M. Samoilenko, and A.A. Boichuk; meanwhile, we use essentially the tool of Moore-Penrose inverse matrices. For a linear differential-algebraic system with concentrated delay, we find sufficient conditions for its solvability and give a construction of generalized Green’s operator for Cauchy’s problem. We also give some examples which illustrate in detail the solvability conditions and the suggested construction.