Convex and Nonsmooth Optimization

Hankel Matrix Rank Minimization with Applications to System Identification and Realization

  • Maryam Fazel
  • Ting Kei Pong
  • Defeng Sun
  • Paul Tseng
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    We introduce a flexible optimization framework for nuclear norm minimization of matrices with linear structure, including Hankel, Toeplitz and moment structures, and catalog applications from diverse fields under this framework. We discuss various first-order methods for solving the resulting optimization problem, including alternating direction methods of multipliers, proximal point algorithms and gradient projection methods. We … Read more

    Mean squared error minimization for inverse moment problems

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Martin Mevissen
    • Categories Convex Optimization, Semi-definite Programming

    We consider the problem of approximating the unknown density $u\in L^2(\Omega,\lambda)$ of a measure $\mu$ on $\Omega\subset\R^n$, absolutely continuous with respect to some given reference measure $\lambda$, from the only knowledge of finitely many moments of $\mu$. Given $d\in\N$ and moments of order $d$, we provide a polynomial $p_d$ which minimizes the mean square error … Read more

    Fast global convergence of gradient methods for high-dimensional statistical recovery

  • Alekh Agarwal
  • Martin J Wainwright
  • Sahand Negahban
    • Categories Convex Optimization, Statistics Tags , ,

    Many statistical $M$-estimators are based on convex optimization problems formed by the combination of a data-dependent loss function with a norm-based regularizer. We analyze the convergence rates of projected gradient and composite gradient methods for solving such problems, working within a high-dimensional framework that allows the data dimension $\pdim$ to grow with (and possibly exceed) … Read more

    Erratum to: On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets” [Optim. Letters, 2012]

  • Peter J.C. Dickinson
  • Gabriele Eichfelder
  • Janez Povh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper, an erratum is provided to the article “\emph{On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets}”, published in Optim.\ Letters, 2012. Due to precise observation of the first author, it has been found that the proof of Lemma 9 has a nontrivial gap, and consequently the main result (Theorem … Read more

    On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers

  • Wei Deng
  • Wotao Yin
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    The formulation min f(x)+g(y) subject to Ax+By=b, where f and g are extended-value convex functions, arises in many application areas such as signal processing, imaging and image processing, statistics, and machine learning either naturally or after variable splitting. In many common problems, one of the two objective functions is strictly convex and has Lipschitz continuous … Read more

    A Fair, Sequential Multiple Objective Optimization Algorithm

  • Can Kizilkale
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Game Theory Tags , ,

    In multi-objective optimization the objective is to reach a point which is Pareto ecient. However we usually encounter many such points and choosing a point amongst them possesses another problem. In many applications we are required to choose a point having a good spread over all objective functions which is a direct consequence of the … Read more

    A Newton’s method for the continuous quadratic knapsack problem

  • Roberto Cominetti
  • Walter F. Mascarenhas
  • Paulo J. S. Silva
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    We introduce a new efficient method to solve the continuous quadratic knapsack problem. This is a highly structured quadratic program that appears in different contexts. The method converges after O(n) iterations with overall arithmetic complexity O(n²). Numerical experiments show that in practice the method converges in a small number of iterations with overall linear complexity, … Read more

    Computational aspects of risk-averse optimisation in two-stage stochastic models

  • Csaba I. Fábián
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    In this paper we argue for aggregated models in decomposition schemes for two-stage stochastic programming problems. We observe that analogous schemes proved effective for single-stage risk-averse problems, and for general linear programming problems. A major drawback of the aggregated approach for two-stage problems is that an aggregated master problem can not contain all the information … Read more

    Learning Circulant Sensing Kernels

  • Stanley Osher
  • Yangyang Xu
  • Wotao Yin
    • Categories Convex Optimization, Data-Mining, Quadratic Programming Tags , , , , ,

    In signal acquisition, Toeplitz and circulant matrices are widely used as sensing operators. They correspond to discrete convolutions and are easily or even naturally realized in various applications. For compressive sensing, recent work has used random Toeplitz and circulant sensing matrices and proved their efficiency in theory, by computer simulations, as well as through physical … Read more

    An Efficient Augmented Lagrangian Method with Applications to Total Variation Minimization

  • Hong Jiang
  • Wotao Yin
  • Yin Zhang
  • Chengbo Li
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    Based on the classic augmented Lagrangian multiplier method, we propose, analyze and test an algorithm for solving a class of equality-constrained non-smooth optimization problems (chiefly but not necessarily convex programs) with a particular structure. The algorithm effectively combines an alternating direction technique with a nonmonotone line search to minimize the augmented Lagrangian function at each … Read more