Nonlinear Optimization

Branching and Bounding Improvements for Global Optimization Algorithms with Lipschitz Continuity Properties

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Jaroslav M. Fowkes
    • Categories Global Optimization, Nonlinear Optimization Tags ,

    We present improvements to branch and bound techniques for globally optimizing functions with Lipschitz continuity properties by developing novel bounding procedures and parallelisation strategies. The bounding procedures involve nonconvex quadratic or cubic lower bounds on the objective and use estimates of the spectrum of the Hessian or derivative tensor, respectively. As the nonconvex lower bounds … Read more

    A Riemannian symmetric rank-one trust-region method

  • Pierre-Antoine Absil
  • Kyle A. Gallivan
  • Wen Huang
    • Categories Nonlinear Optimization

    The well-known symmetric rank-one trust-region method—where the Hessian approximation is generated by the symmetric rank-one update—is generalized to the problem of minimizing a real-valued function over a $d$-dimensional Riemannian manifold. The generalization relies on basic differential-geometric concepts, such as tangent spaces, Riemannian metrics, and the Riemannian gradient, as well as on the more recent notions … Read more

    Efficient tridiagonal preconditioner for the matrix-free truncated Newton method

  • Ladislav Lukšan
  • Jan Vlček
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    In this report, we study an efficient tridiagonal preconditioner, based on numerical differentiation, applied to the matrix-free truncated Newton method for unconstrained optimization. It is proved that this preconditioner is positive definite for many practical problems. The efficiency of the resulting matrix-free truncated Newton method is demonstrated by results of extensive numerical experiments. Citation Technical … Read more

    An inexact and nonmonotone proximal method for smooth unconstrained minimization

  • Sandra Augusta Santos
  • R. C. M. Silva
    • Categories Unconstrained Optimization

    An implementable proximal point algorithm is established for the smooth nonconvex unconstrained minimization problem. At each iteration, the algorithm minimizes approximately a general quadratic by a truncated strategy with step length control. The main contributions are: (i) a framework for updating the proximal parameter; (ii) inexact criteria for approximately solving the subproblems; (iii) a nonmonotone … Read more

    Second-order necessary conditions in Pontryagin form for optimal control problems

  • Joseph Frédéric Bonnans
  • Xavier Dupuis
  • Laurent Pfeiffer
    • Categories Constrained Nonlinear Optimization, Systems governed by Differential Equations Optimization

    In this report, we state and prove first- and second-order necessary conditions in Pontryagin form for optimal control problems with pure state and mixed control-state constraints. We say that a Lagrange multiplier of an optimal control problem is a Pontryagin multiplier if it is such that Pontryagin’s minimum principle holds, and we call optimality conditions … Read more

    Second-order sufficient conditions for strong solutions to optimal control problems

  • Joseph Frédéric Bonnans
  • Xavier Dupuis
  • Laurent Pfeiffer
    • Categories Constrained Nonlinear Optimization, Systems governed by Differential Equations Optimization

    In this report, given a reference feasible trajectory of an optimal control problem, we say that the quadratic growth property for bounded strong solutions holds if the cost function of the problem has a quadratic growth over the set of feasible trajectories with a bounded control and with a state variable sufficiently close to the … Read more

    Robust convex relaxation for the planted clique and densest k-subgraph problems

  • Brendan Ames
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    We consider the problem of identifying the densest k-node subgraph in a given graph. We write this problem as an instance of rank-constrained cardinality minimization and then relax using the nuclear and l1 norms. Although the original combinatorial problem is NP-hard, we show that the densest k-subgraph can be recovered from the solution of our … Read more

    Adaptive Observations And Multilevel Optimization In Data Assimilation

  • Serge Gratton
  • Monserrat Rincon-Camacho
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Optimization of Systems modeled by PDEs Tags , ,

    We propose to use a decomposition of large-scale incremental four dimensional (4D-Var) data assimilation problems in order to make their numerical solution more efficient. This decomposition is based on exploiting an adaptive hierarchy of the observations. Starting with a low-cardinality set and the solution of its corresponding optimization problem, observations are adaptively added based on … Read more

    Dual equilibrium problems: how a succession of aspiration points converges to an equilibrium

  • Felipe Garcia Moreno
  • Paulo Roberto Oliveira
  • Antoine Soubeyran
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization Tags , , , ,

    We consider an equilibrium problem defined on a convex set, whose cost bifunction may not be monotone. We show that this problem can be solved by the inexact partial proximal method with quasi distance. As an application, at the psychological level of behavioral dynamics, this paper shows two points: i) how a dual equilibrium problem … Read more

    A Trust-Region Method for Unconstrained Multiobjective Problems with Applications in Satisficing Processes

  • Paulo Roberto Oliveira
  • Antoine Soubeyran
  • Kely Diana Villacorta
    • Categories Applications - OR and Management Sciences, Multi-Criteria Optimization, Nonlinear Optimization Tags , , , , ,

    Multiobjective optimization has a significant number of real life applications. For this reason, in this paper, we consider the problem of finding Pareto critical points for unconstrained multiobjective problems and present a trust-region method to solve it. Under certain assumptions, which are derived in a very natural way from assumptions used by \citet{conn} to establish … Read more