Luke Winternitz

Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization

  • Pierre-Antoine Absil
  • Luke Winternitz
  • AndrĂ© L. Tits
    • Categories Linear Programming Tags , , ,

    In earlier work (Tits et al., SIAM J. Optim., 17(1):119–146, 2006; Winternitz et al., COAP, doi=10.1007/s10589-010-9389-4, 2011), the present authors and their collaborators proposed primal-dual interior-point (PDIP) algorithms for linear optimization that, at each iteration, use only a subset of the (dual) inequality constraints in constructing the search direction. For problems with many more constraints … 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