Paul Tseng

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

    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

    A First-Order Interior-Point Method for Linearly Constrained Smooth Optimization

  • Immanuel M. Bomze
  • Paul Tseng
  • Werner Schachinger
    • Categories Nonlinear Optimization, Quadratic Programming

    We propose a first-order interior-point method for linearly constrained smooth optimization that unifies and extends first-order affine-scaling method and replicator dynamics method for standard quadratic programming. Global convergence and, in the case of quadratic programs, (sub)linear convergence rate and iterate convergence results are derived. Numerical experience on simplex constrained problems with 1000 variables is reported. … Read more

    A Coordinate Gradient Descent Method for Linearly Constrained Smooth Optimization and Support Vector Machines Training

  • Paul Tseng
  • Sangwoon Yun
    • Categories Constrained Nonlinear Optimization, Data-Mining Tags , , , , , , , ,

    Support vector machines (SVMs) training may be posed as a large quadratic program (QP) with bound constraints and a single linear equality constraint. We propose a (block) coordinate gradient descent method for solving this problem and, more generally, linearly constrained smooth optimization. Our method is closely related to decomposition methods currently popular for SVM training. … Read more

    A Coordinate Gradient Descent Method for Nonsmooth Separable Minimization

  • Paul Tseng
  • Sangwoon Yun
    • Categories Bound-constrained Optimization, Convex and Nonsmooth Optimization Tags

    We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with l_1-regularization. We propose a (block) coordinate gradient descent method for solving this class of nonsmooth separable problems. We establish global convergence and, under a local Lipschitzian … Read more

    Exact regularization of convex programs

  • Michael P. Friedlander
  • Paul Tseng
    • Categories Convex Optimization Tags , , , , , , , ,

    The regularization of a convex program is exact if all solutions of the regularized problem are also solutions of the original problem for all values of the regularization parameter below some positive threshold. For a general convex program, we show that the regularization is exact if and only if a certain selection problem has a … Read more

    Elastic-Mode Algorithms for Mathematical Programs with Equilibrium Constraints: Global Convergence and Stationarity Properties

  • Mihai Anitescu
  • Paul Tseng
  • Stephen Wright
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , ,

    The elastic-mode formulation of the problem of minimizing a nonlinear function subject to equilibrium constraints has appealing local properties in that, for a finite value of the penalty parameter, local solutions satisfying first- and second-order necessary optimality conditions for the original problem are also first- and second-order points of the elastic-mode formulation. Here we study … Read more

    Set Intersection Theorems and Existence of Optimal Solutions

  • Dimitri Bertsekas
  • Paul Tseng
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , ,

    The question of nonemptiness of the intersection of a nested sequence of closed sets is fundamental in a number of important optimization topics, including the existence of optimal solutions, the validity of the minimax inequality in zero sum games, and the absence of a duality gap in constrained optimization. We introduce the new notion of … Read more

    An Analysis of the EM Algorithm andEntropy-Like Proximal Point Methods

  • Paul Tseng
    • Categories Nonlinear Optimization Tags , , , ,

    The EM algorithm is a popular method for maximum likelihood estimation from incomplete data. This method may be viewed as a proximal point method for maximizing the log-likelhood function using an integral form of the Kullback-Leibler distance function. Motivated by this interpretation, we consider a proximal point method using an integral form of entropy-like distance … Read more