Optimization Online


Multilevel Optimization Modeling for Risk-Averse Stochastic Programming

Jonathan Eckstein(jeckstei***at***rci.rutgers.edu)
Deniz Eskandani(deniz.eskandani***at***rutgers.edu)
Jingnan Fan(jf546***at***rutgers.edu)

Abstract: Coherent risk measures have become a popular tool for incorporating risk aversion into stochastic optimization models. For dynamic models in which uncertainty is resolved at more than one stage, however, using coherent risk measures within a standard single-level optimization framework becomes problematic. To avoid severe time-consistency difficulties, the current state of the art is to employ risk measures of a specific nested form, which unfortunately have some undesirable and somewhat counterintuitive modeling properties. For one thing, this technique requires increasing risk aversion as risks and reward recede in time. Further, it produces objective functions that cannot be law invariant with respect to the total incurred costs and rewards, meaning that two solutions with identical probability distributions of final wealth may be assigned different levels of risk, and the nested form of the objective function cannot be simplified. These properties deter practical acceptance of such models, and are particularly undesirable for situations with close final time horizons. This paper summarizes these issues and then presents an alternative multilevel optimization modeling approach that enforces a form of time consistency through constraints rather than by restricting the modeler's choice of objective function. This technique leads to models that are time-consistent even while using time-inconsistent risk measures, and can easily be formulated to be law invariant with respect to the final wealth if so desired. We argue that this approach should be the starting point for all multistage optimization modeling. When used with time-consistent objective functions, we show its multilevel optimization constraints become redundant and the associated models thus simplify to a more familiar single-objective form. Unfortunately, this paper also shows that its proposed approach leads to NP-hard models, even in the simplest imaginable setting in which it would be needed: three-stage linear problems on a finite probability space, using the standard mean-semideviation and average-value-at-risk measures. Finally, we show that for a simple but reasonably realistic test application, that the kind of models we propose, while being drawn from an NP-hard family and certainly more time consuming to solve than those obtained from the nested-objective approach, are readily solvable to global optimality using a standard commercial MILP solver. Therefore, there seems some promise of the modeling approach being useful despite its computational complexity properties.

Keywords: Stochastic programming, risk measures, computational complexity, multilevel optimization

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 08/24/2014
Entry Accepted: 08/25/2014
Entry Last Modified: 08/24/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society