In this paper we present a scaling-invariant interior-point predictor-corrector type algorithm for linear programming (LP) whose iteration-complexity is polynomially bounded by the dimension and the logarithm of a certain condition number of the LP constraint matrix. At the predictor stage, the algorithm either takes the step along the standard affine scaling direction or a new … Read more
We consider the problem of finding an $\epsilon-$optimal solution of a standard linear program with real data, i.e., of finding a feasible point at which the objective function value differs by at most $\epsilon$ from the optimal value. In the worst-case scenario the best complexity result to date guarantees that such a point is obtained … Read more
In this paper we devise a new version of primal simplex algorithms in which the classical iteration is decomposed two basic operations: the move and the pivot. The move operation decreases the primal objective value and the pivot operation increases the dual objective. We define the condition number of the pivot operation and present a … Read more
We provide explicit sufficient conditions for a polynomial $f$ to be a sum of squares (s.o.s.), linear in the coefficients of $f$. All conditions are simple and provide an explicit description of a convex polyhedral subcone of the cone of s.o.s. polynomials of degree at most $2d$. We also provide a simple condition to ensure … 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
A new initialization or `Phase I’ strategy for feasible interior point methods for linear programming is proposed that computes a point on the primal-dual central path associated with the linear program. Provided there exist primal-dual strictly feasible points — an all-pervasive assumption in interior point method theory that implies the existence of the central path … Read more
We propose an approach to the classical newsvendor problem and its extensions subject to uncertain demand that: (a) works directly with data, i.e., combines historical data and optimization in a single framework, (b) yields robust solutions and incorporates risk preferences using one scalar parameter, rather than utility functions, (c) allows for tractable formulations, specifically, linear … Read more
By introducing redundant Klee-Minty examples, we have previously shown that the central path can be bent along the edges of the Klee-Minty cubes, thus having $2^n-2$ sharp turns in dimension $n$. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler … Read more
We describe a method of generating a warm-start point for interior point methods in the context of stochastic programming. Our approach exploits the structural information of the stochastic problem so that it can be seen as a structure-exploiting initial point generator. We solve a small-scale version of the problem corresponding to a reduced event tree … Read more
We consider a family of linear optimization problems over the n-dimensional Klee-Minty cube and show that the central path may visit all of its vertices in the same order as simplex methods do. This is achieved by carefully adding an exponential number of redundant constraints that forces the central path to take at least 2^n-2 … Read more