不可行初始点的 Newton 方法

前面描述的 Newton 方法是一种可行下降方法。本节描述它的一个推广，可以处理不可行的初始点和迭代点。

不可行点处的 Newton 步

与 Newton 方法一样，从等式约束极小化问题的最优性条件出发：

$$A{x}^{\star }=b,\mathrm{\nabla }f(x^{\star })+A^{\mathrm{\top }}{\nu }^{\star }=0$$

设 $x$ 为当前点——我们不假设它可行，但假设 $x\in \mathrm{dom}f$。目标是找到一步 $\mathrm{\Delta }x$ 使 $x+\mathrm{\Delta }x$（至少近似地）满足最优性条件，即 $x+\mathrm{\Delta }x\approx x^{\star }$。将 $x+\mathrm{\Delta }x$ 代入 $x^{\star }$、$w$ 代入 ${\nu }^{\star }$，并对梯度使用一阶近似 $\mathrm{\nabla }f(x+\mathrm{\Delta }x)\approx \mathrm{\nabla }f(x)+{\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }x$，得到

$$A(x+\mathrm{\Delta }x)=b,\mathrm{\nabla }f(x)+{\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }x+A^{\mathrm{\top }}w=0$$

即线性方程组

$$\left[\begin{array}{cc}{\mathrm{\nabla }}^{2}f(x)& A^{\mathrm{\top }}\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }x\\ w\end{array}\right]=-\left[\begin{array}{c}\mathrm{\nabla }f(x)\\ Ax-b\end{array}\right]$$

这组方程与可行点处定义 Newton 步的方程相同，唯一的差别是右端第二个块包含 $Ax-b$——线性等式约束的残差向量​（residual vector）。当 $x$ 可行时，残差为零，方程退化为可行点处的标准 Newton 步方程。因此我们仍然用记号 $\mathrm{\Delta }{x}_{\mathrm{nt}}$ 表示由上式定义的步，并把它称为 $x$ 处的 Newton 步而不会混淆。

原始—对偶 Newton 步解释

上述方程可以从原始—对偶方法​（primal-dual method）的角度解释。所谓原始—对偶方法，是指同时更新原始变量 $x$ 和对偶变量 $\nu$，使最优性条件（近似地）得到满足的方法。

把最优性条件表示为 $r(x^{\star },{\nu }^{\star })=0$，其中 $r:{\mathbf{R}}^n\times {\mathbf{R}}^p\to {\mathbf{R}}^n\times {\mathbf{R}}^p$ 定义为

$$r(x,\nu )=(r_{\mathrm{dual}}(x,\nu ),r_{\mathrm{pri}}(x,\nu )),r_{\mathrm{dual}}(x,\nu )=\mathrm{\nabla }f(x)+A^{\mathrm{\top }}\nu ,r_{\mathrm{pri}}(x,\nu )=Ax-b$$

$r_{\mathrm{dual}}$ 与 $r_{\mathrm{pri}}$ 分别称为对偶残差​（dual residual）与原始残差​（primal residual）。对当前估计 $y=(x,\nu )$，定义原始—对偶 Newton 步​（primal-dual Newton step）$\mathrm{\Delta }{y}_{\mathrm{pd}}$ 为使 $r$ 的一阶 Taylor 近似为零的步：

$$Dr(y)\mathrm{\Delta }{y}_{\mathrm{pd}}=-r(y)$$

注意这里把 $x$ 和 $\nu$ 都视为变量：$\mathrm{\Delta }{y}_{\mathrm{pd}}=(\mathrm{\Delta }{x}_{\mathrm{pd}},\mathrm{\Delta }{\nu }_{\mathrm{pd}})$ 同时给出原始步与对偶步。计算 $r$ 的导数可得

$$\left[\begin{array}{cc}{\mathrm{\nabla }}^{2}f(x)& A^{\mathrm{\top }}\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }{x}_{\mathrm{pd}}\\ \mathrm{\Delta }{\nu }_{\mathrm{pd}}\end{array}\right]=-\left[\begin{array}{c}\mathrm{\nabla }f(x)+A^{\mathrm{\top }}\nu \\ Ax-b\end{array}\right]$$

