Two properties of condition numbers for convex programs via implicitly defined barrier functions

We study two issues on condition numbers for convex programs: one has to do with the growth of the condition numbers of the linear equations arising in interior-point algorithms; the other deals with solving conic systems and estimating their distance to infeasibility. These two issues share a common ground: the key tool for their development … Read more

Generating Convex Polynomial Inequalities for Mixed 0-1 Programs

We develop a method for generating valid convex polynomial inequalities for mixed 0-1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities. Article Download View Generating Convex … Read more

Improved linear programming bounds for antipodal spherical codes

Let $S\subset[-1,1)$. A finite set $C=\{x_i\}_{i=1}^M\subset\Re^n$ is called a {\em spherical S-code} if $||x_i||=1$ for each $i$, and $x_i^T x_j\in S$, $i\ne j$. For $S=[-1,.5]$ maximizing $M=|C|$ is commonly referred to as the {\em kissing number} problem. A well-known technique based on harmonic analysis and linear programming can be used to bound $M$. We consider … Read more

Slice Models in General Purpose Modeling Systems

Slice models are collections of mathematical programs with the same structure but different data. Examples of slice models appear in Data Envelopment Analysis, where they are used to evaluate efficiency, and cross-validation, where they are used to measure generalization ability. Because they involve multiple programs, slice models tend to be data-intensive and time consuming to … Read more

Constraint Identification and Algorithm Stabilization for Degenerate Nonlinear Programs

In the vicinity of a solution of a nonlinear programming problem at which both strict complementarity and linear independence of the active constraints may fail to hold, we describe a technique for distinguishing weakly active from strongly active constraints. We show that this information can be used to modify the sequential quadratic programming algorithm so … Read more

On implementing a primal-dual interior-point method for conic quadratic optimization

Conic quadratic optimization is the problem of minimizing a linear function subject to the intersection of an affine set and the product of quadratic cones. The problem is a convex optimization problem and has numerous applications in engineering, economics, and other areas of science. Indeed, linear and convex quadratic optimization is a special case. Conic … Read more

A Family of Facets for the p-Median Polytope

We present a nontrivial family of facet-defining inequalities for the p-median polytope. We incorporate the inequalities in a branch-and-cut scheme, and we report computational results that demonstrate their effectiveness. Citation Department of Industrial Engineering, State University of New York at Buffalo, submitted Article Download View A Family of Facets for the p-Median Polytope

Facets of the Complementarity Knapsack Polytope

We present a polyhedral study of the complementarity knapsack problem, in which no auxiliary binary variables are introduced, but rather the inequalities are derived in the space of the continuous variables. Citation School of Industrial and Systems Engineering, GA Tech, under review Article Download View Facets of the Complementarity Knapsack Polytope

A Family of Inequalities for the Generalized Assignment Polytope

We present a family of inequalities that are valid for the generalized assignment polytope. Although the inequalities are not facet-defining in general, they define facets of a polytope of a relaxation. We report computational results on the use of the inequalities in a branch-and-cut scheme that demonstrate their effectiveness. Citation Department of Industrial Engineering, State … Read more

Optimization on Computational Grids

We define the concept of a computational grid, and describe recent work in solving large and complex optimization problems on this type of platform; in particular, integer programming, the quadratic assignment problem, and stochastic programming problems. This article focuses on work conducted in the metaneos project. Citation Preprint, Mathematics and Computer Science Division, Argonne National … Read more