Bilevel Programming Problem with Quantile Follower’s Objective Function⋆ Sergey V. Ivanov1,2 and Vera K. Korbulakova2 1 Sobolev Institute of Mathematics Acad. Koptyug avenue, 4, Novosibirsk, Russia, 630090 sergeyivanov89@mail.ru 2 Moscow Aviation Institute, Volokolamskoe shosse, 4, Moscow, Russia, A-80, GSP-3, 125993 verakorbulakova@gmail.com Abstract. We consider a bilevel programming problem. The leader’s objective function is assumed to be linear. The follower’s problem is a quantile mini- mization problem. It is assumed that the follower’s loss function is bilinear. We obtain a deterministic equivalent of the original problem in the case of a scalar random variable. In the case of the normal distribution of the random vector, an algorithm to solve the follower’s problem is suggested. We consider an economic model example to illustrate the suggested method. Results of computation are described. Keywords: stochastic programming, bilevel programming, value-at-risk, quan- tile function. Introduction Bilevel programming problems [1–3] describe hierarchical systems. There are two deci- sion makers in these systems. The first decision maker is a so-called leader, the second decision maker is a so-called follower. The follower chooses his strategy by solving a follower’s optimization problem. In the follower’s problem, the leader’s strategy is fixed. The leader takes into account the optimal follower’s strategy as the function of his strategy. Thus the follower’s problem contains restriction on optimality of the follower’s strategy. Stochastic bilevel problems allow us to take into account random parameters, which affect the system. Usually in bilevel stochastic problems, the follower chooses his strat- egy when a realization of the random parameters becomes known [4–6]. However, from a practical point of view, the follower often does not have information about values of the random parameters. Unlike [4], in the present paper, we assume that the fol- lower does not know all parameters of his problem, but their distribution is known. ⋆ The first author’s work has been supported by Russian Science Foundation (project 15-11- 10009). Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org Bilevel Programming Problem 29 This stochastic bilevel problem is more complex, because the follower’s problem is a stochastic programming one. We suggest using the quantile function [7] as the fol- lower’s objective function. The quantile criterion (or Value-at-Risk criterion) is used to model systems with high reliability requirements. The quantile function is defined as the guaranteed with a fixed probability level of a given loss function. In this paper, we suppose that the follower’s loss function is bilinear. A particu- lar case of this quantile optimization problem is considered in [8], where a method to reduce this problem to a one-dimensional optimization problem is suggested. To com- pute the value of the objective function in this one-dimensional problem, a quadratic optimization problem has to be solved. A similar idea is used in the present paper to solve the follower’s problem. We assume that the leader’s problem is linear. For this problem, we suggest a deterministic equivalent in the one-dimensional case. In the case of normal distribution, we suggest an algorithm to solve the follower’s problem. To show the usefulness of the model, we consider a simple applied economic example. 1 Statement of the problem Let u ∈ Rn be a leader’s strategy, y ∈ Rm be a follower’s strategy. Let a random vector X with realizations x ∈ X ⊂ Rm be given. We suppose that the follower’s loss function is bilinear and given by the relation Φ(y, x) , x⊤ y. (1) Let us define the quantile function Φα (y) , min{ϕ | P{Φ(y, X) ≤ ϕ} ≥ α}, (2) where P is the probability measure generated by the distribution function of the random vector X. The value Φα (y) of the quantile function is the minimum level of the follower’s loss function Φ(y, x), which cannot be exceeded with probability α ∈ (0, 1). Let the follower’s problem be given as Φα (y) → min , (3) y∈Y (u) where α ∈ (0, 1), Y (u) , {y ∈ Rk | A2 u + B2 y ≥ b2 } (4) l2 ×k l2 ×m is the set of feasible follower’s strategies, A2 ∈ R , B2 ∈ R are matrices, b2 ∈ Rl2 is a vector. Let us denote by Y ∗ (u) , Arg min{Φα (y) | y ∈ Y (u)} (5) y the set of optimal follower’s strategies. The bilevel stochastic programming problem (the leader’s problem) is stated as cT1 u + f T y → min , (6) u∈U(y),y∈Y ∗ (u) 30 S.V. Ivanov, V.K. Korbulakova where U (y) = {u ∈ Rn | A1 u + B1 y ≥ b1 }, (7) c1 ∈ Rn , f ∈ Rk , and b1 ∈ Rl1 are vectors, A1 ∈ Rl1 ×n , B1 ∈ Rl1 ×k are matrices. 2 Scalar case In this section, we research the scalar case of the original problem. We consider this case separately, because in this case a deterministic equivalent to the original problem can be obtained. Let X be a scalar random variable, i.e., x ∈ R. Then the follower’s strategy y is also scalar. We suppose that y ≥ 0. In this case, the follower’s problem is stated as Y ∗ (u) , Arg min{Φα (y) | A2 u + B2 y ≥ b2 , y ≥ 0}, (8) y∈R where B2 = (B21 , B22 , . . . , B2l2 )⊤ . Let us denote by xα the α-quantile of the distribution of the random variable X, i.e., xα , min{x ∈ R | P{X ≤ x} ≥ α}. (9) In this section, we suppose that the leader’s strategies belong to the set U , {u ∈ Rn | A1 u ≥ b1 }, (10) i.e., B1 is the zero matrix. Proposition 1. Let the following conditions hold: (i) The follower’s problem is given by (8); (ii) xα > 0; (iii) B2i > 0, i = 1, l2 ; (iv) B1 is the zero matrix; (v) f > 0. Then the set of optimal strategies of problem (6) coincides with the set of optimal strategies u of the problem c⊤ 1 u + fψ → min (11) ψ∈R,u∈U subject to b2i − A2i u ≤ ψ, i = 1, n, (12) B2i ψ ≥ 0, (13) where A2i is the i-th row of the matrix A2 , b2i is the i-th element of the vector b2 . Also, the optimal values of objective funtions (6) and (11) are equal. Bilevel Programming Problem 31 Proof. Notice that Φα (y) = xα y because y ≥ 0. Since condition (iii) holds, from (8) it follows that b2i − A2i u y≥ , i = 1, l2 . (14) B2i Hence we have   b2i − A2i u  Y ∗ (u) = max ,0 . (15) i=1,l2 B2i The set Y ∗ (u) is a singleton. Substituting (15) into (6), we obtain the problem   b2i − A2i u  c⊤ 1 u + f max , 0 → min . (16) i=1,l2 B2i u∈U Introducing the auxiliary variable ψ, we can reduce problem (16) to linear programming problem (11) subject to (12) and (13). We thus proved that the original problem can be reduced to a linear programming problem under assumptions of Proposition 1. As we can see from the proof, conditions of Proposition 1 provide the existence of an optimal strategy of the original problem. 3 Gaussian Case In this section, we return to general statement (6), but we assume that the random vector X is normal distributed with expectation µ and covariance matrix Σ, i.e., X ∼ N (µ, Σ). Also, we assume that α ∈ (0.5, 1). Let us consider follower’s problem (3). If X ∼ N (µ, Σ), then p Φα (y) = µ⊤ y + zα y ⊤ Σy, (17) where zα is the α-quantile of the standard normal distribution. Hence the follower’s problem can be written as p µ⊤ y + zα y ⊤ Σy → min . (18) y∈Y (u) p Since the function y 7→ y ⊤ Σy is a seminorm, problem (18) is convex. This problem can be solved using methods of convex programming (see, e.g., [9]). However, we would like to notice that problem (18) can be reduced to a quadratic programming problem if µ⊤ y is fixed. Let us add the constraint µ⊤ y = θ to problem (18). Then an optimal strategy of the follower’s problem can be found as a solution to the problem p θ + zα y ⊤ Σy → min (19) y∈Y (u) subject to µ⊤ y = θ. (20) It is easily seen that problem (19) is equivalent to the quadratic programming problem y ⊤ Σy → min . (21) y∈Y (u), µ⊤ y=θ 32 S.V. Ivanov, V.K. Korbulakova Let us denote by y(θ) an optimal solution to problem (21). Since the leader’s strategy u is fixed, we omit dependence y(θ) on u. Consider the function q g(θ) = θ + zα y(θ)⊤ Σy(θ). (22) Notice that the value g(θ) is equal to the optimal objective value of problem (18) under additional constraint µ⊤ y = θ. So we can find an optimal value θ denoted by θ∗ solving the problem g(θ) → min . (23) θ∈R Since problem (18) is convex and the constraint µ⊤ y = θ is linear, the function g(θ) is unimodal. If it is known that θ∗ ∈ [θmin , θmax ], where θmin and θmax are lower and upper bounds for θ∗ , then problem (23) can be solved using, e.g., the golden section search [10]. Thus, the following algorithm to solve the follower’s problem can be suggested. Algorithm 1. Find optimal θ∗ ∈ [θmin , θmax ]; 2. Find optimal y ∗ by solving problem (21) for θ = θ∗ . Using the follower’s optimal strategy, we can solve the leader’s problem. The leader’s problem is nonconvex in general. Its optimal solution can be found using methods of nonconvex optimization. Also, the bilevel problem can be reduced to a nonconvex optimization problem with equilibrium constraints (see, e.g., [2]) using the Karush- Kuhn-Tucker conditions. If the leader’s strategy is scalar, the leader’s problem can be solved using methods of one-dimensional optimization. 4 Example Let us solve the following simple applied problem. Let the leader be an investor, the follower be a manufacturer. The leader’s strategy u ∈ R is the volume of investments. The manufacturer produces two types of products. The follower’s strategy is the vector (y1 , y2 )⊤ , where yi , i = 1, 2, is the volume of output of the i-th product. The follower’s objective function is given by Φα (y) = min{ϕ | P{−(X1 y1 + X2 y2 ) ≤ ϕ} ≥ α}. (24) where Xi , i = 1, 2, is a random profit from one unit of the i-th product. The follower’s problem is stated as Φα (y) → min (25) y subject to B2 y ≤ b 2 , (26) b⊤ 3 y ≤ u, (27) where B2 is a technological matrix, b2 is a vector of resources, b3 is a vector of manufac- turing costs. Notice that the value of the follower’s objective function is the minimum Bilevel Programming Problem 33 level of the follower’s loss (i.e., −X ⊤ y = −(X1 y1 + X2 y2 )), which cannot be exceeded with probability α. The leader’s problem is stated as u − f ⊤y → min , (28) u≥0,y∈Y ∗ (u) where fi is an investor’s profit from one unit of the i-th product. The leader intends to minimize difference between the volume u of investments and the profit f ⊤ y. We solve the problem for the following input data: B2 = 1 2 , b2 = 2, b3 = (2, 1.6)⊤ ; f = (1.8, 2.4)⊤; α = 0.975.  (29) We assume that     2 0.7 0 X∼ , . (30) 3 0 1 Using the suggested algorithm, we can solve the follower’s problem for a fixed value of the leader’s strategy. By setting different values of the follower’s strategy, we obtain the plot of the leader’s objective value against the leader’s strategy. This plot is depicted in Fig. 1. As we can see, small and large values of investments give large value of the 0.4 Leader's objective value 0.2 0.5 1 1.5 2 2.5 3 0 Leader's strategy, u -0.2 -0.4 -0.6 Fig. 1. The plot of the leader’s objective value against the leader’s strategy objective function. In the case of small investments, the leader does not have profit. In the case of large investments, the profit is much less than the volume of the investments. Solving the leader’s problem, we obtain the following results. The optimal leader’s strategy is u∗ = 2.024; the optimal leader’s objective value is equal to −0.5872; the optimal follower’s strategy is y ∗ = (0.3540, 0.8225)⊤. 5 Conclusion In this paper, the bilevel programming problem with quantile follower’s objective func- tion is considered. We should notice that this problem is difficult to solve because it is 34 S.V. Ivanov, V.K. Korbulakova nonconvex in general. However, we could find the optimal solution to the problem for the considered example, where the leader’s strategy is scalar. References 1. Bard, J.F.: Practical bilevel optimization: Algorithms and applications. Kluwer Academie Publishers, Dordrecht (1998) 2. Dempe, S.: Foundations of bilevel programming. Kluwer Academie Publishers, Dordrecht (2002) 3. Dempe, S., Kalashnikov, V., Pérez-Valdés, G.A., Kalashnykova, N.: Bilevel programming problems — theory, algorithms and applications to energy networks, Springer Verlag (2015) 4. Ivanov, S.V.: Bilevel stochastic linear programming problems with quantile criterion. Au- tomat Rem Control. 75, 107–118 (2014) 5. Chen, A., Kim, J., Zhou, Z., Chootinan, P.: Alpha reliable network design problem. Trans- portation Research Record: Journal of the Transportation Research Board. 2029, 49–57 (2007) 6. Christiansen, S., Patriksson, M., Wynter, L.: Stochastic bilevel programming in structural optimization. Struct Multidiscip O. 21, 361–371 (2001) 7. Kibzun, A.I., Kan, Yu.S.: Stochastic programming problems with probability and quantile functions. John Wiley and Sons, Chichester, New York, Brisbane, Toronto, Singapore (1996) 8. Kan, Yu.S., Tuzov, N.V.: Quantile minimization of the normal distribution of a bilinear loss function. Automat Rem Control. 59, 1568–1576 (1998) 9. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cam- bridge (2004) 10. Vasil’ev, F.P.: Optimization Methods (in Russian). MTsNMO, Moscow (2011)