把 $\nu +\mathrm{\Delta }{\nu }_{\mathrm{pd}}$ 记为 ${\nu }^{+}$，上式等价于

$$\left[\begin{array}{cc}{\mathrm{\nabla }}^{2}f(x)& A^{\mathrm{\top }}\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }{x}_{\mathrm{pd}}\\ {\nu }^{+}\end{array}\right]=-\left[\begin{array}{c}\mathrm{\nabla }f(x)\\ Ax-b\end{array}\right]$$

这与不可行点处 Newton 步的方程完全一样，因此有

$$\mathrm{\Delta }{x}_{\mathrm{nt}}=\mathrm{\Delta }{x}_{\mathrm{pd}},w={\nu }^{+}=\nu +\mathrm{\Delta }{\nu }_{\mathrm{pd}}$$

即（不可行的）Newton 步等于原始—对偶步的原始部分，而对偶向量 $w$ 是更新后的原始—对偶变量 ${\nu }^{+}$。

两种表达形式各有侧重：一种以原始和对偶残差为右端，同时给出 Newton 步与对偶步；另一种给出 Newton 步与更新后的对偶变量，并表明计算原始步（或更新后的对偶变量）时不需要知道当前对偶变量的值。

残差范数下降性质

在不可行点处，Newton 方向不一定是 $f$ 的下降方向：

$${\frac{d}{dt}f(x+t\mathrm{\Delta }x)|}_{t=0}=\mathrm{\nabla }f(x{)}^{\mathrm{\top }}\mathrm{\Delta }x=-\mathrm{\Delta }{x}^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)\mathrm{\Delta }x+(Ax-b{)}^{\mathrm{\top }}w$$

（除非 $x$ 可行，即 $Ax=b$，此式一般不为负。）然而原始—对偶解释表明，残差的范数沿 Newton 方向下降：

$${\frac{d}{dt}\parallel r(y+t\mathrm{\Delta }{y}_{\mathrm{pd}}){\parallel }_2|}_{t=0}=-\parallel r(y){\parallel }_2$$

因此可以用 $\parallel r{\parallel }_2$（而不是 $f$）来度量不可行初始点 Newton 方法的进展，例如在直线搜索中。

全步长可行性性质

由构造可知，按定义取出的 Newton 步满足 $A(x+\mathrm{\Delta }{x}_{\mathrm{nt}})=b$。因此，若沿 Newton 步取步长 1，则下一个迭代点可行。一旦 $x$ 可行，Newton 步就成为可行方向，之后无论步长如何选取，所有迭代点都将可行。

更一般地，可以分析阻尼步（$t\in [0,1]$）对等式约束残差 $r_{\mathrm{pri}}$ 的影响：步长为 $t$ 的阻尼步使残差按因子 $1-t$ 缩小：

$$r_{\mathrm{pri}}^{+}=A(x+t\mathrm{\Delta }{x}_{\mathrm{nt}})-b=(1-t)(Ax-b)=(1-t)r_{\mathrm{pri}}$$

对一系列阻尼步迭代，残差满足

$$r^{(k)}=(\prod _{i=0}^{k-1}(1-t^{(i)}))r^{(0)}$$

这说明每一步的原始残差都与初始原始残差同向，并在每一步被缩小；同时，一旦取了全步长，之后的所有迭代点都原始可行。

不可行初始点的 Newton 方法

利用上述 Newton 步（以及对偶部分 $\mathrm{\Delta }{\nu }_{\mathrm{nt}}=w-\nu$），可以发展出一种从 $x^{(0)}\in \mathrm{dom}f$（不一定要满足 $A{x}^{(0)}=b$）出发的方法。

算法 10.2（不可行初始点的 Newton 方法） 给定初始点 $x\in \mathrm{dom}f$，$\nu$，容许误差 $ϵ>0$，$\alpha \in (0,1/2)$，$\beta \in (0,1)$。

1. 计算原始与对偶 Newton 步 $\mathrm{\Delta }{x}_{\mathrm{nt}}$，$\mathrm{\Delta }{\nu }_{\mathrm{nt}}$。
2. 关于 $\parallel r{\parallel }_2$ 的回溯直线搜索：令 $t:=1$；当 $\parallel r(x+t\mathrm{\Delta }{x}_{\mathrm{nt}},\nu +t\mathrm{\Delta }{\nu }_{\mathrm{nt}}){\parallel }_2>(1-\alpha t)\parallel r(x,\nu ){\parallel }_2$ 时，令 $t:=\beta t$。
3. 更新：$x:=x+t\mathrm{\Delta }{x}_{\mathrm{nt}}$，$\nu :=\nu +t\mathrm{\Delta }{\nu }_{\mathrm{nt}}$。

