The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal … Read more
In this paper, ellipse is used to approximate the central path of the linear programming. An interior-point algorithm is devised to search the optimizers along the ellipse. The algorithm is proved to be polynomial with the complexity bound $O(n^{\frac{1}{2}}\log(1/\epsilon))$. Numerical test is conducted for problems in Netlib. For most tested Netlib problems, the result shows … Read more
We study the interactions between computational and economic performance of dispatch operations under highly dynamic environments. In particular, we discuss the need for extending the forecast horizon of the dispatch formulation in order to anticipate steep variations of renewable power and highly elastic loads. We present computational strategies to solve the increasingly larger optimization problems … Read more
In 1951, Dantzig showed the equivalence of linear programming and two-person zero-sum games. However, in the description of his reduction from linear programming to zero-sum games, he noted that there was one case in which his reduction does not work. This also led to incomplete proofs of the relationship between the Minmax Theorem of game … Read more
In this paper, we study polynomial-time interior-point algorithms in view of information geometry. We introduce an information geometric structure for a conic linear program based on a self-concordant barrier function. Riemannian metric is defined with the Hessian of the barrier function. We introduce two connections $\nabla$ and $\nabla^*$ which roughly corresponds to the primal and … Read more
The L1 norm has been applied in numerous variations of principal component analysis (PCA). L1-norm PCA is an attractive alternative to traditional L2-based PCA because it can impart robustness in the presence of outliers and is indicated for models where standard Gaussian assumptions about the noise may not apply. Of all the previously-proposed PCA schemes … Read more
In this paper we present a redesign of a linear algebra kernel of an interior point method to avoid the explicit use of problem matrices. The only access to the original problem data needed are the matrix-vector multiplications with the Hessian and Jacobian matrices. Such a redesign requires the use of suitably preconditioned iterative methods … Read more
We present a number of new algorithmic ideas for solving LP relaxations of extremely large precedence constrained production scheduling problems. These ideas are used to develop an implementation that is tested on a variety of real-life, large scale instances; yielding optimal solutions in very practicable CPU time. CitationUnpublished. Columbia University, BHP Billiton, August 2009.ArticleDownload View … Read more
Arc-search is developed in optimization algorithms. In this paper, simple analytic arcs are used to approximate the central path of the linear programming. The primal-dual path-following interior-point method is then used to search optimizers along the arcs for linear programming. They require fewer iterations to find the optimal solutions in all the tested problems in … Read more
The Farkas Lemma is extended to simultaneous linear operator and polyhedral sublinear operator inequalities by Boolean valued analysis. CitationSobolev Institute of Mathematics, Novosibirsk, 630090 RussiaArticleDownload View PDF