smoothing

The Landscape of the Proximal Point Method for Nonconvex-Nonconcave Minimax Optimization

  • Benjamin Grimmer
  • Haihao Lu
  • Vahab S. Mirrokni
  • Pratik Worah
    • Categories Robust Optimization, Unconstrained Optimization Tags , , , , , ,

    Minimax optimization has become a central tool for modern machine learning with applications in generative adversarial networks, robust optimization, reinforcement learning, etc. These applications are often nonconvex-nonconcave, but the existing theory is unable to identify and deal with the fundamental difficulties posed by nonconvex-nonconcave structures. In this paper, we study the classic proximal point method … Read more

    Solving Chance-Constrained Problems via a Smooth Sample-Based Nonlinear Approximation

  • James R. Luedtke
  • Alejandra Pena-Ordieres
  • Andreas Wächter
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , , , ,

    We introduce a new method for solving nonlinear continuous optimization problems with chance constraints. Our method is based on a reformulation of the probabilistic constraint as a quantile function. The quantile function is approximated via a differentiable sample average approximation. We provide theoretical statistical guarantees of the approximation, and illustrate empirically that the reformulation can … Read more

    A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization

  • Albert S. Berahas
  • Liyuan Cao
  • Katya Scheinberg
  • Krzysztof Choromanski
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    In this paper, we analyze several methods for approximating gradients of noisy functions using only function values. These methods include finite differences, linear interpolation, Gaussian smoothing and smoothing on a unit sphere. The methods differ in the number of functions sampled, the choice of the sample points, and the way in which the gradient approximations … Read more

    Subdifferentiation and Smoothing of Nonsmooth Integral Functionals

  • James V. Burke
  • Xiaojun Chen
  • Hailin Sun
    • Categories Nonsmooth Optimization Tags , , ,

    The subdifferential calculus for the expectation of nonsmooth random integrands involves many fundamental and challenging problems in stochastic optimization. It is known that for Clarke regular integrands, the Clarke subdifferential equals the expectation of their Clarke subdifferential. In particular, this holds for convex integrands. However, little is known about calculation of Clarke subgradients for the … Read more

    Efficiency of minimizing compositions of convex functions and smooth maps

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

    We consider the problem of minimizing a sum of a convex function and a composition of a convex function with a smooth map. Important examples include exact penalty formulations of nonlinear programs and nonlinear least squares problems with side constraints. The basic algorithm we rely on is the well-known prox-linear method, which in each iteration … Read more

    On max-k-sums

  • Michael J. Todd
    • Categories Basic Sciences Applications, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The max-$k$-sum of a set of real scalars is the maximum sum of a subset of size $k$, or alternatively the sum of the $k$ largest elements. We study two extensions: First, we show how to obtain smooth approximations to functions that are pointwise max-$k$-sums of smooth functions. Second, we discuss how the max-$k$-sum can … Read more

    Virtuous smoothing for global optimization

  • Jon Lee
  • Daphne Skipper
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    In the context of global optimization and mixed-integer non-linear programming, generalizing a technique of D’Ambrosio, Fampa, Lee and Vigerske for handling the square-root function, we develop a virtuous smoothing method, using cubics, aimed at functions having some limited non-smoothness. Our results pertain to root functions ($w^p$ with $0

    Solving disjunctive optimization problems by generalized semi-infinite optimization techniques

  • Peter Kirst
  • Oliver Stein
    • Categories Nonsmooth Optimization, Semi-infinite Programming Tags , , , ,

    We describe a new possibility to model disjunctive optimization problems as generalized semi-infinite programs. In contrast to existing methods, for our approach neither a conjunctive nor a disjunctive normal form is expected. Applying existing lower level reformulations for the corresponding semi-infinite program we derive conjunctive nonlinear problems without any logical expressions, which can be locally … Read more

    Trust-region methods without using derivatives: Worst case complexity and the non-smooth case

  • R. Garmanjani
  • Luis Nunes Vicente
  • Diogo Júdice
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , ,

    Trust-region methods are a broad class of methods for continuous optimization that found application in a variety of problems and contexts. In particular, they have been studied and applied for problems without using derivatives. The analysis of trust-region derivative-free methods has focused on global convergence, and they have been proved to generate a sequence of … Read more

    An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems

  • Yunlong He
  • Renato D.C. Monteiro
    • Categories Convex Optimization, Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , , , , ,

    This article proposes a new algorithm for solving a class of composite convex-concave saddle-point problems. The new algorithm is a special instance of the hybrid proximal extragradient framework in which a Nesterov’s accelerated variant is used to approximately solve the prox subproblems. One of the advantages of the new method is that it works for … Read more