Advances in Applied Mathematics
Vol.07 No.07(2018), Article ID:25988,7 pages
10.12677/AAM.2018.77105

Statistical Inference of Two-Stage Linear Second-Order Conic Stochastic Programs

Qingsong Duan, Liwei Zhang

School of Mathematical Sciences, Dalian University of Technology, Dalian Liaoning

Received: Jun. 24th, 2018; accepted: Jul. 13th, 2018; published: Jul. 20th, 2018

ABSTRACT

In this paper, we consider a linear second-order conic optimization problem and in which all parameters are perturbed and random variables. We demonstrate that the optimal value function can be expressed as a min-max optimization problem over compact convex set, and we present the asymptotic distribution of an SAA estimator of the optimal value for a two-stage program whose second stage problem is a second-order conic programming problem.

Keywords:Second-Order Conic Optimization, Two-Stage Stochastic Problem, SAA Estimator Asymptotic Distribution

线性二阶锥两阶段随机规划问题的统计推断

段庆松,张立卫

大连理工大学,数学科学学院,辽宁 大连

收稿日期:2018年6月24日;录用日期:2018年7月13日;发布日期:2018年7月20日

摘 要

在本篇文章中,我们考虑一类带有线性二阶锥约束的两阶段随机规划问题,该问题的全部参数都是随机变量。我们将原问题的最优值函数改写为一个包含紧致凸约束集合的极小极大问题,利用第二阶段问题的Lagrange对偶性质,得到其最优值函数的样本均值近似(SAA)估计的渐近分布。

关键词 :二阶锥优化,两阶段随机规划问题,SAA估计的渐近分布

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

经典的线性两阶段优化问题的模型如下:

min x n d T x + Ε [ ( θ ( x , ξ ) ) ] s .t . A x = b , x 0 , θ ( x , ξ ) = min y m c T y s .t . W y + T x = h , y 0 , (1.1)

其中 x n , y m 分别是第一阶段和第二阶段问题的决策变量, d n ξ = { c , W , T , h } 是随机变量,其中 c n , W l × m , T l × n , h l 。当 ξ 服从的概率分布进行扰动时, θ ( x , ξ ) 的连续性在研究线性二阶锥问题的稳定性分析中起着关键的作用。很多文章研究过包含线性二阶锥约束的优化问题,然而所有变量都是随机的情况很少被考虑,只有少数的例外:Römisch和Wets在 [1] 中得到了最优值函数 θ ( x , ξ ) 的Lipschitz连续性,Han和Chen在 [2] 中研究了所含参数全是随机变量的线性规划的连续性质。

本篇文章中,我们研究带有线性二阶锥约束的两阶段随机规划问题,即 θ ( x , ξ ) 是如下问题的最优值函数:

P ( x , ξ ) min y m c T y s .t . a i T y + q i T x b i B i y 2 , i = 1 , , l (1.2)

ξ = ( c ; A ; Q ; B ; b ) 是随机变量,其中 c : Ω m A = ( a 1 , , a l ) T : Ω l × m b : Ω l Q = ( q 1 , , q l ) T : Ω l × n ,以及 B = ( B 1 ; ; B l ) , B i : Ω J × m , i = 1 , , l

g i ( x , y ; ξ ) : = ( B i y , a i T y + q i T x b i ) , i = 1 , , l Θ J + 1 = { ( s , t ) J × : t s 2 } J + 1 是一个二阶锥,

则问题(1.2)可以改写为

min y c T y s .t . g i ( x , y ; ξ ) Θ J + 1 , i = 1 , , l

学者们对于此问题的最优值函数和最优解集映射进行了定性和定量的稳定性分析 [3] ,并研究了其扰动问题和对偶问题最优解集的上半连续性以及最优解集的Hadamard方向可微性 [4] 。在此基础上,本文利用该问题的样本均值近似(SAA)估计的渐近分布来研究其统计推断。

SAA方法是研究一般随机规划问题的常用方法。考虑问题

min x X f ( x ) : = Ε [ F ( x , ξ ) ] (1.3)

