Recently Chubanov proposed a method which solves homogeneous linear equality systems with positive variables in polynomial time. Chubanov’s method can be considered as a column-wise rescaling procedure. We adapt Chubanov’s method to the von Neumann problem, and so we design a polynomial time column-wise rescaling von Neumann algorithm. This algorithm is the first variant of … Read more
We present an improved version of an infeasible interior-point method for linear optimization published in 2006. In the earlier version each iteration consisted of one so-called infeasibility step and a few – at most three – centering steps. In this paper each iteration consists of only a infeasibility step, whereas the iteration bound improves the … Read more
We present an infeasible primal-dual interior point method for semidefinite optimization problems, making use of constraint reduction. We show that the algorithm is globally convergent and has polynomial complexity, the first such complexity result for primal-dual constraint reduction algorithms for any class of problems. Our algorithm is a modification of one with no constraint reduction … Read more
This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim., 16(4):1110–1136, 2006). We introduce a kernel function in the algorithm. For $p\in[0,1)$, the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, … Read more
In this paper we present an infeasible interior-point algorithm for solving linear optimization problems. This algorithm is obtained by modifying the search direction in the algorithm [C. Roos, A full-Newton step ${O}(n)$ infeasible interior-point algorithm for linear optimization, 16(4) 2006, 1110-1136.]. The analysis of our algorithm is much simpler than that of the Roos’s algorithm … Read more
After a brief introduction to Jordan algebras, we present a primal-dual interior-point algorithm for second-order conic optimization that uses full Nesterov-Todd-steps; no line searches are required. The number of iterations of the algorithm is $O(\sqrt{N}\log ({N}/{\varepsilon})$, where $N$ stands for the number of second-order cones in the problem formulation and $\varepsilon$ is the desired accuracy. … Read more
Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed an efficient primal-dual infeasible interior-point algorithm with full Newton steps for linear optimization problems. In this paper we extend the algorithm to semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence … Read more
It has been shown in various papers that most interior-point algorithms and their analysis can be generalized to semidefinite optimization. This paper presents an extension of the recent variant of Mehrotra’s predictor-corrector algorithm that was proposed by Salahi et al. (2005) for linear optimization problems. Based on the NT (Nesterov and Todd 1997) direction as … Read more
Motivated by a numerical example which shows that a feasible version of Mehrotra’s original predictor-corrector algorithm might be inefficient in practice, Salahi et al., proposed a so-called safeguard based variant of the algorithm that enjoys polynomial iteration complexity while its practical efficiency is preserved. In this paper we analyze the same Mehrotra’s algorithm from a … Read more
The main goals of this paper are to: i) relate two iteration-complexity bounds associated with the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming (LP), and; ii) study the geometrical structure of the central path in the context of LP. The first forementioned iteration-complexity bound is expressed in terms of an integral introduced by Sonnevend, Stoer and … Read more