Nonlinear Optimization

Adaptive Cubic Regularization methods with dynamic inexact Hessian information and applications to finite-sum minimization

  • Stefania Bellavia
  • Benedetta Morini
  • Gianmarco Gurioli
    • Categories Unconstrained Optimization Tags

    We consider the Adaptive Regularization with Cubics approach for solving nonconvex optimization problems and propose a new variant based on inexact Hessian information chosen dynamically. The theoretical analysis of the proposed procedure is given. The key property of ARC framework, constituted by optimal worst-case function/derivative evaluation bounds for first- and second-order critical point, is guaranteed. … Read more

    Bilevel optimization: theory, algorithms and applications

  • Stephan Dempe
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization

    Bilevel optimization problems are hierarchical optimization problems where the feasible region of the so-called upper level problem is restricted by the graph of the solution set mapping of the lower level problem. Aim of this article is to collect a large number of references on this topic, to show the diversity of contributions and to … Read more

    Asynchronous Sequential Inertial Iterations for Common Fixed Points Problems with an Application to Linear Systems

  • Yair Censor
  • Howard Heaton
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , ,

    The common fixed points problem requires finding a point in the intersection of fixed points sets of a finite collection of operators. Quickly solving problems of this sort is of great practical importance for engineering and scientific tasks (e.g., for computed tomography). Iterative methods for solving these problems often employ a Krasnosel’skii-Mann type iteration. We … Read more

    Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization

  • Filip Hanzely
  • Peter Richtarik
  • Lin Xiao
    • Categories Convex Optimization, Nonlinear Optimization Tags , , , ,

    We consider the problem of minimizing the sum of two convex functions: one is differentiable and relatively smooth with respect to a reference convex function, and the other can be nondifferentiable but simple to optimize. The relatively smooth condition is much weaker than the standard assumption of uniform Lipschitz continuity of the gradients, thus significantly … Read more

    Generalized Stochastic Frank-Wolfe Algorithm with Stochastic “Substitute” Gradient for Structured Convex Optimization

  • Robert M. Freund
  • Haihao Lu
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , ,

    The stochastic Frank-Wolfe method has recently attracted much general interest in the context of optimization for statistical and machine learning due to its ability to work with a more general feasible region. However, there has been a complexity gap in the guaranteed convergence rate for stochastic Frank-Wolfe compared to its deterministic counterpart. In this work, … Read more

    Significant Generalization of the Convergence Proof for the Direct Transcription Method for Constrained Optimal Control Problems

  • Martin Neuenhofen
    • Categories Nonlinear Optimization

    In the arXiv paper [arXiv:1712.07761] from December 2017 we presented a convergent direct transcription method for optimal control problems. In the present paper we present a significantly generalized convergence theory in succinct form. Therein, we replace strong assumptions that we had formerly made on local uniqueness of the solution, and on differentiability of a particular … Read more

    Minimizing convex quadratics with variable precision Krylov methods

  • Serge Gratton
  • Philippe L. Toint
  • Ehouarn Simon
    • Categories Convex Optimization, Optimization Software and Modeling Systems, Quadratic Programming Tags , ,

    Iterative algorithms for the solution of convex quadratic optimization problems are investigated, which exploit inaccurate matrix-vector products. Theoretical bounds on the performance of a Conjugate Gradients and a Full-Orthormalization methods are derived, the necessary quantities occurring in the theoretical bounds estimated and new practical algorithms derived. Numerical experiments suggest that the new methods have significant … Read more

    A hybrid algorithm for the two-trust-region subproblem

  • Saeid Ansary Karbasy
  • Maziar Salahi
    • Categories Global Optimization, Quadratic Programming Tags , , ,

    Two-trust-region subproblem (TTRS), which is the minimization of a general quadratic function over the intersection of two full-dimensional ellipsoids, has been the subject of several recent research. In this paper, to solve TTRS, a hybrid of efficient algorithms for finding global and local-nonglobal minimizers of trust-region subproblem and the alternating direction method of multipliers (ADMM) … Read more

    Convex computation of extremal invariant measures of nonlinear dynamical systems and Markov processes

  • Didier Henrion
  • Milan Korda
  • Igor Mezic
    • Categories Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We propose a convex-optimization-based framework for computation of invariant measures of polynomial dynamical systems and Markov processes, in discrete and con- tinuous time. The set of all invariant measures is characterized as the feasible set of an infinite-dimensional linear program (LP). The objective functional of this LP is then used to single-out a specific measure … Read more

    Semidenite Approximations of Invariant Measures for Polynomial Systems

  • Marcelo Forets
  • Didier Henrion
  • Victor Magron
    • Categories Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , , ,

    We consider the problem of approximating numerically the moments and the supports of measures which are invariant with respect to the dynamics of continuousand discrete-time polynomial systems, under semialgebraic set constraints. First, we address the problem of approximating the density and hence the support of an invariant measure which is absolutely continuous with respect to … Read more