重复上述步骤直至 $Ax=b$ 且 $\parallel r(x,\nu ){\parallel }_2⩽ϵ$。

该算法与标准（可行初始点的）Newton 方法非常相似，但有以下差别：搜索方向包含依赖于原始残差的额外修正项；直线搜索以残差范数（而不是函数值 $f$）为基础；终止条件是原始可行且（对偶）残差范数很小。

关于第 2 步的直线搜索需要说明：以残差范数为基础的直线搜索比基于函数值的直线搜索代价稍高，但增加量通常可以忽略；而且由于残差范数沿 Newton 方向的导数为 $-\parallel r{\parallel }_2$，直线搜索必在有限步内终止。

全步长可行性性质表明：一旦某次迭代取了步长 1，下一个迭代点就可行；此后不可行初始点 Newton 方法与（可行的）标准 Newton 方法方向相同。因此该方法有很多变体，例如：一旦达到可行性就切换到标准 Newton 方法（即把直线搜索改为基于 $f$，终止准则改为 $\lambda (x{)}^2/2⩽ϵ$）。

用不可行初始点 Newton 方法简化初始化

不可行初始点 Newton 方法的主要优点在于初始化。若 $\mathrm{dom}f={\mathbf{R}}^n$，初始化可行 Newton 方法只需计算 $Ax=b$ 的一个解，此时使用不可行初始点 Newton 方法除了方便之外并无特别的优势。

当 $\mathrm{dom}f$ 不是全空间时，找到 $\mathrm{dom}f$ 中满足 $Ax=b$ 的点本身可能就是挑战。一般的方法（当 $\mathrm{dom}f$ 复杂或不知道它是否与 $\{z\mid Az=b\}$ 相交时，这可能是最好的方法）是用阶段 I 方法（phase I，见内点法一章）计算这样的点（或验证交集为空）。但当 $\mathrm{dom}f$ 比较简单且已知它与 $\{z\mid Az=b\}$ 相交时，不可行初始点 Newton 方法提供了一个简单的替代方案。一个常见例子是 $\mathrm{dom}f={\mathbf{R}}_{++}^n$ 的情形，如等式约束解析中心问题

$$\mathrm{minimize}-\sum _{i=1}^n\log x_i\mathrm{subject}\mathrm{to}Ax=b$$

初始化（可行的）Newton 方法需要找到满足 $Ax=b$ 的 $x^{(0)}\succ 0$，这等价于求解一个标准形式 LP 可行性问题；而不可行初始点 Newton 方法只需从任意正的初始点（例如 $x^{(0)}=\mathbf{1}$）出发即可。

同样的技巧也可用于未知定义域内点的无约束问题。例如考虑上述问题的对偶

$$\mathrm{maximize}g(\nu )=-b^{\mathrm{\top }}\nu +n+\sum _{i=1}^n\log (A^{\mathrm{\top }}\nu {)}_i$$

初始化需要找到满足 $A^{\mathrm{\top }}{\nu }^{(0)}\succ 0$ 的点（即求解一组线性不等式）。可以用阶段 I 方法，或者把问题改写为等式约束问题

$$\mathrm{maximize}-b^{\mathrm{\top }}\nu +n+\sum _{i=1}^n\log y_i\mathrm{subject}\mathrm{to}y=A^{\mathrm{\top }}\nu$$

然后用不可行初始点 Newton 方法从任意正的 $y^{(0)}$（和任意 ${\nu }^{(0)}$）出发。

用不可行初始点 Newton 方法做初始化的缺点是：当不存在严格可行点时，没有明确的方法检测到这一点——残差范数只会缓慢收敛到某个正值。（阶段 I 方法则可以无歧义地判定这一事实。）此外，达到可行之前，不可行初始点 Newton 方法的收敛可能很慢。

收敛性分析

