## Analysis of Copositive Optimization Based Linear Programming Bounds on Standard Quadratic Optimization

The problem of minimizing a quadratic form over the unit simplex, referred to as a standard quadratic optimization problem, admits an exact reformulation as a linear optimization problem over the convex cone of completely positive matrices. This computationally intractable cone can be approximated from the inside and from the outside by two sequences of nested … Read more

## Numerical Optimization of Eigenvalues of Hermitian Matrix Functions

The eigenvalues of a Hermitian matrix function that depends on one parameter analytically can be ordered so that each eigenvalue is an analytic function of the parameter. Ordering these analytic eigenvalues from the largest to the smallest yields continuous and piece-wise analytic functions. For multi-variate Hermitian matrix functions that depend on $d$ parameters analytically, the … Read more

## On the Accuracy of Uniform Polyhedral Approximations of the Copositive Cone

We consider linear optimization problems over the cone of copositive matrices. Such conic optimization problems, called {\em copositive programs}, arise from the reformulation of a wide variety of difficult optimization problems. We propose a hierarchy of increasingly better outer polyhedral approximations to the copositive cone. We establish that the sequence of approximations is exact in … Read more

## A Linearly Convergent Linear-Time First-Order Algorithm for Support Vector Classification with a Core Set Result

We present a simple, first-order approximation algorithm for the support vector classification problem. Given a pair of linearly separable data sets and $\epsilon \in (0,1)$, the proposed algorithm computes a separating hyperplane whose margin is within a factor of $(1-\epsilon)$ of that of the maximum-margin separating hyperplane. We discuss how our algorithm can be extended … Read more

## Identification and Elimination of Interior Points for the Minimum Enclosing Ball Problem

Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$, we consider the problem of reducing the input set for the computation of the minimum enclosing ball of $\cA$. In this note, given an approximate solution to the minimum enclosing ball problem, we propose a simple procedure to identify and eliminate points in $\cA$ that are guaranteed to lie … Read more