A Semidefinite Programming Approach for the Nearest Correlation Matrix Problem

The nearest \cm\ problem is to find a positive semidefinite matrix with unit diagonal that is nearest in the Frobenius norm to a given symmetric matrix $A$. This problem can be formulated as an optimization problem with a quadratic objective function and semidefinite programming constraints. Using such a formulation, we derive and test a primal-dual … Read more

A masked spectral bound for maximum-entropy sampling

We introduce a new masked spectral bound for the maximum-entropy sampling problem. This bound is a continuous generalization of the very effective spectral partition bound. Optimization of the masked spectral bound requires the minimization of a nonconvex, nondifferentiable function over a semidefiniteness constraint. We describe a nonlinear affine scaling algorithm to approximately minimize the bound. … Read more

Decomposition and Dynamic Cut Generation in Integer Linear Programming

Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen the linear programming relaxation. Recently, a number of … Read more

A hybrid multistart heuristic for the uncapacitated facility location problem

We present a multistart heuristic for the uncapacitated facility location problem, based on a very successful method we originally developed for the P-median problem. We show extensive empirical evidence to the effectiveness of our algorithm in practice. For most benchmarks instances in the literature, we obtain solutions that are either optimal or a fraction of … Read more

An Exact Algorithm for the Capacitated Vertex p-Center Problem

We develop a simple and practical exact algorithm for the problem of locating $p$ facilities and assigning clients to them within capacity restrictions in order to minimize the maximum distance between a client and the facility to which it is assigned (capacitated $p$-center). The algorithm iteratively sets a maximum distance value within which it tries … Read more

An Algorithm for Degenerate Nonlinear Programming with Rapid Local Convergence

The paper describes and analyzes an algorithmic framework for solving nonlinear programming problems in which strict complementarity conditions and constraint qualifications are not necessarily satisfied at a solution. The framework is constructed from three main algorithmic ingredients. The first is any conventional method for nonlinear programming that produces estimates of the Lagrange multipliers at each … Read more

Continuous Line Drawings via the Traveling Salesman Problem

We describe how to use the traveling salesman problem (TSP) to create continuous line drawings of target pictures. Citation Dept. of Mathematics, Oberlin College, Oberlin, Ohio 44074 Article Download View Continuous Line Drawings via the Traveling Salesman Problem

A Comparative Study of New Barrier Functions for Primal-Dual Interior-Point Algorithms in Linear Optimization

Recently, so-called self-regular barrier functions for primal-dual interior-point methods (IPMs) for linear optimization were introduced. Each such barrier function is determined by its (univariate) self-regular kernel function. We introduce a new class of kernel functions. The class is defined by some simple conditions on the kernel function and its derivatives. These properties enable us to … Read more

The structured distance to ill-posedness for conic systems

An important measure of conditioning of a conic linear system is the size of the smallest structured perturbation making the system ill-posed. We show that this measure is unchanged if we restrict to perturbations of low rank. We thereby derive a broad generalization of the classical Eckart-Young result characterizing the distance to ill-posedness for a … Read more