前言

本文章是根据法国国立高等电力技术、电子学、计算机、水力学与电信学校 (E.N.S.E.E.I.H.T.) 第七学期课程*“Optimisation”* 总结而来的【部分课程笔记】。碍于本人学识有限，部分叙述难免存在纰漏，请读者注意甄别。

最优化问题解题步骤

1. 建模最优化问题

我们首先需要根据题目的描述对于问题 (P)(\mathcal{P}) 进行数学建模。包括问题中提供的任何信息。确定

(1) 我们想要最大化或最小化目标函数，并将其统一转换成最小化问题；

(2) 为目标方程中的变量依照题意添加约束，统一标准化为小于等于约束；

(3) 如果可以，结合图形更加直观。

2. 确定目标函数的定义域 Ω\Omega

目标函数的定义域 Ω\Omega 的封闭性、有无界性、是否非空 和 凹凸性：必须是一个封闭(closed) 的、有界的(bounded) 非空 (non-empty) 凸区间 (convex interval) （即两端都有端点并包含这些端点的区间，且区间中任意两点的连线上的所有点都属于这个区间）

3. 判断目标函数在定义域 Ω\Omega 上的极值情况

  • 存在性 (existence)：一阶偏导 (梯度) ∇\nabla 检验，评估目标函数在定义域 Ω\Omega 中的一阶偏导，简单判断目标函数的极值情况。例如：

    f(x1,x2,x3)  ⇒  f(z,z,z)  →z→∞  f→∞ 无全局最大值f(x_1,x_2,x_3)\;\Rightarrow \; f(z,z,z) \; \xrightarrow{z\to \infin}\; f\to \infin \text{ 无全局最大值}，

    f(x1,x2,x3)  ⇒  f(z,z,z)  →z→−∞  f→−∞ 无全局最小值f(x_1,x_2,x_3)\;\Rightarrow \; f(z,z,z) \; \xrightarrow{z\to -\infin}\; f\to -\infin \text{ 无全局最小值}

  • 唯一性 (unicité)：二阶偏导 (梯度) ∇2\nabla^2 检验，要求：定义域 Ω\Omega 中必须只有一个极值。测试：求目标函数的二阶偏导 ，并在临界数处对其进行评估。如果该值为 <0<0，则临界数表示严格极大值 (strict maximum)。如果该值为>0>0，则临界数表示严格极小值 (strict minimum)。

4. 构造拉格朗日乘数法或KKT\mathcal{KKT}

下略。

范数

是数学中的一种基本概念。 在泛函分析中，它定义在赋范线性空间中，并满足一定的条件，即 ①非负性；②齐次性；③三角不等式。 它常常被用来度量某个向量空间（或矩阵）中的每个向量的长度或大小。

  • l1范数l_1范数 ：

    ∥x∥1=∑i=1n∣xi∣\lVert x\rVert_1 = \sum_{i=1}^n |x_i|

  • l2范数l_2范数 ：

    ∥x∥2=xTx=∑i=1nxi2\lVert x\rVert_2 = \sqrt{x^Tx} = \sqrt{\sum_{i=1}^n x_i^2}

  • l∞范数l_\infin范数 ：

    ∥x∥∞=max{∣xi∣:i∈1,2,...,n}\lVert x\rVert_{\infin} = max\{ |x_i|:i\in 1,2,...,n\}

  • lp范数l_p范数 ：

    ∥x∥p=(∑i=1n∣xi∣p)1p,p∈[1,∞)\lVert x\rVert_p =(\sum_{i=1}^n |x_i|^p)^{\frac {1}{p}},p \in [1,\infin)

凸集

凸集 (Convex set)

给定非空集合 F⊆RnF \subseteq \R^n，如果 ∀x,y∈F,α∈[0,1]\forall x,y \in F, \alpha \in [0,1] 都有 αx+(1−α)y∈F\alpha x+(1-\alpha) y \in F，那么我们就称这个 FF 为 Rn\R^n 中的一个凸集，即集合中的任意两点的连线仍然属于该集合。

凸组合 (Convex combination)

x1,x2,...,xkx^1, x^2,...,x^k 的凸组合：

λ1x1+λ2x2+...+λkxk\lambda_1x^1 + \lambda_2x^2 + ... +\lambda_kx^k

其中，λ1,λ2,...,λk≥0,∑i=1kλi=1\lambda_1, \lambda_2,...,\lambda_k \ge 0, \sum_{i=1}^k \lambda_i = 1