其中X是 n 空间的一个非空闭子集,函数 F : X × Ξ ξ 是概率分布P在支撑集合 Ξ d 上产生的随机变量。如果目标函数 F ( x , ξ ) 是某个问题的最优值函数,那么问题(1.3)就可以被考虑为一个两阶段随机规划问题。我们假设期望值函数 f ( x ) 是有定义的,并且对于所有的 x X ,是有限的,即对于每一个 x X , ξ Ξ ,最优值 F ( x , ξ ) 取得有限值。SAA方法的思想是选取随机变量 ξ 的N个样本真实值 ξ 1 , , ξ N ,样本真实值由蒙特卡罗方法模拟得到的N个历史观察值。对于 x X ,期望值函数 f ( x ) 可以由 F ( x , ξ i ) , j = 1 , , N 的平均值估计得出。那么问题(1.3)可以被如下问题近似:

min x X { f ^ N ( x ) : = 1 N j = 1 N F ( x , ξ j ) } .

在随机规划的研究过程中,King和Wets [5] 以及Robinson [6] 利用上图收敛分析研究了SAA估计的一致性。King和Rockafellar [7] 以及Shapiro [8] 研究了随机规划问题最优解的近似SAA估计。

本篇文章中,我们给出了问题(1.2)的Lagrange对偶问题,从而将原问题的最优值函数改写成一个极大极小问题,利用最优值函数的Hadamard方向可微性和Delta定理得到了线性二阶锥两阶段随机规划问题最优值函数的SAA估计的近似分布。

2. 最优值函数的统计推断

首先分析线性二阶锥两阶段随机规划问题的扰动问题的性质,给定参数 u = ( c , A , Q , B , b , x ) ,当其收敛到 u ˜ = ( c ˜ , A ˜ , Q ˜ , B ˜ , b ˜ , x ˜ ) 时,我们分析最优值函数 θ ( , ) 的性质。其扰动问题 P ( x ˜ , ξ ˜ ) 可以表示为如下形式:

min y c ˜ T y s .t . g ( y , x ˜ ; ξ ˜ ) Θ (2.1)

其中 g ( y , x ˜ ; ξ ˜ ) = ( g 1 ( y , x ˜ ; ξ ˜ ) , , g ( y , x ˜ ; ξ ˜ ) l ) Θ = Θ J i + 1 × × Θ J l + 1 。设 f ( y , u ˜ ) = c ˜ T y 。令 Φ ( u ˜ ) 表示问题 (2.1)

的可行集合,记为

Φ ( u ˜ ) = { y m : g i ( y , x ˜ ; ξ ˜ ) Θ J i + 1 , i = 1 , , l } .

同时令 Y * ( u ˜ ) 表示问题(2.1)的最优解集。定义

Ψ ( u ˜ , α ) = Φ ( u ˜ ) l e v α f ( , u ˜ )

其中

lev α f ( , u ˜ ) = { y m : f ( y , u ˜ ) α } , α .

我们可以推导出二阶锥优化问题(2.1)的Lagrange对偶问题。问题(2.1)的Lagrange函数可以写为

L ( y , λ ˜ ; u ˜ ) = c ˜ T y i = 1 l λ ˜ i , g i ( y , x ˜ ; ξ ˜ ) = c ˜ T y λ ˜ , Α ˜ y i = 1 l λ ˜ j i + 1 i ( q ˜ i T x b ˜ i ) ,

其中 λ ˜ = ( λ ˜ 1 , , λ ˜ l ) ,线性算子 Α ˜ : m J 1 + 1 × × J l + 1 定义如下

Α ˜ y = ( ( B ˜ 1 y , a ˜ 1 T y ) ; ; ( B ˜ l y , a ˜ l T y ) ) ,

则问题(2.1)的Lagrange对偶可写为

max i = 1 l λ ˜ J i + 1 i ( b ˜ i q ˜ i T x ) s .t . c ˜ Α ˜ * λ ˜ = 0 λ ˜ Θ (2.2)

这里 Α ˜ * Α ˜ 的伴随矩阵且 Α ˜ * λ ˜ 可由如下的形式计算

Α ˜ * λ ˜ = i = 1 l [ B ˜ i T , a ˜ i ] λ ˜ i .

ϕ ( λ ˜ , u ˜ ) = i = 1 l λ ˜ J i + 1 i ( b ˜ i q ˜ i T x ) Λ * ( u ˜ ) 分别表示问题(2.2)最优值函数以及最优解集。问题(2.2)

的可行集合可以由

