Convex Optimization

A Fixed-Point Continuation Method for l_1-Regularized Minimization with Applications to Compressed Sensing

  • Elaine Hale
  • Wotao Yin
  • Yin Zhang
    • Categories Applications - Science and Engineering, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We consider solving minimization problems with $\ell_1$-regularization: $$\min \|x\|_1 + \mu f(x),$$ particularly for $f(x) = \frac{1}{2}\|Ax-b\|_M^2$ where $A \in \R^{m \times n}$ with $m < n$. Our goal is to construct efficient and robust algorithms for solving large-scale problems with dense data, and our approach is based on two powerful algorithmic ideas, operator-splitting and ... Read more

    A gradient-based approach for computing Nash equilibria of large sequential games

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

    We propose a new gradient based scheme to approximate Nash equilibria of large sequential two-player, zero-sum games. The algorithm uses modern smoothing techniques for saddle-point problems tailored specifically for the polytopes used in the Nash equilibrium problem. CitationWorking Paper, Tepper School of Business, Carnegie Mellon UniversityArticleDownload View PDF

    In pursuit of a root

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

    The basis pursuit technique is used to find a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise fits the least-squares problem only approximately, and a single parameter determines a curve that traces the trade-off between the least-squares fit and the one-norm of the solution. We show that the function that describes this … Read more

    Semidefinite Representation of Convex Sets

  • J. William Helton
  • Jiawang Nie
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , , , , , , , , , ,

    Let $S =\{x\in \re^n:\, g_1(x)\geq 0, \cdots, g_m(x)\geq 0\}$ be a semialgebraic set defined by multivariate polynomials $g_i(x)$. Assume $S$ is convex, compact and has nonempty interior. Let $S_i =\{x\in \re^n:\, g_i(x)\geq 0\}$, and $\bdS$ (resp. $\bdS_i$) be the boundary of $S$ (resp. $S_i$). This paper, as does the subject of semidefinite programming (SDP), concerns … Read more

    An iterative approach for cone complementarity problems for nonsmooth multibody dynamics

  • Mihai Anitescu
  • Alessandro Tasora
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Mechanical Engineering

    Aiming at a fast and robust simulation of large multibody systems with contacts and friction, this work presents a novel method for solving large cone complementarity problems by means of a fixed-point iteration. The method is an extension of the Gauss-Seidel and Gauss-Jacobi method with overrelaxation for symmetric convex linear complementarity problems. The method is … Read more

    Convex duality and entropy-based moment closure: Characterizing degenerate densities

  • Cory D. Hauck
  • C. David Levermore
  • André L. Tits
    • Categories Convex Optimization, Infinite Dimensional Optimization Tags , , , , , ,

    A common method for constructing a function from a finite set of moments is to solve a constrained minimization problem. The idea is to find, among all functions with the given moments, that function which minimizes a physically motivated, strictly convex functional. In the kinetic theory of gases, this functional is the kinetic entropy; the … Read more

    The kernel average for two convex functions and its application to the extension and representation of monotone operators

  • Heinz Bauschke
  • Xianfu Wang
    • Categories Convex Optimization Tags , , , , , , , , ,

    We provide and analyze a based average for two convex functions, based on a kernel function. It covers several known averages such as the arithmetic average, epigraphical average, and the proximal average. When applied to the Fitzpatrick function and the conjugate of Fitzpatrick function associated with a monotone operator, our average produces an autoconjugate (also … Read more

    Two Algorithms for the Minimum Enclosing Ball Problem

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

    Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$ and $\eps > 0$, we propose and analyze two algorithms for the problem of computing a $(1 + \eps)$-approximation to the radius of the minimum enclosing ball of $\cA$. The first algorithm is closely related to the Frank-Wolfe algorithm with a proper initialization applied to the dual formulation of … Read more

    An Augmented Primal-Dual Method for Linear Conic Programs

  • Florian Jarre
  • Franz Rendl
    • Categories Convex Optimization Tags , ,

    We propose a new iterative approach for solving linear programs over convex cones. Assuming that Slaters condition is satisfied, the conic problem is transformed to the minimization of a convex differentiable function. This “agumented primal-dual function” or “apd-function” is restricted to an affine set in the primal-dual space. The evaluation of the function and its … Read more

    Approximate Primal Solutions and Rate Analysis in Dual Subgradient Methods

  • Angelia Nedich
  • Asuman Ozdaglar
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    We study primal solutions obtained as a by-product of subgradient methods when solving the Lagrangian dual of a primal convex constrained optimization problem (possibly nonsmooth). The existing literature on the use of subgradient methods for generating primal optimal solutions is limited to the methods producing such solutions only asymptotically (i.e., in the limit as the … Read more