Applications – Science and Engineering

Convergence and Convergence Rate of Stochastic Gradient Search in the Case of Multiple and Non-Isolated Extrema

  • Vladislav B. Tadic
    • Categories Control Applications, Stochastic Programming Tags , , , , ,

    The asymptotic behavior of stochastic gradient algorithms is studied. Relying on some results of differential geometry (Lojasiewicz gradient inequality), the almost sure point-convergence is demonstrated and relatively tight almost sure bounds on the convergence rate are derived. In sharp contrast to all existing result of this kind, the asymptotic results obtained here do not require … Read more

    Trace Norm Regularization: Reformulations, Algorithms, and Multi-task Learning

  • Shuiwang Ji
  • Ting Kei Pong
  • Paul Tseng
  • Jieping Ye
    • Categories Convex Optimization, Data-Mining, Semi-definite Programming Tags , , , , , ,

    We consider a recently proposed optimization formulation of multi-task learning based on trace norm regularized least squares. While this problem may be formulated as a semidefinite program (SDP), its size is beyond general SDP solvers. Previous solution approaches apply proximal gradient methods to solve the primal problem. We derive new primal and dual reformulations of … Read more

    Reconstruction of CT Images from Parsimonious Angular Measurements via Compressed Sensing

  • Necdet Serhat Aybat
  • Amit Chakraborty
    • Categories Biomedical Applications, Convex and Nonsmooth Optimization Tags , , , ,

    Computed Tomography is one of the most popular diagnostic tools available to medical professionals. However, its diagnostic power comes at a cost to the patient- significant radiation exposure. The amount of radiation exposure is a function of the number of angular measurements necessary to successfully reconstruct the imaged volume. Compressed sensing on the other hand … 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

    Real-Time Optimization as a Generalized Equation

  • Mihai Anitescu
  • Victor M. Zavala
    • Categories Complementarity and Variational Inequalities, Control Applications, Nonlinear Optimization Tags , , , ,

    We establish results for the problem of tracking a time-dependent manifold arising in online nonlinear programming by casting this as a generalized equation. We demonstrate that if points along a solution manifold are consistently strongly regular, it is possible to track the manifold approximately by solving a linear complementarity problem (LCP) at each time step. … Read more

    Rank-Sparsity Incoherence for Matrix Decomposition

  • Venkat Chandrasekaran
  • Pablo A. Parrilo
  • Sujay Sanghavi
  • Alan S. Willsky
    • Categories Control Applications, Convex Optimization, Statistics Tags , , , , , , ,

    Suppose we are given a matrix that is formed by adding an unknown sparse matrix to an unknown low-rank matrix. Our goal is to decompose the given matrix into its sparse and low-rank components. Such a problem arises in a number of applications in model and system identification, and is NP-hard in general. In this … Read more

    Control problems with mixed constraints and application to an optimal investment problem

  • Joseph Frédéric Bonnans
  • Dan Tiba
    • Categories Optimization of Systems modeled by PDEs Tags , , , ,

    We discuss two optimal control problems of parabolic equations, with mixed state and control constraints, for which the standard qualification condition does not hold. Our first example is a bottleneck problem, and the second one is an optimal investment problem where a utility type function is to be minimized. By an adapted penalization technique, we … Read more

    Solving large p-median problems using a Lagrangean heuristic

  • Andréa Cynthia Santos
    • Categories Approximation Algorithms, Facility Planning and Design, Telecommunications Tags , ,

    The p-median problem consists in locating p medians in a given graph, such that the total cost of assigning each demand to the closest median is minimized. In this work, a Lagrangean heuristic is proposed and it uses two dual information to build primal solutions. It outperforms a classic heuristic based on the same Lagrangean … Read more

    Covariance regularization in inverse space

  • Takashi Tsuchiya
  • Genta Ueno
    • Categories Data-Mining, Semi-definite Programming Tags , ,

    This paper proposes to apply Gaussian graphical models to estimate the large-scale normal distribution in the context of data assimilation from a relatively small number of data from the satellite. Data assimilation is a field which fits simulation models to observation data developed mainly in meteorology and oceanography. The optimization problem tends to be huge … Read more

    Analysis and Generalizations of the Linearized Bregman Method

  • Wotao Yin
    • Categories Basic Sciences Applications, Convex Optimization Tags , , , ,

    This paper reviews the Bregman methods, analyzes the linearized Bregman method, and proposes fast generalization of the latter for solving the basis pursuit and related problems. The analysis shows that the linearized Bregman method has the exact penalty property, namely, it converges to an exact solution of the basis pursuit problem if and only if … Read more