Month: July 2015

Fully Polynomial Time hBcApproximation Schemes for Continuous Stochastic Convex Dynamic Programs

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming Tags , ,

    We develop fully polynomial time $(\Sigma,\Pi)$-approximation schemes for stochastic dynamic programs with continuous state and action spaces, when the single-period cost functions are convex Lipschitz-continuous functions that are accessed via value oracle calls. That is, for every given additive error parameter $\Sigma>0$ and multiplicative error factor $\Pi=1+\epsilon>1$, the scheme returns a feasible solution whose value … Read more

    An optimal randomized incremental gradient method

  • Guanghui Lan
  • Yi Zhou
    • Categories Convex Optimization Tags , , , , ,

    In this paper, we consider a class of finite-sum convex optimization problems whose objective function is given by the summation of $m$ ($\ge 1$) smooth components together with some other relatively simple terms. We first introduce a deterministic primal-dual gradient (PDG) method that can achieve the optimal black-box iteration complexity for solving these composite optimization … Read more

    Robust truss optimization using the sequential parametric convex approximation method

  • Alfredo Canelas
  • Miguel Carrasco
  • Julio López
    • Categories Global Optimization, Multidisciplinary Design Optimization, Second-Order Cone Programming Tags , , ,

    We study the design of robust truss structures under mechanical equilibrium, displacements and stress constraints. Our main objective is to minimize the total amount of material, for the purpose of finding the most economic structure. A robust design is found by considering load perturbations. The nature of the constraints makes the mathematical program nonconvex. In … Read more

    The Value of Stochastic Programming in Day-Ahead and Intraday Generation Unit Commitment

  • Kenneth McKinnon
  • Tim Schulze
    • Categories Scheduling, Stochastic Programming Tags , , ,

    The recent expansion of renewable energy supplies has prompted the development of a variety of efficient stochastic optimization models and solution techniques for hydro-thermal scheduling. However, little has been published about the added value of stochastic models over deterministic ones. In the context of day-ahead and intraday unit commitment under wind uncertainty, we compare two-stage … Read more

    A Stabilised Scenario Decomposition Algorithm Applied to Stochastic Unit Commitment Problems

  • Andreas Grothey
  • Kenneth McKinnon
  • Tim Schulze
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , , ,

    In recent years the expansion of energy supplies from volatile renewable sources has triggered an increased interest in stochastic optimization models for hydro-thermal unit commitment. Several studies have modelled this as a two-stage or multi-stage stochastic mixed-integer optimization problem. Solving such problems directly is computationally intractable for large instances, and alternative approaches are required. In … Read more

    A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function

  • Radu Ioan Bot
  • Ernö Robert Csetnek
    • Categories Nonsmooth Optimization, Systems governed by Differential Equations Optimization Tags , , , ,

    We address the minimization of the sum of a proper, convex and lower semicontinuous with a (possibly nonconvex) smooth function from the perspective of an implicit dynamical system of forward-backward type. The latter is formulated by means of the gradient of the smooth function and of the proximal point operator of the nonsmooth one. The … Read more

    BFO, a trainable derivative-free Brute Force Optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables

  • Margherita Porcelli
  • Philippe L. Toint
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization, Nonlinear Optimization Tags , , , ,

    A direct-search derivative-free Matlab optimizer for bound-constrained problems is described, whose remarkable features are its ability to handle a mix of continuous and discrete variables, a versatile interface as well as a novel self-training option. Its performance compares favourably with that of NOMAD, a state-of-the art package. It is also applicable to multilevel equilibrium- or … Read more

    Using the Johnson-Lindenstrauss lemma in linear and integer programming

  • Leo Liberti
  • Pierre-Louis Poirion
  • Ky Vu
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , , ,

    The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this paper we … Read more

    Near-Optimal Ambiguity sets for Distributionally Robust Optimization

  • Vishal Gupta
    • Categories Robust Optimization, Statistics Tags , ,

    We propose a novel, Bayesian framework for assessing the relative strengths of data-driven ambiguity sets in distributionally robust optimization (DRO). The key idea is to measure the relative size between a candidate ambiguity set and an \emph{asymptotically optimal} set as the amount of data grows large. This asymptotically optimal set is provably the smallest convex … Read more