The dual face algorithm uses Cholesky factorization, as would be not very suitable for sparse computations. The purpose of this paper is to present a dual face algorithm using Gauss-Jordan elimination for solving bounded-variable LP problems. Article Download View Dual Face Algorithm Using Gauss-Jordan Elimination for Linear Programming
Quantifying the risk of unfortunate events occurring, despite limited distributional information, is a basic problem underlying many practical questions. Indeed, quantifying constraint violation probabilities in distributionally robust programming or judging the risk of financial positions can both be seen to involve risk quantification, notwithstanding distributional ambiguity. In this work we discuss worst-case probability and conditional … Read more
In this paper we consider a mathematical program with second-order cone complementarity constraints (SOCMPCC). The SOCMPCC generalizes the mathematical program with complementarity constraints (MPCC) in replacing the set of nonnegative reals by a second-order cone. We show that if the SOCMPCC is considered as an optimization problem with convex cone constraints, then Robinson’s constraint qualification … Read more
Zhang et al recently propose another approach to the face algorithm. This note gives a modification of the result. Article Download View ON ON AN EFFICIENT IMPLEMENTATION OF THE FACE ALGORITHM FOR LINEAR PROGRAMMING''
We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (i) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (ii) computing real-time certificates of collision avoidance for a simple model of … Read more
We focus on a family of quantum coin-flipping protocols based on quantum bit-commitment. We discuss how the semidefinite programming formulations of cheating strategies can be reduced to optimizing a linear combination of fidelity functions over a polytope. These turn out to be much simpler semidefinite programs which can be modelled using second-order cone programming problems. … Read more
We show that the independence polytope of every regular matroid has an extended formulation of size quadratic in the size of its ground set. This generalizes a similar statement for (co-)graphic matroids, which is a simple consequence of Martin’s extended formulation for the spanning-tree polytope. In our construction, we make use of Seymour’s decomposition theorem … Read more
We show that for any positive integer $d$, there are families of switched linear systems—in fixed dimension and defined by two matrices only—that are stable under arbitrary switching but do not admit (i) a polynomial Lyapunov function of degree $\leq d$, or (ii) a polytopic Lyapunov function with $\leq d$ facets, or (iii) a piecewise … Read more
It has been an open question whether the Linear Programming (LP) problem can be solved in strong polynomial time. The simplex algorithm does not offer a polynomial bound, and polynomial algorithms by Khachiyan and Karmarkar don’t have the strong characteristic. The curious fact that non-linear algorithms would be needed to deliver the strongest complexity result … Read more
We consider several semidefinite programming relaxations for the max-$k$-cut problem, with increasing complexity. The optimal solution of the weakest presented semidefinite programming relaxation has a closed form expression that includes the largest Laplacian eigenvalue of the graph under consideration. This is the first known eigenvalue bound for the max-$k$-cut when $k>2$ that is applicable to … Read more