Page 11 - 《软件学报》2025年第5期

杨紫萱 等: 基于 PAC 学习的组合式概率障碍证书生成 1911

(2)
(1)
δ δ ,δ ,...,δ (K) K 个样本
在 ∆ 上随机采样不确定性参数 的 K 个独立同分布的样本 , 并将原问题转化为求解与这
相关的约束优化问题, 从而降低计算复杂度. 假设原凸优化问题为:

 T
min c γ

c (2)



 s.t. h δ (γ) ⩽ 0,∀δ ∈ ∆
将求解无限个约束的凸优化问题转化为求解有限个约束的凸优化问题:

 T
min c γ


c (3)


 s.t. h δ (i)(γ) ⩽ 0, i = 1,2,...,K
公式 (3) 放松了公式 (2), 因为它只考虑了与采样的样本 δ (i) 相对应的 K 个有限约束, 若公式 (3) 无解, 则公式 (2)
的解集为空集. 由于公式 (3) 的约束有限, 并且是一个凸优化问题, 因此只要 K 不是一个非常大的数, 可以通过数
值优化器进行求解.
K 的取值
在场景优化方法中, 最关键的是如何选择适当的样本数 K , 以保证得到足够准确的优化结果. 通常,
要足够大, 以确保样本的覆盖性和可靠性. 然而 K 又不能过大, 应尽量减少计算成本. 因此, 对于不同的问题和应用
场景, 需要综合考虑样本数 K 的选择, 以平衡准确性和计算效率之间的权衡. 对于样本数 K , 存在以下定理.
定理 1. 若公式 (3) 可行并且存在唯一的最优解 γ , 给定安全需求阈值参数 ε ∈ (0,1) 和置信度水平参数
∗
β ∈ (0,1) , 如果满足

( )
2 1
ε ⩾ ln +m (4)
K β
∗
其中, K 为从 ∆ 中随机采样的样本数, m 为约束中优化变量的个数, 那么至少在 1−β 的置信度下最优解 γ 满足 ∆
∗
中所有约束的概率大于等于 1−ε , 即 P({δ ∈ ∆|h δ (γ ) ⩽ 0}) ⩾ 1−ε .

2.3 基于微分中值定理的区间线性化方法
I I I b = {b | b ⩽ b ⩽ b} 是一个
I
对于线性区间不等式组 A x ⩽ b , 其中 A = {A | A ⩽ A ⩽ A} 是一个 m×n 维区间矩阵,
I I I I X S 表示所有强
m 维区间向量. 向量 x 0 是 A x ⩽ b 的一个强解, 若满足 Ax 0 ⩽ b 对于每个 A ∈ A 和 b ∈ b 都成立. 用
解的集合, 有以下命题成立.
命题 1. 若线性区间不等式组 A x ⩽ b 有解, 则所有强解的集合 X S = {x 1 − x 2 | Ax 1 − Ax 2 ⩽ b, x 1 ⩾ 0, x 2 ⩾ 0} . 若线
I
I
I I
性区间不等式组 A x ⩾ b 有解, 则所有强解的集合 X S = {x 1 − x 2 | Ax 1 − Ax 2 ⩾ b, x 1 ⩾ 0, x 2 ⩾ 0} .
若想得到具有区间数值的线性不等式系统的强解, 则可以通过命题 1 将区间不等式转化为线性规划问题计
算. 定义 3 定义了区间运算的基本规则.
定 义 3 . 已 知 区 间 X = [a,a] 和 区 间 Y = [b,b] , 则 区 间 X ·Y = [min{ab,ab,ab,ab},max{ab,ab,ab,ab}] , 区 间

c X ±c = [a±c,a±c] cX = [ca,ca] .
X −Y = [a−b,a−b] . 给定一个常数 , ,
每个区间表示为一对下界和上界, 当线性化一个区间不等式时, 更小的区间长度通常近似效果更好, 因为这意
味着下界和上界的差异更小, 可以减少线性化过程中的误差和近似带来的不确定性. 对于已知的连续函数 g(x) ,
x ∈ [x, x] , 由微分中值定理可知:

∂g
g(x)−g(x) = (ζ)(x− x), ζ ∈ [x, x].
∂x
定理 2 引入基于中值定理的连续函数区间化方法.
x+ x
定理 n ˘ x = , 则
2
2. 给定一个连续函数 g(x) : R → R, x ∈ [x, x] , 中点
∂g
g(x) ∈ g(˘x)+ ([x, x])[x− ˘x, x− ˘x],
∂x
∂g
其中, ([x, x]) 表示对 g(x) 的偏导直接进行区间乘法运算得到的结果.
∂x
基于微分中值定理的区间线性化方法首先通过定理 2 将连续函数转化为区间形式, 再通过命题 1 进行线性