Likelihood robust optimization for data-driven problems

Abstract

We consider optimal decision-making problems in an uncertain environment. In particular, we consider the case in which the distribution of the input is unknown, yet there is some historical data drawn from the distribution. In this paper, we propose a new type of distributionally robust optimization model called the likelihood robust optimization (LRO) model for this class of problems. In contrast to previous work on distributionally robust optimization that focuses on certain parameters (e.g., mean, variance, etc.) of the input distribution, we exploit the historical data and define the accessible distribution set to contain only those distributions that make the observed data achieve a certain level of likelihood. Then we formulate the targeting problem as one of optimizing the expected value of the objective function under the worst-case distribution in that set. Our model avoids the over-conservativeness of some prior robust approaches by ruling out unrealistic distributions while maintaining robustness of the solution for any statistically likely outcomes. We present statistical analyses of our model using Bayesian statistics and empirical likelihood theory. Specifically, we prove the asymptotic behavior of our distribution set and establish the relationship between our model and other distributionally robust models. To test the performance of our model, we apply it to the newsvendor problem and the portfolio selection problem. The test results show that the solutions of our model indeed have desirable performance.

Appendix

Proof of Proposition 1

First, we show that problem (4) is a convex optimization problem. To see this, we first write (4) in a slightly different but equivalent way:

$$\begin{aligned} \text{ maximize }_{\varvec{x},\lambda ,\mu , \varvec{y}}&\mu +\lambda (\gamma +N-\sum _{i=1}^nN_i\log {N_i})-N\lambda \log {\lambda }+\lambda \sum _{i=1}^nN_i\log {y_i}\nonumber \\ \text{ s.t. }&\lambda \ge 0, \quad h(\varvec{x},\varvec{\xi }_i)-\mu \ge y_i, \forall i, \quad \varvec{x}\in D. \end{aligned}$$

(15)

Note that because the objective is to maximize, (15) is an equivalent representation of (4). It is easy to see that when $h(\varvec{x}, \varvec{\xi })$ is concave in $\varvec{x}$, the constraints are all convex constraints. Now we only need to verify that the objective function is jointly concave. Note that the first two terms of the objective function are linear, therefore, we only need to show that the function $-N\lambda \log {\lambda } + \lambda \sum _{i=1}^n N_i \log {y_i}$ is jointly concave in $\lambda$ and $\varvec{y}$. We consider the Hessian matrix of the objective function with respect to $\lambda$ and $\varvec{y}$:

$$\begin{aligned} H = \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} -\frac{N}{\lambda } &{} \frac{N_1}{y_1} &{} \frac{N_2}{y_2} &{} \cdots &{} \frac{N_n}{y_n} \\ \frac{N_1}{y_1} &{} -\frac{\lambda N_1}{y_1^2} &{} 0 &{} \cdots &{} 0 \\ \frac{N_2}{y_2}&{} 0 &{} -\frac{\lambda N_2}{y_2^2} &{} \cdots &{} 0\\ \vdots &{} \vdots &{} \vdots &{} \ddots &{} \vdots \\ \frac{N_n}{y_n} &{} 0 &{} 0 &{} \cdots &{} -\frac{\lambda N_n}{y_n^2} \end{array} \right) . \end{aligned}$$

Now consider a diagonal matrix A with diagonal elements $\lambda , y_1,\ldots ,y_n$, then we have

$$\begin{aligned} A^THA = \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} -N\lambda &{} \lambda N_1 &{} \lambda N_2 &{} \cdots &{} \lambda N_n \\ \lambda N_1 &{} -\lambda N_1 &{} 0 &{} \cdots &{} 0 \\ \lambda N_2&{} 0 &{} -\lambda N_2 &{} \cdots &{} 0\\ \vdots &{} \vdots &{} \vdots &{} \ddots &{} \vdots \\ \lambda N_n &{} 0 &{} 0 &{} \cdots &{} -\lambda N_n \end{array} \right) \end{aligned}$$

which is a diagonal dominant matrix with all negative diagonal elements. Thus $A^THA$ is negative semidefinite, which further implies that H is negative semidefinite. Thus the objective function is a concave function and the optimization problem is a convex optimization problem.

Finally, we prove that the worst-case distribution satisfies:

$$\begin{aligned} p_i = \frac{\lambda ^* N_i}{h(\varvec{x}^*, {\varvec{\xi }}_i) - \mu ^*}, \quad \forall i. \end{aligned}$$

We consider the derivative of the Lagrangian function $L(\varvec{p},\lambda , \mu )$ with respect to $p_i$. By the KKT conditions, we must have $p_i\nabla _{p_i} L(\varvec{p}, \lambda , \mu ) = 0$, which implies that $p_i(h(\varvec{x}^*, \varvec{\xi }_i) -\mu ^*) = \lambda ^* N_i$. Also, we note that in (4), since there is a term of $\log {(h(\varvec{x}, \varvec{\xi }_i) -\mu )}$, therefore, $h(\varvec{x}^*, \varvec{\xi }_i) -\mu ^*\ne 0$. Thus Proposition 1 is proved. $\square$