χ ( c ˜ , A ˜ , B ˜ ) = { λ ˜ = ( λ ˜ 1 ; ; λ ˜ l ) Θ : c ˜ Α ˜ * λ ˜ = 0 }

表示。进一步,可以定义

Γ ( u ˜ , α ) = χ ( c ˜ , A ˜ , B ˜ ) l e v α ϕ ( , u ˜ ) ,

其中

l e v α ϕ ( , u ˜ ) = { λ ˜ J 1 + 1 × × J l + 1 : ϕ ( λ ˜ , u ˜ ) α } , α .

由引理3.3和 [4] 中的引理2.3可知,原问题和对偶问题的可行集是水平有界的,即对于某些, δ > 0 , α , x ˜ X ξ ˜ ( c , A , Q , B , b ) δ 以及有界集合 Β m , Η J 1 + 1 × J l + 1 ,有

Ψ ( u ˜ , α ) Β , Γ ( u ˜ , α ) Η .

则由Lagrange对偶定理,扰动问题的最优值可以写成下面的极大极小问题:

θ ( c ˜ , A ˜ , Q ˜ , B ˜ , x ˜ ) = max λ Θ Η min y Β L ( y , λ ; u ˜ ) .

为了进一步的研究,我们给出关于问题(1.2)和(2.1)的三个假设。

假设1: X n 是一个非空紧致凸集。

假设2:对于每个 x X ,问题(1.2)的最优值函数是有限的,且问题(1.2)的最优解集是紧致的。

假设3:对于每个 x X ,问题(1.2)的Slater条件成立,即对于每个 x n ,存在 y x 使得

g i ( y x , x ; ξ ) int Θ J i + 1 , i = 1 , , l .

上式也等价为 a i T y x + q i T x b i > B i y x , i = 1 , , l

如果假设3成立,则对偶问题(2.2)有一个非空子集且问题(1.2)和其对偶问题(2.2)的对偶间隙为0。文献 [4] 证明了,原问题和对偶问题的可行集是凸集,假设1~3成立时,扰动问题和其对偶问题的Slater条件在 ξ 附近都成立,而且两个问题的最优解集都是上半连续的。文章 [3] 在同样的假设下,得到了关于扰动问题的最优值函数和最优解集映射的定性和定量的稳定性分析结果。

引理1:给定 ( c ; A ; Q ; B ; b ) x X ,若假设1~3成立,则最优值函数 θ ( c ˜ , A ˜ , Q ˜ , B ˜ , b ˜ , x ˜ ) 在点 ( c , A , Q , B , b , x ) 处是方向可微的。进一步, θ ( c ˜ , A ˜ , Q ˜ , B ˜ , b ˜ , x ˜ ) 在点 ( c , A , Q , B , b , x ) 处是Hadamard方向可微的。因此我们可以得到 θ ( u ˜ ) 在u处的Taylor展开式为

θ ( u ˜ ) = θ ( u ) + inf y Y * ( u ) sup λ Λ * ( u ) ( Δ c Δ Α * λ ) T y + i = 1 l λ J i + 1 i ( Δ b i Δ q i T x q i T Δ x ) + o ( Δ u ) ,

其中 u ˜ = ( c ˜ , A ˜ , Q ˜ , B ˜ , b ˜ , x ˜ ) u = ( c , A , Q , B , b , x ) 以及 Δ u = u ˜ u , Δ u δ

现在我们考虑第二阶段问题(1.2)的最优值函数的渐近性质,其最优值函数,记为 θ ( ξ , x ) ,其中随机变量 ξ = ( c ˜ , A ˜ , Q ˜ , B ˜ , b ˜ ) 。令

f ( x , ξ ) = d T x + θ ( x , ξ ) ,

则两阶段随机规划问题可以表示为

min Ε [ f ( x , ξ ) ] s .t . x X

ξ 1 , , ξ N 是独立同分布的样本,则样本均值近似问题为

min f ^ N ( x ) s .t . x X

其中

f ^ N ( x ) = f ( x , 1 N i = 1 N ξ i ) = d T x + θ ( x , 1 N i = 1 N ξ i ) .

我们用 ν * S * 分别表示原问题(2.3)的最优值和最优解集,同时令 ν ^ N , S ^ N 表示SAA问题(2.4)的最优值和最优解集。

