Nonlinear Optimization

On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Unconstrained Optimization Tags , ,

    It is shown that the steepest descent and Newton’s method for unconstrained nonconvex optimization under standard assumptions may be both require a number of iterations and function evaluations arbitrarily close to O(epsilon^{-2}) to drive the norm of the gradient below epsilon. This shows that the upper bound of O(epsilon^{-2}) evaluations known for the steepest descent … Read more

    Stopping rules and backward error analysis for bound-constrained optimization

  • Serge Gratton
  • Philippe L. Toint
  • Mélodie Mouffe
    • Categories Bound-constrained Optimization, Optimization Software Design Principles Tags , , , ,

    Termination criteria for the iterative solution of bound-constrained optimization problems are examined in the light of backward error analysis. It is shown that the problem of determining a suitable perturbation on the problem’s data corresponding to the definition of the backward error is analytically solvable under mild assumptions. Moreover, a link between existing termination criteria … Read more

    Analysis of direct searches for non-Lipschitzian functions

  • Ana Luisa Custódio
  • Luis Nunes Vicente
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , ,

    It is known that the Clarke generalized directional derivative is nonnegative along the limit directions generated by directional direct-search methods at a limit point of certain subsequences of unsuccessful iterates, if the function being minimized is Lipschitz continuous near the limit point. In this paper we generalize this result for non-Lipschitzian functions using Rockafellar generalized … Read more

    Optimizing radial basis functions by D.C. programming and its use in direct search for global derivative-free optimization

  • Hoai An Le Thi
  • A. Ismael F. Vaz
  • Luis Nunes Vicente
    • Categories Global Optimization, Nonlinear Optimization Tags , , , , , ,

    In this paper we address the global optimization of functions subject to bound and linear constraints without using derivatives of the objective function. We investigate the use of derivative-free models based on radial basis functions (RBFs) in the search step of direct-search methods of directional type. We also study the application of algorithms based on … Read more

    Matrix-Free Interior Point Method

  • Jacek Gondzio
    • Categories Linear Programming, Quadratic Programming Tags , , , , ,

    In this paper we present a redesign of a linear algebra kernel of an interior point method to avoid the explicit use of problem matrices. The only access to the original problem data needed are the matrix-vector multiplications with the Hessian and Jacobian matrices. Such a redesign requires the use of suitably preconditioned iterative methods … Read more

    On approximate KKT condition and its extension to continuous variational inequalities

  • Gabriel Haeser
  • María Laura Schuverdt
    • Categories Nonlinear Optimization Tags , ,

    In this work we introduce a necessary natural sequential Approximate-Karush-Kuhn-Tucker (AKKT) condition for a point to be a solution of a continuous variational inequality problem without constraint quali cations, and we prove its relation with the Approximate Gradient Projection condition (AGP) of Garciga-Otero and Svaiter. We also prove that a slight variation of the AKKT condition … Read more

    On the convergence of the projected gradient method for vector optimization

  • Ellen H. Fukuda
  • L. M. Graña Drummond
    • Categories Constrained Nonlinear Optimization, Multi-Criteria Optimization Tags , , ,

    In 2004, Graña Drummond and Iusem proposed an extension of the projected gradient method for constrained vector optimization problems. In that method, an Armijo-like rule, implemented with a backtracking procedure, was used in order to determine the steplengths. The authors just showed stationarity of all cluster points and, for another version of the algorithm (with … Read more

    A globally convergent modified conjugate-gradient line-search algorithm with inertia controlling

  • Ioannis G. Akrotirianakis
  • Joshua D. Griffin
  • Wenwen Zhou
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this paper we have addressed the problem of unboundedness in the search direction when the Hessian is indefinite or near singular. A new algorithm has been proposed which naturally handles singular Hessian matrices, and is theoretically equivalent to the trust-region approach. This is accomplished by performing explicit matrix modifications adaptively that mimic the implicit … Read more

    Two-Stage Quadratic Integer Programs with Stochastic Right-Hand Sides

  • Osman Y. Ozaltin
  • Oleg A. Prokopyev
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Stochastic Programming Tags , , ,

    We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We fi rst derive some basic properties of value functions of quadratic integer programs. We then propose a two-phase solution approach. The first phase constructs the value functions of quadratic integer programs in both stages. The second phase … Read more

    On the Stopping Criterion for Numerical Methods Used to Solve Linear Systems with Additive Gaussian Noise

  • Jean-Pierre Dussault
  • Yves Goussard
  • Benoit Hamelin
    • Categories Statistics, Unconstrained Optimization Tags , , , ,

    We consider the inversion of a linear operator with centered Gaussian white noise by MAP estimation with a Gaussian prior distribution on the solution. The actual estimator is computed approximately by a numerical method. We propose a relation between the stationarity measure of this approximate solution to the mean square error of the exact solution. … Read more