(461c) Multistage Adaptive Conditional Value at Risk Optimization Using Piecewise Linear Decision Rule

Many practical decision making problems in process operations can be represented as multi-stage adaptive optimization problem, where some decisions can be adjusted based on the information revealed at the time of decision making. Adaptive/adjustable optimization has received an increased level of research interest since the seminal paper of Ben-Tal et al. [1]. The framework includes non-adjustable variables interpreted as “here and now” decisions and adjustable variables interpreted as “wait and see” variables. While the fully-adjustable counterpart problem is generally intractable, applying some restrictions on the form of future-stage decisions can reduce the problem complexity. Among those restrictions, linear decision rule based approximation is widely applied to adjustable variables to obtain tractable approximation, where the future-stage decisions are restricted to be affine function of the uncertain parameters. Furthermore, to improve the solution optimality of linear decision rule based model while maintaining the problem tractable, various improved decision rule approximation methods were studied. For example, linear decision rule approximation can be improved by extending the affine dependency to the auxiliary variables that are used in describing the uncertainty set [2].

In the literature, decision rule based approximation has received lots of study for stochastic programming (SP) and robust optimization (RO). Each method portrays a specific meaning of the cost (objective function): stochastic programing finds the optimal expected cost, while robust optimization computes the worst-case cost. In this work, we investigate the multistage adaptive optimization with conditional value at risk (CVaR) objective. CVaR determines the average cost conditional on being on the bad tail of the distribution (expected cost that exceeds the corresponding value at risk). It provides a trade-off between stochastic programming and robust optimization, and quantifies the level of risk with the optimal solution. It also represents a mean to relate the decreased cost with the increased level of risk.

We propose a method for handling conditional value at risk objective in multistage adaptive/adjustable optimization under uncertainty. Furthermore, we addressed approximation quality improvement through piecewise linear decision rule. The idea of lifted uncertainty set [3] is implemented in the proposed CVaR optimization formulation. The proposed CVaR optimization method is further compared with stochastic programming and robust optimization formulations. A computational study is performed using two classical problems in operation research: transportation and news vendor problems. It is observed that the optimal solution to SP is not accompanied with risk level and the RO solution leads to the most conservative results. On the other hand, for CVaR objective based formulation, it provides a trade-off between the SP and RO. The numerical investigation illustrates the possibility of using CVaR as a tool to select risky versus neutral decision policies. Studies on larger scale problems are also performed to highlight the flexibility of using CVaR method, and the nature of cost improvements it brings.

References:

[1] Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A.: Adjustable robust solutions of uncertain linear programs. Mathematical Programming. 2004, 99(2), 351–376.

[2] Chen, X., Zhang, Y.: Uncertain linear programs: Extended affinely adjustable robust counterparts. Operations Research. 2009, 57(6), 1469–1482.

[3] Georghiou A, Wiesemann W, Kuhn D. Generalized decision rule approximations for stochastic programming via liftings. Mathematical Programming. 2015, 152(1-2), 301-38.