对偶问题笔记（1）

2023-12-19 00:32:12

目录

1 从 Lagrange 函数引入对偶问题

考虑如下优化问题 { min ? f 0 ( x ) s . t f i ( x ) ≤ 0 , i = 1 , ? ? , p , h j ( x ) = 0 , j = 1 , ? ? , q , x ∈ Ω , \begin{align} \begin{cases}\min f_0(x)\\\mathrm{s.t}\quad f_i(x)\leq0,\quad i=1,\cdots,p,\\h_j(x)=0,\quad j=1,\cdots,q,\\x\in\Omega,\end{cases}\end{align} ? ? ??minf0?(x)s.tfi?(x)≤0,i=1,?,p,hj?(x)=0,j=1,?,q,x∈Ω,???其中 { f i } i = 0 p , ? { h j } j = 1 q \{f_i\}_{i=0}^p,\:\{h_j\}_{j=1}^q {fi?}i=0p?,{hj?}j=1q? 均为定义在 R n \mathbb{R}^n Rn 取值于 R ￣ \overline{\mathbb{R}} R 上的函数， Ω ? R n \Omega\subset\mathbb{R}^n Ω?Rn. 设可行集 D : = { x ∈ Ω ∣ f i ( x ) ≤ 0 , ? i = 1 , ? ? , p ; ? h j ( x ) = 0 , j = 1 , ? ? , q } \mathcal{D}:=\{x\in\Omega|f_i(x)\leq0,~i=1,\cdots,p;~h_j(x)=0,j=1,\cdots,q\} D:={x∈Ω∣fi?(x)≤0,?i=1,?,p;?hj?(x)=0,j=1,?,q}满足如下条件（该条件是为了后面定义的拉格朗日函数） { ? ∞ < f i ( x ) ≤ ∞ i = 0 , 1 , ? ? , p , ? ∞ < h j ( x ) < ∞ j = 1 , ? ? , q , ? x ∈ Ω . \begin{align}\begin{cases}-\infty<f_i(x)\leq\infty&i=0,1,\cdots,p,\\-\infty<h_j(x)<\infty&j=1,\cdots,q,\end{cases}\quad\forall x\in\Omega.\end{align} {?∞<fi?(x)≤∞?∞<hj?(x)<∞?i=0,1,?,p,j=1,?,q,??x∈Ω.??该问题的 Lagrange 函数定义为
L ( x , λ , μ ) : = f 0 ( x ) + ∑ i = 1 p λ i f i ( x ) + ∑ j = 1 q μ j h j ( x ) , ( x , λ , μ ) ∈ Ω × R + p × R q , \begin{aligned}L(x,\lambda,\mu)&:=f_0(x)+\sum_{i=1}^p\lambda_if_i(x)+\sum_{j=1}^q\mu_jh_j(x),\quad(x,\lambda,\mu)\in\Omega\times\mathbb{R}_+^p\times\mathbb{R}^q,\end{aligned} L(x,λ,μ)?:=f0?(x)+i=1∑p?λi?fi?(x)+j=1∑q?μj?hj?(x),(x,λ,μ)∈Ω×R+p?×Rq,?

其中 λ : = ( λ 1 , . . . , λ p ) T , μ : = ( μ 1 , . . . , μ q ) T . \begin{aligned}\lambda&:=(\lambda_1,...,\lambda_p)^T,\quad\mu:=(\mu_1,...,\mu_q)^T.\end{aligned} λ?:=(λ1?,...,λp?)T,μ:=(μ1?,...,μq?)T.?

从正则化的角度来看 Lagrange 函数可以发现 Lagrange 乘子 { λ i } i = 1 p \{\lambda_i\}_{i=1}^p {λi?}i=1p? 和 { μ j } j = 1 q \{\mu_j\}_{j=1}^q {μj?}j=1q? 充当了惩罚项的作用：对任意给定的 x ∈ Ω x\in\Omega x∈Ω 和 1 ≤ i ≤ p 1\leq i\leq p 1≤i≤p, 如果 f i ( x ) > 0 , f_i( x) > 0, fi?(x)>0,那么 L ( x , λ , μ ) → L( x, \lambda, \mu) \to L(x,λ,μ)→ ∞ ? ( λ i → ∞ ) \infty~(\lambda_i\to\infty) ∞?(λi?→∞).类似地，对任意 1 ≤ j ≤ q 1\leq j\leq q 1≤j≤q,如果 h j ( x ) ≠ 0 h_j(x)\neq0 hj?(x)=0, 也有 L ( x , λ , μ ) → ∞ ? ( μ j → L(x,\lambda,\mu)\to\infty~(\mu_j\to L(x,λ,μ)→∞?(μj?→ ∞ \infty ∞或 ? ∞ ) -\infty) ?∞).

所以根据 (2) 有 sup ? λ ? 0 , μ L ( x , λ , μ ) = { f 0 ( x ) x ∈ D , ∞ x ∈ Ω ? D , \begin{align} &&\sup\limits_{\lambda\succeq0,\mu}L(x,\lambda,\mu)=\begin{cases}f_0(x)&x\in\mathcal{D},\\\infty&x\in\Omega\setminus\mathcal{D},\end{cases}& \end{align} ??λ?0,μsup?L(x,λ,μ)={f0?(x)∞?x∈D,x∈Ω?D,????
从而
ξ ? : = inf ? x ∈ D f 0 ( x ) = inf ? x ∈ Ω sup ? λ ? 0 , μ L ( x , λ , μ ) . \begin{aligned}\xi^{*}:=\inf_{x\in\mathcal{D}}f_{0}(x)=\inf_{x\in\Omega}\sup_{\lambda\succeq0,\mu}L(x,\lambda,\mu). \end{aligned} ξ?:=x∈Dinf?f0?(x)=x∈Ωinf?λ?0,μsup?L(x,λ,μ).?
根据上确界和下确界的性质有：
sup ? λ ? 0 , μ inf ? x ∈ Ω L ( x , λ , μ ) ≤ inf ? x ∈ Ω sup ? λ ? 0 , μ L ( x , λ , μ ) . \begin{align}\sup_{\lambda\succeq0,\mu}\inf_{x\in\Omega}L(x,\lambda,\mu)\leq\inf_{x\in\Omega}\sup_{\lambda\succeq0,\mu}L(x,\lambda,\mu).\end{align} λ?0,μsup?x∈Ωinf?L(x,λ,μ)≤x∈Ωinf?λ?0,μsup?L(x,λ,μ).??记 η ? : = sup ? λ ? 0 , μ g ( λ , μ ) , \begin{aligned}\eta^*:=\sup_{\lambda\succeq0,\mu}g(\lambda,\mu),\end{aligned} η?:=λ?0,μsup?g(λ,μ),?其中 g ( λ , μ ) : = inf ? x ∈ Ω L ( x , λ , μ ) , ( λ , μ ) ∈ R + p × R q . \begin{align}g(\lambda,\mu):=\inf_{x\in\Omega}L(x,\lambda,\mu),\quad(\lambda,\mu)\in\mathbb{R}_+^p\times\mathbb{R}^q.\end{align} g(λ,μ):=x∈Ωinf?L(x,λ,μ),(λ,μ)∈R+p?×Rq.??则有
η ? = sup ? λ ? 0 , μ g ( λ , μ ) ≤ inf ? x ∈ D f 0 ( x ) = ξ ? . \begin{aligned}\eta^*=\sup_{\lambda\succeq0,\mu}g(\lambda,\mu)\leq\inf_{x\in\mathcal{D}}f_0(x)=\xi^*.\end{aligned} η?=λ?0,μsup?g(λ,μ)≤x∈Dinf?f0?(x)=ξ?.?上式给出了优化问题 (1)的最优值 ξ ? \xi^* ξ? 的一个下界，这个下界可以通过求解如下优化问题而得到 { max ? g ( λ , μ ) , s . t λ ? 0 \begin{align}\begin{cases}\max g(\lambda,\mu),\\\mathrm{s.t}\quad\lambda\succeq0&\end{cases}\end{align} {maxg(λ,μ),s.tλ?0????

定义 1.1.1 (对偶函数，对偶问题，对偶性) 我们称(6)为(1)的对偶问题，相对地， 称(1)为原问题. (5)所定义的函数 g ( λ , μ ) g(\lambda,\mu) g(λ,μ) 称为 Lagrange 对偶函数，简称为对偶函数，向量 λ , μ \lambda,\mu λ,μ 称为对偶变量. 不等式(4), 即 η ? ≤ ξ ? \eta^*\leq\xi^* η?≤ξ?, 称为问题 (1)的弱对偶性. 若等式 η ? = ξ ? \eta^*=\xi^* η?=ξ? 成立，则称问题 (1)满足强对偶性.

命题 1.1.1 (对偶问题是凸的) 由(5)所定义的对偶函数 g g g 是 R + p × R q \mathbb{R}_+^p\times\mathbb{R}^q R+p?×Rq 上上半连续的凹函数.

证.对任意固定的 x ∈ R n x\in\mathbb{R}^n x∈Rn,易见 L ( x , λ , μ ) L(x,\lambda,\mu) L(x,λ,μ) 是 λ , μ \lambda,\mu λ,μ 的仿射函数，因而 g ( λ , μ ) g(\lambda,\mu) g(λ,μ) 是仿射函数的逐点下确界，所以是 R + p × R q \mathbb{R}_+^p\times\mathbb{R}^q R+p?×Rq 上凹函数.（这是因为有命题：凸函数是仿射函数的逐点上确界）

设 ( λ k , μ k ) ∈ R + p × R q (\lambda_k,\mu_k)\in\mathbb{R}_+^p\times\mathbb{R}^q (λk?,μk?)∈R+p?×Rq 满足 ( λ k , μ k ) → ( λ 0 , μ 0 ) ∈ R + p × R q (\lambda_k,\mu_k)\to(\lambda_0,\mu_0)\in\mathbb{R}_+^p\times\mathbb{R}^q (λk?,μk?)→(λ0?,μ0?)∈R+p?×Rq,那么， ? x ∈ Ω \forall x\in\Omega ?x∈Ω, 有 g ( λ k , μ k ) ≤ L ( x , λ k , μ k ) \begin{aligned}g(\lambda_k,\mu_k)\le L(x,\lambda_k,\mu_k)\end{aligned} g(λk?,μk?)≤L(x,λk?,μk?)?从而
lim ? k → ∞ g ( λ k , μ k ) ≤ lim ? ￣ k → ∞ L ( x , λ k , μ k ) = L ( x , λ 0 , μ 0 ) \begin{aligned}\lim_{k\to\infty}g(\lambda_k,\mu_k)\le\overline{\lim}_{k\to\infty}L(x,\lambda_k,\mu_k)=L(x,\lambda_0,\mu_0)\end{aligned} k→∞lim?g(λk?,μk?)≤limk→∞?L(x,λk?,μk?)=L(x,λ0?,μ0?)?由 x x x 的任意性, 两边对 x ∈ ? x ∈ ? x∈? 求下确界, 得 l i m ￣ ? k → ∞ g ( λ k , μ k ) ≤ g ( λ 0 , μ 0 ) . \operatorname*{\overline{lim}}_{k\to\infty}g(\lambda_k,\mu_k)\leq g(\lambda_0,\mu_0). k→∞lim?g(λk?,μk?)≤g(λ0?,μ0?).所以 g g g是上半连续的.

注：当
? ∞ < f i ( x ) , h j ( x ) < ∞ , ? x ∈ Ω , i = 1 , . . . , p ; j = 1 , . . . , q \begin{align} -\infty<f_i(x),h_j(x)<\infty,\quad\forall x\in\Omega,\quad i=1,...,p;\quad j=1,...,q\end{align} ?∞<fi?(x),hj?(x)<∞,?x∈Ω,i=1,...,p;j=1,...,q??时，Lagrange 函数 L ( x , λ , μ ) L(x,\lambda,\mu) L(x,λ,μ) 对所有 ( x , λ , μ ) ∈ Ω × R p × R q (x,\lambda,\mu)\in\Omega\times\mathbb{R}^p\times\mathbb{R}^q (x,λ,μ)∈Ω×Rp×Rq 有定义，且对偶函数 g ( λ , μ ) : = inf ? x ∈ Ω L ( x , λ , μ ) g(\lambda,\mu):=\inf_{x\in\Omega}L(x,\lambda,\mu) g(λ,μ):=x∈Ωinf?L(x,λ,μ)对所有 ( λ , μ ) ∈ R p × R q (\lambda,\mu)\in\mathbb{R}^p\times\mathbb{R}^q (λ,μ)∈Rp×Rq 有定义. 考察命题 1.1.1的证明可知，此时 g g g 是定义在 R p × R q \mathbb{R}^p\times\mathbb{R}^q Rp×Rq的上凹函数.

2. 强对偶性与 KKT 条件

对偶问题可以提供原问题重要的信息. 如上所述, 优化问题(1)恒满足弱对偶性. 它说明对偶问题的最优值 η ? η^? η? 是原问题的最优值 ξ ? ξ^? ξ? 的一个下界. 实际上在强对偶条件下, 原问题与对偶问题的解满足
一个与 KKT 条件类似但更一般的条件, 它无需目标函数和约束函数的可微性以及点 x ? x^? x?的正则性. 当这些函数可微时, 它可以导出 KKT 条件. 从这个视角导出 KKT 条件使得对 Lagrange 乘子有更好的了解, 它们实际上是对偶问题的解.

命题 2.1 设优化问题(1)满足(2), ( x ? , λ ? , μ ? ) ∈ D × R + p × R q (x^*,\lambda^*,\mu^*)\in\mathcal{D}\times\mathbb{R}_+^p\times\mathbb{R}^q (x?,λ?,μ?)∈D×R+p?×Rq. 那么
ξ ? = η ? , f 0 ( x ? ) = ξ ? , g ( λ ? , μ ? ) = η ? , \begin{align} \xi^*=\eta^*,\quad f_0(x^*)=\xi^*,\quad g(\lambda^*,\mu^*)=\eta^*,\end{align} ξ?=η?,f0?(x?)=ξ?,g(λ?,μ?)=η?,??等价于 λ i ? f i ( x ? ) = 0 , i = 1 , ? ? , p ; L ( x ? , λ ? , μ ? ) = inf ? x ∈ Ω L ( x , λ ? , μ ? ) . \begin{align} \lambda_i^*f_i(x^*)=0,\quad i=1,\cdots,p;\quad L(x^*,\lambda^*,\mu^*)=\inf_{x\in\Omega}L(x,\lambda^*,\mu^*).\end{align} λi??fi?(x?)=0,i=1,?,p;L(x?,λ?,μ?)=x∈Ωinf?L(x,λ?,μ?).??此外，上述任一条成立时，有 L ( x ? , λ ? , μ ? ) = ξ ? = η ? L(x^*,\lambda^*,\mu^*)=\xi^*=\eta^* L(x?,λ?,μ?)=ξ?=η?, 且若还存在 x ∈ Ω x\in\Omega x∈Ω 使得 f 0 ( x ) < ∞ , f i ( x ) < ∞ , ? ∞ < h j ( x ) < ∞ , f_0(x)<\infty,\quad f_i(x)<\infty,\quad-\infty<h_j(x)<\infty, f0?(x)<∞,fi?(x)<∞,?∞<hj?(x)<∞,则 ξ ? < ∞ . \xi^*<\infty. ξ?<∞.

证. 设(9)成立，则 inf ? x ∈ D f 0 ( x ) = ξ ? ≤ f 0 ( x ? ) = L ( x ? , λ ? , μ ? ) = inf ? x ∈ Ω L ( x , λ ? , μ ? ) = g ( λ ? , μ ? ) ≤ η ? ≤ ξ ? . \begin{align}\inf_{x\in\mathcal{D}}f_{0}(x)= \xi^*\leq f_0(x^*)=L(x^*,\lambda^*,\mu^*)=\inf_{x\in\Omega}L(x,\lambda^*,\mu^*)=g(\lambda^*,\mu^*)\leq\eta^*\leq\xi^*.\end{align} x∈Dinf?f0?(x)=ξ?≤f0?(x?)=L(x?,λ?,μ?)=x∈Ωinf?L(x,λ?,μ?)=g(λ?,μ?)≤η?≤ξ?.??所以，(8)成立.

反之，设(8)成立，则 ξ ? = f 0 ( x ? ) ≥ L ( x ? , λ ? , μ ? ) ≥ inf ? x ∈ Ω L ( x , λ ? , μ ? ) = g ( λ ? , μ ? ) = η ? = ξ ? . \xi^*=f_0(x^*)\geq L(x^*,\lambda^*,\mu^*)\geq\inf_{x\in\Omega}L(x,\lambda^*,\mu^*)=g(\lambda^*,\mu^*)=\eta^*=\xi^*. ξ?=f0?(x?)≥L(x?,λ?,μ?)≥x∈Ωinf?L(x,λ?,μ?)=g(λ?,μ?)=η?=ξ?.所以 f 0 ( x ? ) = L ( x ? , λ ? , μ ? ) = g ( λ ? , μ ? ) f_0(x^*)=L(x^*,\lambda^*,\mu^*)=g(\lambda^*,\mu^*) f0?(x?)=L(x?,λ?,μ?)=g(λ?,μ?).第一个等号是(8)给出的条件，以及由 λ ? ? 0 , x ? ∈ D \lambda^*\succeq0,\quad x^*\in\mathcal{D} λ??0,x?∈D 可以推导出 (9)的第一式；第二个等号即为(9) 的第二式.

上述条件成立时，有(10)成立，因而 L ( x ? , λ ? , μ ? ) = ξ ? = η ? L(x^*,\lambda^*,\mu^*)=\xi^*=\eta^* L(x?,λ?,μ?)=ξ?=η?. 若还存在 x ∈ Ω x\in\Omega x∈Ω 使得
(9)成立，则利用(8)有， ξ ? = L ( x ? , λ ? , μ ? ) ≤ L ( x , λ ? , μ ? ) < ∞ . \xi^*=L(x^*,\lambda^*,\mu^*)\leq L(x,\lambda^*,\mu^*)<\infty. ξ?=L(x?,λ?,μ?)≤L(x,λ?,μ?)<∞. 我们称条件 x ? ∈ D x^*\in\mathcal{D} x?∈D 为优化问题(1)的可行条件，而称条件(9)为其对偶可行条件，它的关键作用可以从不等式(10)中看出，它确保了强对偶性以及原问题与对偶问题的可解性. 特别，(9)的第一式 “ λ i ? f i ( x ? ) = 0 , i = 1 , ? ? , p ? \lambda_i^*f_i(x^*)=0,\quad i=1,\cdots,p^* λi??fi?(x?)=0,i=1,?,p? 被称为互补松弛条件.

命题 2.2 (强对偶性等价于 KKT 条件) 设优化问题(1)满足(2), ( x ? , λ ? , μ ? ) ∈ (x^*,\lambda^*,\mu^*)\in (x?,λ?,μ?)∈ R n × R p × R q \mathbb{R}^n\times\mathbb{R}^p\times\mathbb{R}^q Rn×Rp×Rq.那么， x ? x^* x? 和 ( λ ? , μ ? ) (\lambda^*,\mu^*) (λ?,μ?) 分别是原问题(1)以及对偶问题(6)的解且满足强对偶性 ξ ? = η ? \xi^*=\eta^* ξ?=η? 当且仅当 { x ? ∈ D , λ i ? ≥ 0 , i = 1 , ? ? , p ; λ i ? f i ( x ? ) = 0 , i = 1 , ? ? , p ; L ( x ? , λ ? , μ ? ) = inf ? x ∈ Ω L ( x , λ ? , μ ? ) . \begin{align} \begin{cases}x^*\in\mathcal{D},\\\lambda_i^*\geq0,\quad i=1,\cdots,p;\\\lambda_i^*f_i(x^*)=0,\quad i=1,\cdots,p;\\L(x^*,\lambda^*,\mu^*)=\inf_{x\in\Omega}L(x,\lambda^*,\mu^*).\end{cases}\end{align} ? ? ??x?∈D,λi??≥0,i=1,?,p;λi??fi?(x?)=0,i=1,?,p;L(x?,λ?,μ?)=infx∈Ω?L(x,λ?,μ?).???证. 必要性. x ? x^* x? 是原问题(1)的解，按照定义可以推出 x ? ∈ D x^*\in\mathcal{D} x?∈D 且 f 0 ( x ? ) = ξ ? ; ( λ ? , μ ? ) f_0(x^*)=\xi^*;(\lambda^*,\mu^*) f0?(x?)=ξ?;(λ?,μ?) 是对偶问题(6)的解，同样地按照定义可以推出 λ ? ? 0 \lambda^*\succeq0 λ??0 且 g ( λ ? , μ ? ) = η ? ; g(\lambda^*,\mu^*)=\eta^*; g(λ?,μ?)=η?; 又由于 ξ ? = η ? \xi^*=\eta^* ξ?=η?, 所以 ( x ? , λ ? , μ ? ) ∈ (x^*,\lambda^*,\mu^*)\in (x?,λ?,μ?)∈ D × R + p × R q \mathcal{D}\times\mathbb{R}_+^p\times\mathbb{R}^q D×R+p?×Rq 且(8)成立. 显然 x ? ∈ D x^*\in\mathcal{D} x?∈D 即为 (11)的第一式成立； λ ? ∈ R + p \lambda^*\in\mathbb{R}_+^p λ?∈R+p? 蕴含(11)的第二行成立；根据 命题 2.1 可知, ξ ? = η ? , f 0 ( x ? ) = ξ ? , g ( λ ? , μ ? ) = η ? , \xi^*=\eta^*,\quad f_0(x^*)=\xi^*,\quad g(\lambda^*,\mu^*)=\eta^*, ξ?=η?,f0?(x?)=ξ?,g(λ?,μ?)=η?, 等价于 λ i ? f i ( x ? ) = 0 , i = 1 , ? ? , p ; L ( x ? , λ ? , μ ? ) = inf ? x ∈ Ω L ( x , λ ? , μ ? ) . \lambda_i^*f_i(x^*)=0,\quad i=1,\cdots,p;\quad L(x^*,\lambda^*,\mu^*)=\inf_{x\in\Omega}L(x,\lambda^*,\mu^*). λi??fi?(x?)=0,i=1,?,p;L(x?,λ?,μ?)=infx∈Ω?L(x,λ?,μ?).，即(11)的最后两行成立.

充分性. 设(11)也就是KKT条件成立，显然由KKT条件的前两行可以推出 ( x ? , λ ? , μ ? ) ∈ D × R + p × R q (x^*,\lambda^*,\mu^*)\in\mathcal{D}\times\mathbb{R}_+^p\times\mathbb{R}^q (x?,λ?,μ?)∈D×R+p?×Rq,而KKT条件的后两行即为(9). 由命题 2.1知 (8)与(9)等价，从而有(9)的条件 ξ ? = η ? , f 0 ( x ? ) = ξ ? , g ( λ ? , μ ? ) = η ? \xi^*=\eta^*,\quad f_0(x^*)=\xi^*,\quad g(\lambda^*,\mu^*)=\eta^* ξ?=η?,f0?(x?)=ξ?,g(λ?,μ?)=η? 成立.

注：当满足KKT条件（或者说满足强对偶性时），条件 L ( x ? , λ ? , μ ? ) = inf ? x ∈ Ω L ( x , λ ? , μ ? ) L(x^*,\lambda^*,\mu^*)=\inf_{x\in\Omega}L(x,\lambda^*,\mu^*) L(x?,λ?,μ?)=infx∈Ω?L(x,λ?,μ?) 可以写成 L ( x ? , λ ? , μ ? ) = g ( λ ? , μ ? ) . L(x^*,\lambda^*,\mu^*)=g(\lambda^*,\mu^*). L(x?,λ?,μ?)=g(λ?,μ?).

推论 2.3 设优化问题(1)满足 ( 2 ) , ( λ ? , μ ? ) ∈ R p × R q , x ? ∈ r i ( Ω ) (2),\quad(\lambda^*,\mu^*)\in\mathbb{R}^p\times\mathbb{R}^q,\quad x^*\in\mathbf{ri}(\Omega) (2),(λ?,μ?)∈Rp×Rq,x?∈ri(Ω),且 { f i } i = 0 p \{f_i\}_{i=0}^p {fi?}i=0p? 和 { h j } j = 1 q \{h_j\}_{j=1}^q {hj?}j=1q? 均在 x ? x^* x? 处可微，那么，
L ( x ? , λ ? , μ ? ) = inf ? x ∈ Ω L ( x , λ ? , μ ? ) \begin{align} L(x^*,\lambda^*,\mu^*)=\inf_{x\in\Omega}L(x,\lambda^*,\mu^*)\end{align} L(x?,λ?,μ?)=x∈Ωinf?L(x,λ?,μ?)??蕴含 ? x L ( x ? , λ ? , μ ? ) ⊥ V Ω . \begin{align}\nabla_xL(x^*,\lambda^*,\mu^*)\perp V_\Omega.\end{align} ?x?L(x?,λ?,μ?)⊥VΩ?.??并且当优化问题(1)是凸问题时，二者等价.

证. 由于 x ? ∈ r i ( Ω ) x^*\in\mathbf{ri}(\Omega) x?∈ri(Ω), 利用优化问题笔记中的 命题 1.2.1 可知 (12)能够推导出(13). 特别地当优化问题(1)是凸问题时，由于 L ( x , λ ? , μ ? ) L(x,\lambda^*,\mu^*) L(x,λ?,μ?) 关于 x x x 为凸函数，由优化问题笔记中的命题 3.1.2 可知 x ? x^* x? 是 ( f , D ) (f,\mathcal{D}) (f,D) 的一个全局最优解当且仅当 ? f ( x ? ) T ( x ? x ? ) ≥ 0 , ? x ∈ D \nabla f(x^*)^T(x-x^*)\ge0,\quad\forall x\in\mathcal{D} ?f(x?)T(x?x?)≥0,?x∈D，(12)等价于
? x L ( x ? , λ ? , μ ? ) T ( x ? x ? ) ≥ 0 , ? x ∈ Ω . \nabla_xL(x^*,\lambda^*,\mu^*)^T(x-x^*)\geq0,\quad\forall x\in\Omega. ?x?L(x?,λ?,μ?)T(x?x?)≥0,?x∈Ω.由于 x ? ∈ r i ( Ω ) x^*\in\mathbf{ri}(\Omega) x?∈ri(Ω),根据优化问题中的引理 1.2.2可知此条件等价于 (13).

命题 2.2 说明当优化问题(1) 满足强对偶性, 且原问题和对偶问题均可解时, 可以按一定的步骤求解其最优解 x ? x^* x?:

算法 2.1 优化问题(1)的求解算法：
(2.1.1) 计算对偶函数 g ( λ , μ ) g(\lambda,\mu) g(λ,μ);
(2.1.2) 求解对偶问题(6), 得解 ( λ ? , μ ? ) ∈ R + p × R q ; (\lambda^*,\mu^*)\in\mathbb{R}_+^p\times\mathbb{R}^q; (λ?,μ?)∈R+p?×Rq;
(2.1.3) 求解 L ( x ? , λ ? , μ ? ) = g ( λ ? , μ ? ) L(x^*,\lambda^*,\mu^*)=g(\lambda^*,\mu^*) L(x?,λ?,μ?)=g(λ?,μ?),得解 x ? ; x^*; x?;
(2.1.4) 检验 x ? x^* x? 是否对偶可行条件的第一项：
x ? ∈ D , λ i ? f i ( x ? ) = 0 , i = 1 , ? ? , p . \begin{align} x^*\in\mathcal{D},\quad\lambda_i^*f_i(x^*)=0,\quad i=1,\cdots,p.\end{align} x?∈D,λi??fi?(x?)=0,i=1,?,p.??

注：根据对偶函数 g ( λ , μ ) g(\lambda,\mu) g(λ,μ) 的定义可知，步骤 (2.1.) 等价于求解优化问题
x ? = argmin ? x ∈ Ω L ( x , λ ? , μ ? ) . x^*=\operatorname*{argmin}_{x\in\Omega}L(x,\lambda^*,\mu^*). x?=x∈Ωargmin?L(x,λ?,μ?).一旦 算法 2.1 能执行完成，并使所求得的 x ? x^* x? 以及 ( λ ? , μ ? ) (\lambda^*,\mu^*) (λ?,μ?) 满足(14), 那么，根据 命题 2.2, x ? x^* x? 和 ( λ ? , μ ? ) (\lambda^*,\mu^*) (λ?,μ?) 必是优化问题(1)及其对偶问题 (6)的解，且满足强对偶性.

3. 对偶性的鞍点特征

在这小节中将说明强对偶性的几何表现。

首先，强对偶性 η ? = ξ ? \eta^*=\xi^* η?=ξ?, 即 sup ? λ ? 0 , μ ∈ R q inf ? x ∈ Ω L ( x , λ , μ ) = inf ? x ∈ Ω sup ? λ ? 0 , μ ∈ R q L ( x , λ , μ ) \begin{align} \sup_{\lambda\succeq0,\mu\in\mathbb{R}^q}\inf_{x\in\Omega}L(x,\lambda,\mu)=\inf_{x\in\Omega}\sup_{\lambda\succeq0,\mu\in\mathbb{R}^q}L(x,\lambda,\mu)\end{align} λ?0,μ∈Rqsup?x∈Ωinf?L(x,λ,μ)=x∈Ωinf?λ?0,μ∈Rqsup?L(x,λ,μ)??中，拉格朗日函数 L ( x , λ , μ ) L(x,\lambda,\mu) L(x,λ,μ) 可以看成由两部分所组成： ( x ) (x) (x)和 ( λ , μ ) (\lambda,\mu) (λ,μ)，更为一般地，考虑多元函数 f ( x , y ) f(x,y) f(x,y)以及类似于(15)的等式： sup ? y ∈ B inf ? x ∈ A f ( x , y ) = inf ? x ∈ A sup ? y ∈ B f ( x , y ) \begin{align}\sup_{y\in B}\inf_{x\in A}f(x,y)=\inf_{x\in A}\sup_{y\in B}f(x,y)\end{align} y∈Bsup?x∈Ainf?f(x,y)=x∈Ainf?y∈Bsup?f(x,y)??其中有效定义域为 dom ( f ) = A × B ? R n × R m \begin{aligned}\textbf{dom}(f)=A\times B\subset\mathbb{R}^n\times\mathbb{R}^m\end{aligned} dom(f)=A×B?Rn×Rm?，记 ξ ? : = inf ? x ∈ A sup ? y ∈ B f ( x , y ) , η ? = sup ? y ∈ B inf ? x ∈ A f ( x , y ) . \begin{align}\xi^*:=\inf_{x\in A}\sup_{y\in B}f(x,y),\quad\eta^*=\sup_{y\in B}\inf_{x\in A}f(x,y).\end{align} ξ?:=x∈Ainf?y∈Bsup?f(x,y),η?=y∈Bsup?x∈Ainf?f(x,y).??

命题 3.1 (极大极小不等式) 给定函数 f : A × B → R ￣ f:A\times B\to\overline{\mathbb{R}} f:A×B→R,其中 A ? R n , ? B ? R m A\subset\mathbb{R}^n,~B\subset\mathbb{R}^m A?Rn,?B?Rm 均为非空子集，有 η ? ≤ ξ ? . \eta^*\leq\xi^*. η?≤ξ?.

证. 对任意的 x ∈ A , ? y ∈ B x\in A,\:y\in B x∈A,y∈B,根据确界的定义，有 inf ? x ∈ A f ( x , y ) ≤ f ( x , y ) \inf_{x\in A}f(x,y)\leq f(x,y) infx∈A?f(x,y)≤f(x,y).两边对 y ∈ B y\in B y∈B 求上确界，得
sup ? y ∈ B inf ? x ∈ A f ( x , y ) ≤ sup ? y ∈ B f ( x , y ) . \sup\limits_{y\in B}\inf\limits_{x\in A}f(x,y)\leq\sup\limits_{y\in B}f(x,y). y∈Bsup?x∈Ainf?f(x,y)≤y∈Bsup?f(x,y).两边再对 x ∈ A x\in A x∈A 求下确界即得 η ? ≤ ξ ? . \eta^*\leq\xi^*. η?≤ξ?.

类似于Larange 对偶函数的情况，称 η ? ≤ ξ ? . \eta^*\leq\xi^*. η?≤ξ?. 为弱对偶性，称 η ? = ξ ? . \eta^*=\xi^*. η?=ξ?.为强对偶性.

若(16)左边的上确界能达到，那么，存在 y ? ∈ B y^*\in B y?∈B, 使得 η ? = inf ? x ∈ A f ( x , y ? ) = sup ? y ∈ B inf ? x ∈ A f ( x , y ) . \begin{aligned}\eta^*=\inf_{x\in A}f(x,y^*)=\sup_{y\in B}\inf_{x\in A}f(x,y).\end{aligned} η?=x∈Ainf?f(x,y?)=y∈Bsup?x∈Ainf?f(x,y).?同理，对于(16)式右边的下确界，若可以达到，则存在 x ? ∈ A x^*\in A x?∈A, 使得 ξ ? = sup ? y ∈ B f ( x ? , y ) = inf ? x ∈ A sup ? y ∈ B f ( x , y ) . \begin{aligned}\xi^*=\sup_{y\in B}f(x^*,y)=\inf_{x\in A}\sup_{y\in B}f(x,y).\end{aligned} ξ?=y∈Bsup?f(x?,y)=x∈Ainf?y∈Bsup?f(x,y).?所以，当(16)成立的时候，也就是 ξ ? = η ? \xi^* = \eta^* ξ?=η?，则有： sup ? y ∈ B f ( x ? , y ) = ξ ? = η ? = inf ? x ∈ A f ( x , y ? ) . \sup_{y\in B}f(x^*,y)=\xi^*=\eta^*=\inf_{x\in A}f(x,y^*). y∈Bsup?f(x?,y)=ξ?=η?=x∈Ainf?f(x,y?).从而
f ( x ? , y ) ≤ sup ? y ∈ B f ( x ? , y ) = ξ ? = η ? = inf ? x ∈ A f ( x , y ? ) ≤ f ( x , y ? ) , ? x ∈ A , ? y ∈ B . \begin{aligned}f(x^*,y)\leq\sup\limits_{y\in B}f(x^*,y)=\xi^*=\eta^*=\inf\limits_{x\in A}f(x,y^*)\leq f(x,y^*),\quad\forall x\in A,\:y\in B.\end{aligned} f(x?,y)≤y∈Bsup?f(x?,y)=ξ?=η?=x∈Ainf?f(x,y?)≤f(x,y?),?x∈A,y∈B.?上式中取 x = x ? , ? y = y ? x=x^*,\:y=y^* x=x?,y=y?, 可以得到 f ( x ? , y ? ) = ξ ? = η ? f(x^*,y^*)=\xi^*=\eta^* f(x?,y?)=ξ?=η?. 所以
f ( x ? , y ) ≤ f ( x ? , y ? ) ≤ f ( x , y ? ) , ? x ∈ A , ? y ∈ B . \begin{align} f(x^*,y)\leq f(x^*,y^*)\leq f(x,y^*),\quad\forall x\in A,\:y\in B.\end{align} f(x?,y)≤f(x?,y?)≤f(x,y?),?x∈A,y∈B.??这说明 ( x ? , y ? ) (x^*,y^*) (x?,y?) 是 f f f 中的鞍点，定义如下.

定义 3.1 (鞍点) 对于函数 f : A × B → R ￣ f:A\times B\to\overline{\mathbb{R}} f:A×B→R,其中 A ? R n , B ? R m A\subset\mathbb{R}^n,\quad B\subset\mathbb{R}^m A?Rn,B?Rm ,若 ( x ? , y ? ) ∈ A × B (x^*,y^*)\in A\times B (x?,y?)∈A×B 满足(18),则称之为 f f f 的一个鞍点.


图 3.1：鞍点示意图

命题 3.2 (强对偶性的鞍点刻画) 给定函数 f : A × B → R ￣ f:A\times B\to\overline{\mathbb{R}} f:A×B→R,其中 A ? R n , ? B ? R m A\subset\mathbb{R}^n,~B\subset\mathbb{R}^m A?Rn,?B?Rm, ( x ? , y ? ) ∈ A × B (x^*,y^*)\in A\times B (x?,y?)∈A×B 是 f f f 的一个鞍点，即满足(18), 当且仅当 sup ? y ∈ B f ( x ? , y ) = ξ ? = η ? = inf ? x ∈ A f ( x , y ? ) . \begin{align} \sup\limits_{y\in B}f(x^*,y)=\xi^*=\eta^*=\inf\limits_{x\in A}f(x,y^*).\end{align} y∈Bsup?f(x?,y)=ξ?=η?=x∈Ainf?f(x,y?).??此外，当 ( x ? , y ? ) (x^*,y^*) (x?,y?) 是 f f f的鞍点时，有 f ( x ? , y ? ) = ξ ? . f( x^* , y^* ) = \xi^* . f(x?,y?)=ξ?.

证.充分性如上已证，下证必要性.

设 ( x ? , y ? ) (x^*,y^*) (x?,y?) 是 f f f 的一个鞍点，则(18)式成立，即 f ( x ? , y ) ≤ f ( x ? , y ? ) ≤ f ( x , y ? ) , ? x ∈ A , ? y ∈ B f(x^*,y)\leq f(x^*,y^*)\leq f(x,y^*),\quad\forall x\in A,\:y\in B f(x?,y)≤f(x?,y?)≤f(x,y?),?x∈A,y∈B，这个式子的第一个不等式对 y ∈ B y \in B y∈B 求上确界，第而个不等式对 x ∈ A x \in A x∈A 求下确界，可以得到 sup ? y ∈ B f ( x ? , y ) ≤ f ( x ? , y ? ) ≤ inf ? x ∈ A f ( x , y ? ) . \begin{align}\sup_{y\in B}f(x^*,y)\leq f(x^*,y^*)\leq\inf_{x\in A}f(x,y^*).\end{align} y∈Bsup?f(x?,y)≤f(x?,y?)≤x∈Ainf?f(x,y?).??从而有 ξ ? = inf ? x ∈ A sup ? y ∈ B f ( x , y ) ≤ sup ? y ∈ B f ( x ? , y ) ≤ f ( x ? , y ? ) ≤ inf ? x ∈ A f ( x , y ? ) ≤ sup ? y ∈ B inf ? x ∈ A f ( x , y ) = η ? . \begin{aligned}\xi^*&=\inf_{x\in A}\sup_{y\in B}f(x,y)\le\sup_{y\in B}f(x^*,y)\le f(x^*,y^*)\le\inf_{x\in A}f(x,y^*)\le\sup_{y\in B}\inf_{x\in A}f(x,y)=\eta^*.\end{aligned} ξ??=x∈Ainf?y∈Bsup?f(x,y)≤y∈Bsup?f(x?,y)≤f(x?,y?)≤x∈Ainf?f(x,y?)≤y∈Bsup?x∈Ainf?f(x,y)=η?.?

如果我们将鞍点的定义用到优化问题(1)的拉格朗日函数中去，会发生什么呢？设 g ( λ , μ ) g(\lambda,\mu) g(λ,μ)是优化问题(1)的对偶函数，而 ξ ? \xi^* ξ? 和 η ? \eta^* η? 分别是优化问题(1)及其对偶问题的最优解，我们称解 ( x ? , λ ? , μ ? ) (x^*,\lambda^*,\mu^*) (x?,λ?,μ?)为拉格朗日函数 L ( x , λ , μ ) L(x,\lambda,\mu) L(x,λ,μ)的鞍点，如果满足条件： L ( x ? , λ , μ ) ≤ L ( x ? , λ ? , μ ? ) ≤ L ( x , λ ? , μ ? ) , ? x ∈ Ω , ( λ , μ ) ∈ R + p × R q . L(x^*,\lambda,\mu)\leq L(x^*,\lambda^*,\mu^*)\leq L(x,\lambda^*,\mu^*),\quad\forall x\in\Omega,(\lambda,\mu)\in\mathbb{R}_+^p\times\mathbb{R}^q. L(x?,λ,μ)≤L(x?,λ?,μ?)≤L(x,λ?,μ?),?x∈Ω,(λ,μ)∈R+p?×Rq.于是，这就可以说明鞍点是可以用来刻画优化问题(1)及其对偶问题(6)的解以及强对偶性.

文章来源:https://blog.csdn.net/weixin_47255403/article/details/135067432
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。