Euclidean Distance Matrix Completion Problems

A Euclidean distance matrix is one in which the $(i,j)$ entry specifies the squared distance between particle $i$ and particle $j$. Given a partially-specified symmetric matrix $A$ with zero diagonal, the Euclidean distance matrix completion problem (EDMCP) is to determine the unspecified entries to make $A$ a Euclidean distance matrix. We survey three different approaches … Read more

A Pivoting Algorithm for Linear Programming with Linear Complementarity Constraints

We present a pivoting algorithm for solving linear programs with linear complementarity constraints. Our method generalizes the simplex method for linear programming to deal with complementarity conditions. We develop an anticycling scheme that can verify Bouligand stationarity. We also give an optimization-based technique to find an initial feasible vertex. Starting with a feasible vertex, our … Read more

Modified Cholesky Algorithms: A Catalog with New Approaches

Given an n by n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A+E, where E is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much … Read more