Asymptotic behavior of solutions to the Monge--Ampère equations with slow convergence rate at infinity
0
Citation
0
Reference
10
Related Paper
Abstract:
We consider the asymptotic behavior of solutions to the Monge--Amp\`ere equations with slow convergence rate at infinity and fulfill previous results under faster convergence rate by Bao--Li--Zhang [Calc. Var PDE. 52(2015). pp. 39-63]. Different from known results, we obtain the limit of Hessian and/or gradient of solution at infinity relying on the convergence rate. The basic idea is to use a revised level set method, the spherical harmonic expansion and the iteration method.Keywords:
Infinity
Hessian matrix
Harmonic
Asymptotic expansion
Hessian matrix
Quasi-Newton method
Iterated function
Rank (graph theory)
Sequence (biology)
Matrix (chemical analysis)
Cite
Citations (215)
Cubic-regularized Newton's method (CR) is a popular algorithm that guarantees to produce a second-order stationary solution for solving nonconvex optimization problems. However, existing understandings of the convergence rate of CR are conditioned on special types of geometrical properties of the objective function. In this paper, we explore the asymptotic convergence rate of CR by exploiting the ubiquitous Kurdyka-Lojasiewicz (KL) property of nonconvex objective functions. In specific, we characterize the asymptotic convergence rate of various types of optimality measures for CR including function value gap, variable distance gap, gradient norm and least eigenvalue of the Hessian matrix. Our results fully characterize the diverse convergence behaviors of these optimality measures in the full parameter regime of the KL property. Moreover, we show that the obtained asymptotic convergence rates of CR are order-wise faster than those of first-order gradient descent algorithms under the KL property.
Hessian matrix
Regularization
Cite
Citations (3)
The authors show in this chapter, two different approaches for efficiently estimating the second-order derivatives (Hessian matrix) of a given objective function. The cost of evaluating the Hessian using classical finite difference approach is O(n2) where n is the number of parameters. The first adjoint approach reduces the cost of estimating all components of the Hessian matrix to only 2n extra simulations. This approach is simple, and it uses the algorithms developed in previous chapters. A second approach for estimating the complete Hessian is also presented. This approach is more complex than the first approach and requires extra memory storage. This approach requires only n + 1 extra simulations per Hessian evaluation. It follows that the computational cost is approximately one half of the first adjoint approach. This saving comes at the cost of a more complex algorithm and more extensive storage.
Hessian matrix
Hessian equation
Matrix (chemical analysis)
Cite
Citations (0)
In this paper, we introduce a Homogeneous Second-Order Descent Method (HSODM) using the homogenized quadratic approximation to the original function. The merit of homogenization is that only the leftmost eigenvector of a gradient-Hessian integrated matrix is computed at each iteration. Therefore, the algorithm is a single-loop method that does not need to switch to other sophisticated algorithms, and is easy to be implemented. We show that HSODM has a global convergence rate of $O(\epsilon^{-3/2})$ to find an $\epsilon$-approximate second-order stationary point, and has a local quadratic convergence rate under the standard assumptions. The numerical results demonstrate the advantage of the proposed method over other second-order methods.
Hessian matrix
Stationary point
Homogenization
Matrix (chemical analysis)
Descent direction
Cite
Citations (0)
Hessian matrix
Hessian equation
Quasi-Newton method
Matrix (chemical analysis)
Constant (computer programming)
Cite
Citations (2)
Non-asymptotic analysis of quasi-Newton methods have gained traction recently. In particular, several works have established a non-asymptotic superlinear rate of $\mathcal{O}((1/\sqrt{t})^t)$ for the (classic) BFGS method by exploiting the fact that its error of Newton direction approximation approaches zero. Moreover, a greedy variant of BFGS was recently proposed which accelerates its convergence by directly approximating the Hessian, instead of the Newton direction, and achieves a fast local quadratic convergence rate. Alas, the local quadratic convergence of Greedy-BFGS requires way more updates compared to the number of iterations that BFGS requires for a local superlinear rate. This is due to the fact that in Greedy-BFGS the Hessian is directly approximated and the Newton direction approximation may not be as accurate as the one for BFGS. In this paper, we close this gap and present a novel BFGS method that has the best of both worlds in that it leverages the approximation ideas of both BFGS and Greedy-BFGS to properly approximate the Newton direction and the Hessian matrix simultaneously. Our theoretical results show that our method out-performs both BFGS and Greedy-BFGS in terms of convergence rate, while it reaches its quadratic convergence rate with fewer steps compared to Greedy-BFGS. Numerical experiments on various datasets also confirm our theoretical findings.
Hessian matrix
Broyden–Fletcher–Goldfarb–Shanno algorithm
Quasi-Newton method
Cite
Citations (0)
The paper proposes a modification to the simultaneous perturbation stochastic approximation (SPSA) methods based on comparisons made between the first order and the second order SPSA (1SPSA and 2SPSA) algorithms from the perspective of loss function Hessian. At finite iterations, the convergence rate depends on matrix conditioning of the loss function Hessian. It is shown that 2SPSA converges more slowly for a loss function with an M-conditioned Hessian than the one with a well-conditioned Hessian. On the other hand, the convergence rate of 1SPSA is less sensitive to the matrix conditioning of loss function Hessians. The modified 2SPSA (M2SPSA) eliminates the error amplification caused by the inversion of an ill-conditioned Hessian at finite iterations which leads to significant improvements in its convergence rate in problems with an ill-conditioned Hessian matrix. Asymptotically, the efficiency analysis shows that M2SPSA is also superior to 2SPSA in terms of its convergence rate coefficients. It is shown that for the same asymptotic convergence rate, the ratio of the mean square errors for M2SPSA to 2SPSA is always less than one except for a perfectly conditioned Hessian.
Hessian matrix
Hessian equation
Matrix (chemical analysis)
Cite
Citations (0)
The tracking algorithm presented in this paper is based on minimizing the sum-of-squared-difference between a given template and the current image. Theoretically, amongst all standard minimization algorithms, the Newton method has the highest local convergence rate since it is based on a second-order Taylor series of the sum-of-squared-differences. However, the Newton method is time consuming since it needs the computation of the Hessian. In addition, if the Hessian is not positive definite, convergence problems can occur. That is why several methods use an approximation of the Hessian. The price to pay is the loss of the high convergence rate. The aim of this paper is to propose a tracking algorithm based on a second-order minimization method which does not need to compute the Hessian.
Hessian matrix
Minification
Quasi-Newton method
Cite
Citations (268)
In this paper, we present a family of generally applicable schemes for updating the Hessian from electronic structure calculations based on an equation derived with compact finite difference (CFD). The CFD-based equation is of higher accuracy than the quasi-Newton equation on which existing generally applicable Hessian update schemes are based. Direct tests of Hessian update schemes, as well as dynamics simulations using an integrator incorporating Hessian update schemes, have shown four of the new schemes produce reliably higher accuracy than existing Hessian update schemes.
Hessian matrix
Hessian equation
Quasi-Newton method
Cite
Citations (37)
Implementation of the standard full waveform inversion (FWI) poses difficulties as the initial model offsets from the true model. The wavefield reconstruction inversion (WRI) was proposed to mitigate these difficulties by relaxing the wave-equation constraint. In this abstract, working on the nonlinear term in the Hessian matrix of FWI, we develop a new approximate Hessian as an Augmented Gauss-Newton (AGN) Hessian including second-order derivative information. Moreover, we establish an intimate connection between an updating formula which results from approximate solve of the Newton's method with the AGN Hessian on the FWI problem and the WRI method. Our analysis opens new perspectives for developing efficient algorithms for FWI based on the Newton's method and highlights the importance of the nonlinear term in the Hessian matrix, which is ignored in most cases.
Hessian matrix
Hessian equation
Quasi-Newton method
Cite
Citations (0)