上海中高端网站建设,.我爱你 域名网站,网站导航条用什么做,淄博手机网站目录 1 从 Lagrange 函数引入对偶问题2. 强对偶性与 KKT 条件3. 对偶性的鞍点特征 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… 目录 1 从 Lagrange 函数引入对偶问题2. 强对偶性与 KKT 条件3. 对偶性的鞍点特征 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 i1,\cdots,p,\\h_j(x)0,\quad j1,\cdots,q,\\x\in\Omega,\end{cases}\end{align} ⎩ ⎨ ⎧minf0(x)s.tfi(x)≤0,i1,⋯,p,hj(x)0,j1,⋯,q,x∈Ω,其中 { f i } i 0 p , { h j } j 1 q \{f_i\}_{i0}^p,\:\{h_j\}_{j1}^q {fi}i0p,{hj}j1q 均为定义在 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,~i1,\cdots,p;~h_j(x)0,j1,\cdots,q\} D:{x∈Ω∣fi(x)≤0, i1,⋯,p; hj(x)0,j1,⋯,q}满足如下条件该条件是为了后面定义的拉格朗日函数 { − ∞ f i ( x ) ≤ ∞ i 0 , 1 , ⋯ , p , − ∞ h j ( x ) ∞ j 1 , ⋯ , q , ∀ x ∈ Ω . \begin{align}\begin{cases}-\inftyf_i(x)\leq\inftyi0,1,\cdots,p,\\-\inftyh_j(x)\inftyj1,\cdots,q,\end{cases}\quad\forall x\in\Omega.\end{align} {−∞fi(x)≤∞−∞hj(x)∞i0,1,⋯,p,j1,⋯,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_{i1}^p\lambda_if_i(x)\sum_{j1}^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)i1∑pλifi(x)j1∑qμjhj(x),(x,λ,μ)∈Ω×Rp×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\}_{i1}^p {λi}i1p 和 { μ j } j 1 q \{\mu_j\}_{j1}^q {μj}j1q 充当了惩罚项的作用对任意给定的 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},\\\inftyx\in\Omega\setminus\mathcal{D},\end{cases} \end{align} λ⪰0,μsupL(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∈Dinff0(x)x∈Ωinfλ⪰0,μsupL(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,μsupx∈ΩinfL(x,λ,μ)≤x∈Ωinfλ⪰0,μsupL(x,λ,μ).记 η ∗ : sup λ ⪰ 0 , μ g ( λ , μ ) , \begin{aligned}\eta^*:\sup_{\lambda\succeq0,\mu}g(\lambda,\mu),\end{aligned} η∗:λ⪰0,μsupg(λ,μ),其中 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∈ΩinfL(x,λ,μ),(λ,μ)∈Rp×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,μsupg(λ,μ)≤x∈Dinff0(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 Rp×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 Rp×Rq 上凹函数.这是因为有命题凸函数是仿射函数的逐点上确界
设 ( λ k , μ k ) ∈ R p × R q (\lambda_k,\mu_k)\in\mathbb{R}_^p\times\mathbb{R}^q (λk,μk)∈Rp×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)∈Rp×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→∞limg(λ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→∞limg(λk,μk)≤g(λ0,μ0).所以 g g g是上半连续的.
注当 − ∞ f i ( x ) , h j ( x ) ∞ , ∀ x ∈ Ω , i 1 , . . . , p ; j 1 , . . . , q \begin{align} -\inftyf_i(x),h_j(x)\infty,\quad\forall x\in\Omega,\quad i1,...,p;\quad j1,...,q\end{align} −∞fi(x),hj(x)∞,∀x∈Ω,i1,...,p;j1,...,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∈ΩinfL(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×Rp×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 i1,\cdots,p;\quad L(x^*,\lambda^*,\mu^*)\inf_{x\in\Omega}L(x,\lambda^*,\mu^*).\end{align} λi∗fi(x∗)0,i1,⋯,p;L(x∗,λ∗,μ∗)x∈ΩinfL(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-\inftyh_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∈Dinff0(x)ξ∗≤f0(x∗)L(x∗,λ∗,μ∗)x∈ΩinfL(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∈ΩinfL(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 i1,\cdots,p^* λi∗fi(x∗)0,i1,⋯,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 i1,\cdots,p;\\\lambda_i^*f_i(x^*)0,\quad i1,\cdots,p;\\L(x^*,\lambda^*,\mu^*)\inf_{x\in\Omega}L(x,\lambda^*,\mu^*).\end{cases}\end{align} ⎩ ⎨ ⎧x∗∈D,λi∗≥0,i1,⋯,p;λi∗fi(x∗)0,i1,⋯,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×Rp×Rq 且(8)成立. 显然 x ∗ ∈ D x^*\in\mathcal{D} x∗∈D 即为 (11)的第一式成立 λ ∗ ∈ R p \lambda^*\in\mathbb{R}_^p λ∗∈Rp 蕴含(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 i1,\cdots,p;\quad L(x^*,\lambda^*,\mu^*)\inf_{x\in\Omega}L(x,\lambda^*,\mu^*). λi∗fi(x∗)0,i1,⋯,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×Rp×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\}_{i0}^p {fi}i0p 和 { h j } j 1 q \{h_j\}_{j1}^q {hj}j1q 均在 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∈ΩinfL(x,λ∗,μ∗)蕴含 ∇ x L ( x ∗ , λ ∗ , μ ∗ ) ⊥ V Ω . \begin{align}\nabla_xL(x^*,\lambda^*,\mu^*)\perp V_\Omega.\end{align} ∇xL(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. ∇xL(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; (λ∗,μ∗)∈Rp×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 i1,\cdots,p.\end{align} x∗∈D,λi∗fi(x∗)0,i1,⋯,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∈ΩargminL(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,μ∈Rqsupx∈ΩinfL(x,λ,μ)x∈Ωinfλ⪰0,μ∈RqsupL(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∈Bsupx∈Ainff(x,y)x∈Ainfy∈Bsupf(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∈Ainfy∈Bsupf(x,y),η∗y∈Bsupx∈Ainff(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∈Af(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∈Bsupx∈Ainff(x,y)≤y∈Bsupf(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∈Ainff(x,y∗)y∈Bsupx∈Ainff(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∈Bsupf(x∗,y)x∈Ainfy∈Bsupf(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∈Bsupf(x∗,y)ξ∗η∗x∈Ainff(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∈Bsupf(x∗,y)ξ∗η∗x∈Ainff(x,y∗)≤f(x,y∗),∀x∈A,y∈B.上式中取 x x ∗ , y y ∗ xx^*,\:yy^* xx∗,yy∗, 可以得到 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∈Bsupf(x∗,y)ξ∗η∗x∈Ainff(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∈Bsupf(x∗,y)≤f(x∗,y∗)≤x∈Ainff(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∈Ainfy∈Bsupf(x,y)≤y∈Bsupf(x∗,y)≤f(x∗,y∗)≤x∈Ainff(x,y∗)≤y∈Bsupx∈Ainff(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∈Ω,(λ,μ)∈Rp×Rq.于是这就可以说明鞍点是可以用来刻画优化问题(1)及其对偶问题(6)的解以及强对偶性.
