This article considers continuous trajectories of the vector fields induced by primal-dual potential-reduction algorithms for solving linear programming problems. It is known that these trajectories converge to the analytic center of the primal-dual optimal face. We establish that this convergence may be tangential to the central path, tangential to the optimal face, or in between, … Read more
Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more
We consider primal-dual algorithms for certain types of infinite-dimensional optimization problems. Our approach is based on the generalization of the technique of finite-dimensional Euclidean Jordan algebras to the case of infinite-dimensional JB-algebras of finite rank. This generalization enables us to develop polynomial-time primal-dual algorithms for “infinite-dimensional second-order cone programs.” We consider as an example a … Read more
This paper presents the new concept of second-order cone approximations for convex conic programming. Given any open convex cone $K$, a logarithmically homogeneous self-concordant barrier for $K$ and any positive real number $r \le 1$, we associate, with each direction $x \in K$, a second-order cone $\hat K_r(x)$ containing $K$. We show that $K$ is … Read more
The paper studies and designs an genetic algorithm (GA) of the bilevel linear programming problem (BLPP) by constructing the fitness function of the upper-level programming problem based on the definition of the feasible degree. This GA avoids the use of penalty function to deal with the constraints, by changing the randomly generated initial population into … Read more
The purpose of this paper is to extend, as much as possible, the modern theory of condition numbers for conic convex optimization: z_* := min_x {c’x | Ax-b \in C_Y, x \in C_X }, to the more general non-conic format: (GP_d): z_* := min_x {c’x | Ax-b \in C_Y, x \in P}, where P is … Read more
The Watson Sparse Matrix Package (WSMP) is a high-performance robust direct solver for both symmetric and unsymmetric large sparse systems of linear equations. Currently, it works in serial, multi-threaded parallel, message-passing parallel, and a combination of message-passing and multi-threaded modes on IBM RS6000 with AIX and IA32 with Linux. The symmetric solver has features to … Read more
This paper presents an annotated bibliography on interior point methods for solving network flow problems. We consider single and multi-commodity network flow problems, as well as preconditioners used in implementations of conjugate gradient methods for solving the normal systems of equations that arise in interior network flow algorithms. Applications in electrical engineering and miscellaneous papers … Read more
We study interior-point methods for optimization problems in the case of infeasibility or unboundedness. While many such methods are designed to search for optimal solutions even when they do not exist, we show that they can be viewed as implicitly searching for well-defined optimal solutions to related problems whose optimal solutions give certificates of infeasibility … Read more
We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar’s interior-point algorithm by Dunagan, Spielman and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/\sigma ))$. In contrast, the best known bound … Read more