ISSN:
1436-4646
Schlagwort(e):
Potential reduction algorithm
;
linear complementarity problem
;
interior point algorithm
;
Karmarkar's algorithm
;
path of centers
;
central trajectory
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract This paper proposes an interior point algorithm for a positive semi-definite linear complementarity problem: find an (x, y)∈ℝ 2n such thaty=Mx+q, (x,y)⩾0 andx T y=0. The algorithm reduces the potential function $$f(x,y) = (n + \sqrt n )\log x^T y - \sum\limits_{i = 1}^n {\log x_i y_i } $$ by at least 0.2 in each iteration requiring O(n 3) arithmetic operations. If it starts from an interior feasible solution with the potential function value bounded by $$O(\sqrt n L)$$ , it generates, in at most $$O(\sqrt n L)$$ iterations, an approximate solution with the potential function value $$ - O(\sqrt n L)$$ , from which we can compute an exact solution in O(n 3) arithmetic operations. The algorithm is closely related with the central path following algorithm recently given by the authors. We also suggest a unified model for both potential reduction and path following algorithms for positive semi-definite linear complementarity problems.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01594942
Permalink
