【非线性优化】凸锥、对偶锥及极锥

如题所述


非线性优化:探索凸锥、对偶锥与极锥的奥秘


在优化领域,锥规划扮演着关键角色,从二阶锥规划到半定规划,无一不与锥体结构紧密相关。当优化问题转化为对偶问题时,对偶锥和极锥的出现,为我们提供了深入理解问题本质的新视角。让我们一起揭开这些神秘锥体的面纱。


1. 凸锥与对称性

首先,我们定义一个锥体:集合 \(C\) 称为锥体,如果对于任何 \(x\) 和 \(t \geq 0\),满足 \(tx \in C\)(锥的定义)。锥体的特性 显示它必然包含原点。


进一步,当一个集合既是锥体又是凸集时,我们称之为凸锥。凸锥的特性可以通过以下两个条件来刻画:性质1:如果 \(C\) 是凸锥,那么对于任何 \(x, y \in C\) 和 \(0 \leq \lambda \leq 1\),都有 \(\lambda x + (1-\lambda)y \in C\)(凸性的直观体现)。


要证明这些性质等价于凸锥,证明 显示了这两个条件的必要性和充分性:如果 \(C\) 是凸锥,那么满足第2条,而第1条的必要性是通过凸性推出 \(tx \in C\) 推导的;反之,第2条确保 \(C\) 是锥,而第1条保证其凸性。


2. 闭凸锥与实例

闭凸锥是凸集、闭集和锥体的结合体。例如,凸多面体是凸锥的典型例子,非负卦限也是闭凸锥的一个特例。洛伦茨锥,因其形状酷似冰淇淋,被命名为冰激凌锥,它由半正定矩阵构成,通过简单矩阵特征值的分析,可以证明其为凸锥。


半正定矩阵锥,如三维中的集合 \(\{X \in \mathbb{R}^{n \times n}: X \succeq 0\}\),其凸性通过矩阵的特征值和迹的关系得到证明,它将半正定矩阵集合定义为一个凸锥。


3. 凸组合与锥包

类似于凸组合,锥体中存在锥组合的概念,对于 \(n\) 个向量 \(v_i\),它们的锥组合 \(C(v_1, v_2, ..., v_n)\) 是非负系数 \(t_i\) 乘以 \(v_i\) 的集合。定理1揭示了凸锥的这一特性:任意 \(k\) 个点的锥组合仍然在凸锥内。


锥包定义为集合中所有锥组合的最小闭凸集合,定理2强调了它包含原始集合的特性。锥包中的元素可以通过锥表示理论,用有限个线性无关向量表示。


4. 凸锥的拓扑性质与对偶极锥

定理4指出,对于有限集合的锥包,其闭性是关键性质。通过锥表示定理,我们能证明有限个向量的组合闭合,进一步确保了锥包的闭合性。


在半定规划中,对偶锥和极锥是核心概念。对偶锥 \(C^*\) 由满足 \(y^T x \geq 1\) 的所有 \(y\) 构成,而极锥 \(P^+\) 包含所有与 \(C\) 中向量保持90度以上夹角的向量。极锥的特殊性质,如线性子空间的对应关系,展示了它在优化中的重要作用。


温馨提示:答案为网友推荐,仅供参考