Globally convergent DC trust-region methods

In this paper, we investigate the use of DC (Difference of Convex functions) models and algorithms in the application of trust-region methods to the solution of a class of nonlinear optimization problems where the constrained set is closed and convex (and, from a practical point of view, where projecting onto the feasible region is computationally affordable). We consider DC local models for the quadratic model of the objective function used to compute the trust-region step, and apply a primal-dual subgradient method to the solution of the corresponding trust-region subproblems. One is able to prove that the resulting scheme is globally convergent to first-order stationary points. The theory requires the use of exact second-order derivatives but, in turn, the computation of the trust-region step asks only for one projection onto the feasible region (in comparison to the calculation of the generalized Cauchy point which may require more). The numerical efficiency and robustness of the proposed new scheme when applied to bound-constrained problems is measured by comparing its performance against some of the current state-of-the-art nonlinear programming solvers on a vast collection of test problems.     

Stability of Runge-Kutta methods for the generalized pantograph equation

Summary. This paper deals with stability properties of Runge-Kutta (RK) methods applied to a non-autonomous delay differential equation (DDE) with a constant delay which is obtained from the so-called generalized pantograph equation, an autonomous DDE with a variable delay by a change of the independent variable. It is shown that in the case where the RK matrix is regular stability properties of the RK method for the DDE are derived from those for a difference equation, which are examined by similar techniques to those in the case of autonomous DDEs with a constant delay. As a result, it is shown that some RK methods based on classical quadrature have a superior stability property with respect to the generalized pantograph equation. Stability of algebraically stable natural RK methods is also considered. Received May 5, 1998 / Revised version received November 17, 1998 / Published online September 24, 1999     

A new simple model trust-region method with generalized Barzilai-Borwein parameter for large-scale optimization

In this paper a new trust region method with simple model for solving large-scale unconstrained nonlinear optimization is proposed. By employing the generalized weak quasi-Newton equations, we derive several schemes to construct variants of scalar matrices as the Hessian approximation used in the trust region subproblem. Under some reasonable conditions, global convergence of the proposed algorithm is established in the trust region framework. The numerical experiments on solving the test problems with dimensions from 50 to 20,000 in the CUTEr library are reported to show efficiency of the algorithm.     

Critical multipliers in variational systems via second-order generalized differentiation

Mathematical Programming - In this paper we introduce the notions of critical and noncritical multipliers for variational systems and extend to a general framework the corresponding notions by...     

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determined using multipliers generated by solving the trust-region subproblem. To this end we study global convergence of a linear trust-region scheme for linearly-constrained NLPs that we call a trust-search method. The trust-search has two features that are critical to global convergence of decomposition methods for MPECs: a robustness property with respect to switching pieces, and a multiplier convergence result that appears to be quite new for trust-region methods. These combine to clarify and strengthen global convergence of decomposition methods without resorting either to additional conditions such as eventual inactivity of the trust-region constraint, or more complex methods that require a separate subproblem for multiplier estimation.      

Continuation Newton methods with the residual trust-region time-stepping scheme for nonlinear equations

Numerical Algorithms - For nonlinear equations, the homotopy methods (continuation methods) are popular in engineering fields since their convergence regions are large and they are quite reliable...     

Lipschitz properties of nonsmooth functions and set-valued mappings via generalized differentiation

In this paper, we revisit the Mordukhovich subdifferential criterion for Lipschitz continuity of nonsmooth functions and the coderivative criterion for the Aubin/Lipschitz-like property of set-valued mappings in finite dimensions. The criteria are useful and beautiful results in modern variational analysis showing the state of the art of the field. As an application, we establish necessary and sufficient conditions for Lipschitz continuity of the minimal time function and the scalarization function, which play an important role in many aspects of nonsmooth analysis and optimization.     

New zero-finders for trust-region computations

