Nonsmooth Optimization

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

    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

    Necessary Optimality Conditions for two-stage Stochastic Programs with Equilibrium Constraints

  • Huifu Xu
  • Jane J. Ye
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    Developing first order optimality conditions for a two-stage stochastic mathematical program with equilibrium constraints (SMPEC) whose second stage problem has multiple equilibria/solutions is a challenging undone work. In this paper we take this challenge by considering a general class of two-stage whose equilibrium constraints are represented by a parametric variational inequality (where the first stage … Read more

    Sparse Signal Reconstruction via Iterative Support Detection

  • Yilun Wang
  • Wotao Yin
    • Categories Applications - Science and Engineering, Convex Optimization, Nonsmooth Optimization Tags , , ,

    We present a novel sparse signal reconstruction method “ISD”, aiming to achieve fast reconstruction and a reduced requirement on the number of measurements compared to the classical l_1 minimization approach. ISD addresses failed reconstructions of l_1 minimization due to insufficient measurements. It estimates a support set I from a current reconstruction and obtains a new … Read more

    Composite Proximal Bundle Method

  • Claudia Sagastizábal
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , ,

    We consider minimization of nonsmooth functions which can be represented as the composition of a positively homogeneous convex function and a smooth mapping. This is a sufficiently rich class that includes max-functions, largest eigenvalue functions, and norm-1 regularized functions. The bundle method uses an oracle that is able to compute separately the function and subgradient … Read more

    An Augmented Lagrangian Approach for Sparse Principal Component Analysis

  • Zhaosong Lu
  • Yong Zhang
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Statistics Tags , , ,

    Principal component analysis (PCA) is a widely used technique for data analysis and dimension reduction with numerous applications in science and engineering. However, the standard PCA suffers from the fact that the principal components (PCs) are usually linear combinations of all the original variables, and it is thus often difficult to interpret the PCs. To … Read more

    A First-Order Smoothed Penalty Method for Compressed Sensing

  • Necdet Serhat Aybat
  • Garud Iyengar
    • Categories Biomedical Applications, Nonsmooth Optimization Tags , , , , ,

    We propose a first-order smoothed penalty algorithm (SPA) to solve the sparse recovery problem min{||x||_1 : Ax=b}. SPA is efficient as long as the matrix-vector product Ax and A^Ty can be computed efficiently; in particular, A need not be an orthogonal projection matrix. SPA converges to the target signal by solving a sequence of penalized … Read more

    Approximating semidefinite packing problems

  • Garud Iyengar
  • Cliff Stein
  • David Phillips
    • Categories Approximation Algorithms, Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    In this paper we define semidefinite packing programs and describe an algorithm to approximately solve these problems. Semidefinite packing programs arise in many applications such as semidefinite programming relaxations for combinatorial optimization problems, sparse principal component analysis, and sparse variance unfolding technique for dimension reduction. Our algorithm exploits the structural similarity between semidefinite packing programs … Read more

    An Approximate Lagrange Multiplier Rule

  • Joydeep Dutta
  • Suvendu Pattanaik
  • Michel Thera
    • Categories Nonsmooth Optimization Tags , , , ,

    In this paper, we show that for a large class of optimization problems, the Lagrange multiplier rule can be derived from the so-called approximate multiplier rule. In establishing the link between the approximate and the exact multiplier rule we first derive an approximate multiplier rule for a very general class of optimization problems using the … Read more

    Stochastic Nash Equilibrium Problems: Sample Average Approximation and Applications

  • Huifu Xu
  • Dali Zhang
    • Categories Game Theory, Nonsmooth Optimization, Stochastic Programming Tags , , ,

    This paper presents a Nash equilibrium model where the underlying objective functions involve uncertainty and nonsmoothness. The well known sample average approximation method is applied to solve the problem and the first order equilibrium conditions are characterized in terms of Clarke generalized gradients. Under some moderate conditions, it is shown that with probability one, a … Read more