Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

  • Serge Gratton
  • Philippe L. Toint
  • Ehouarn Simon
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(epsilon)|.epsilon^{-2}) evaluations of the problem’s functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, … Read more

    Robust sample average approximation with small sample sizes

  • Edward Anderson
  • Andrew B. Philpott
    • Categories Robust Optimization, Stochastic Programming

    We consider solving stochastic optimization problems in which we seek to minimize the expected value of an objective function with respect to an unknown distribution of random parameters. Our focus is on models that use sample average approximation (SAA) with small sample sizes. We analyse the out-of-sample performance of solutions obtained by solving a robust … Read more

    A Framework for Peak Shaving Through the Coordination of Smart Homes

  • Miguel F. Anjos
  • Michael David de Souza Dutra
  • Sébastien Le Digabel
    • Categories (Mixed) Integer Linear Programming, Energy, Scheduling

    In demand–response programs, aggregators balance the needs of generation companies and end-users. This work proposes a two-phase framework that shaves the aggregated peak loads while maintaining the desired comfort level for users. In the first phase, the users determine their planned consumption. For the second phase, we develop a bilevel model with mixed-integer variables and … Read more

    Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron

  • Francis Bach
  • Mark Schmidt
  • Sharan Vaswani
    • Categories Convex Optimization, Generalized Convexity/Monoticity Tags , , ,

    Modern machine learning focuses on highly expressive models that are able to fit or interpolate the data completely, resulting in zero training loss. For such models, we show that the stochastic gradients of common loss functions satisfy a strong growth condition. Under this condition, we prove that constant step-size stochastic gradient descent (SGD) with Nesterov … Read more

    Weak subgradient algorithm for solving nonsmooth nonconvex unconstrained optimization problems

  • Gulcin Dinc Yalcin
  • Refail Kasimbeyli
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags

    This paper presents a weak subgradient based method for solving nonconvex unconstrained optimization problems. The method uses a weak subgradient of the objective function at a current point, to generate a new one at every iteration. The concept of the weak subgradient is based on the idea of using supporting cones to the graph of … Read more

    An optimal control theory for accelerated optimization

  • Isaac Ross
    • Categories Convex and Nonsmooth Optimization, Unconstrained Optimization Tags , , , , , ,

    Accelerated optimization algorithms can be generated using a double-integrator model for the search dynamics imbedded in an optimal control problem. Citation unpublished Article Download View An optimal control theory for accelerated optimization

    Risk Aversion to Parameter Uncertainty in Markov Decision Processes with an Application to Slow-Onset Disaster Relief

  • Simge Küçükyavuz
  • Merve Merakli
    • Categories Integer Programming, Stochastic Programming, Supply Chain Management Tags , , , , ,

    In classical Markov Decision Processes (MDPs), action costs and transition probabilities are assumed to be known, although an accurate estimation of these parameters is often not possible in practice. This study addresses MDPs under cost and transition probability uncertainty and aims to provide a mathematical framework to obtain policies minimizing the risk of high long-term … Read more

    A polynomial algorithm for minimizing travel time in time-dependent networks with waits

  • Jérémy Omer
  • Michael Poss
    • Categories Network Optimization

    We consider a time-dependent shortest path problem with possible waiting at each node and a global bound $W$ on the total waiting time. The goal is to minimize only the time travelled along the edges of the path, not including the waiting time. We prove that the problem can be solved in polynomial time when … Read more

    A Computational Comparison of Optimization Methods for the Golomb Ruler Problem

  • Burak Kocuk
  • Willem-Jan van Hoeve
    • Categories Integer Programming Tags , ,

    The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of the ruler is minimized. The Golomb ruler problem has applications in information theory, astronomy and … Read more

    Pathfollowing for Parametric Mathematical Programs with Complementarity Constraints

  • Johannes Jäschke
  • Vyacheslav Kungurtsev
    • Categories Constrained Nonlinear Optimization

    In this paper we study procedures for pathfollowing parametric mathematical pro- grams with complementarity constraints. We present two procedures, one based on the penalty approach to solving standalone MPCCs, and one based on tracing active set bifurcations aris- ing from doubly-active complementarity constraints. We demonstrate the performance of these approaches on a variety of examples … Read more