假设4:假设 { c ˜ , A ˜ , Q ˜ , B ˜ , b ˜ } 中任意两个元素是相互独立的, ξ = ( c ˜ , A ˜ , Q ˜ , B ˜ , b ˜ ) 的期望值是 p ¯ = ( c , A , Q , B , b ) ,即 Ε ( ξ ) = p ¯ 。设 ξ 1 , , ξ N 为独立同分布样本,对于 ξ i = ( c ˜ i , A ˜ i , Q ˜ i , B ˜ i , b ˜ i ) i = 1 , , N 以及

ξ ^ N = ( c ^ N , A ^ N , Q ^ N , B ^ N , b ^ N ) = 1 N i = 1 N ( c ˜ i , A ˜ i , Q ˜ i , B ˜ i , b ˜ i ) .

假设

N [ c ^ N c ] d Ν ( 0 , Σ c ) , N [ a ^ i N a i ] d Ν ( 0 , Σ i A ) , i = 1 , , l N [ q ^ i N q i ] d Ν ( 0 , Σ i Q ) , i = 1 , , l N [ [ B ^ i . ] N [ B i . ] ] d Ν ( 0 , Σ i B ) , i = 1 , , l N [ b ^ i N b i ] d Ν ( 0 , Σ i b ) , i = 1 , , l

这里 d 表示依分布收敛。则

N [ ( [ B ^ i . ] N , a ^ i N ) ( [ B i . ] , a i ) ] = N [ [ Α ^ i . ] N [ Α i . ] ] d Ν ( 0 , Σ i Α ) , i = 1 , , l ,

这里 Σ i Α 能被 Σ i A Σ i B 表示。

我们通过Delta引理来分析SAA最优值 ν N 的一阶渐近性质。

引理2:( [9] Theorem 7.59)设 B 1 B 2 为Banach空间, Z N B 1 中随机元素序列,G是一个从 B 1 B 2 的映射。1) 若空间 B 1 是可分的,2) 映射G在点 μ B 1 处是Hadamard方向可微的,3) 当 N 时,序列 τ N 趋于无穷,序列 X N : = τ N ( Z N μ ) 依分布收敛于 B 1 中的随机元素Z,则有

τ N [ G ( Z N ) G ( μ ) ] d G ( μ ; Z ) .

现在我们提出研究SAA问题最优值 ν N 渐近性质的主要定理。

定理1:若假设4成立,则有

N 1 / 2 ( θ ^ N θ * ) d inf x S * inf y Y * ( p ¯ ) sup λ Λ * ( p ¯ ) { V ( x , y , λ ) } , (2.5)

这里 V ( x , y , λ ) 是依赖于 ( x , y , λ ) 的随机变量:

V ( x , y , λ ) ~ Ν ( 0 , y T Σ c y i = 1 l λ i 2 y T Σ i Α y + i = 1 l λ J i + 1 i 2 [ Σ i b x T Σ i Q x ] ) .

更进一步的,如果 S * = { x ¯ } , Y * ( p ¯ ) = { y ¯ } , Λ * ( p ¯ ) = { λ ¯ } ,我们可以得到

N 1 / 2 ( ν ^ N v * ) d Ν ( 0 , y ¯ T Σ c y ¯ i = 1 l λ ¯ i 2 y ¯ T Σ i Α y ¯ + i = 1 l λ ¯ J i + 1 i 2 [ Σ i b x ¯ T Σ i Q x ¯ ] ) . (2.6)

证明:首先我们用引理2分析 N 1 / 2 ( f ^ N ( x ) Ε ( f ( x , ξ ) ) ) 的渐近性质。

B 1 = m × l × m × l × n × J l × m × l B 2 = C ( X ) G : B 1 B 2

G ( ξ ) = d T x + θ ( x , ξ )

τ N = N 1 / 2 , Z N = ξ ^ N , μ = p ¯ ,则可以由假设4得到 τ N ( Z N μ ) d Z ,其中

Z c ~ Ν ( 0 , Σ c ) , Z q i ~ Ν ( 0 , Σ i Q ) , i = 1 , , l , Z [ Α i . ] ~ Ν ( 0 , Σ i Α ) , i = 1 , , l , Z b i ~ Ν ( 0 , Σ i b ) , i = 1 , , l . (2.7)

