Convex and Nonsmooth Optimization

Convergence to the optimal value for barrier methods combined with Hessian Riemannian gradient flows and generalized proximal algorithms

  • Felipe Álvarez
  • Julio López
    • Categories Convex Optimization Tags , ,

    We consider the problem $\min_{x\in\R^n}\{f(x)\mid Ax=b, \ x\in\overline{C},\ g_j(x)\le0,\ j=1,\ldots,s\}$, where $b\in\R^m$, $A\in\R^{m\times n}$ is a full rank matrix, $\overline{C}$ is the closure of a nonempty, open and convex subset $C$ of $\R^n$, and $g_j(\cdot)$, $ j=1,\ldots,s$, are nonlinear convex functions. Our strategy consists firstly in to introduce a barrier-type penalty for the constraints $g_j(x)\le0$, … Read more

    Recovering low-rank and sparse components of matrices from incomplete and noisy observations

  • Tao Min
  • Xiao-Ming Yuan
    • Categories Convex Optimization, Statistics Tags , , , , ,

    Many applications arising in a variety of fields can be well illustrated by the task of recovering the low-rank and sparse components of a given matrix. Recently, it is discovered that this NP-hard task can be well accomplished, both theoretically and numerically, via heuristically solving a convex relaxation problem where the widely-acknowledged nuclear norm and … Read more

    Fast Multiple Splitting Algorithms for Convex Optimization

  • Donald Goldfarb
  • Shiqian Ma
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , , ,

    We present in this paper two different classes of general $K$-splitting algorithms for solving finite-dimensional convex optimization problems. Under the assumption that the function being minimized has a Lipschitz continuous gradient, we prove that the number of iterations needed by the first class of algorithms to obtain an $\epsilon$-optimal solution is $O(1/\epsilon)$. The algorithms in … Read more

    Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions

  • Donald Goldfarb
  • Shiqian Ma
  • Katya Scheinberg
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , , ,

    We present in this paper first-order alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most $O(1/\epsilon)$ iterations to obtain an $\epsilon$-optimal solution, while our accelerated (i.e., fast) versions of them require at most $O(1/\sqrt{\epsilon})$ iterations, with little change in … Read more

    A Sequential Quadratic Programming Algorithm for Nonconvex, Nonsmooth Constrained Optimization

  • Frank E. Curtis
  • Michael L. Overton
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    We consider optimization problems with objective and constraint functions that may be nonconvex and nonsmooth. Problems of this type arise in important applications, many having solutions at points of nondifferentiability of the problem functions. We present a line search algorithm for situations when the objective and constraint functions are locally Lipschitz and continuously differentiable on … Read more

    Hedge Algorithm and Subgradient Methods

  • Michel Baes
  • Michael Bürgisser
    • Categories Convex Optimization Tags , , , ,

    We show that the Hedge Algorithm, a method that is widely used in Machine Learning, can be interpreted as a particular subgradient algorithm for minimizing a well-chosen convex function, namely as a Mirror Descent Scheme. Using this reformulation, we establish three modificitations and extensions of the Hedge Algorithm that are better or at least as … Read more

    Alternating Direction Algorithms for $\ell_1hBcProblems in Compressive Sensing

  • Junfeng Yang
  • Yin Zhang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    In this paper, we propose and study the use of alternating direction algorithms for several $\ell_1$-norm minimization problems arising from sparse solution recovery in compressive sensing, including the basis pursuit problem, the basis-pursuit denoising problems of both unconstrained and constrained forms, as well as others. We present and investigate two classes of algorithms derived from … Read more

    Extension of the semidefinite characterization of sum of squares functional systems to algebraic structures

  • Farid Alizadeh
  • Ricardo A. Collado
  • Dávid Papp
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    We extend Nesterov’s semidefinite programming (SDP) characterization of the cone of functions that can be expressed as sums of squares (SOS) of functions in finite dimensional linear functional spaces. Our extension is to algebraic systems that are endowed with a binary operation which map two elements of a finite dimensional vector space to another vector … Read more

    A Proximal Algorithm with Quasi Distance. Application to Habit’s Formation

  • Felipe Garcia Moreno
  • Paulo Roberto Oliveira
  • Antoine Soubeyran
    • Categories Nonsmooth Optimization, Unconstrained Optimization

    We consider a proximal algorithm with quasi distance applied to nonconvex and nonsmooth functions involving analytic properties for an unconstrained minimization problem. We show the behavioral importance of this proximal point model for habit’s formation in Decision and Making Sciences. Article Download View A Proximal Algorithm with Quasi Distance. Application to Habit's Formation

    Identifying Active Manifolds in Regularization Problems

  • Warren Hare
    • Categories Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , ,

    In this work we consider the problem $\min_x \{ f(x) + P(x) \}$, where $f$ is $\mathcal{C}^2$ and $P$ is nonsmooth, but contains an underlying smooth substructure. Specifically, we assume the function $P$ is prox-regular partly smooth with respect to a active manifold $\M$. Recent work by Tseng and Yun \cite{tseng-yun-2009}, showed that such a … Read more