本节证明：在一定假设下，不可行初始点 Newton 方法收敛于最优点。证明思路与标准 Newton 方法（带或不带等式约束）非常相似：一旦残差范数足够小，算法就取全步长（这意味着可行性已经达到），随后收敛是二次的；同时可以证明在进入二次收敛区域之前，每次迭代使残差范数至少减少一个固定量。由于残差范数非负，这保证了在有限步内残差足够小。

假设

• 下水平集

$$S=\{(x,\nu )\mid x\in \mathrm{dom}f,\parallel r(x,\nu ){\parallel }_2⩽\parallel r(x^{(0)},{\nu }^{(0)}){\parallel }_2\}$$

是闭集（当 $f$ 是闭函数时，$\parallel r(x,\nu ){\parallel }_2$ 也是闭函数，该条件对任意 $x^{(0)}\in \mathrm{dom}f$ 和任意 ${\nu }^{(0)}\in {\mathbf{R}}^p$ 都成立）。

• 在 $S$ 上，$\parallel Dr(x,\nu {)}^{-1}{\parallel }_2={\Vert {\left[\begin{array}{cc}{\mathrm{\nabla }}^{2}f(x)& A^{\mathrm{\top }}\\ A& 0\end{array}\right]}^{-1}\Vert }_2⩽K$。
• 对 $S$ 中的点对，$Dr$ 满足 Lipschitz 条件 $\parallel Dr(x,\nu )-Dr(\tilde{x},\tilde{\nu }){\parallel }_2⩽L\parallel (x,\nu )-(\tilde{x},\tilde{\nu }){\parallel }_2$（这等价于 ${\mathrm{\nabla }}^{2}f(x)$ 满足 Lipschitz 条件）。

这些假设意味着 $\mathrm{dom}f$ 与 $\{z\mid Az=b\}$ 相交，且存在最优点 $(x^{\star },{\nu }^{\star })$。

与标准 Newton 方法的比较​：第二、三条假设（KKT 矩阵有界逆与 Lipschitz 条件）与标准 Newton 方法分析中的假设本质上相同；但这里的下水平集条件更一般。例如等式约束最大熵问题（目标 $\sum _i{x}_i\log x_i$，$\mathrm{dom}f={\mathbf{R}}_{++}^n$）的目标函数不是闭函数（当 $x_i\to 0$ 时 $f$ 不趋于无穷），因此标准 Newton 方法分析的假设可能不成立；但不可行初始点 Newton 方法的下水平集条件对该问题成立（因为负熵函数的梯度范数当 $x_i\to 0$ 时趋于无穷），从而不可行初始点 Newton 方法被保证能求解该问题。当然，若初始点已经满足等式约束，两种方法的唯一区别只在阻尼阶段的直线搜索。

基本不等式

设 $y=(x,\nu )\in S$ 且 $\parallel r(y){\parallel }_2\ne 0$，$\mathrm{\Delta }{y}_{\mathrm{nt}}=(\mathrm{\Delta }{x}_{\mathrm{nt}},\mathrm{\Delta }{\nu }_{\mathrm{nt}})$ 为 $y$ 处的 Newton 步。定义

$$t_{max}=inf\{t>0\mid y+t\mathrm{\Delta }{y}_{\mathrm{nt}}\notin S\}$$

（若 $y+t\mathrm{\Delta }{y}_{\mathrm{nt}}$ 对所有 $t⩾0$ 都属于 $S$，则按惯例取 $t_{max}=\mathrm{\infty }$。）可以证明，对 $0⩽t⩽min\{1,t_{max}\}$ 有基本不等式

$$\parallel r(y+t\mathrm{\Delta }{y}_{\mathrm{nt}}){\parallel }_2⩽(1-t)\parallel r(y){\parallel }_2+(K^{2}L/2)t^2\parallel r(y){\parallel }_2^2$$

证明要点：由 $Dr(y)\mathrm{\Delta }{y}_{\mathrm{nt}}=-r(y)$，有

$$r(y+t\mathrm{\Delta }{y}_{\mathrm{nt}})=(1-t)r(y)+e,e={\int }_0^1(Dr(y+\tau t\mathrm{\Delta }{y}_{\mathrm{nt}})-Dr(y))t\mathrm{\Delta }{y}_{\mathrm{nt}}d\tau$$

