Robert M. Freund We present new results for the conditional gradient method (also known as the Frank-Wolfe method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial … Read more
In this paper, we consider the optimal design of photonic crystal band structures for two-dimensional square lattices. The mathematical formulation of the band gap optimization problem leads to an infinite-dimensional Hermitian eigenvalue optimization problem parametrized by the dielectric material and the wave vector. To make the problem tractable, the original eigenvalue problem is discretized using … Read more
Consider the following supposedly-simple problem: “compute x \in S” where S is a convex set conveyed by a separation oracle, with no further information (e.g., no bounding ball containing or intersecting S, etc.). Our interest in this problem stems from fundamental issues involving the interplay of computational complexity, the geometry of S, and the stability … Read more
For a conic linear system of the form Ax \in K, K a convex cone, several condition measures have been extensively studied in the last dozen years. Herein we show that Renegar’s condition number is bounded from above and below by certain purely geometric quantities associated with A and K, and highlights the role of … Read more
We study the second-order feasibility cone F = { y : \| My \| \le g^Ty } for given data (M,g). We construct a new representation for this cone and its dual based on the spectral decomposition of the matrix M^TM – gg^T. This representation is used to efficiently solve the problem of projecting an … Read more
The classical perceptron algorithm is an elementary row-action/relaxation algorithm for solving a homogeneous linear inequality system Ax > 0. A natural condition measure associated with this algorithm is the Euclidean width t of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/t^2, see Rosenblatt 1962. Dunagan and … Read more
We present a general theory for transforming a homogeneous conic system F: Ax = 0, x \in C, x \ne 0, to an equivalent system via projective transformation induced by the choice of a point in a related dual set. Such a projective transformation serves to pre-condition the conic system into a system that has … Read more
We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the … Read more
There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model’s behavior are precisely controlled independent of the problem instance: (i) the sizes of epsilon-optimal solutions, and (ii) the maximum distance of epsilon-optimal solutions to the … Read more
Given a convex body S and a point x \in S, let sym(x,S) denote the symmetry value of x in S: sym(x,S):= max{t : x + t(x – y) \in S for every y \in S}, which essentially measures how symmetric S is about the point x, and define sym(S):=\max{sym(x,S) : x \in S }. … Read more