从而引理2中的1),2)可以由假设4得出。由引理1可知G在 μ 处是Hadamard方向可微,从而满足引理2中的3)。因此,我们可以由引理2得到

N 1 / 2 [ f ( x , ξ ^ N ) f ( x , Ε ξ ) ] d G ( μ ; Z ) .

注意到 G ( μ ; Z ) = θ ( μ ; Z ) ,则由引理1可以得到

G ( μ ; Z ) = inf y Y * ( p ¯ ) sup λ Λ * ( p ¯ ) { ( Z c Z [ Α i . ] λ ) T y + i = 1 l λ J i + 1 i ( Z i b Z q i T x ) } .

V ( x , y , λ ) = { Z c T y i = 1 l λ i Z [ Α i . ] T y + i = 1 l λ J i + 1 i ( Z i b Z q i T x ) } 则由式(2.7)可以得到

V ( x , y , λ ) ~ N ( 0 , y T Σ c y i = 1 l λ i 2 y T Σ i A y + i = 1 l λ J i + 1 i 2 [ Σ i b x T Σ i Q x ] ) .

等式(2.5)可以由文章 [10] 中定理5.7直接得到。自然地,当 S * = { x ¯ } , Y * ( p ¯ ) = { y ¯ } , Λ * ( p ¯ ) = { λ ¯ }

时,我们可以由(2.5)得到(2.6),证明完毕。

3. 结论

本文基于线性二阶锥两阶段随机规划问题和其对偶问题最优解集的上半连续性,以及最优值函数的Hadamad方向可微性,研究了最优值函数的统计推断。利用Delta定理,我们推导出所有变量都是随机变量的两阶段随机规划问题的SAA估计的渐近分布。

文章引用

段庆松,张立卫. 线性二阶锥两阶段随机规划问题的统计推断
Statistical Inference of Two-Stage Linear Second-Order Conic Stochastic Programs[J]. 应用数学进展, 2018, 07(07): 876-882. https://doi.org/10.12677/AAM.2018.77105

参考文献

  1. 1. Römisch, W. and Wets, R.J.-B. (2007) Stability of ε-Approximate Solutions to Convex Programs. SIAM Journal on Optimization, 18, 961-979. https://doi.org/10.1137/060657716

  2. 2. Han, Y. and Chen, Z. (2015) Quantitative Stability of Full Random Two-Stage Stochastic Programs with Recourse. Optimization Letters, 9, 1075-1090. https://doi.org/10.1007/s11590-014-0827-6

  3. 3. Duan, Q., Xu, M., Guo, S. and Zhang, L. (2015) Quantitative Stability of Two Stage Linear Second-Order Conic Stochastic Programs with Full Random Recours. Journal of Industrial and Management Optimization, 9, 1075.

  4. 4. Duan, Q., Zhang, L. and Zhang, S. (2018) Hadamard Directional Differentiability of the Optimal Value of a Linear Second-Order Conic Programming Problem. http://www.optimization-online.org/DB_HTML/2018/03/6541.html

  5. 5. King, A.J. and Wets, R.J.-B. (1991) Epi-Consistency of Convex Stochastic Program. Stochastics and Stochastics Reports, 34, 83-92. https://doi.org/10.1080/17442509108833676

  6. 6. Robinson, S.M. (1996) Analysis of Sample-Path Optimization. Mathematics of Operations Research, 21, 513-528. https://doi.org/10.1287/moor.21.3.513

  7. 7. King, A.J. and Rockafella, R.T. (1993) Asymptotic Theory for Solutions in Statistical Estimation and Stochastic Programming. Mathematics of Operations Research, 18, 148-162. https://doi.org/10.1287/moor.18.1.148

  8. 8. Shapiro, A. (1989) Asymptotic Properties of Statistical Estimators in Stochastic Program. Annals of Statistics, 17, 841-858. https://doi.org/10.1214/aos/1176347146

  9. 9. Shapiro, A., Dentcheva, D. and Ruszcyński, A. (2009) Lectures on Stochastic Programming Modeling and Theory. SIAM, Philadelphia. https://doi.org/10.1137/1.9780898718751

  10. 10. Bonnans, J.F. and Shapiro, A. (2000) Perturbation Analysis of Optimization Problems. Springer Series in Operations Research, New York. https://doi.org/10.1007/978-1-4612-1394-9

期刊菜单