利用 Lipschitz 条件与 $\parallel Dr(y{)}^{-1}{\parallel }_2⩽K$ 估计 $\parallel e{\parallel }_2⩽(K^{2}L/2)t^2\parallel r(y){\parallel }_2^2$，再用三角不等式即得。

阻尼 Newton 阶段

若 $\parallel r(y){\parallel }_2>1/(K^{2}L)$，可以证明一次迭代使 $\parallel r{\parallel }_2$ 至少减少一个固定的量。基本不等式右端是 $t$ 的二次函数，在 $\overline{t}=1/(K^{2}L\parallel r(y){\parallel }_2)<1$ 处最小，且必有 $t_{max}>\overline{t}$。在 $t=\overline{t}$ 处有

$$\parallel r(y+\overline{t}\mathrm{\Delta }{y}_{\mathrm{nt}}){\parallel }_2⩽\parallel r(y){\parallel }_2-1/(2K^{2}L)⩽(1-\alpha \overline{t})\parallel r(y){\parallel }_2$$

即步长 $\overline{t}$ 满足直线搜索终止条件，因此回溯直线搜索选出的步长 $t⩾\beta \overline{t}$，进而

$$\parallel r(y+t\mathrm{\Delta }{y}_{\mathrm{nt}}){\parallel }_2⩽\parallel r(y){\parallel }_2-\frac{\alpha \beta }{K^{2}L}$$

也就是说，只要 $\parallel r(y){\parallel }_2>1/(K^{2}L)$，每次迭代至少使 $\parallel r{\parallel }_2$ 减少 $\alpha \beta /(K^{2}L)$。因此最多经过

$$\frac{K^{2}L\parallel r(y^{(0)}){\parallel }_2}{\alpha \beta }$$

次迭代就有 $\parallel r(y^{(k)}){\parallel }_2⩽1/(K^{2}L)$。

二次收敛阶段

当 $\parallel r(y){\parallel }_2⩽1/(K^{2}L)$ 时，基本不等式给出（对 $0⩽t⩽min\{1,t_{max}\}$）

$$\parallel r(y+t\mathrm{\Delta }{y}_{\mathrm{nt}}){\parallel }_2⩽(1-t+(1/2)t^2)\parallel r(y){\parallel }_2$$

由此必有 $t_{max}>1$，故不等式在 $t=1$ 处成立：

$$\parallel r(y+\mathrm{\Delta }{y}_{\mathrm{nt}}){\parallel }_2⩽(1/2)\parallel r(y){\parallel }_2⩽(1-\alpha )\parallel r(y){\parallel }_2$$

即回溯直线搜索的终止条件在 $t=1$ 处满足，因此取全步长；而且之后每次迭代都如此。把基本不等式（取 $t=1$）改写为

$$K^{2}L\parallel r(y^{+}){\parallel }_2^2⩽{(K^{2}L\parallel r(y){\parallel }_2^2)}^2$$

递归应用可得 $\parallel r(y^{+k}){\parallel }_2^2$ 的平方收敛：$K^{2}L\parallel r(y^{+k}){\parallel }_2^2⩽(1/2{)}^{2^k}$。

为证明迭代序列收敛，可证明它是 Cauchy 序列：在二次收敛区域内步长总为 1，利用 $\parallel D{r}^{-1}{\parallel }_2⩽K$ 可以估计相邻迭代点的距离，求和得 $\parallel y^{+k}-y{\parallel }_2⩽2K\parallel r(y){\parallel }_2$。由于 $\parallel r(y^{(k)}){\parallel }_2$ 收敛到零，$y^{(k)}$ 是 Cauchy 序列，故收敛；由 $r$ 的连续性，极限点 $y^{\star }$ 满足 $r(y^{\star })=0$，即最优性条件成立。

凸—凹博弈

不可行初始点 Newton 方法收敛性的证明表明，该方法可以用于比等式约束凸优化问题更大的一类问题。设 $r:{\mathbf{R}}^n\to {\mathbf{R}}^n$ 可微，其导数在

$$S=\{x\in \mathrm{dom}r\mid \parallel r(x){\parallel }_2⩽\parallel r(x^{(0)}){\parallel }_2\}$$

