Month: March 2018

Multistage stochastic programs with a random number of stages: dynamic programming equations, solution methods, and application to portfolio selection

  • Vincent Guigues
    • Categories Finance and Economics, Stochastic Programming

    We introduce the class of multistage stochastic optimization problems with a random number of stages. For such problems, we show how to write dynamic programming equations and detail the Stochastic Dual Dynamic Programming algorithm to solve these equations. Finally, we consider a portfolio selection problem over an optimization period of random duration. For several instances … Read more

    The Mesh Adaptive Direct Search Algorithm for Granular and Discrete Variables

  • Charles Audet
  • Sébastien Le Digabel
  • Christophe Tribes
    • Categories Nonlinear Optimization Tags , , , ,

    The mesh adaptive direct search (Mads) algorithm is designed for blackbox optimization problems for which the functions defining the objective and the constraints are typically the outputs of a simulation seen as a blackbox. It is a derivative-free optimization method designed for continuous variables and is supported by a convergence analysis based on the Clarke … Read more

    Computing the Spark: Mixed-Integer Programming for the (Vector) Matroid Girth Problem

  • Andreas M. Tillmann
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Graphs and Matroids Tags , , , ,

    We investigate the NP-hard problem of computing the spark of a matrix (i.e., the smallest number of linearly dependent columns), a key parameter in compressed sensing and sparse signal recovery. To that end, we identify polynomially solvable special cases, gather upper and lower bounding procedures, and propose several exact (mixed-)integer programming models and linear programming … Read more

    Axial symmetry indices for convex cones: axiomatic formalism and applications

  • Alberto Seeger
  • Mounir Torki
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We address the issue of measuring the degree of axial symmetry of a convex cone. By following an axiomatic approach, we introduce and explore the concept of axial symmetry index. This concept is illustrated with the help of several interesting examples. By way of application, we establish a conic version of the Blekherman inequality concerning … Read more

    Optimality conditions and global convergence for nonlinear semidefinite programming

  • Roberto Andreani
  • Gabriel Haeser
  • Daiana O. Santos
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , , ,

    Sequential optimality conditions have played a major role in unifying and extending global convergence results for several classes of algorithms for general nonlinear optimization. In this paper, we extend theses concepts for nonlinear semidefinite programming. We define two sequential optimality conditions for nonlinear semidefinite programming. The first is a natural extension of the so-called Approximate-Karush-Kuhn-Tucker … Read more

    Dual approach for two-stage robust nonlinear optimization

  • Frans J.C.T. de Ruiter
  • Dick den Hertog
  • Jianzhe Zhen
    • Categories Robust Optimization Tags , , ,

    Adjustable robust minimization problems in which the adjustable variables appear in a convex way are difficult to solve. For example, if we substitute linear decision rules for the adjustable variables, then the model becomes convex in the uncertain parameters, whereas for computational tractability we need concavity in the uncertain parameters. In this paper we reformulate … Read more

    MIQP-Based Algorithm for the Global Solution of Economic Dispatch Problems with Valve-Point Effects

  • Pierre-Antoine Absil
  • Benoît Sluysmans
  • Nicolas Stevens
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

    Even in a static setting, the economic load dispatch problem (ELDP)—namely the cost-optimal distribution of power among generating units to meet a specific demand subject to system constraints—turns out to be a challenge owing to the consideration of valve-point effects (VPE), which make the cost function nonsmooth and nonconvex. We present a new method, termed … Read more

    Scenario Reduction for Risk-Averse Stochastic Programs

  • Sebastian Arpon
  • Tito Homem-de-Mello
  • Bernardo K. Pagnoncelli
    • Categories Stochastic Programming

    In this paper we discuss scenario reduction methods for risk-averse stochastic optimization problems. Scenario reduction techniques have received some attention in the literature and are used by practitioners, as such methods allow for an approximation of the random variables in the problem with a moderate number of scenarios, which in turn make the optimization problem … Read more

    Models and algorithms for the robust resource constrained shortest path problem

  • Fatma Gzara
  • Da Lu
    • Categories Network Optimization, Robust Optimization, Transportation Tags , , ,

    We study the robust resource constrained shortest path problem (RCSPP) under uncertainty in cost and multiple resource consumption. Contrary to the deterministic RCSPP where the cost and the consumption of resources on an arc are known and fixed, the robust RCSPP models the case where both the cost and the resource consumption are random, and … Read more

    A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization

  • Shicong Cen
  • Andre Milzarek
  • Michael Ulbrich
  • Zaiwen Wen
  • Xiantao Xiao
    • Categories Nonsmooth Optimization Tags , , , ,

    In this work, we present a globalized stochastic semismooth Newton method for solving stochastic optimization problems involving smooth nonconvex and nonsmooth convex terms in the objective function. We assume that only noisy gradient and Hessian information of the smooth part of the objective function is available via calling stochastic first and second order oracles. The … Read more