Robert M. Freund

New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure

  • Robert M. Freund
  • Haihao Lu
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem f^* = \min_{x \in Q} f(x), where we presume knowledge of a strict lower bound f_slb < f^*. [Indeed, f_slb is naturally ... Read more

    A New Perspective on Boosting in Linear Regression via Subgradient Optimization and Relatives

  • Robert M. Freund
  • Rahul Mazumder
  • Paul Grigas
    • Categories Data-Mining, Nonsmooth Optimization, Statistics Tags , , , ,

    In this paper we analyze boosting algorithms in linear regression from a new perspective: that of modern first-order methods in convex optimization. We show that classic boosting algorithms in linear regression, namely the incremental forward stagewise algorithm (FS-epsilon) and least squares boosting (LS-Boost-epsilon), can be viewed as subgradient descent to minimize the loss function defined … Read more

    Fabrication-Adaptive Optimization, with an Application to Photonic Crystal Design

  • Robert M. Freund
  • Han Men
  • Ngoc-Cuong Nguyen
  • Jaime Peraire
  • Joel Saa-Seoane
    • Categories Basic Sciences Applications, Optimization of Systems modeled by PDEs, Robust Optimization Tags , , ,

    It is often the case that the computed optimal solution of an optimization problem cannot be implemented directly, irrespective of data accuracy, due to either (i) technological limitations (such as physical tolerances of machines or processes), (ii) the deliberate simplification of a model to keep it tractable (by ignoring certain types of constraints that pose … Read more

    New Analysis and Results for the Conditional Gradient Method

  • Robert M. Freund
  • Paul Grigas
    • Categories Convex Optimization Tags , , , ,

    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

    Band Gap Optimization of Two-Dimensional Photonic Crystals Using Semidefinite Programming and Subspace Methods

  • Robert M. Freund
  • Han Men
  • Ngoc-Cuong Nguyen
  • Pablo A. Parrilo
  • Jaime Peraire
    • Categories Optimization of Systems modeled by PDEs, Semi-definite Programming Tags , ,

    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

    Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model

  • Robert M. Freund
  • Jorge Vera
    • Categories Convex Optimization Tags , , , ,

    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

    A Geometric Analysis of Renegar’s Condition Number, and its interplay with Conic Curvature

  • Alexandre Belloni
  • Robert M. Freund
    • Categories Linear, Cone and Semidefinite Programming

    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

    On the Second-Order Feasibility Cone: Primal-Dual Representation and Efficient Projection

  • Alexandre Belloni
  • Robert M. Freund
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    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

    An Efficient Re-scaled Perceptron Algorithm for Conic Systems

  • Alexandre Belloni
  • Robert M. Freund
  • Santosh Vempala
    • Categories Linear, Cone and Semidefinite Programming

    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

    Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System

  • Alexandre Belloni
  • Robert M. Freund
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    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