Month: July 2018

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

    An improved projection and rescaling algorithm for conic feasibility problems

  • Yanqin Bai
  • Cornelis Roos
  • Wei Zhang
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    Motivated by Chubanov’s projection-based method for linear feasibility problems [Chubanov2015], a projection and rescaling algorithm for the conic feasibility problem \[ find \; x\in L\bigcap \Omega \] is proposed in [Pena2016], where $L$ and $\Omega$ are respectively a linear subspace and the interior of a symmetric cone in a finitely dimensional vector space $V$. When … 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

    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 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

    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 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

    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

    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