Month: February 2017

From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

  • Daniel Kuhn
  • Tobias Sutter
  • John Lygeros
  • Peyman Mohajerin Esfahani
    • Categories Dynamic Programming, Infinite Dimensional Optimization, Stochastic Programming Tags , , , ,

    We consider linear programming (LP) problems in infinite dimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinite-dimensional LP to tractable finite convex programs in which the performance of the approximation is quantified explicitly. To this end, we adopt the recent developments in two areas of … Read more

    Dynamic Data-Driven Estimation of Non-Parametric Choice Models

  • Nam Ho-Nguyen
  • Fatma Kılınç-Karzan
    • Categories Convex Optimization, Marketing Tags , , ,

    We study non-parametric estimation of choice models, which was introduced to alleviate unreasonable assumptions in traditional parametric models, and are prevalent in several application areas. Existing literature focuses only on the static observational setting where all of the observations are given upfront, and lacks algorithms that provide explicit convergence rate guarantees or an a priori … Read more

    Direct search based on probabilistic feasible descent for bound and linearly constrained problems

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
  • Z. Zhang
    • Categories Bound-constrained Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    Direct search is a methodology for derivative-free optimization whose iterations are characterized by evaluating the objective function using a set of polling directions. In deterministic direct search applied to smooth objectives, these directions must somehow conform to the geometry of the feasible region and typically consist of positive generators of approximate tangent cones (which then … Read more

    Complexity and global rates of trust-region methods based on probabilistic models

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
  • Z. Zhang
    • Categories Stochastic Programming, Unconstrained Optimization Tags , , ,

    Trust-region algorithms have been proved to globally converge with probability one when the accuracy of the trust-region models is imposed with a certain probability conditioning on the iteration history. In this paper, we study their complexity, providing global rates and worst case complexity bounds on the number of iterations (with overwhelmingly high probability), for both … Read more

    MultiGLODS: Global and Local Multiobjective Optimization using Direct Search

  • Ana Luisa Custódio
  • J. F. A. Madeira
    • Categories Global Optimization, Nonlinear Optimization Tags , , , ,

    The optimization of multimodal functions is a challenging task, in particular when derivatives are not available for use. Recently, in a directional direct search framework, a clever multistart strategy was proposed for global derivative-free optimization of single objective functions. The goal of the current work is to generalize this approach to the computation of global … Read more

    Dynamic programming algorithms, efficient solution of the LP-relaxation and approximation schemes for the Penalized Knapsack Problem

  • Federico Della Croce
  • Ulrich Pferschy
  • Rosario Scatamacchia
    • Categories 0-1 Programming, Combinatorial Optimization, Dynamic Programming Tags , , ,

    We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solution. We propose an exact approach relying on a procedure which narrows the relevant range … Read more

    Simultaneous convexification of bilinear functions over polytopes with application to network interdiction

  • Danial Davarnia
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Network Optimization

    We study the simultaneous convexification of graphs of bilinear functions that contain bilinear products between variables x and y, where x belongs to a general polytope and y belongs to a simplex. We propose a constructive procedure to obtain a linear description of the convex hull of the resulting set. This procedure can be applied … Read more

    Gas Storage Valuation in Incomplete Markets

  • Nils Löhndorf
  • David Wozabal
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , , ,

    Natural gas storage valuation is an important problem in energy trading, yet most valuation approaches are based on heuristics or ignore that gas markets are incomplete. We propose an exact valuation model for incomplete gas markets based on multistage stochastic programming. Market incompleteness structurally changes the problem of storage valuation and asset backed trading and … Read more

    Locality sensitive heuristics for solving the Data Mule Routing Problem

  • Lucia Drummond
  • Luiz Satoru Ochi
  • P.H. González
  • Philippe Michelon
  • P.L.A Munhoz
  • U.S. Souza
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Telecommunications Tags , , , ,

    A usual way to collect data in a Wireless Sensor Network (WSN) is by the support of a special agent, called data mule, that moves between sensor nodes and performs all communication between them. In this work, the focus is on the construction of the route that the data mule must follow to serve all … Read more

    Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary

  • Gabriel Haeser
  • Yinyu Ye
  • Hongcheng Liu
    • Categories Nonlinear Optimization Tags , , , ,

    In this paper we consider the minimization of a continuous function that is potentially not differentiable or not twice differentiable on the boundary of the feasible region. By exploiting an interior point technique, we present first- and second-order optimality conditions for this problem that reduces to classical ones when the derivative on the boundary is … Read more