A new family of high order directions for unconstrained optimization inspired by Chebyshev and Shamanskii methods

  • Jean-Pierre Dussault
  • Bilel Kchouk
    • Categories Nonlinear Optimization, Unconstrained Optimization

    The 1669-1670 Newton-Raphson’s method is still used to solve equations systems and unconstrained optimization problems. Since this method, some other algorithms inspired by Newton’s have been proposed: in 1839 Chebyshev developped a high order cubical convergence algorithm, and in 1967 Shamanskii proposed an acceleration of Newton’s method. By considering a Newton-type methods as displacement directions, … Read more

    On the Difficulty of Deciding Asymptotic Stability of Cubic Homogeneous Vector Fields

  • Amir Ali Ahmadi
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , ,

    It is well-known that asymptotic stability (AS) of homogeneous polynomial vector fields of degree one (i.e., linear systems) can be decided in polynomial time e.g. by searching for a quadratic Lyapunov function. Since homogeneous vector fields of even degree can never be AS, the next interesting degree to consider is equal to three. In this … Read more

    Subdifferentials of nonconvex supremum functions and their applications to semi-infinite and infinite programs with Lipschitzian data

  • Boris S. Mordukhovich
  • Nghia Tran
    • Categories Nonsmooth Optimization, Semi-infinite Programming Tags , , ,

    The paper is devoted to the subdifferential study and applications of the supremum of uniformly Lipschitzian functions over arbitrary index sets with no topology. Based on advanced techniques of variational analysis, we evaluate major subdifferentials of the supremum functions in the general framework of Asplund (in particular, reflexive) spaces with no convexity or relaxation assumptions. … Read more

    Improved Column Generation for Highly Degenerate Master Problems

  • Jacques Desrosiers
  • Jean-Bertrand Gauthier
  • Marco E. Lübbecke
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , ,

    Column generation for solving linear programs with a huge number of variables alternates between solving a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to suffer from degeneracy of the master problem, exposing what is called the tailing-off effect. Inspired by recent advances in … Read more

    Global Search Strategies for Solving Multilinear Least-squares Problems

  • Mats Andersson
  • Oleg Burdakov
  • Hans Knutsson
  • Spartak Zikrin
    • Categories Basic Sciences Applications, Global Optimization, Nonlinear Systems and Least-Squares

    The multilinear least-squares (MLLS) problem is an extension of the linear least-squares problem. The difference is that a multilinear operator is used in place of a matrix-vector product. The MLLS is typically a large-scale problem characterized by a large number of local minimizers. It originates, for instance, from the design of filter networks. We present … Read more

    A Class of Dantzig-Wolfe Type Decomposition Methods for Variational Inequality Problems

  • Juan Pablo Luna
  • Claudia Sagastizábal
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization Tags ,

    We consider a class of decomposition methods for variational inequalities, which is related to the classical Dantzig–Wolfe decomposition of linear programs. Our approach is rather general, in that it can be used with set-valued or nonmonotone operators, as well as various kinds of approximations in the subproblems of the functions and derivatives in the single-valued … Read more

    On the Geometry of Acceptability Functionals

  • Alois Pichler
    • Categories Dynamic Programming, Stochastic Programming Tags , ,

    Abstract In this paper we discuss continuity properties of acceptability functionals or risk measures. The dependence of the random variable is investigated first. The main contribution and focus of this paper is to study how acceptability functionals vary whenever the underlying probability measure is perturbed. Abstract It turns out that the Wasserstein distance provides a … Read more

    Time-inconsistent multistage stochastic programs: martingale bounds

  • Georg Ch. Pflug
  • Alois Pichler
    • Categories Dynamic Programming, Stochastic Programming Tags , ,

    Abstract. It is well known that multistage programs, which maximize expectation or expected utility, allow a dynamic programming formulation, and that other objectives destroy the dynamic programming character of the problem. This paper considers a risk measure at the final stage of a multistage stochastic program. Although these problems are not time consistent, it is … Read more

    A LINEAR TIME ALGORITHM FOR THE KOOPMANS-BECKMANN QAP LINEARIZATION AND RELATED PROBLEMS

  • Santosh N. Kabadi
  • Abraham Punnen
    • Categories Combinatorial Optimization Tags , ,

    An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. The QAP linearization problem can be solved in O(n4) … Read more

    Joint Spectral Radius and Path-Complete Graph Lyapunov Functions

  • Amir Ali Ahmadi
  • Raphaël Jungers
  • Pablo A. Parrilo
  • Mardavij Roozbehani
    • Categories Approximation Algorithms, Control Applications, Semi-definite Programming Tags , , , , ,

    We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of … Read more