Convex and Nonsmooth Optimization

Alternating directions based contraction method for generally separable linearly constrained convex programming problems

  • Bingsheng He
  • Xiao-Ming Yuan
  • Min Tao
  • Minghua Xu
    • Categories Convex Optimization Tags , , , ,

    The classical alternating direction method (ADM) has been well studied in the context of linearly constrained convex programming problems and variational inequalities where both the involved operators and constraints are separable into two parts. In particular, recentness has witnessed a number of novel applications arising in diversified areas (e.g. Image Processing and Statistics), for which … Read more

    Alternating direction algorithms for total variation deconvolution in image reconstruction

  • Tao Min
  • Junfeng Yang
    • Categories Convex Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    Image restoration and reconstruction from blurry and noisy observation is known to be ill-posed. To stabilize the recovery, total variation (TV) regularization was introduced by Rudin, Osher and Fatemi in \cite{LIR92}, which has demonstrated superiority in preserving image edges. However, the nondifferentiability of TV makes the underlying optimization problems difficult to solve. In this paper, … Read more

    Local superlinear convergence of polynomial-time interior-point methods for hyperbolic cone optimization problems

  • Yurii Nesterov
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper, we establish the local superlinear convergence property of some polynomial-time interior-point methods for an important family of conic optimization problems. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier function, which must have {\em negative curvature}. We propose a new path-following predictor-corrector scheme, which work only … Read more

    A Facial Reduction Algorithm for Finding Sparse SOS Representations

  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , ,

    Facial reduction algorithm reduces the size of the positive semidefinite cone in SDP. The elimination method for a sparse SOS polynomial ([3]) removes unnecessary monomials for an SOS representation. In this paper, we establish a relationship between a facial reduction algorithm and the elimination method for a sparse SOS polynomial. Citation Technical Report CS-09-02, Department … Read more

    PARNES: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

  • Ming Gu
  • Lek-Heng Lim
  • Cinna Julie Wu
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Optimization Software Benchmark Tags , , , , , , ,

    In this article we propose an algorithm, NESTA-LASSO, for the LASSO problem (i.e., an underdetermined linear least-squares problem with a one-norm constraint on the solution) that exhibits linear convergence under the restricted isometry property (RIP) and some other reasonable assumptions. Inspired by the state-of-the-art sparse recovery method, NESTA, we rely on an accelerated proximal gradient … Read more

    Sparse and Low-Rank Matrix Decomposition Via Alternating Direction Methods

  • Junfeng Yang
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , ,

    The problem of recovering the sparse and low-rank components of a matrix captures a broad spectrum of applications. Authors in [4] proposed the concept of “rank-sparsity incoherence” to characterize the fundamental identifiability of the recovery, and derived practical sufficient conditions to ensure the high possibility of recovery. This exact recovery is achieved via solving a … Read more

    On closedness conditions, strong separation, and convex dualit y

  • Miklós Ujvári
    • Categories Convex Optimization

    In the paper, we describe various applications of the closedness and duality theorems of [7] and [8]. First, the strong separability of a polyhedron and a linear image of a convex set is characterized. Then,it is shown how stability conditions (known from the generalized Fenchel-Rockafellar duality theory) can be reformulated as closedness conditions. Finally, we … Read more

    Smoothing techniques for solving semidefinite programs with many constraints

  • Michel Baes
  • Michael Bürgisser
    • Categories Nonsmooth Optimization, Semi-definite Programming Tags , ,

    We use smoothing techniques to solve approximately mildly structured semidefinite programs with many constraints. As smoothing techniques require a specific problem format, we introduce an alternative problem formulation that fulfills the structural assumptions. The resulting algorithm has a complexity that depends linearly both on the number of constraints and on the inverse of the accuracy. … Read more

    A Simpler Approach to Matrix Completion

  • Benjamin Recht
    • Categories Convex Optimization, Data-Mining, Statistics Tags , , , , , ,

    This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Candes and Recht, Candes and Tao, and Keshavan, Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular … Read more

    A Unifying Polyhedral Approximation Framework for Convex Optimization

  • Dimitri Bertsekas
  • Huizhen Yu
    • Categories Convex Optimization, Network Optimization Tags , , ,

    We propose a unifying framework for polyhedral approximation in convex optimization. It subsumes classical methods, such as cutting plane and simplicial decomposition, but also includes new methods, and new versions/extensions of old methods, such as a simplicial decomposition method for nondifferentiable optimization, and a new piecewise linear approximation method for convex single commodity network flow … Read more