（闭集）上满足 Lipschitz 条件，且 $\parallel Dr(x{)}^{-1}{\parallel }_2$ 在 $S$ 上有界，则从 $x^{(0)}$ 出发的不可行初始点 Newton 方法收敛于 $r(x)=0$ 在 $S$ 中的解。一个有趣的例子是求解凸—凹博弈​（convex-concave game）。

无约束（零和、双人）博弈由支付函数 $f:{\mathbf{R}}^{p+q}\to \mathbf{R}$ 定义：玩家 1 选择 $u\in {\mathbf{R}}^p$，玩家 2 选择 $v\in {\mathbf{R}}^q$，玩家 1 向玩家 2 支付 $f(u,v)$；玩家 1 希望最小化支付，玩家 2 希望最大化它。若玩家 1 先出招且玩家 2 知道其选择，则支付为 $\underset{u}{inf}\underset{v}{sup}f(u,v)$；若玩家 2 先出招，则支付为 $\underset{v}{sup}\underset{u}{inf}f(u,v)$。前者总不小于后者，其差可解释为后出招一方的优势。若存在 $(u^{\star },v^{\star })$ 使得对所有 $u,v$，

$$f(u^{\star },v)⩽f(u^{\star },v^{\star })⩽f(u,v^{\star })$$

则称 $(u^{\star },v^{\star })$ 为博弈的解或鞍点​（saddle-point）；解存在时后出招没有任何优势。若对每个 $v$，$f(u,v)$ 是 $u$ 的凸函数，而对每个 $u$，$f(u,v)$ 是 $v$ 的凹函数，则称博弈是凸—凹的。当 $f$ 可微（且凸—凹）时，鞍点由 $\mathrm{\nabla }f(u^{\star },v^{\star })=0$ 刻画。

可以把不可行初始点 Newton 方法用于计算二阶可微的凸—凹博弈的解：定义残差 $r(u,v)=\mathrm{\nabla }f(u,v)$ 并应用该方法。在博弈的语境下，不可行初始点 Newton 方法就直接称为（凸—凹博弈的）Newton 方法。当 $Dr={\mathrm{\nabla }}^{2}f$ 有界可逆且在上述下水平集上满足 Lipschitz 条件时，可以保证收敛。类似强凸条件的是强凸—凹​（strongly convex-concave）假设：存在 $m>0$ 使 ${\mathrm{\nabla }}_{uu}^{2}f(u,v)⪰mI$ 且 ${\mathrm{\nabla }}_{vv}^{2}f(u,v)⪯-mI$（对所有 $(u,v)\in S$）；它蕴含 $Dr$ 有界逆的条件。

例子

简单例子​：对随机生成的等式约束解析中心问题（$n=100$，$m=50$），从 $x^{(0)}=\mathbf{1}$、${\nu }^{(0)}=0$ 出发，采用 $\alpha =0.01$、$\beta =0.5$：第 8 次迭代取了全步长，原始残差随之（几乎）变为零并保持为零；从第 9 次迭代左右开始，（对偶）残差二次收敛到零。

不可行例子​：对同一规模但 $\mathrm{dom}f$ 与 $\{z\mid Az=b\}$ 不相交（问题不可行）的实例，步长从不为 1，残差也不收敛到零——这展示了当定义域与等式约束不相交时该方法的行为。

凸—凹博弈例子​：对 ${\mathbf{R}}^{100}\times {\mathbf{R}}^{100}$ 上支付函数为

$$f(u,v)=u^{\mathrm{\top }}Av+b^{\mathrm{\top }}u+c^{\mathrm{\top }}v-\log (1-u^{\mathrm{\top }}u)+\log (1-v^{\mathrm{\top }}v)$$

（$\mathrm{dom}f=\{(u,v)\mid u^{\mathrm{\top }}u<1,v^{\mathrm{\top }}v<1\}$，数据随机生成）的凸—凹博弈，从 $u^{(0)}=v^{(0)}=0$ 出发的（不可行初始点）Newton 方法在约 5 次迭代后呈现明显的二次收敛。

待配图​：对应教材图 10.1–图 10.5 —— 原始/对偶残差范数与步长随迭代次数的变化曲线（可行例、不可行例与凸—凹博弈例）。