nonlinear optimization

A Self-Correcting Variable-Metric Algorithm Framework for Nonsmooth Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Baoyu Zhou
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    An algorithm framework is proposed for minimizing nonsmooth functions. The framework is variable-metric in that, in each iteration, a step is computed using a symmetric positive definite matrix whose value is updated as in a quasi-Newton scheme. However, unlike previously proposed variable-metric algorithms for minimizing nonsmooth functions, the framework exploits self-correcting properties made possible through … Read more

    An Inexact Regularized Newton Framework with a Worst-Case Iteration Complexity of $\mathcal{O}(\epsilon^{-3/2})$ for Nonconvex Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Mohammadreza Samadi
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    An algorithm for solving smooth nonconvex optimization problems is proposed that, in the worst-case, takes $\mathcal{O}(\epsilon^{-3/2})$ iterations to drive the norm of the gradient of the objective function below a prescribed positive real number $\epsilon$ and can take $\mathcal{O}(\epsilon^{-3})$ iterations to drive the leftmost eigenvalue of the Hessian of the objective above $-\epsilon$. The proposed … Read more

    A Sigmoidal Approximation for Chance-constrained Nonlinear Programs

  • Yankai Cao
  • Victor M. Zavala
    • Categories Stochastic Programming Tags , , ,

    We propose a sigmoidal approximation (SigVaR) for the value-at-risk (VaR) and we use this approximation to tackle nonlinear programming problems (NLPs) with chance constraints. We prove that the approximation is conservative and that the level of conservatism can be made arbitrarily small for limiting parameter values. The SigVar approximation brings computational benefits over exact mixed-integer … Read more

    On the behavior of Lagrange multipliers in convex and non-convex infeasible interior point methods

  • Gabriel Haeser
  • Yinyu Ye
  • Oliver Hinder
    • Categories Nonlinear Optimization Tags , , , ,

    This paper analyzes sequences generated by infeasible interior point methods. In convex and non-convex settings, we prove that moving the primal feasibility at the same rate as complementarity will ensure that the Lagrange multiplier sequence will remain bounded, provided the limit point of the primal sequence has a Lagrange multiplier, without constraint qualification assumptions. We … Read more

    A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis

  • Elhoucine Bergou
  • Youssef Diouane
  • Serge Gratton
    • Categories Unconstrained Optimization Tags , , , , ,

    Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity amongst second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such scaled norm, the obtained method … Read more

    On the use of the energy norm in trust-region and adaptive cubic regularization subproblems

  • Elhoucine Bergou
  • Youssef Diouane
  • Serge Gratton
    • Categories Unconstrained Optimization Tags , , , , , , ,

    We consider solving unconstrained optimization problems by means of two popular globalization techniques: trust-region (TR) algorithms and adaptive regularized framework using cubics (ARC). Both techniques require the solution of a so-called “subproblem” in which a trial step is computed by solving an optimization problem involving an approximation of the objective function, called “the model”. The … Read more

    Partially separable convexly-constrained optimization with non-Lipschitz singularities and its complexity

  • Xiaojun Chen
  • Philippe L. Toint
  • Hong Wang
    • Categories Nonsmooth Optimization Tags , ,

    An adaptive regularization algorithm using high-order models is proposed for partially separable convexly constrained nonlinear optimization problems whose objective function contains non-Lipschitzian $\ell_q$-norm regularization terms for $q\in (0,1)$. It is shown that the algorithm using an $p$-th order Taylor model for $p$ odd needs in general at most $O(\epsilon^{-(p+1)/p})$ evaluations of the objective function and … Read more

    Complexity Analysis of a Trust Funnel Algorithm for Equality Constrained Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Mohammadreza Samadi
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    A method is proposed for solving equality constrained nonlinear optimization problems involving twice continuously differentiable functions. The method employs a trust funnel approach consisting of two phases: a first phase to locate an $\epsilon$-feasible point and a second phase to seek optimality while maintaining at least $\epsilon$-feasibility. A two-phase approach of this kind based on … Read more

    A Sequential Algorithm for Solving Nonlinear Optimization Problems with Chance Constraints

  • Frank E. Curtis
  • Victor M. Zavala
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , ,

    An algorithm is presented for solving nonlinear optimization problems with chance constraints, i.e., those in which a constraint involving an uncertain parameter must be satisfied with at least a minimum probability. In particular, the algorithm is designed to solve cardinality-constrained nonlinear optimization problems that arise in sample average approximations of chance-constrained problems, as well as … Read more

    Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    High-order optimality conditions for convexly-constrained nonlinear optimization problems are analyzed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order $\epsilon$-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that, if derivatives of the objective function up to order $q \geq 1$ … Read more