Nonsmooth Optimization

FAST FIRST-ORDER METHODS FOR COMPOSITE CONVEX OPTIMIZATION WITH BACKTRACKING

  • Xi Bai
  • Donald Goldfarb
  • Katya Scheinberg
    • Categories Nonsmooth Optimization Tags , , , , ,

    We propose new versions of accelerated first order methods for convex composite optimization, where the prox parameter is allowed to increase from one iteration to the next. In particular we show that a full backtracking strategy can be used within the FISTA \cite{Beck-Teboulle-2009} and FALM algorithms \cite{Goldfarb-Ma-Scheinberg-2010} while preserving their worst-case iteration complexities of $O(\sqrt{L(f)/\epsilon})$. … Read more

    Snow water equivalent estimation using blackbox optimization

  • Stéphane Alarie
  • Charles Audet
  • Vincent Garnier
  • Sébastien Le Digabel
  • Louis-Alexandre Leclaire
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    Accurate measurements of snow water equivalent (SWE) is an important factor in managing water resources for hydroelectric power generation. SWE over a catchment area may be estimated via kriging on measures obtained by snow monitoring devices positioned at strategic locations. The question studied in this paper is to find the device locations that minimize the … Read more

    Use of quadratic models with mesh adaptive direct search for constrained black box optimization

  • Andrew R. Conn
  • Sébastien Le Digabel
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    We consider a derivative-free optimization, and in particular black box optimization, where the functions to be minimized and the functions representing the constraints are given by black boxes without derivatives. Two fundamental families of methods are available: model-based methods and directional direct search algorithms. This work exploits the flexibility of the second type of methods … Read more

    Convergence analysis of a proximal Gauss-Newton method

  • Saverio Salzo
  • Silvia Villa
    • Categories Nonlinear Systems and Least-Squares, Nonsmooth Optimization

    An extension of the Gauss-Newton algorithm is proposed to find local minimizers of penalized nonlinear least squares problems, under generalized Lipschitz assumptions. Convergence results of local type are obtained, as well as an estimate of the radius of the convergence ball. Some applications for solving constrained nonlinear equations are discussed and the numerical performance of … Read more

    The dimension of semialgebraic subdifferential graphs.

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
  • Alexander D. Ioffe
    • Categories Nonsmooth Optimization Tags , , , ,

    Examples exist of extended-real-valued closed functions on $\R^n$ whose subdifferentials (in the standard, limiting sense) have large graphs. By contrast, if such a function is semi-algebraic, then its subdifferential graph must have everywhere constant local dimension $n$. This result is related to a celebrated theorem of Minty, and surprisingly may fail for the Clarke subdifferential. … Read more

    SOME REGULARITY RESULTS FOR THE PSEUDOSPECTRAL ABSCISSA AND PSEUDOSPECTRAL RADIUS OF A MATRIX

  • Mert Gurbuzbalaban
  • Michael L. Overton
    • Categories Global Optimization Theory, Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    The $\epsilon$-pseudospectral abscissa $\alpha_\epsilon$ and radius $\rho_\epsilon$ of an n x n matrix are respectively the maximal real part and the maximal modulus of points in its $\epsilon$-pseudospectrum, defined using the spectral norm. It was proved in [A.S. Lewis and C.H.J. Pang. Variational analysis of pseudospectra. SIAM Journal on Optimization, 19:1048-1072, 2008] that for fixed … Read more

    On Nesterov’s Nonsmooth Chebyschev-Rosenbrock Functions

  • Mert Gurbuzbalaban
  • Michael L. Overton
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Nonsmooth Optimization

    We discuss two nonsmooth functions on R^n introduced by Nesterov. We show that the first variant is partly smooth in the sense of [A.S. Lewis. Active sets, nonsmoothness and sensitivity. SIAM Journal on Optimization, 13:702–725, 2003.] and that its only stationary point is the global minimizer. In contrast, we show that the second variant has … Read more

    An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors

  • Zaiwen Wen
  • Yangyang Xu
  • Wotao Yin
  • Yin Zhang
    • Categories Data-Mining, Nonsmooth Optimization Tags , , ,

    This paper introduces a novel algorithm for the nonnegative matrix factorization and completion problem, which aims to nd nonnegative matrices X and Y from a subset of entries of a nonnegative matrix M so that XY approximates M. This problem is closely related to the two existing problems: nonnegative matrix factorization and low-rank matrix completion, … Read more

    A Double Smoothing Technique for Constrained Convex Optimization Problems and Applications to Optimal Control

  • Olivier Devolder
  • François Glineur
  • Yurii Nesterov
    • Categories Convex Optimization, Infinite Dimensional Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper, we propose an efficient approach for solving a class of convex optimization problems in Hilbert spaces. Our feasible region is a (possibly infinite-dimensional) simple convex set, i.e. we assume that projections on this set are computationally easy to compute. The problem we consider is the minimization of a convex function over this … Read more

    Error bounds for vector-valued functions: necessary and sufficient conditions

  • Ewa M. Bednarczuk
  • Alexander Y. Kruger
    • Categories Nonsmooth Optimization Tags , , ,

    In this paper, we attempt to extend the definition and existing local error bound criteria to vector-valued functions, or more generally, to functions taking values in a normed linear space. Some new derivative-like objects (slopes and subdifferentials) are introduced and a general classification scheme of error bound criteria is presented. CitationPublished in Nonlinear Analysis. Theory, … Read more