Bilevel Programming Problem with Quantile ⋆ Follower's Ob jective Function

Abstract

We consider a bilevel programming problem. The leader's objective function is assumed to be linear. The follower's problem is a quantile minimization 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
• quantile function

Introduction

Bilevel programming problems [1–3] describe hierarchical systems. There are two decision 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 strategy 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 follower 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-1110009).

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 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 follower’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 particular 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 compute 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.

Let us define the quantile function

Φα(y) , min{ϕ | P{Φ(y, X ) ≤ ϕ} ≥ α}, 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 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) where 2

Scalar case

U (y) = {u ∈ Rn | A1u + B1y ≥ b1}, c1 ∈ Rn, f ∈ Rk, and b1 ∈ Rl1 are vectors, A1 ∈ Rl1×n, B1 ∈ Rl1×k are matrices. 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) | A2u + B2y ≥ b2, y ≥ 0},

y∈R where B2 = (B21, B22, . . . , B2l2 )⊤.

Let us denote by xα the α-quantile of the distribution of the random variable X , i.e.,

In this section, we suppose that the leader’s strategies belong to the set xα , min{x ∈ R | P{X ≤ x} ≥ α}.

U , {u ∈ Rn | A1u ≥ b1}, ( 7 ) ( 8 ) ( 9 ) ( 10 ) (11) (12) (13) 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. 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.

Then the set of optimal strategies of problem ( 6 ) coincides with the set of optimal strategies u of the problem subject to c1⊤u + f ψ →

min ψ∈R,u∈U b2i − A2iu

B2i

≤ ψ, i = 1, n, ψ ≥ 0,

Hence we have

Proof. Notice that Φα(y) = xαy because y ≥ 0. Since condition (iii) holds, from ( 8 ) it follows that y ≥ b2i − A2iu , i = 1, l2.

B2i Y ∗(u) = max i=1,l2 b2i − A2iu , 0

B2i .

The set Y ∗(u) is a singleton. Substituting (15) into ( 6 ), we obtain the problem c1⊤u + f max i=1,l2 b2i − A2iu , 0

B2i → min .

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. (14) (15) (16) (17) (18) (19) (20) . 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 Since the function y 7→ py⊤Σ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 where zα is the α-quantile of the standard normal distribution. Hence the follower’s problem can be written as Φα(y) = μ⊤y + zαpy⊤Σy, μ⊤y + zαpy⊤Σy →

min . y∈Y (u) 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

g(θ) = θ + zαqy(θ)⊤Σy(θ).

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 .

θ∈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 KarushKuhn-Tucker conditions. If the leader’s strategy is scalar, the leader’s problem can be solved using methods of one-dimensional optimization. (22) (23) (24) (25) (26) (27) where B2 is a technological matrix, b2 is a vector of resources, b3 is a vector of manufacturing costs. Notice that the value of the follower’s objective function is the minimum 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{−(X1y1 + X2y2) ≤ ϕ} ≥ α}. where Xi, i = 1, 2, is a random profit from one unit of the i-th product. The follower’s problem is stated as subject to Φα(y) → min

y B2y ≤ b2, b3⊤y ≤ u, level of the follower’s loss (i.e., −X ⊤y = −(X1y1 + X2y2)), which cannot be exceeded with probability α.

The leader’s problem is stated as , 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: 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 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 function is considered. We should notice that this problem is difficult to solve because it is 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´ erez -Vald´es, 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 . Automat Rem Control . 75 , 107 - 118 ( 2014 )

5. Chen , A. , Kim , J. , Zhou , Z. , Chootinan , P. : Alpha reliable network design problem . Transportation 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, Cambridge ( 2004 )

10. Vasil'ev , F.P. : Optimization Methods (in Russian) . MTsNMO , Moscow ( 2011 )