Trust-region methods are among the most popular schemes for determining a local minimum of a nonlinear function in several variables. These methods approximate the nonlinear function by a quadratic polynomial, and a trust-region radius determines the size of the sphere in which the quadratic approximation of the nonlinear function is deemed to be accurate. The trust-region radius has to be computed repeatedly during the minimization process. Each trust-region radius is computed by determining a zero of a nonlinear function ψ(x). This is often done with Newton’s method or a variation thereof. These methods give quadratic convergence of the computed approximations of the trust-region radius. This paper describes a cubically convergent zero-finder that is based on the observation that the second derivative \(\psi ^{\prime \prime }(x)\) can be evaluated inexpensively when the first derivative \(\psi ^{\prime }(x)\) is known. Computed examples illustrate the performance of the zero-finder proposed.     

S-Stability properties for generalized Runge-Kutta methods

Summary A class of generalized Runge-Kutta methods is considered for the numerical integration of stiff systems of ordinary differential equations. These methods are characterized by the fact that the coefficients of the integration formulas are matrices depending on the Jacobian, or on an approximation to the Jacobian. Special attention is paid to stability aspects. In particular, theS-stability properties of the method are investigated. The concept of internal stability is discussed. Internal stability imposes conditions on intermediate results in the Runge-Kutta scheme. Some numerical examples are discussed.     

A retrospective trust-region method for unconstrained optimization

We introduce a new trust-region method for unconstrained optimization where the radius update is computed using the model information at the current iterate rather than at the preceding one. The update is then performed according to how well the current model retrospectively predicts the value of the objective function at last iterate. Global convergence to first- and second-order critical points is proved under classical assumptions and preliminary numerical experiments on CUTEr problems indicate that the new method is very competitive.     

Preconditioned sor methods for generalized least-squares problems

1.IntroductionThegeneralizedleastsquaresproblem,definedasmin(Ax--b)"W--'(Ax--b),(1.1)xacwhereAERm",m>n,bERm,andWERm'misasymmetricandpositivedefinitematrix,isfrequentlyfoundwhensolvingproblemsinstatistics,engineeringandeconomics.Forexample,wegetgeneralizedleastsquaresproblemswhensolvingnonlinearregressionanalysisbyquasi-likelihoodestimation,imagereconstructionproblemsandeconomicmodelsobtainedbythemaximumlikelihoodmethod(of.[1,21).Paige[3,4]investigatestheproblemexplicitly.Hechangestheorig…     

Improved generalized differentiability conditions for Newton-like methods

We provide a semilocal convergence analysis for Newton-like methods using the ω$\omega$-versions of the famous Newton–Kantorovich theorem (Argyros (2004) [1], Argyros (2007) [3], Kantorovich and Akilov (1982) [13]). In the special case of Newton’s method, our results have the following advantages over the corresponding ones (Ezquerro and Hernaández (2002) [10], Proinov (2010) [17]) under the same information and computational cost: finer error estimates on the distances involved; at least as precise information on the location of the solution, and weaker sufficient convergence conditions.     

Recession methods for generalized vector equilibrium problems

By using the recession method, we give some necessary and/or sufficient condition of solutions of generalized vector equilibrium problems.     

Stability of a functional equation for generalized polynomials

All solutions of the equation \({f(x)+\sum_{i=1}^na_if(x+\rho_iy)+\sum_{j=1}^lb_jf(\sigma_jy)=0}\) are generalized polynomials of degree at most n. The general solution heavily depends on the parameters \({a_i, \rho_i, b_j, \sigma_j}\). Here the stability of this equation is investigated, i. e., for given suitable \({\varphi}\) the inequality \({\Vert f(x)+\sum_{i=1}^na_if(x+\rho_iy)+\sum_{j=1}^lb_jf(\sigma_jy)\Vert\le\varphi(x,y)}\) is considered. The method does not seem to standard: At first it is shown that f is “close” to some generalized polynomial P of degree at most n; and then it is shown that P is a solution of the equation above. In this context it is not necessary to know all solutions of the equation. Even more, there is no need to decide whether the equation has non-trivial solutions or not.     

BFGS trust-region method for symmetric nonlinear equations

In this paper, we propose a BFGS trust-region method for solving symmetric nonlinear equations. The global convergence and the superlinear convergence of the presented method will be established under favorable conditions. Numerical results show that the new algorithm is effective.