complexity

Complexity of Convex Optimization using Geometry-based Measures and a Reference Point

  • Robert M. Freund
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Our concern lies in solving the following convex optimization problem: minimize cx subject to Ax=b, x \in P, where P is a closed convex set, not necessarily a cone. We bound the complexity of computing an almost-optimal solution of this problem in terms of natural geometry-based measures of the feasible region and the level-set of … Read more

    Warm start strategies in interior-point methods for linear programming

  • Stephen Wright
  • E. Alper Yildirim
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We study the situation in which, having solved a linear program with an interior-point method, we are presented with a new problem instance whose data is slightly perturbed from the original. We describe strategies for recovering a “warm-start” point for the perturbed problem instance from the iterates of the original problem instance. We obtain worst-case … Read more