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

    Best case exponential running time of a branch-and-bound algorithm using an optimal semidefinite relaxation

  • Florian Jarre
    • Categories Branch and Cut Algorithms, Linear, Cone and Semidefinite Programming Tags , ,

    Chvatal (1980) has given a simple example of a knapsack problem for which a branch-and-bound algorithm using domination and linear relaxations to eliminate subproblems will use an exponential number of steps in the best case. In this short note it is shown that Chvatals result remains true when the LP relaxation is replaced with a … Read more

    Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms

  • Gregor Hendel
  • Matthias Miltenberger
  • Jakob Witzig
    • Categories (Mixed) Integer Linear Programming Tags , ,

    State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics … Read more

    The Cyclic Douglas-Rachford Algorithm with r-sets-Douglas-Rachford Operators

  • Francisco J. Aragón Artacho
  • Yair Censor
  • Aviv Gibali
    • Categories Convex Optimization

    The Douglas-Rachford (DR) algorithm is an iterative procedure that uses sequential reflections onto convex sets and which has become popular for convex feasibility problems. In this paper we propose a structural generalization that allows to use r-sets-DR operators in a cyclic fashion. We prove convergence and present numerical illustrations of the potential advantage of such … Read more

    A new concept of slope for set-valued maps and applications in set optimization studied with Kuroiwa’s set approach

  • Xuan Duc Ha Truong
    • Categories Multi-Criteria Optimization

    In this paper, scalarizing functions defined with the help of the Hiriart-Urruty signed distance are used to characterize set order relations and weak optimal solutions in set optimization studied with Kuroiwa’s set approach and to introduce a new concept of slope for a set-valued map. It turns out that this slope possesses most properties of … Read more

    Resilience assessment for interdependent urban infrastructure systems using dynamic network flow models

  • Panagiotis Angeloudis
  • Nils Goldbeck
  • Washington Ochieng
    • Categories Civil and Environmental Engineering, Optimization of Simulated Systems, Transportation

    Critical infrastructure systems in cities are becoming increasingly interdependent, therefore exacerbating the impacts of disruptive events through cascading failures, hindered asset repairs and network congestion. Current resilience assessment methods fall short of fully capturing such interdependency effects as they tend to model asset reliability and network flows separately and often rely on static flow assignment … 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

    Characterizations of Differentiability, Smoothing Techniques and DC Programming with Applications to Image Reconstructions

  • Nguyen Thai An
  • Le Thi Hoai An
  • Daniel Giles
  • Nguyen Mau Nam
    • Categories Convex and Nonsmooth Optimization

    In this paper, we study characterizations of differentiability for real-valued functions based on generalized differentiation. These characterizations provide the mathematical foundation for Nesterov’s smoothing techniques in infinite dimensions. As an application, we provide a simple approach to image reconstructions based on Nesterov’s smoothing techniques and DC programming that involves the $\ell_1-\ell_2$ regularization. ArticleDownload View PDF

    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

    Finding Minimum Volume Circumscribing Ellipsoids Using Generalized Copositive Programming

  • Grani A. Hanasusanto
  • Areesh Mittal
    • Categories Linear, Cone and Semidefinite Programming

    We study the problem of finding the Lowner-John ellipsoid, i.e., an ellipsoid with minimum volume that contains a given convex set. We reformulate the problem as a generalized copositive program, and use that reformulation to derive tractable semidefinite programming approximations for instances where the set is defined by affine and quadratic inequalities. We prove that, … Read more