Relative-Continuity” for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent

  • Haihao Lu
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    The usual approach to developing and analyzing first-order methods for non-smooth (stochastic or deterministic) convex optimization assumes that the objective function is uniformly Lipschitz continuous with parameter $M_f$. However, in many settings the non-differentiable convex function $f(\cdot)$ is not uniformly Lipschitz continuous — for example (i) the classical support vector machine (SVM) problem, (ii) the … Read more

    Generalized ADMM with Optimal Inde nite Proximal Term for Linearly Constrained Convex Optimization

  • Xingju Cai
  • Fan Jiang
  • Zhongming Wu
    • Categories Convex Optimization Tags , , , , ,

    We consider the generalized alternating direction method of multipliers (ADMM) for linearly constrained convex optimization. Many problems derived from practical applications have showed that usually one of the subproblems in the generalized ADMM is hard to solve, thus a special proximal term is added. In the literature, the proximal term can be inde nite which plays … Read more

    Numerically tractable optimistic bilevel problems

  • Lorenzo Lampariello
  • Simone Sagratella
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Game Theory Tags , ,

    We consider fully convex lower level standard optimistic bilevel problems. We show that this class of mathematical programs is sufficiently broad to encompass significant real-world applications. We establish that the critical points of a relaxation of the original problem correspond to the equilibria of a suitably defined generalized Nash equilibrium problem. The latter game is … Read more

    Shared Mobility for Last-Mile Delivery: Design, Operational Prescriptions and Environmental Impact

  • Liu Sheng
    • Categories Applications - OR and Management Sciences, Supply Chain Management, Transportation

    This is the online external supplement for paper “Shared Mobility for Last-Mile Delivery: Design, Operational Prescriptions and Environmental Impact”. Article Download View Shared Mobility for Last-Mile Delivery: Design, Operational Prescriptions and Environmental Impact

    CONVERGENCE RATE OF GRADIENT BASED ADAPTIVE RESTART FOR ACCELERATED GRADIENT SCHEMES

  • Shivkumar Chandrasekaran
  • Ming Gu
  • Can Kizilkale
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    The accelerated gradient algorithm is known to have non-monotonic, periodic convergence behavior in the high momentum regime. If important function parameters like the condition number are known, the momentum can be adjusted to get linear convergence. Unfortunately these parameters are usually not accessible, so instead heuristics are used for deciding when to restart. One of … Read more

    A New Exact Algorithm to Optimize a Linear Function Over the Set of Efficient Solutions for Bi-objective Mixed Integer Linear Programs

  • Hadi Charkhgard
  • Alvaro Sierra-Altamiranda
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization Tags , , ,

    We present the first (criterion space search) algorithm for optimizing a linear function over the set of efficient solutions of bi-objective mixed integer linear programs. The proposed algorithm is developed based on the Triangle Splitting Method (Boland et al. 2015b) which can find a full representation of the nondominated frontier of any bi-objective mixed integer … Read more

    A Primal-Dual Lifting Scheme for Two-Stage Robust Optimization

  • Angelos Georghiou
  • Angelos Tsoukalas
  • Wolfram Wiesemann
    • Categories Robust Optimization Tags , , ,

    Two-stage robust optimization problems, in which decisions are taken both in anticipation of and in response to the observation of an unknown parameter vector from within an uncertainty set, are notoriously challenging. In this paper, we develop convergent hierarchies of primal (conservative) and dual (progressive) bounds for these problems that trade off the competing goals … Read more

    Derivative-Free Robust Optimization by Outer Approximations

  • Matt Menickelly
  • Stefan M. Wild
    • Categories Nonsmooth Optimization, Robust Optimization, Unconstrained Optimization Tags , , ,

    We develop an algorithm for minimax problems that arise in robust optimization in the absence of objective function derivatives. The algorithm utilizes an extension of methods for inexact outer approximation in sampling a potentially infinite-cardinality uncertainty set. Clarke stationarity of the algorithm output is established alongside desirable features of the model-based trust-region subproblems encountered. We … Read more

    Underestimate Sequences via Quadratic Averaging

  • Naga Venkata Chaitanya Gudapati
  • Rachael Tappenden
  • Majid Jahani
  • Chenxin Ma
  • Martin Takac
    • Categories Nonlinear Optimization, Unconstrained Optimization

    In this work we introduce the concept of an Underestimate Sequence (UES), which is a natural extension of Nesterov’s estimate sequence. Our definition of a UES utilizes three sequences, one of which is a lower bound (or under-estimator) of the objective function. The question of how to construct an appropriate sequence of lower bounds is … Read more

    Index Policies and Performance Bounds for Dynamic Selection Problems

  • David B. Brown
  • James E. Smith
    • Categories Applications - OR and Management Sciences, Dynamic Programming Tags , , , ,

    We consider dynamic selection problems, where a decision maker repeatedly selects a set of items from a larger collection of available items. A classic example is the dynamic assortment problem with demand learning, where a retailer chooses items to offer for sale subject to a display space constraint. The retailer may adjust the assortment over … Read more