Convex Optimization

On the behavior of subgradient projections methods for convex feasibility problems in Euclidean spaces

  • Dan Butnariu
  • Yair Censor
  • Ethan Hadar
  • Pini Gurfil
    • Categories Convex Optimization Tags , , ,

    We study some methods of subgradient projections for solving a convex feasibility problem with general (not necessarily hyperplanes or half-spaces) convex sets in the inconsistent case and propose a strategy that controls the relaxation parameters in a specific self-adapting manner. This strategy leaves enough user-flexibility but gives a mathematical guarantee for the algorithm’s behavior in … Read more

    First-order algorithm with (ln(1/\epsilon))$ convergence for $\epsilonhBcequilibrium in two-person zero-sum games

  • Andrew Gilpin
  • Javier F. Peña
  • Tuomas Sandholm
    • Categories Convex Optimization, Game Theory Tags , ,

    We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x\in Q_1} \max_{y\in Q_2} \ip{x}{Ay} = \max_{y\in Q_2} \min_{x\in Q_1} \ip{x}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an $\epsilon$-equilibrium to this min-max problem in $\Oh(\kappa(A) \ln(1/\epsilon))$ first-order iterations, … Read more

    Smoothing techniques for computing Nash equilibria of sequential games

  • Andrew Gilpin
  • Javier F. Peña
  • Samid Hoda
    • Categories Convex Optimization, Game Theory Tags , ,

    We develop first-order smoothing techniques for saddle-point problems that arise in the Nash equilibria computation of sequential games. The crux of our work is a construction of suitable prox-functions for a certain class of polytopes that encode the sequential nature of the games. An implementation based on our smoothing techniques computes approximate Nash equilibria for … Read more

    Duality of ellipsoidal approximations via semi-infinite programming

  • Filiz Gurtuna
    • Categories Convex Optimization, Semi-infinite Programming Tags , , , , , , , , , ,

    In this work, we develop duality of the minimum volume circumscribed ellipsoid and the maximum volume inscribed ellipsoid problems. We present a unified treatment of both problems using convex semi–infinite programming. We establish the known duality relationship between the minimum volume circumscribed ellipsoid problem and the optimal experimental design problem in statistics. The duality results … Read more

    An Algorithm and a Core Set Result for the Weighted Euclidean One-Center Problem

  • Piyush Kumar
  • E. Alper Yildirim
    • Categories Convex Optimization Tags , , ,

    Given ${\cal A} := \{a^1,\ldots,a^m\} \subset \R^n$ with corresponding positive weights ${\cal W} := \{\omega_1,\ldots,\omega_m\}$, the weighted Euclidean one-center problem, which is a generalization of the minimum enclosing ball problem, involves the computation of a point $c_{\cal A} \in \R^n$ that minimizes the maximum weighted Euclidean distance from $c_{\cal A}$ to each point in ${\cal … Read more

    Kernel Support Vector Regression with imprecise output

  • Emilio Carrizosa
  • José F. Gordillo
  • Frank Plastria
    • Categories Convex Optimization, Data-Mining, Quadratic Programming Tags , , ,

    We consider a regression problem where uncertainty affects to the dependent variable of the elements of the database. A model based on the standard epsilon-Support Vector Regression approach is given, where two hyperplanes need to be constructed to predict the interval-valued dependent variable. By using the Hausdorff distance to measure the error between predicted and … Read more

    Probing the Pareto frontier for basis pursuit solutions

  • Michael P. Friedlander
  • Ewout van den Berg
    • Categories Basic Sciences Applications, Convex Optimization Tags , , , , , , ,

    The basis pursuit problem seeks a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise (BPDN) fits the least-squares problem only approximately, and a single parameter determines a curve that traces the optimal trade-off between the least-squares fit and the one-norm of the solution. We prove that this curve is convex and continuously … Read more

    Convex Optimization Methods for Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Ming Yuan
    • Categories Convex Optimization, Nonsmooth Optimization, Statistics Tags , , , , , ,

    In this paper, we study convex optimization methods for computing the trace norm regularized least squares estimate in multivariate linear regression. The so-called factor estimation and selection (FES) method, recently proposed by Yuan et al. [17], conducts parameter estimation and factor selection simultaneously and have been shown to enjoy nice properties in both large and … Read more

    What Shape is your Conjugate? A Survey of Computational Convex Analysis and its Applications

  • Yves Lucet
    • Categories Applications - OR and Management Sciences, Convex Optimization Tags , , , , , ,

    Computational Convex Analysis algorithms have been rediscovered several times in the past by researchers from different fields. To further communications between practitioners, we review the field of Computational Convex Analysis, which focuses on the numerical computation of fundamental transforms arising from convex analysis. Current models use symbolic, numeric, and hybrid symbolic-numeric algorithms. Our objective is … Read more

    Robust Efficient Frontier Analysis with a Separable Uncertainty Model

  • Stephen Boyd
  • Seung-Jean Kim
    • Categories Convex Optimization, Finance and Economics, Robust Optimization Tags , , , , , , ,

    Mean-variance (MV) analysis is often sensitive to model mis-specification or uncertainty, meaning that the MV efficient portfolios constructed with an estimate of the model parameters (i.e., the expected return vector and covariance of asset returns) can give very poor performance for another set of parameters that is similar and statistically hard to distinguish from the … Read more