Re: complexity of LP
- From: spellucci@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx (Peter Spellucci)
- Date: Thu, 6 Apr 2006 10:51:46 +0000 (UTC)
In article <e126fd$dro$1@xxxxxxxxxxxxx>,
Steve Borbash <sink300@xxxxxxxxxxx> writes:
What is the state of the art in solving a linear program? I have heard
of a result (from the 1980s I think) that says that the LP can be solved
in time O(n^3 L) where n is the number of variables and L is the number
of bits required to describe the instance. Is that still the sharpest
result for the worst-case complexity?
I know of no better (general) results.
one must discern between the complexity in regards of step numbers
and teh complexity of the single step, which of course depends much on the
properties of the system matrix.
the step number best bound is O(sqrt(n)L)
the relevant papers are
Zbl 0691.90053
Gonzaga, Clovis C.
An algorithm for solving linear programming problems in $O(n\sp 3L)$ operations. (English)
[CA] Progress in mathematical programming. Interior-point and related methods, Proc. Conf., Pacific Grove/Calif. 1987, 1-28 (1989).
[For the entire collection see Zbl 0669.00026.] \par This paper describes a short-step penalty function algorithm that solves linear programming problems
in no more than $O(n\sp{0.5}L)$ iterations. The total number of arithmetic operations is bounded by $O(n\sp 3L)$, carried on with the same precision as
that in Karmarkar's algorithm. Each iteration updates a penalty multiplier and solves a Newton-Raphson iteration on the traditional logarithmic barrier
function using approximated Hessian matrices. The resulting sequence follows the path of optimal solutions for the penalized functions as in a
predictor-corrector homotopy algorithm.
Zbl 0751.90048
Renegar, James; Shub, Michael
Unified complexity analysis for Newton LP methods. (English)
[J] Math. Program., Ser. A 53, No.1, 1-16 (1992). [ISSN 0025-5610]
The authors show that a theorem of S. Smale can be applied to unify the polynomial-time bound proofs of several of the recent interior algorithms. They
consider, in particular, {\it C. C. Gonzaga's} linear programming barrier method [in: Progress in mathematical programming, Interior-point and related
methods, Proc. Conf., Pacific Grove/Calif. 1987, 1-28 (1989; Zbl 0691.90053)], the barrier method applied to convex quadratic programming, a primal linear
programming method, a primal-dual linear programming method, and a primal-dual method applied to convex quadratic programming. A good reference for
all this material is the collection of papers mentioned above.
Zbl 0891.90127
Bertsimas, Dimitris; Luo, Xiaodong
On the worst case complexity of potential reduction algorithms for linear programming. (English)
[J] Math. Program. 77, No.3(A), 321-333 (1997). [ISSN 0025-5610]
There are several classes of interior point algorithms that solve linear programming problems in $O(\sqrt nL)$ iterations. Among them, several potential
reduction algorithms combine both theoretical ($O(\sqrt nL)$ iterations) and practical efficiency as they allow the flexibility of line searches in the potential
function, and thus can lead to practical implementations. It is a significant open question whether interior point algorithms can lead to better complexity
bounds. In the present paper, we give some negative answers to this question for the class of potential reduction algorithms. We show that, even if we
allow line searches in the potential function, and even for problems that have network structure, the bound $O(\sqrt nL)$ is tight for several potential
reduction algorithms, i.e., there is a class of examples with network structure, in which the algorithms need at least $\Omega(\sqrt nL)$ iterations to find an
optimal solution.
Zbl 0894.90112
Vera, Jorge R.
On the complexity of linear programming under finite precision arithmetic. (English)
[J] Math. Program. 80, No.1(A), 91-123 (1998). [ISSN 0025-5610]
We study the complexity of solving linear programs in finite precision arithmetic. This is the normal setup in scientific computation, as digital computers work
in finite precision. We analyze two aspects of the complexity: one is the number of arithmetic operations required to solve the problem approximately, and
the other is the working precision required to carry out some critical computations safely. We show how the ``conditioning'' of the problem instance affects
the working precision required and the computational requirements of a classical logarithmic barrier algorithm to approximate the optimal value of the
problem within a given tolerance. Our results show that these complexity measures depend linearly on the logarithm of a certain condition measure. We
carry out the analysis by looking at how well Newton's method can follow the central trajectory of the feasible set, and computing error bounds in terms of
the condition measure. These results can be interpreted as a theoretical indication of ``good'' numerical behavior of the logarithmic barrier method, in the
sense that a problem instance ``twice as hard'' as the other from the numerical point of view, requires only at most twice as much precision to be solved.
hth
peter
.
- References:
- complexity of LP
- From: Steve Borbash
- complexity of LP
- Prev by Date: Re: Second derivate of at determint det(A(t))
- Next by Date: Re: How can we find (approximatly) pricipal component without explicit calculating covariance matrix ?
- Previous by thread: complexity of LP
- Next by thread: Second derivate of at determint det(A(t))
- Index(es):
Relevant Pages
|
