|
|
|
|
|
 |
Search published articles |
 |
|
Showing 3 results for Polynomial Complexity
Mansouri, Siyavash, Zangiabadi,
Volume 3, Issue 1 (4-2012)
Abstract
We present a new algorithm obtained by changing the search directions in the algorithm given in [8]. This algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only the full Nesterov-Todd (NT)step. Moreover, we obtain the currently best known iteration bound for the infeasible interior-point algorithms with full NT steps, namely O(nlogn/e) , which is as good as the linear analogue.
Bai, Lesaja, Mansouri, Roos, Zangiabadi,
Volume 3, Issue 2 (9-2012)
Abstract
Many efficient interior-point methods (IPMs) are based on the use of a self-concordant barrier function for the domain of the problem that has to be solved. Recently, a wide class of new barrier functions has been introduced in which the functions are not self-concordant, but despite this fact give rise to efficient IPMs. Here, we introduce the notion of locally self-concordant barrier functions and we prove that the new barrier functions are locally self-concordant. In many cases, the (local) complexity numbers of the new barrier functions along the central path are better than the complexity number of the logarithmic barrier function by a factor between 0.5 and 1.
Dr. Behrouz Kheirfam,
Volume 6, Issue 2 (9-2015)
Abstract
In this paper, we propose an arc-search corrector-predictor
interior-point method for solving $P_*(kappa)$-linear
complementarity problems. The proposed algorithm searches the
optimizers along an ellipse that is an approximation of the central
path. The algorithm generates a sequence of iterates in the wide
neighborhood of central path introduced by Ai and Zhang. The
algorithm does not depend on the handicap $kappa$ of the problem,
so that it can be used for any $P_*(kappa)$-linear complementarity
problem. Based on the ellipse approximation of the central path and
the wide neighborhood, we show that the proposed algorithm has
$O((1+kappa)sqrt{n}L)$ iteration complexity, the best-known
iteration complexity obtained so far by any interior-point method
for solving $P_*(kappa)$-linear complementarity problems.
|
|
|
|
|
|
|
|
|
