Nonsmooth Optimization

New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure

  • Robert M. Freund
  • Haihao Lu
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem f^* = \min_{x \in Q} f(x), where we presume knowledge of a strict lower bound f_slb < f^*. [Indeed, f_slb is naturally ... Read more

    Variational Analysis and Applications to Group Dynamics

  • Antoine Soubeyran
  • Bao Q. Truong
    • Categories Applications - OR and Management Sciences, Multi-Criteria Optimization, Nonsmooth Optimization Tags , , , , ,

    In this paper, we establish a new version of Ekeland’s variational principle in a new setting of cone pseudo-quasimetric spaces. In constrast to metric spaces, we do not require that each forward Cauchy sequence is forward convergent and that each forward convergent sequence has the unique forward limit. The motivation of this paper comes from … Read more

    Local monotonicity and full stability for parametric variational systems

  • Boris S. Mordukhovich
  • Tran Nghia
    • Categories Nonsmooth Optimization Tags , ,

    The paper introduces and characterizes new notions of Lipschitzian and H\”olderian full stability of solutions to general parametric variational systems described via partial subdifferential of prox-regular functions acting in finite-dimensional and Hilbert spaces. These notions, postulated certain quantitative properties of single-valued localizations of solution maps, are closely related to local strong maximal monotonicity of associated … Read more

    On the Convergence of Multi-Block Alternating Direction Method of Multipliers and Block Coordinate Descent Method

  • Caihua Chen
  • Xin Liu
  • Yinyu Ye
  • Min Li
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    The paper answers several open questions of the alternating direction method of multipliers (ADMM) and the block coordinate descent (BCD) method that are now wildly used to solve large scale convex optimization problems in many fields. For ADMM, it is still lack of theoretical understanding of the algorithm when the objective function is not separable … Read more

    Semidefinite approximations of the polynomial abscissa

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Tiên-So'n Pham
  • Roxana Hess
    • Categories Control Applications, Nonsmooth Optimization, Semi-definite Programming Tags , , , ,

    Given a univariate polynomial, its abscissa is the maximum real part of its roots. The abscissa arises naturally when controlling linear differential equations. As a function of the polynomial coefficients, the abscissa is H\”older continuous, and not locally Lipschitz in general, which is a source of numerical difficulties for designing and optimizing control laws. In … Read more

    A DERIVATIVE-FREE APPROACH TO CONSTRAINED MULTIOBJECTIVE NONSMOOTH OPTIMIZATION

  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    In this work, we consider multiobjective optimization problems with both bound constraints on the variables and general nonlinear constraints, where objective and constraint function values can only be obtained by querying a black box. We define a linesearch-based solution method, and we show that it converges to a set of Pareto stationary points. To this … Read more

    Variational analysis of spectral functions simplified

  • Dmitriy Drusvyatskiy
  • Courtney Paquette
    • Categories Nonsmooth Optimization Tags , , , , , ,

    Spectral functions of symmetric matrices — those depending on matrices only through their eigenvalues — appear often in optimization. A cornerstone variational analytic tool for studying such functions is a formula relating their subdifferentials to the subdifferentials of their diagonal restrictions. This paper presents a new, short, and revealing derivation of this result. We then … Read more

    On the non-ergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming

  • Xin Liu
  • Ya-Feng Liu
  • Shiqian Ma
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags ,

    In this paper, we consider the linearly constrained composite convex optimization problem, whose objective is a sum of a smooth function and a possibly nonsmooth function. We propose an inexact augmented Lagrangian (IAL) framework for solving the problem. The stopping criterion used in solving the augmented Lagrangian (AL) subproblem in the proposed IAL framework is … Read more

    On the von Neumann and Frank-Wolfe Algorithms with Away Steps

  • Javier F. Peña
  • Daniel Rodriguez
  • Negar Soheili
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    The von Neumann algorithm is a simple coordinate-descent algorithm to determine whether the origin belongs to a polytope generated by a finite set of points. When the origin is in the interior of the polytope, the algorithm generates a sequence of points in the polytope that converges linearly to zero. The algorithm’s rate of convergence … Read more

    Stability of p-order metric regularity

  • Kung Fu Ng
  • He Yiran
    • Categories Nonsmooth Optimization

    This paper shows that $p$-order metric regularity is preserved under perturbation of H\”older continuous mapping of order $1/p$, which answers affirmatively a problem posed recently by Dontchev. Citation Technical report, Department of Mathematics, Chinese University of Hong Kong, 07/2015