linear programming

An Information Geometric Approach to Polynomial-time Interior-point Algorithms: Complexity Bound via Curvature Integral

  • Atsumi Ohara
  • Takashi Tsuchiya
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , ,

    In this paper, we study polynomial-time interior-point algorithms in view of information geometry. Information geometry is a differential geometric framework which has been successfully applied to statistics, learning theory, signal processing etc. We consider information geometric structure for conic linear programs introduced by self-concordant barrier functions, and develop a precise iteration-complexity estimate of the polynomial-time … Read more

    Optimization by the Fixed-Point Method, Version 2.17

  • Jalaluddin Abdullah
    • Categories Constrained Nonlinear Optimization, Linear Programming Tags , , ,

    Abstract: After developing necessary background theory, the original primal and dual are specified, and the invariant primal and dual LP’s are defined. Pairs of linear mappings are defined which establish an effectively one-to-one correspondences between solutions to the original and invariant problems. The invariant problems are recast as a fixed-point problem and precise solution conditions … Read more

    Convergence Analysis of Inexact Infeasible Interior Point Method for Linear Optimization

  • Ghussoun Al-Jeiroudi
  • Jacek Gondzio
    • Categories Linear Programming Tags , , ,

    In this paper we present the convergence analysis of the inexact infeasible path-following(IIPF) interior point algorithm. In this algorithm the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix. The KKT system is solved approximately. Therefore, it becomes … Read more

    A Constraint-Reduced Variant of Mehrotra’s Predictor-Corrector Algorithm

  • Stacey Nicholls
  • Dianne P. O'Leary
  • Luke Winternitz
  • André L. Tits
    • Categories Linear Programming Tags , , ,

    Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm^2) operations. When n>>m it is often the case that at … Read more

    Approximate Solutions for Deterministic and Stochastic Multi-Dimensional Sequencing

  • B Jothi
  • Sachin Patkar
  • Chandra Poojari
  • Janak Porwal
    • Categories Approximation Algorithms, Scheduling Tags , , , ,

    We investigate the problem of sequencing jobs that have multiple components. Each component of the job needs to be processed independently on a specified machine. We derive approximate algorithms for the problem of scheduling such vector jobs to minimize their total completion time in the deterministic as well as stochastic setting. In particular, we propose … Read more

    A gradient-based approach for computing Nash equilibria of large sequential games

  • Andrew Gilpin
  • Javier F. Peña
  • Samid Hoda
    • Categories Convex Optimization, Game Theory, Linear Programming Tags , ,

    We propose a new gradient based scheme to approximate Nash equilibria of large sequential two-player, zero-sum games. The algorithm uses modern smoothing techniques for saddle-point problems tailored specifically for the polytopes used in the Nash equilibrium problem. Citation Working Paper, Tepper School of Business, Carnegie Mellon University Article Download View A gradient-based approach for computing … Read more

    A polynomial predictor-corrector trust-region algorithm for linear programming

  • Guanghui Lan
  • Renato D.C. Monteiro
  • Takashi Tsuchiya
    • Categories Linear Programming, Nonlinear Optimization Tags , , , ,

    In this paper we present a scaling-invariant interior-point predictor-corrector type algorithm for linear programming (LP) whose iteration-complexity is polynomially bounded by the dimension and the logarithm of a certain condition number of the LP constraint matrix. At the predictor stage, the algorithm either takes the step along the standard affine scaling direction or a new … Read more

    A reduced duality gaps simplex algorithm for linear programming

  • Yan Zizong
    • Categories Linear Programming Tags , , ,

    In this paper we devise a new version of primal simplex algorithms in which the classical iteration is decomposed two basic operations: the move and the pivot. The move operation decreases the primal objective value and the pivot operation increases the dual objective. We define the condition number of the pivot operation and present a … Read more

    Mehrotra-type predictor-corrector algorithms revisited

  • Maziar Salahi
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , ,

    Motivated by a numerical example which shows that a feasible version of Mehrotra’s original predictor-corrector algorithm might be inefficient in practice, Salahi et al., proposed a so-called safeguard based variant of the algorithm that enjoys polynomial iteration complexity while its practical efficiency is preserved. In this paper we analyze the same Mehrotra’s algorithm from a … Read more

    Sensitivity analysis in linear semi-infinite programming via partitions

  • Miguel A. Goberna
  • Tamás Terlaky
  • Maxim I. Todorov
    • Categories Other Topics, Semi-infinite Programming Tags , , ,

    This paper provides sufficient conditions for the optimal value function of a given linear semi-infinite programming problem to depend linearly on the size of the perturbations, when these perturbations are directional, involve either the cost coefficients or the right-hand-side function or both, and they are sufficiently small. Two kinds of partitions are considered. The first … Read more