Year: 2021

Exponential Decay of Sensitivity in Graph-Structured Nonlinear Programs

  • Mihai Anitescu
  • Victor M. Zavala
  • Sungho Shin
    • Categories Nonlinear Optimization Tags

    We study solution sensitivity for nonlinear programs (NLPs) whose structure is induced by a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. These graph-structured NLPs arise in many applications such as dynamic optimization, stochastic optimization, optimization with partial differential equations, and network optimization. We show that the sensitivity of the primal-dual solution at node $i\in \mathcal{V}$ against a data perturbation at … Read more

    A Robust Approach for Modeling Limited Observability in Bilevel Optimization

  • Yasmine Beck
  • Martin Schmidt
    • Categories Finance and Economics, Robust Optimization Tags , , , ,

    In bilevel optimization, hierarchical optimization problems are considered in which two players – the leader and the follower – act and react in a non-cooperative and sequential manner. In many real-world applications, the leader may face a follower whose reaction deviates from the one expected by the leader due to some kind of bounded rationality. … Read more

    Heteroscedasticity-aware residuals-based contextual stochastic optimization

  • Rohit Kannan
  • Güzin Bayraksan
  • James R. Luedtke
    • Categories Robust Optimization, Stochastic Programming Tags , , , , , ,

    We explore generalizations of some integrated learning and optimization frameworks for data-driven contextual stochastic optimization that can adapt to heteroscedasticity. We identify conditions on the stochastic program, data generation process, and the prediction setup under which these generalizations possess asymptotic and finite sample guarantees for a class of stochastic programs, including two-stage stochastic mixed-integer programs … Read more

    Worst-case analysis of clique MIPs

  • Austin Buchanan
  • Jose L. Walteros
  • Mohammad Javad Naderi
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Combinatorial Optimization

    The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) … Read more

    First-order algorithms for robust optimization problems via convex-concave saddle-point Lagrangian reformulation

  • Krzysztof Postek
  • Shimrit Shtern
    • Categories Convex Optimization, Robust Optimization

    Robust optimization (RO) is one of the key paradigms for solving optimization problems affected by uncertainty. Two principal approaches for RO, the robust counterpart method and the adversarial approach, potentially lead to excessively large optimization problems. For that reason, first order approaches, based on online-convex-optimization, have been proposed (Ben-Tal et al. (2015), Kilinc-Karzan and Ho-Nguyen … Read more

    Solving Multiplicative Programs by Binary-encoding the Multiplication Operation

  • Hadi Charkhgard
  • Fabian Rigterink
  • Payman Ghasemi Saghand
  • Vahid Mahmoodian
    • Categories Applications - OR and Management Sciences, Game Theory Tags ,

    Multiplicative programs in the form of maximization and/or minimization have numerous applications in conservation planning, game theory, and multi-objective optimization settings. In practice, multiplicative programs are challenging to solve because of their multiplicative objective function (a product of continuous or integer variables). These challenges are twofold: 1. As the number of factors in the objective … Read more

    Random-Sampling Monte-Carlo Tree Search Methods for Cost Approximation in Long-Horizon Optimal Control

  • Hans D Mittelmann
  • Shankarachary Ragi
    • Categories Applications - Science and Engineering, Control Applications Tags , , ,

    We develop Monte-Carlo based heuristic approaches to approximate the objective function in long horizon optimal control problems. In these approaches, to approximate the expectation operator in the objective function, we evolve the system state over multiple trajectories into the future while sampling the noise disturbances at each time-step, and find the average (or weighted average) … Read more

    Dynamic string-averaging CQ-methods for the split feasibility problem with percentage violation constraints arising in radiation therapy treatment planning

  • Mark Brooke
  • Yair Censor
  • Aviv Gibali
    • Categories Biomedical Applications, Nonlinear Optimization Tags , , , , , , ,

    We study a feasibility-seeking problem with percentage violation constraints. These are additional constraints, that are appended to an existing family of constraints, which single out certain subsets of the existing constraints and declare that up to a specified fraction of the number of constraints in each subset is allowed to be violated by up to … Read more

    Model-Free Assortment Pricing with Transaction Data

  • Ningyuan Chen
  • Andre Augusto Cire
  • Ming Hu
  • Saman Lagzi
    • Categories Applications - OR and Management Sciences, Approximation Algorithms, Robust Optimization

    We study a problem in which a firm sets prices for products based on the transaction data, i.e., which product past customers chose from an assortment and what were the historical prices that they observed. Our approach does not impose a model on the distribution of the customers’ valuations and only assumes, instead, that purchase … Read more

    The structure of conservative gradient fields

  • Adrian Lewis
  • Tonghua Tian
    • Categories Nonsmooth Optimization Tags , , , , , , ,

    The classical Clarke subdifferential alone is inadequate for understanding automatic differentiation in nonsmooth contexts. Instead, we can sometimes rely on enlarged generalized gradients called “conservative fields”, defined through the natural path-wise chain rule: one application is the convergence analysis of gradient-based deep learning algorithms. In the semi-algebraic case, we show that all conservative fields are … Read more