黑塞矩阵 (Hessain)

在之前的学习中我们已经知道，一阶导数，也就是目标函数的梯度，反映了函数值随着自变量 xx 变化的速率情况。所谓二阶导数，就是在一阶导数的基础上再求导数，反映了一阶导数的变化情况。

例如对于二次型函数 f(x)=x2f(x) = x^2，它的一阶导数就是 df(x)dx=2x\frac {df(x)}{dx} = 2x，二阶导数为 d2f(x)dx2=2\frac{d^2f(x)}{dx^2} = 2

将其推广，对于一般的多元函数 f(x):Rn→Rf(x) : \R^n \to \R， 对其求一阶偏导数 (partial)，一阶偏导为向量称作梯度 (gradient):

∇f(x)=[∂f∂x1∂f∂x2⋮∂f∂xn]\nabla f(x) = \begin{bmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \vdots\\ \frac{\partial f}{\partial x_n} \end{bmatrix}

我们再对一阶导数 \frac{\part f(x)}{\part x} 对于 xix_i 求偏导，我们可以得到

∇(∂f∂xi)=∇2f(x)=[∂∂x1∂f∂x1∂∂x2∂f∂x1⋯∂∂xn∂f∂x1∂∂x1∂f∂x2∂∂x2∂f∂x2⋯∂∂xn∂f∂x2⋮⋮⋱⋮∂∂x1∂f∂xn∂∂x2∂f∂xn⋯∂∂xn∂f∂xn]←Hessian  Matrix\nabla (\frac{\partial f}{\partial x_i}) = \nabla^2 f(x) = \begin{bmatrix} \frac{\partial}{\partial x_1}\frac{\partial f}{\partial x_1} & \frac{\partial}{\partial x_2}\frac{\partial f}{\partial x_1} & \cdots & \frac{\partial}{\partial x_n}\frac{\partial f}{\partial x_1} \\ \frac{\partial}{\partial x_1}\frac{\partial f}{\partial x_2} & \frac{\partial}{\partial x_2}\frac{\partial f}{\partial x_2} & \cdots & \frac{\partial}{\partial x_n}\frac{\partial f}{\partial x_2} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial}{\partial x_1}\frac{\partial f}{\partial x_n} & \frac{\partial}{\partial x_2}\frac{\partial f}{\partial x_n} & \cdots & \frac{\partial}{\partial x_n}\frac{\partial f}{\partial x_n} \\ \end{bmatrix} \leftarrow Hessian \; Matrix

黑塞矩阵是对梯度再求一次偏导，所以它是 n×nn \times n 的方阵，满足对称性 Hij=Hji\mathcal{H}_{ij} = \mathcal{H}_{ji}

例：对于 f(x,y)=5x+8y+xy−x2−2y2f(x,y) = 5x + 8y +xy -x^2 -2y^2

∇f(x,y)=[∂f∂x∂f∂y]=[5−2x+y8+x−4y]H(x)=[211−4]\nabla f(x,y) = \begin{bmatrix} \frac{\partial f}{\partial x} \\ \frac{\partial f}{\partial y} \end{bmatrix} = \begin{bmatrix} 5-2x+y \\ 8+x-4y \end{bmatrix}\\ \mathcal{H} (x) = \begin{bmatrix} 2 & 1 \\ 1 & -4\\ \end{bmatrix}

对于二次函数，黑塞矩阵为常数矩阵。

黑塞矩阵的意义

如果一个函数的黑塞矩阵是正定 (positive definite) 的，即特征值大于 0，也即目标函数在所有可行方向 dd 上的二阶导数都大于 00。我们就可以得出 f(x)f(x) 是一个严格的凸函数，其极值就是极小值，而且也是**全局的最小值**。

矩阵的正定

正定矩阵首先是一个对称阵。以下我们介绍一种判断矩阵是否正定的方法，Sylvester’s Criterion：

Sylvester’s Criterion

各阶行列式（顺序主子式）都大于0 ⇒\Rightarrow 矩阵正定 ≻0\succ 0

