Strengthening Lasserre’s Hierarchy in Real and Complex Polynomial Optimization

  • Jie Wang
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , ,

    We establish a connection between multiplication operators and shift operators. Moreover, we derive positive semidefinite conditions of finite rank moment sequences and use these conditions to strengthen Lasserre’s hierarchy for real and complex polynomial optimization. Integration of the strengthening technique with sparsity is considered. Extensive numerical experiments show that our strengthening technique can significantly improve … Read more

    Tricks from the Trade for Large-Scale Markdown Pricing: Heuristic Cut Generation for Lagrangian Decomposition

  • Robert Streeck
  • Andreas Schmitt
  • Torsten Gellert
  • Asya Dipkaya
  • Vladimir Fux
  • Tim Januschowski
  • Timo Berthold
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

    In automated decision making processes in the online fashion industry, the ‘predict-then-optimize’ paradigm is frequently applied, particularly for markdown pricing strategies. This typically involves a mixed-integer optimization step, which is crucial for maximizing profit and merchandise volume. In practice, the size and complexity of the optimization problem is prohibitive for using off-the-shelf solvers for mixed … Read more

    A Sequential Benders-based Mixed-Integer Quadratic Programming Algorithm

  • Andrea Ghezzi
  • Wim Van Roy
  • Sebastian Sager
  • Moritz Diehl
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Optimization Software Benchmark Tags , , , ,

    For continuous decision spaces, nonlinear programs (NLPs) can be efficiently solved via sequential quadratic programming (SQP) and, more generally, sequential convex programming (SCP). These algorithms linearize only the nonlinear equality constraints and keep the outer convex structure of the problem intact, such as (conic) inequality constraints or convex objective terms. The aim of the presented … Read more

    A Max-Min-Max Algorithm for Large-Scale Robust Optimization

  • Kai Tu
  • Zhi Chen
  • Man-Chung Yue
    • Categories Robust Optimization Tags , , ,

    Robust optimization (RO) is a powerful paradigm for decision making under uncertainty. Existing algorithms for solving RO, including the reformulation approach and the cutting-plane method, do not scale well, hindering the application of RO to large-scale decision problems. In this paper, we devise a first-order algorithm for solving RO based on a novel max-min-max perspective. … Read more

    Revisiting the fitting of the Nelson-Siegel and Svensson models

  • Dirk Banholzer
  • Jörg Fliege
  • Ralf Werner
    • Categories Finance and Economics, Global Optimization Applications, Nonlinear Systems and Least-Squares Tags , , , , ,

    The Nelson-Siegel and the Svensson models are two of the most widely used models for the term structure of interest rates. Even though the models are quite simple and intuitive, fitting them to market data is numerically challenging and various difficulties have been reported. In this paper, a novel mathematical analysis of the fitting problem … Read more

    Polyhedral Analysis of Quadratic Optimization Problems with Stieltjes Matrices and Indicators

  • Peijing Liu
  • Alper Atamturk
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    In this paper, we consider convex quadratic optimization problems with indicators on the continuous variables. In particular, we assume that the Hessian of the quadratic term is a Stieltjes matrix, which naturally appears in sparse graphical inference problems and others. We describe an explicit convex formulation for the problem by studying the Stieltjes polyhedron arising … Read more

    The best approximation pair problem relative to two subsets in a normed space

  • Daniel Reem
  • Yair Censor
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Infinite Dimensional Optimization Tags , , , , , , , , ,

    In the classical best approximation pair (BAP) problem, one is given two nonempty, closed, convex and disjoint subsets in a finite- or an infinite-dimensional Hilbert space, and the goal is to find a pair of points, each from each subset, which realizes the distance between the subsets. This problem, which has a long history, has … Read more

    An MILP-Based Solution Scheme for Factored and Robust Factored Markov Decision Processes

  • Huikang Liu
  • Wolfram Wiesemann
  • Man-Chung Yue
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags ,

    Factored Markov decision processes (MDPs) are a prominent paradigm within the artificial intelligence community for modeling and solving large-scale MDPs whose rewards and dynamics decompose into smaller, loosely interacting components. Through the use of dynamic Bayesian networks and context-specific independence, factored MDPs can achieve an exponential reduction in the state space of an MDP and … Read more

    Applying random coordinate descent in a probability maximization scheme

  • Edit Csizmás
  • Rajmund Drenyovszki
  • Tamas Szantai
  • Csaba I. Fábián
    • Categories Stochastic Programming Tags , ,

    Gradient computation of multivariate distribution functions calls for considerable effort. A standard procedure is component-wise computation, hence coordinate descent is an attractive choice. This paper deals with constrained convex problems. We apply random coordinate descent in an approximation scheme that is an inexact cutting-plane method from a dual viewpoint. We present convergence proofs and a … Read more

    Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation

  • Michael Sucker
  • Jalal Fadili
  • Peter Ochs
    • Categories Optimization in Data Science, Other Topics Tags ,

    We use the PAC-Bayesian theory for the setting of learning-to-optimize. To the best of our knowledge, we present the first framework to learn optimization algorithms with provable generalization guarantees (PAC-Bayesian bounds) and explicit trade-off between convergence guarantees and convergence speed, which contrasts with the typical worst-case analysis. Our learned optimization algorithms provably outperform related ones … Read more