A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions

  • Sergei Chubanov
    • Categories Linear Programming Tags , ,

    This paper proposes a polynomial algorithm for linear programming which is strongly polynomial for linear optimization problems $\min\{c^Tx : Ax = b, x\ge {\bf 0}\}$ having optimal solutions where each non-zero component $x_j$ belongs to an interval of the form $[\alpha_j, \alpha_j\cdot 2^{p(n)}],$ where $\alpha_j$ is some positive value and $p(n)$ is a polynomial of … Read more

    Variational principles with generalized distances and applications to behavioral sciences

  • Phan Q. Khanh
  • Antoine Soubeyran
  • Bao Q. Truong
    • Categories Applications - OR and Management Sciences, Global Optimization, Nonsmooth Optimization Tags , , , , ,

    This paper has a two-fold focus on proving that the quasimetric and the weak $\tau$-distance versions of the Ekeland variational principle are equivalent in the sense that one implies the other and on presenting the need of such extensions for possible applications in the formation and break of workers hiring and firing routines. Article Download … Read more

    Global convergence of the Heavy-ball method for convex optimization

  • Hamid Reza Feyzmahdavian
  • Euhanna Ghadimi
  • Mikael Johansson
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , ,

    This paper establishes global convergence and provides global bounds of the convergence rate of the Heavy-ball method for convex optimization problems. When the objective function has Lipschitz-continuous gradient, we show that the Cesa ́ro average of the iterates converges to the optimum at a rate of $O(1/k)$ where k is the number of iterations. When … Read more

    On the Adaptivity Gap in Two-stage Robust Linear Optimization under Uncertain Constraints

  • Pranjal Awasthi
  • Vineet Goyal
  • Brian Lu
    • Categories Approximation Algorithms, Robust Optimization

    In this paper, we study the performance of static solutions in two-stage adjustable robust packing linear optimization problem with uncertain constraint coefficients. Such problems arise in many important applications such as revenue management and resource allocation problems where demand requests have uncertain resource requirements. The goal is to find a two-stage solution that maximizes the … Read more

    Generalized Dual Face Algorithm for Linear Programming

  • Ping-Qi Pan
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , ,

    As a natural extension of the dual simplex algorithm, the dual face algorithm performed remarkably in computational experiments with a set of Netlib standard problems. In this paper, we generalize it to bounded-variable LP problems via local duality. Citation Department of Mathematics, Southeast University, Nanjing, 210096, China, 12/2014 Article Download View Generalized Dual Face Algorithm … Read more

    An asymptotic inclusion speed for the Douglas-Rachford splitting method in Hilbert spaces

  • Yunda Dong
    • Categories Convex Optimization

    In this paper, we consider the Douglas-Rachford splitting method for monotone inclusion in Hilbert spaces. It can be implemented as follows: from the current iterate, first use forward-backward step to get the intermediate point, then to get the new iterate. Generally speaking, the sum operator involved in the Douglas-Rachford splitting takes the value of every … Read more

    Activity Identification and Local Linear Convergence of Douglas-Rachford/ADMM under Partial Smoothness

  • Jalal Fadili
  • Jingwei Liang
  • Russell Luke
  • Gabriel Peyré
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    Proximal splitting algorithms are becoming popular to solve convex optimization problems in variational image processing. Within this class, Douglas-Rachford (DR) and ADMM are designed to minimize the sum of two proper lower semicontinuous convex functions whose proximity operators are easy to compute. The goal of this work is to understand the local convergence behaviour of … Read more

    A Filter SQP Method: Local Convergence and Numerical Results

  • Nicholas I. M. Gould
  • Daniel P. Robinson
  • Yueling Loh
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    The work by Gould, Loh, and Robinson [“A filter method with unified step computation for nonlinear optimization”, SIAM J. Optim., 24 (2014), pp. 175–209] established global convergence of a new filter line search method for finding local first-order solutions to nonlinear and nonconvex constrained optimization problems. A key contribution of that work was that the … Read more

    A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching

  • Santanu S. Dey
  • Hyemin Jeon
  • Burak Kocuk
  • Jeff Linderoth
  • James R. Luedtke
  • Xu Andy Sun
    • Categories Applications - Science and Engineering, Integer Programming Tags , ,

    It is well-known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. In fact, the USA Energy Policy Act of 2005 (Section 1223) states that the U.S. should “encourage, as appropriate, the deployment of advanced transmission technologies” including “optimized transmission line configurations”. As such, … Read more

    Set approach for set optimization with variable ordering structures

  • Gabriele Eichfelder
  • Maria Pilecka
    • Categories Infinite Dimensional Optimization, Multi-Criteria Optimization, Other Topics

    This paper aims at combining variable ordering structures with set relations in set optimization, which have been defined using the constant ordering cone before. Since the purpose is to connect these two important approaches in set optimization, we do not restrict our considerations to one certain relation. Conversely, we provide the reader with many new … Read more