[2−10−12−10−12]⇒∣2∣>0∣2−1−12∣>0∣2−10−12−10−12∣>0\begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix} \quad \Rightarrow \quad \begin{vmatrix} 2 \end{vmatrix} > 0\quad \begin{vmatrix} 2 & -1 \\ -1 & 2 \end{vmatrix} > 0\quad \begin{vmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{vmatrix} > 0

无约束优化问题的最优性条件

无约束优化问题： min⁡f(x)\min f(x)

最优解的定义：

  • 局部最优解：对于一个解 xˉ\bar x，在 xˉ\bar x 的临域空间 Ns(xˉ)N_s(\bar x) 内 f(xˉ)f(\bar x) 的值是最大或最小的。

    ∀x∈Ns(xˉ),f(x)≥f(xˉ)  或  f(x)≤f(xˉ)\forall x \in N_s(\bar x), f(x) \ge f(\bar x) \;或\; f(x) \le f(\bar x)

  • 全局最优解：对于一个解 xˉ\bar x，在任意n维空间 Rn\R^n 内 f(xˉ)f(\bar x) 的值是最大或最小的。

    ∀x∈Rn,f(x)≥f(xˉ)  或  f(x)≤f(xˉ)\forall x \in \R^n, f(x) \ge f(\bar x) \;或\; f(x) \le f(\bar x)

  • 严格局部最优解：对于一个解 xˉ\bar x，在 xˉ\bar x 的临域空间 Ns(xˉ)N_s(\bar x) 内 f(xˉ)f(\bar x) 的值是严格最大或最小的（不包含等于情况）。

    ∀x∈Ns(xˉ),f(x)>f(xˉ)  或  f(x)<f(xˉ)\forall x \in N_s(\bar x), f(x) > f(\bar x) \;或\; f(x) < f(\bar x)

  • 严格全局最优解：对于一个解 xˉ\bar x，在任意n维空间 Rn\R^n 内 f(xˉ)f(\bar x) 的值是严格最大或最小的（不包含等于情况）。

    ∀x∈Rn,f(x)>f(xˉ)  或  f(x)<f(xˉ)\forall x \in \R^n, f(x) > f(\bar x) \;或\; f(x) < f(\bar x)

最优性条件

考虑无约束优化问题： min⁡f(x)\min f(x)

  • 必要条件：若 x∗x^* 是最优解，则 x∗x^* 有如下性质：

    (1)∇f(x∗)=0目标函数在 x∗的位置时梯度为零(2)∇2f(x∗)⪰0目标函数在 x∗的位置时黑塞矩阵是半正定的(1)\quad \nabla f(x^*) = 0 \qquad \qquad \qquad \text{目标函数在 } x^* \text{的位置时梯度为零} \\ (2)\quad \nabla^2 f(x^*) \succeq 0 \qquad \text{目标函数在 } x^* \text{的位置时黑塞矩阵是半正定的}

  • 充分条件：

    若∇f(x∗)=0,∇2f(x∗)≻0⇒则x∗是严格最优的若 \nabla f(x^*) = 0, \nabla^2 f(x^*) \succ 0 \quad \Rightarrow \quad 则 x^* 是严格最优的

无约束优化：线搜索 和 信赖域

考虑无约束优化问题： min⁡f(x)\min f(x)

迭代下降算法的描述：

给定一个初始点 x0x_0 ，我们可以判断 x0x_0 是否是我们需要找的点，如果不是，我们要产生点列 {xk}k=1∞\{x_k\}^\infin_{k=1} ，并且满足 f(xk+1)<f(x)f(x_{k+1}) < f(x) “下一个点的函数值比当前点的函数值小”。我们有两种策略：线搜索 (Line search) 和 信赖域 (Trust region)

线搜索方法
算法描述
  1. 给定初始点 x0x_0
  2. 判断 x0x_0 是否满足【终止条件】；是，则终止
  3. 当前点为 xkx_k，首先找到【下降方向 dkd_k】（从这个点出发，有一段步长的距离，目标函数值会减小的方向）
  4. 确定【步长 αk>0\alpha _k > 0 】，使得 f(xk+αkdk)<f(x)f(x_k + \alpha_k d_k) < f(x)
  5. 我们就得到了下一个点 xk+1:=xk+αkdkx_{k+1} :=x_k + \alpha_k d_k；转第 2 步
  • 终止条件：∥∇f(xk)∥2≤E\lVert \nabla f(x_k) \rVert_2 \le \mathcal{E}，其中 E\mathcal{E} 是一个很小的正整数，意味着当梯度趋近于 0
  • 下降方向 dkd_k 的选择：最速下降、共轭梯度等
  • 步长 αk\alpha _k 的选择：我们令 ϕ(α):=f(xk+αdk)\phi(\alpha) := f(x_k + \alpha d_k)，步长 αk=min⁡ϕ(α),α≥0\alpha_k = \min \phi (\alpha),\alpha \ge 0
  • 算法结束后会给我们一个点列 {xk}\{x_k\}，我们需要关心点列的收敛性和收敛速度
信赖域方法
  1. 当前点为 xkx_k，首先决定“活动范围 Δ\Delta” ∥d∥2≤Δ\lVert d\rVert_2 \le \Delta
  2. 再决定“活动方向”

无约束优化：最速下降

收敛速度

设当前点列 {xk}\{x_k\} 收敛到 x∗x^*，若存在极限

lim⁡k→∞∥xk+1−x∗∥2∥xk−x∗∥2=β\lim_{k\to \infin} \frac{\lVert x_{k+1} - x^* \rVert_2}{\lVert x_{k} - x^* \rVert_2} = \beta

  • 当 0<β<10 < \beta < 1 时，则称点列 {xk}\{x_k\} 为线性收敛
  • 当 β=0\beta = 0 时，则称点列 {xk}\{x_k\} 为超线性收敛

若存在某个 p≥1p \ge 1，有

lim⁡k→∞∥xk+1−x∗∥2∥xk−x∗∥2p=β<+∞\lim_{k\to \infin} \frac{\lVert x_{k+1} - x^* \rVert_2}{\lVert x_{k} - x^* \rVert_2^p} = \beta <+\infin

则称点列 {xk}\{x_k\} 为p阶收敛

  • 当 p>1p > 1 时，p阶收敛必为超线性收敛
最速下降法

也叫做梯度下降法。【基本思想】是选择 xkx_k 处的负梯度方向作为搜素方向，即 $d_k = -\nabla f(x_k) $

  • 优点：简单直观；收敛；搜素方向只需计算 $-\nabla f(x_k) $
  • 缺点：收敛速度慢（线性搜索）；Zigzag现象（路径是“之”字形）；不具备“在有限步内求得凸二次函数最优解”的特性

约束优化：KKT\mathcal{KKT} 条件

一阶必要条件 : 最优解→KKT点最优解 \to \mathcal{KKT} 点

假设 x∗x^* 是问题 P\mathcal{P} 的局部最优解，且 x∗x^* 某处的约束规范 (constraint qualification) 成立，则存在 λ\lambda，μ\mu 使得

min⁡x∈R2f(x)s.t.∀i∈{1,2,...,l}:hi(x)=0且∀j∈{1,2,...,m}:gj(x)≤0可行集S(E)={x∣满足  s.t.}\min_{x\in \R^2} f(x) \\ s.t. \quad \forall i \in \{1,2,...,l\}:h_i(x)=0\quad 且 \quad \forall j \in \{1,2,...,m\}:g_j(x) \le 0 \\ 可行集 S(\mathcal{E}) = \{x| 满足 \; s.t.\} \\

  1. ∇f(x∗)+∑i=1mλi∇gi(x∗)+∑i=1lμi∇hi(x∗)=0\nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla g_i(x^*) + \sum_{i=1}^l \mu_i \nabla h_i(x^*)= 0

  2. ∀i∈{1,2,...,m}:λi≥0\forall i \in \{1,2,...,m\}:\lambda_i \ge 0

  3. ∀i∈{1,2,...,m}:gi(x∗)≤0\forall i \in \{1,2,...,m\}:g_i(x^*) \le 0

  4. ∀i∈{1,2,...,m}:hi(x∗)=0\forall i \in \{1,2,...,m\}:h_i(x^*) = 0

  5. ∀i∈{1,2,...,m}:λigi(x∗)=0\forall i \in \{1,2,...,m\}:\lambda_i g_i(x^*) = 0

二阶充分条件 : KKT点→最优解\mathcal{KKT}点 \to 最优解

假设 x∗x^* 满足上述的 KKT\mathcal{KKT} 条件，我们定义一个函数 L(x)=f(x)+∑μihi(x)+∑λigi(x))\mathcal{L}(x) = f(x) + \sum \mu_i h_i(x) + \sum \lambda_i g_i(x))，可知：

  1. ∇xL(x∗)=0KKT条件中的第 1 条\nabla_{x} \mathcal{L}(x^*) = 0 \qquad \mathcal{KKT}\text{条件中的第 1 条}
  2. L(x∗)=f(x∗)+∑μihi(x∗)+∑λigi(x∗))=f(x∗)+0+0⇒L(x∗)=f(x∗)\mathcal{L}(x^*) = f(x^*) + \sum \mu_i h_i(x^*) + \sum \lambda_i g_i(x^*)) = f(x^*) + 0 + 0 \quad \Rightarrow \quad \mathcal{L}(x^*) = f(x^*)
  3. ∀x∈S(E),  L(x)≤f(x)\forall x \in S(\mathcal{E}),\;\mathcal{L}(x) \le f(x)

