Month: June 2007

Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems

  • Mario A. T. Figueiredo
  • Stephen Wright
  • Robert Nowak
    • Categories Applications - Science and Engineering, Bound-constrained Optimization Tags ,

    Many problems in signal processing and statistical inference involve finding sparse solutions to under-determined, or ill-conditioned, linear systems of equations. A standard approach consists in minimizing an objective function which includes a quadratic (squared $\ell_2$) error term combined with a sparseness-inducing ($\ell_1$) regularization term.{\it Basis pursuit}, the {\it least absolute shrinkage and selection operator} (LASSO), … Read more

    Smooth Optimization Approach for Covariance Selection

  • Zhaosong Lu
    • Categories Convex and Nonsmooth Optimization, Statistics Tags , ,

    In this paper we study a smooth optimization approach for solving a class of non-smooth {\it strongly} concave maximization problems. In particular, we apply Nesterov’s smooth optimization technique \cite{Nest83-1,Nest05-1} to their dual counterparts that are smooth convex problems. It is shown that the resulting approach has $\cO(1/{\sqrt{\epsilon}})$ iteration complexity for finding an $\epsilon$-optimal solution to … Read more

    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

    Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

  • Maryam Fazel
  • Benjamin Recht
  • Pablo A. Parrilo
    • Categories Convex and Nonsmooth Optimization, Semi-definite Programming, Statistics Tags , , ,

    The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, … Read more

    Explicit reformulations for robust optimization problems with general uncertainty sets

  • Igor Averbakh
  • Yun-Bin Zhao
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Robust Optimization Tags ,

    We consider a rather general class of mathematical programming problems with data uncertainty, where the uncertainty set is represented by a system of convex inequalities. We prove that the robust counterparts of this class of problems can be equivalently reformulated as finite and explicit optimization problems. Moreover, we develop simplified reformulations for problems with uncertainty … Read more

    Symmetry in semidefinite programs

  • Frank Vallentin
    • Categories Semi-definite Programming Tags , , ,

    This paper is a tutorial in a general and explicit procedure to simplify semidefinite programming problems which are invariant under the action of a group. The procedure is based on basic notions of representation theory of finite groups. As an example we derive the block diagonalization of the Terwilliger algebra in this framework. Here its … Read more

    Column basis reduction and decomposable knapsack problems

  • Bala Krishnamoorthy
  • Gabor Pataki
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b’   ≤   Ax   ≤   b,   x ∈ Zn with b’   ≤   (AU)y   ≤   b,   y ∈ Zn, where U is a unimodular matrix computed via basis reduction, to make the … Read more

    An O(n^2) Algorithm for Lot Sizing with Inventory Bounds and Fixed Costs

  • Alper Atamturk
  • Simge Küçükyavuz
    • Categories Applications - OR and Management Sciences, Production and Logistics

    Lot-sizing problems with inventory bounds and fixed charges have not received much attention in the literature, even though there are many emerging applications in which highly specialized storage is the main activity of interest. The traditional infinite capacity and variable cost assumptions on inventory that have been prevalent in the literature are inappropriate in situations … Read more

    Partition Inequalities for Capacitated Survivable Network Design Based on Directed P-Cycles

  • Alper Atamturk
  • Deepak Rajan
    • Categories Applications - OR and Management Sciences, Telecommunications

    We study the design of capacitated survivable networks using directed p-cycles. A p-cycle is a cycle with at least three arcs, used for rerouting disrupted flow during edge failures. Survivability of the network is accomplished by reserving sufficient slack on directed p-cycles so that if an edge fails, its flow can be rerouted along the … Read more

    The Flow Set with Partial Order

  • Alper Atamturk
  • Muhong Zhang
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches

    The flow set with partial order is a mixed-integer set described by a budget on total flow and a partial order on the arcs that may carry positive flow. This set is a common substructure of resource allocation and scheduling problems with precedence constraints and robust network flow problems under demand/capacity uncertainty. We give a … Read more