Optimality of Linear Policies in Distributionally Robust Linear Quadratic Control

  • Bahar Taskesen
  • Dan Iancu
  • Çağıl Koçyiğit
  • Daniel Kuhn
    • Categories Other Topics

    We study a generalization of the classical discrete-time, Linear-Quadratic-Gaussian (LQG) control problem where the noise distributions affecting the states and observations are unknown and chosen adversarially from divergence-based ambiguity sets centered around a known nominal distribution. For a finite horizon model with Gaussian nominal noise and a structural assumption on the divergence that is satisfied … Read more

    rAdam: restart Adam method to escape from local minima for bound constrained non-linear optimization problems

  • Thi-Thoi Tran
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , , , , , ,

    This paper presents a restart version of the Adaptive Moment Estimation (Adam) method for bound constrained nonlinear optimization problems. It aims to avoid getting trapped in a local minima and enable exploration the global optimum. The proposed method combines an adapted restart strategy coupling with barrier methodology to handle the bound constraints. Computational comparison with … Read more

    Solving the Partial Inverse Knapsack Problem

  • Eva Ley
  • Nikolas Lykourinos
  • Maximilian Merkert
  • Andreas M. Tillmann
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

    In this paper, we investigate the partial inverse knapsack problem, a bilevel optimization problem in which the follower solves a classical 0/1-knapsack problem with item profit values comprised of a fixed part and a modification determined by the leader. Specifically, the leader problem seeks a minimal change to given item profits such that there is … Read more

    Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications

  • Zijian Liu
    • Categories Convex Optimization, Nonsmooth Optimization Tags , ,

    In Online Convex Optimization (OCO), when the stochastic gradient has a finite variance, many algorithms provably work and guarantee a sublinear regret. However, limited results are known if the gradient estimate has a heavy tail, i.e., the stochastic gradient only admits a finite \(\mathsf{p}\)-th central moment for some \(\mathsf{p}\in\left(1,2\right]\). Motivated by it, this work examines … Read more

    Extending the reflect flow formulation to variable-sized one-dimensional cutting and skiving stock problems

  • Maxence Delorme
  • John Martinovic
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    Flow formulations have been widely studied for the one-dimensional cutting stock problem and several of its extensions. Among these, the so-called reflect model has shown the best empirical performance when solved directly with a general-purpose integer linear programming solver due to its reduced number of variables and constraints. However, existing adaptations of reflect for the … Read more

    The Optimal Smoothings of Sublinear Functions and Convex Cones

  • Thabo Samakhoana
  • Benjamin Grimmer
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    This paper considers the problem of smoothing convex functions and sets, seeking the nearest smooth convex function or set to a given one. For convex cones and sublinear functions, a full characterization of the set of all optimal smoothings is given. These provide if and only if characterizations of the set of optimal smoothings for … Read more

    ASPEN: An Additional Sampling Penalty Method for Finite-Sum Optimization Problems with Nonlinear Equality Constraints

  • Nataša Krejić
  • Nataša Krklec Jerinkić
  • Tijana Ostojić
  • Nemanja Vučićević
    • Categories Nonlinear Optimization, Stochastic Approaches, Stochastic Programming Tags , , , , , ,

    We propose a novel algorithm for solving non-convex, nonlinear equality-constrained finite-sum optimization problems. The proposed algorithm incorporates an additional sampling strategy for sample size update into the well-known framework of quadratic penalty methods. Thus, depending on the problem at hand, the resulting method may exhibit a sample size strategy ranging from a mini-batch on one … Read more

    A linesearch-based derivative-free method for noisy black-box problems

  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Alberto De Santis
    • Categories Nonlinear Optimization, Stochastic Programming, Unconstrained Optimization Tags , ,

    In this work we consider unconstrained optimization problems. The objective function is known through a zeroth order stochastic oracle that gives an estimate of the true objective function. To solve these problems, we propose a derivativefree algorithm based on extrapolation techniques. Under reasonable assumptions we are able to prove convergence properties for the proposed algorithms. … Read more

    Inspection Games with Incomplete Information and Heterogeneous Resources

  • Bobak McCann
  • Mathieu Dahan
    • Categories Game Theory, Linear Programming, Stochastic Programming Tags , , , ,

    We study a two-player zero-sum inspection game with incomplete information, where an inspector deploys resources to maximize the expected damage value of detected illegal items hidden by an adversary across capacitated locations. Inspection and illegal resources differ in their detection capabilities and damage values. Both players face uncertainty regarding each other’s available resources, modeled via … Read more

    On Relatively Smooth Optimization over Riemannian Manifolds

  • Chang He
  • Jiaxiang Li
  • Bo Jiang
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Programming Tags ,

    We study optimization over Riemannian embedded submanifolds, where the objective function is relatively smooth in the ambient Euclidean space. Such problems have broad applications but are still largely unexplored. We introduce two Riemannian first-order methods, namely the retraction-based and projection-based Riemannian Bregman gradient methods, by incorporating the Bregman distance into the update steps. The retraction-based … Read more