有以下结论：

  • 由 2, 3 可知，若 x∗x^* 是 L(x)\mathcal{L} (x) 的最优解，则x∗x^* 也是 P\mathcal{P} 的最优解：f(x∗)=L(x∗)≤L(x)≤f(x)f(x^*) = \mathcal{L}(x^*) \le \mathcal{L}(x) \le f(x)
  • 若 ∇xxL(x∗)⪰0,  ∀x∈S(E)\nabla_{xx} \mathcal{L}(x^*) \succeq 0, \; \forall x \in S(\mathcal{E})，则 x∗x^* 是 P\mathcal{P} 的全局最优解
  • 若 ∇xxL(x∗)⪰0,  ∀x∈{S(E)∩临域NS(x∗)}\nabla_{xx} \mathcal{L}(x^*) \succeq 0, \; \forall x \in \{S(\mathcal{E})\cap _{临域}N_S(x*)\}，则 x∗x^* 是 P\mathcal{P} 的局部最优解
  • 若 ∇xxL(x∗)≻0\nabla_{xx} \mathcal{L}(x^*) \succ 0，则 x∗x^* 是 P\mathcal{P} 的严格局部最优解

约束优化：对偶理论

考虑如下一般形式的约束优化问题：

(P):  min⁡x∈R2f(x)s.t.{hi(x)=0,  ∀i∈{1,2,...,l}gj(x)≤0,  ∀j∈{1,2,...,m}x∈X可行集S(E)={x∈X∣满足  s.t.}(\mathcal{P}):\; \min_{x\in \R^2} f(x) \\ s.t. \quad \left\{\begin{aligned} & h_i(x)=0, \;\forall i \in \{1,2,...,l\} \\ & g_j(x) \le 0 , \; \forall j \in \{1,2,...,m\} \\ & x \in X \end{aligned}\right. \\ \\ 可行集 S(\mathcal{E}) = \{ x \in X | 满足 \; s.t.\} \\

其中 XX 是“集合约束”，如果：

  1. X=RnX = \R^n 所研究的问题 P\mathcal{P} 就是在 n 维实数域上的连续优化问题，就可以运用以上知识
  2. X=Z+nX = \Z^n_+ 所研究的问题 P\mathcal{P} 就是在 n 维整数（或非负整数）域上的连续优化问题，就可以运用以上知识
  3. X={0,1}nX = \{0,1\}^n 所研究的问题 P\mathcal{P} 就是在 n 维 0-1 集合上的离散整数优化问题
对偶问题的意义

原问题  (P)→构建对偶问题  (D)原问题 \; (\mathcal{P}) \quad \xrightarrow{构建} \quad 对偶问题 \; (\mathcal{D})

  1. 如果原问题 (P)(\mathcal{P}) 是非凸问题，我们很难求解这一类 NP-hard 问题，我们就可以构造一个和原问题 (P)(\mathcal{P}) 的关系紧密又简单的对偶问题 (D)(\mathcal{D}) 来求解；
  2. 在线性规划问题中的对偶问题；
  3. 鲁棒优化，锥优化
拉格朗日对偶问题

(P):  min⁡x∈R2f(x)s.t.{hi(x)=0,  ∀i∈{1,2,...,l}gj(x)≤0,  ∀j∈{1,2,...,m}x∈X可行集S(E)={x∈X∣满足  s.t.}(\mathcal{P}):\; \min_{x\in \R^2} f(x) \\ s.t. \quad \left\{\begin{aligned} & h_i(x)=0, \;\forall i \in \{1,2,...,l\} \\ & g_j(x) \le 0 , \; \forall j \in \{1,2,...,m\} \\ & x \in X \end{aligned}\right. \\ \\ 可行集 S(\mathcal{E}) = \{ x \in X | 满足 \; s.t.\} \\

我们引入拉格朗日函数：

L(x,λ,μ)=f(x)+∑i=1lμihi(x)+∑i=1mλigi(x))\mathcal{L}(x, \lambda, \mu) = f(x) + \sum_{i=1}^l \mu_i h_i(x) + \sum_{i=1}^m \lambda_i g_i(x))

此时我们对拉格朗日函数 L\mathcal{L} 求最小值，得到拉格朗日对偶函数 (dual function)：

d(λ,μ)=min⁡x∈X(L(x,λ,μ))=min⁡x∈X{f(x)+∑i=1lμihi(x)+∑i=1mλigi(x)}≤min⁡x∈S(E){f(x)+∑i=1lμihi(x)+∑i=1mλigi(x)}≤min⁡x∈S(E){f(x)}\begin{aligned} d(\lambda,\mu) & = \min _{x \in X} (\mathcal{L}(x, \lambda, \mu)) = \min _{x \in X} \{ f(x) + \sum_{i=1}^l \mu_i h_i(x) + \sum_{i=1}^m \lambda_i g_i(x)\} \\ & \le \min _{x \in S(\mathcal{E})} \{ f(x) + \sum_{i=1}^l \mu_i h_i(x) + \sum_{i=1}^m \lambda_i g_i(x)\} \\ & \le \min _{x \in S(\mathcal{E})} \{ f(x) \} \end{aligned}

  • 对于 ∀(λ,μ),λ≥0\forall (\lambda, \mu), \lambda \ge 0 必有 d(λ,μ)≤v(P)d(\lambda,\mu) \le v (\mathcal{P})，即 d(λ,μ)d(\lambda, \mu) 是 v(P)v (\mathcal{P}) 的下界，所以我们要找出 d(λ,μ)d(\lambda, \mu) 的【最大值】

此时我们就可以给出拉格朗日问题的对偶问题 (D)(\mathcal{D}) ：

(D):  max⁡d(λ,μ)s.t.λi≥0,  ∀i∈{1,2,...,m}(\mathcal{D}):\; \max d(\lambda, \mu) \\ s.t. \quad \lambda_i \ge 0,\; \forall i \in \{1,2,...,m\}

写成以下形式：

(D):  max⁡λ≥0min⁡x∈X(L(x,λ,μ))→交换min⁡x∈Xmax⁡λ≥0(L(x,λ,μ))(\mathcal{D}):\; \max _{\lambda \ge 0} \quad \min _{x \in X} (\mathcal{L}(x, \lambda, \mu)) \quad \xrightarrow{交换} \quad \min _{x \in X} \quad \max _{\lambda \ge 0} (\mathcal{L}(x, \lambda, \mu))

经过推导，问题 (D)(\mathcal{D}) 可转化成原问题 (P)(\mathcal{P})：

(P):  min⁡x∈R2f(x)s.t.{hi(x)=0,  ∀i∈{1,2,...,l}gj(x)≤0,  ∀j∈{1,2,...,m}x∈X(\mathcal{P}):\; \min_{x\in \R^2} f(x) \\ s.t. \quad \left\{\begin{aligned} & h_i(x)=0, \;\forall i \in \{1,2,...,l\} \\ & g_j(x) \le 0 , \; \forall j \in \{1,2,...,m\} \\ & x \in X \end{aligned}\right.

弱对偶定理

在之前拉格朗日对偶问题中，“对于 ∀(λ,μ),λ≥0\forall (\lambda, \mu), \lambda \ge 0 必有 d(λ,μ)≤v(P)d(\lambda,\mu) \le v (\mathcal{P})，即 d(λ,μ)d(\lambda, \mu) 是 v(P)v (\mathcal{P}) 的下界，所以我们要找出 d(λ,μ)d(\lambda, \mu) 的最大值”。我们可以推导到一般：

  • 设 $ v (\mathcal{P})$ 是原问题 (P)(\mathcal{P}) 的最优值，$ v (\mathcal{D})$ 是对偶问题 (D)(\mathcal{D}) 的最优值，则 $ v (\mathcal{D}) \le v (\mathcal{P})$

推论：假设 xˉ∈S(E)，(λˉ,μˉ),λˉ≥0  且  d(λˉ,μˉ)=f(xˉ)\bar x \in S(\mathcal{E})，(\bar \lambda,\bar \mu),\bar \lambda \ge 0 \; 且 \; d(\bar \lambda,\bar \mu) = f(\bar x)，则 $ v (\mathcal{P}) = v (\mathcal{D}) ; 且 ; \bar x,(\bar \lambda,\bar \mu) ; 是; v (\mathcal{P}) ; 和 ; v (\mathcal{D}) ; 的最优解$