第1章 预备知识
本章介绍锥优化中的一些基本概念和结论， 主要包括偏序、凸锥及基本的锥优化问题及其对偶.
1.1 偏序与凸锥
在线性规划中约束不等式 ax≥b 的定义非常明确， 即给定向量， 若 a 分量≥ b 分量:
在接下来的一种关系中， 我们再次遇到了不等式符号， 但现在它代表了实数间的一个“算术”关系. Rm 中的逐点偏序关系满足实数标准序关系的下列基本性质， 即对于向量 a， b， c， d 2 Rm 有
(1) 自反性: a≥a;
(2) 反对称性: 若 a≥b 且 b≥a， 则 a = b;
(3) 传递性: 若 a ≥b 且 b≥c， 则 a = c;
(4) 线性运算的相容性:
同质性， 若 a≥b 且 λ 是非负实数， 则 λa ≥λb;
可加性， 若 a ≥b 且 c≥d， 则 a + c≥b + d.
阐明满足上述性质 (1)—(4) 的向量不等式后， 接着考虑 Rm 中的向量， 假设 Rm 具有一个偏序记为， 由它连接的向量对 a， b 满足上述性质 (1)—(4) 时称为一个良序.
一个良序由非负向量的集合 K 完全决定， 其中， 即. 事实上， 令. 由性质 (1) 和 (4) 可得. 反之， 若， 通过加不等式， 则有. 集合 K不是任意的， 容易证明其必须为尖凸锥， 即满足以下条件:
(1) K 关于加运算是非空且闭的，
(2) K 是个锥，
(3) K 是尖的，
几何上， K 不包含任意通过原点的直线. 因此， Rm 上的每一个非空尖凸锥 K可以诱导出一个 Rm 上满足性质 (1)—(4) 的偏序. 定义这个序为≥K:
称由非负向量组成的锥Rm+为非负象限，
非负象限 Rm+不是尖凸锥， 但具有下面两个有用的性质:
(1) 这个锥是闭的， 若来自这个锥的向量序列 ai 有限， 则其必属于这个锥.
(2) 这个锥具有非空的内点， 存在一个向量， 使得锥中包含一个以该向量为中心的正半径球.
这两条性质非常重要， 例如， 性质 (1) 确保了在不等式中传递逐项极限的可能性， 即
限制来自锥 K 的偏序具有性质 (1) 和 (2) 是有意义的. 至此， 再谈到好的偏序关系≥K， 总是假设集合 K 是一个具有非空内点的尖的闭凸锥. 注意到， K 的闭性， 使得传递极限在≥K-不等式中成为可能， 即
K 的内点的非空性允许我们按照下面的规则定义严格不等式和非严格不等式，
其中 intK 是锥 K 的内点. 例如， 简单地说， 严格坐标不等式就是在通常的算术意义下， a 的坐标严格大于 b 的相应坐标. 我们感兴趣的一些偏序关系由下面的锥给出:
(1) 非负象限锥 Rm+.
(2) 二阶锥 (或劳伦斯锥).
(3) 半正定锥 Sm+ . 这个锥存在于 m×m 对称阵的空间 Sm 中， 由所有 m×m 的半正定矩阵 A 构成， 即
1.2 锥优化问题
假设 K 是 Rm 上的具有非空内点的凸尖闭锥. 给定约束矩阵A 和右端向量， 考虑优化问题
我们称其为与锥 K 相关的锥优化 (conic programming) 问题. 注意到锥优化与线性规划的区别在于后者处理的是 K = Rm+的情况. 在锥优化的框架下， 我们可以处理许多线性规划无法覆盖的更广泛的应用.
对偶理论是线性规划中的重要理论结果之一， 相同的范式可用于处理锥优化的对偶问题. 这里需要澄清的一个问题是: 满足纯量不等式的向量λ 在什么情况下可以使向量不等式 Ax≥K b 成立？在一些特定的偏序关系下， 例如 K = Rm+时， 容许向量λ是分量非负的向量. 然而， 对于偏序≥K， 当 K 不是Rm+时， 这些向量不一定是可接受的.
例 1.1 考虑 R3 上的偏序≥L3 由三维的劳伦斯锥确定:
不等式
是有效的; 但是用一个正权向量 λ = (1， 1， 0.1)T 聚合这个不等式， 会得到错误的不等式-1.8≥0. 因此对于偏序≥L3 不是所有的非负权向量都是可接受的.
对这个问题的回答是定义一个权向量λ使其满足
(1.1)
当λ具有这个性质时， 纯量不等式 λTa≥λTb 就是向量不等式a≥K b 的一个结果:
展开
