A lower bound on the number of iterations of long-step primal-dual linear programming algorithms.
Michael J. ToddYinyu YePublished in: Ann. Oper. Res. (1996)
Keyphrases
- linear programming
- primal dual
- interior point
- simplex algorithm
- lower bound
- linear program
- computational complexity
- algorithm for linear programming
- semidefinite programming
- linear programming problems
- optimal solution
- interior point methods
- objective function
- affine scaling
- dual feasible
- search direction
- upper bound
- interior point algorithm
- convergence rate
- learning algorithm
- worst case
- branch and bound
- constant factor
- stopping criterion
- simplex method
- linear programming relaxation
- optimization problems
- convex optimization problems
- variational inequalities
- nonlinear programming
- feasible solution
- combinatorial optimization
- convex functions
- convex optimization
- computationally intensive
- lagrangian relaxation
- lower and upper bounds
- multi objective