冯诺依曼(Von Neumann)迹不等式证明

这篇具有很好参考价值的文章主要介绍了冯诺依曼(Von Neumann)迹不等式证明。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

冯诺依曼迹不等式的定义

假设 A ∈ S + + n \mathbf{A} \in {\mathbb{S}_{++}^n} AS++n B ∈ S + + n \mathbf{B} \in {\mathbb{S}_{++}^n} BS++n,其特征值分别为:
λ 1 ( A ) ≥ λ 2 ( A ) ≥ ⋯ ≥ λ n ( A ) > 0 , λ 1 ( B ) ≥ λ 2 ( B ) ≥ ⋯ ≥ λ n ( B ) > 0 \lambda_1(\mathbf{A}) \geq \lambda_2(\mathbf{A}) \geq \cdots \geq \lambda_n(\mathbf{A}) >0,\lambda_1(\mathbf{B}) \geq \lambda_2(\mathbf{B}) \geq \cdots \geq \lambda_n(\mathbf{B})>0 λ1(A)λ2(A)λn(A)>0,λ1(B)λ2(B)λn(B)>0
有如不等式成立:
∑ i = 1 n λ i ( A ) λ n − i + 1 ( B ) ≤ t r ( A B ) = ∑ i = 1 n λ i ( A B ) ≤ ∑ i = 1 n λ i ( A ) λ i ( B ) \sum_{i=1}^n \lambda_i(\mathbf{A})\lambda_{n-i+1}(\mathbf{B})\leq\mathrm{tr}(\mathbf{AB})=\sum_{i=1}^n \lambda_i(\mathbf{A B})\leq \sum_{i=1}^n \lambda_i(\mathbf{A})\lambda_{i}(\mathbf{B}) i=1nλi(A)λni+1(B)tr(AB)=i=1nλi(AB)i=1nλi(A)λi(B)
该不等式称为:冯诺依曼不等式

本文主要证明冯诺依曼迹不等式的左边部分,右边不等式较为容易理解。

冯诺依曼迹不等式的证明

柯西中值定理

在证明之前需要引入一个重要的柯西中值定理(Cauchy Interlacing Theorem):

λ i + 1 ( C ) ≤ λ i ( C ~ ) ≤ λ i ( C ) \lambda_{i+1}(\mathbf{C}) \leq \lambda_i(\widetilde{\mathbf{C}}) \leq \lambda_i(\mathbf{C}) λi+1(C)λi(C )λi(C)
其中 C ~ ∈ S + + n − 1 \widetilde{\mathbf{C}} \in {\mathbb{S}_{++}^{n-1}} C S++n1 C ∈ S + + n \mathbf{C} \in {\mathbb{S}_{++}^n} CS++n n − 1 n-1 n1维度的主子矩阵(Principal submatrix)。

证:
存在一个正交矩阵 P ∈ R ( n ) × ( n − 1 ) \mathbf{P} \in \mathbb{R}^{(n) \times(n-1)} PR(n)×(n1)使得 P T C P = C ~ \mathbf{P}^{\mathrm{T}} \mathbf{C P}=\widetilde{\mathbf{C}} PTCP=C ,对于 i ≤ n − 1 i\leq n-1 in1基于Courant-Fischer theorem,有:
λ i ( C ~ ) = max ⁡ S i ⊆ R n − 1 min ⁡ x ∈ S i , ∥ x ∥ 2 = 1 x T C ~ x = max ⁡ S i ⊆ R n − 1 min ⁡ x ∈ S i , ∥ x ∥ 2 = 1 ( P x ) T C ( P x ) ≤ max ⁡ P i ∈ R n min ⁡ y ∈ P i , ∥ y ∥ 2 = 1 y T C y = λ i ( C ) \lambda_i(\widetilde{\mathbf{C}})=\max _{\mathcal{S}_i \subseteq \mathbb{R}^{n-1}} \min _{\mathbf{x} \in \mathcal{S}_i,\|\mathbf{x}\|_2=1} \mathbf{x}^{\mathrm{T}} \widetilde{\mathbf{C}} \mathbf{x}=\max _{\mathcal{S}_i \subseteq \mathbb{R}^{n-1}} \min _{\mathbf{x} \in \mathcal{S}_i,\|\mathbf{x}\|_2=1}(\mathbf{P x})^{\mathrm{T}} \mathbf{C}(\mathbf{P x})\leq \max _{\mathcal{P}_i \in \mathbb{R}^n} \min _{\mathbf{y} \in \mathcal{P}_i,\|\boldsymbol{y}\|_2=1} \mathbf{y}^{\mathrm{T}} \mathbf{C y}=\lambda_i(\mathbf{C}) λi(C )=SiRn1maxxSi,x2=1minxTC x=SiRn1maxxSi,x2=1min(Px)TC(Px)PiRnmaxyPi,y2=1minyTCy=λi(C)

同时有:
λ i ( C ~ ) = min ⁡ S n − i ∈ R n − 1 max ⁡ x ∈ S n − i , ∥ x ∥ 2 = 1 x T C ~ x = min ⁡ S n − i ⊆ R n − 1 max ⁡ x ∈ S n − i , ∥ x ∥ 2 = 1 ( P x ) T C ( P x ) ≥ min ⁡ P n − i ∈ R n max ⁡ y ∈ P n − i , ∥ y ∥ 2 = 1 y T C y = λ i + 1 ( C ) \lambda_i(\widetilde{\mathbf{C}})=\min _{\mathcal{S}_{n-i} \in \mathbb{R}^{n-1}} \max _{\mathbf{x} \in \mathcal{S}_{n-i},\|\mathbf{x}\|_2=1} \mathbf{x}^{\mathrm{T}} \widetilde{\mathbf{C}} \mathbf{x}=\min _{\mathcal{S}_{n-i} \subseteq \mathbb{R}^{n-1}} \max _{\mathbf{x} \in \mathcal{S}_{n-i},\|\mathbf{x}\|_2=1}(\mathbf{P x})^{\mathrm{T}} \mathbf{C}(\mathbf{P x})\geq\min _{\mathcal{P}_{n-i} \in \mathbb{R}^n} \max _{\mathbf{y} \in \mathcal{P}_{n-i},\|y\|_2=1} \mathbf{y}^{\mathrm{T}} \mathbf{C y}=\lambda_{i+1}(\mathbf{C}) λi(C )=SniRn1minxSni,x2=1maxxTC x=SniRn1minxSni,x2=1max(Px)TC(Px)PniRnminyPni,y2=1maxyTCy=λi+1(C)

综上:
λ i + 1 ( C ) ≤ λ i ( C ~ ) ≤ λ i ( C ) \lambda_{i+1}(\mathbf{C}) \leq \lambda_i(\widetilde{\mathbf{C}}) \leq \lambda_i(\mathbf{C}) λi+1(C)λi(C )λi(C)
证毕

数学归纳法

基于上面的柯西中值定理,然后利用数学归纳法证明:

∑ i = 1 n − 1 ( λ i ( Λ A ) − λ n ( Λ A ) ) C i , i ≥ ∑ i = 1 n − 1 ( λ i ( Λ A ) − λ n ( Λ A ) ) λ n − i ( C ~ ) \sum_{i=1}^{n-1}( \lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_n(\boldsymbol{\Lambda}_{\mathbf{A}}))\mathbf{C}_{i, i}\geq\sum_{i=1}^{n-1}(\lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_n(\boldsymbol{\Lambda}_{\mathbf{A}})) \lambda_{n-i}(\widetilde{\mathbf{C}}) i=1n1(λi(ΛA)λn(ΛA))Ci,ii=1n1(λi(ΛA)λn(ΛA))λni(C )

证明:

定义对角矩阵 Λ A ′ ∈ S + + k + 1 \boldsymbol{\Lambda}^{'}_{\mathbf{A}} \in {\mathbb{S}_{++}^{k+1}} ΛAS++k+1 C ′ ∈ S + + k + 1 \mathbf{C}^{'} \in {\mathbb{S}_{++}^{k+1}} CS++k+1,其中对角阵 Λ A ∈ S + + k \boldsymbol{\Lambda}_{\mathbf{A}}\in \mathbb{S}_{++}^{k} ΛAS++k C ∈ S + + k \mathbf{C}\in \mathbb{S}_{++}^{k} CS++k分别是 Λ A ′ \boldsymbol{\Lambda}^{'}_{\mathbf{A}} ΛA C ′ \mathbf{C}^{'} C k k k维主子矩阵,因此对于任意的 1 ≤ i ≤ k 1 \leq i \leq k 1ik,有 λ i ( Λ A ′ ) = λ i ( Λ A ) \lambda_i(\boldsymbol{\Lambda}^{'}_{\mathbf{A}})=\lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}}) λi(ΛA)=λi(ΛA) C i , i ′ = C i , i \mathbf{C}_{i, i}^{\prime}=\mathbf{C}_{i, i} Ci,i=Ci,i成立。

n = 2 n=2 n=2时,显然成立。

假定当 n = k n=k n=k时成立,有:
∑ i = 1 k − 1 ( λ i ( Λ A ) − λ k ( Λ A ) ) C i , i ≥ ∑ i = 1 k − 1 ( λ i ( Λ A ) − λ k ( Λ A ) ) λ k − i ( C ~ ) \sum_{i=1}^{k-1}\left(\lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_k(\boldsymbol{\Lambda}_{\mathbf{A}})\right) \mathbf{C}_{i, i} \geq \sum_{i=1}^{k-1}\left(\lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_k(\boldsymbol{\Lambda}_{\mathbf{A}})\right) \lambda_{k-i}(\widetilde{\mathbf{C}}) i=1k1(λi(ΛA)λk(ΛA))Ci,ii=1k1(λi(ΛA)λk(ΛA))λki(C )
则当 n = k + 1 n=k+1 n=k+1时有:
∑ i = 1 k ( λ i ( Λ A ′ ) − λ k + 1 ( Λ A ′ ) ) C i , i ′ = ∑ i = 1 k ( λ i ( Λ A ′ ) − λ k ( Λ A ′ ) + λ k ( Λ A ′ ) − λ k + 1 ( A ′ ) ) C i , i ′ = ∑ i = 1 k − 1 ( λ i ( Λ A ′ ) − λ k ( Λ A ′ ) ) C i , i ′ + ( λ k ( Λ A ′ ) − λ k + 1 ( Λ A ′ ) ) ∑ i = 1 k C i , i ′ = ∑ i = 1 k − 1 ( λ i ( Λ A ) − λ k ( Λ A ) ) C i , i + ( λ k ( Λ A ) − λ k + 1 ( Λ A ′ ) ) ∑ i = 1 k C i , i ′ ≥ ∑ i = 1 k − 1 ( λ i ( Λ A ) − λ k ( Λ A ) ) λ k − i ( C ~ ) + ( λ k ( Λ A ) − λ k + 1 ( Λ A ′ ) ) ∑ i = 1 k C i , i ′ ≥ ∑ i = 1 k − 1 ( λ i ( Λ A ′ ) − λ k ( Λ A ′ ) ) λ k − i + 1 ( C ) + ( λ k ( Λ A ′ ) − λ k + 1 ( Λ A ′ ) ) ∑ i = 1 k λ k − i + 1 ( C ) = ∑ i = 1 k ( λ i ( Λ A ′ ) − λ k + 1 ( Λ A ′ ) ) λ k − i + 1 ( C ) \begin{aligned} & \sum_{i=1}^k(\lambda_i(\boldsymbol{\Lambda}^{'}_{\mathbf{A}})-\lambda_{k+1}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )) \mathbf{C}_{i, i}^{\prime} \\ =& \sum_{i=1}^k(\lambda_i(\boldsymbol{\Lambda}^{'}_{\mathbf{A}})-\lambda_{k}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )+\lambda_{k}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )-\lambda_{k+1}(\mathbf{A}^{\prime})) \mathbf{C}_{i, i}^{\prime} \\ =& \sum_{i=1}^{k-1}(\lambda_i(\boldsymbol{\Lambda}^{'}_{\mathbf{A}})-\lambda_{k}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )) \mathbf{C}_{i, i}^{\prime}+(\lambda_k(\boldsymbol{\Lambda}^{'}_{\mathbf{A}})-\lambda_{k+1}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )) \sum_{i=1}^k \mathbf{C}_{i, i}^{\prime}\\=& \sum_{i=1}^{k-1}(\lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_{k}(\boldsymbol{\Lambda}_{\mathbf{A}} )) \mathbf{C}_{i, i}+(\lambda_k(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_{k+1}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )) \sum_{i=1}^k \mathbf{C}_{i, i}^{\prime}\\\geq&\sum_{i=1}^{k-1}(\lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_k(\boldsymbol{\Lambda}_{\mathbf{A}})) \lambda_{k-i}(\widetilde{\mathbf{C}})+(\lambda_k(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_{k+1}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )) \sum_{i=1}^k \mathbf{C}_{i, i}^{\prime}\\\geq&\sum_{i=1}^{k-1}(\lambda_i(\boldsymbol{\Lambda}^{'}_{\mathbf{A}})-\lambda_{k}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )) \lambda_{k-i+1}({\mathbf{C}})+(\lambda_k(\boldsymbol{\Lambda}_{\mathbf{A}}^{\prime})-\lambda_{k+1}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )) \sum_{i=1}^k \lambda_{k-i+1}(\mathbf{C})\\=&\sum_{i=1}^{k}(\lambda_i(\boldsymbol{\Lambda}^{'}_{\mathbf{A}})-\lambda_{k+1}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )) \lambda_{k-i+1}({\mathbf{C}}) \end{aligned} ====i=1k(λi(ΛA)λk+1(ΛA))Ci,ii=1k(λi(ΛA)λk(ΛA)+λk(ΛA)λk+1(A))Ci,ii=1k1(λi(ΛA)λk(ΛA))Ci,i+(λk(ΛA)λk+1(ΛA))i=1kCi,ii=1k1(λi(ΛA)λk(ΛA))Ci,i+(λk(ΛA)λk+1(ΛA))i=1kCi,ii=1k1(λi(ΛA)λk(ΛA))λki(C )+(λk(ΛA)λk+1(ΛA))i=1kCi,ii=1k1(λi(ΛA)λk(ΛA))λki+1(C)+(λk(ΛA)λk+1(ΛA))i=1kλki+1(C)i=1k(λi(ΛA)λk+1(ΛA))λki+1(C)

  • :第一个不等式利用了 n = k n=k n=k时成立的不等式,第二个不等式利用了前面的柯西中值定理。
    即:
    ∑ i = 1 k ( λ i ( Λ A ′ ) − λ k + 1 ( Λ A ′ ) ) C i , i ′ ≥ ∑ i = 1 k ( λ i ( Λ A ′ ) − λ k + 1 ( Λ A ′ ) ) λ k − i + 1 ( C ) \sum_{i=1}^k(\lambda_i(\boldsymbol{\Lambda}^{'}_{\mathbf{A}})-\lambda_{k+1}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )) \mathbf{C}_{i, i}^{\prime}\geq\sum_{i=1}^{k}(\lambda_i(\boldsymbol{\Lambda}^{'}_{\mathbf{A}})-\lambda_{k+1}(\boldsymbol{\Lambda}^{'}_{\mathbf{A}} )) \lambda_{k-i+1}({\mathbf{C}}) i=1k(λi(ΛA)λk+1(ΛA))Ci,ii=1k(λi(ΛA)λk+1(ΛA))λki+1(C)

证毕。

冯诺依曼迹不等式的证明

A \mathbf{A} A A \mathbf{A} A做特征值分解分别有: A = U Λ A U T \mathbf{A}=\mathbf{U} \boldsymbol{\Lambda}_{\mathbf{A}} \mathbf{U}^{\mathrm{T}} A=UΛAUT B = V Λ B V T \mathbf{B}=\mathbf{V} \boldsymbol{\Lambda}_{\mathbf{B}} \mathbf{V}^{\mathrm{T}} B=VΛBVT,则:
tr ⁡ ( A B ) = tr ⁡ ( U Λ A U T V Λ B V T ) = tr ⁡ ( Λ A U T V ⏟ Q Λ B V T U ⏟ Q T ) = tr ⁡ ( Λ A Q Λ B Q T ⏟ C ) = tr ⁡ ( Λ A C ) = ∑ i = 1 n λ i ( Λ A ) C i , i = ∑ i = 1 n λ i ( A ) C i , i \operatorname{tr}(\mathbf{A B})=\operatorname{tr}\left(\mathbf{U} \boldsymbol{\Lambda}_{\mathbf{A}} \mathbf{U}^{\mathrm{T}} \mathbf{V} \boldsymbol{\Lambda}_{\mathbf{B}} \mathbf{V}^{\mathrm{T}}\right)=\operatorname{tr}(\boldsymbol{\Lambda}_{\mathbf{A}} \underbrace{\mathbf{U}^{\mathrm{T}} \mathbf{V}}_{\mathbf{Q}} \boldsymbol{\Lambda}_{\mathbf{B}} \underbrace{\mathbf{V}^{\mathrm{T}} \mathbf{U}}_{\mathbf{Q}^{\mathrm{T}}})=\operatorname{tr}(\underbrace{\boldsymbol{\Lambda}_{\mathrm{A}} \mathbf{Q} \boldsymbol{\Lambda}_{\mathbf{B}} \mathbf{Q}^{\mathrm{T}}}_{\mathrm{C}})=\operatorname{tr}\left(\boldsymbol{\Lambda}_{\mathbf{A}} \mathbf{C}\right)=\sum_{i=1}^n \lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}}) \mathbf{C}_{i, i}=\sum_{i=1}^n \lambda_i(\mathbf{A}) \mathbf{C}_{i, i} tr(AB)=tr(UΛAUTVΛBVT)=tr(ΛAQ UTVΛBQT VTU)=tr(C ΛAQΛBQT)=tr(ΛAC)=i=1nλi(ΛA)Ci,i=i=1nλi(A)Ci,i

不难发现, Λ A \boldsymbol{\Lambda}_{\mathbf{A}} ΛA A \mathbf{A} A有相同的特征值, C \mathbf{C} C B \mathbf{B} B有相同的特征值。

∑ i = 1 n λ i ( Λ A ) C i , i = ∑ i = 1 n − 1 λ i ( Λ A ) C i , i + λ n ( Λ A ) ( ∑ i = 1 n C i , i − ∑ i = 1 n − 1 C i , i ) = ∑ i = 1 n − 1 ( λ i ( Λ A ) − λ n ( Λ A ) ) C i , i + λ n ( Λ A ) ∑ i = 1 n C i , i ≥ ∑ i = 1 n − 1 ( λ i ( Λ A ) − λ n ( Λ A ) ) λ n − i ( C ~ ) + λ n ( Λ A ) ∑ i = 1 n C i , i ≥ ∑ i = 1 n − 1 ( λ i ( Λ A ) − λ n ( Λ A ) ) λ n − i + 1 ( C ) + λ n ( Λ A ) ∑ i = 1 n λ n − i + 1 ( C ) = ∑ i = 1 n λ i ( Λ A ) λ n − i + 1 ( C ) = ∑ i = 1 n λ i ( A ) λ n − i + 1 ( B ) \begin{aligned} \sum_{i=1}^n \lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}}) \mathbf{C}_{i, i}&=\sum_{i=1}^{n-1}\lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}}) \mathbf{C}_{i, i}+\lambda_n(\boldsymbol{\Lambda}_{\mathbf{A}}) (\sum_{i=1}^n\mathbf{C}_{i, i}-\sum_{i=1}^{n-1}\mathbf{C}_{i, i})\\&=\sum_{i=1}^{n-1}( \lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_n(\boldsymbol{\Lambda}_{\mathbf{A}}))\mathbf{C}_{i, i}+\lambda_n(\boldsymbol{\Lambda}_{\mathbf{A}})\sum_{i=1}^n\mathbf{C}_{i, i}\\&\geq \sum_{i=1}^{n-1}(\lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_n(\boldsymbol{\Lambda}_{\mathbf{A}})) \lambda_{n-i}(\widetilde{\mathbf{C}})+\lambda_n(\boldsymbol{\Lambda}_{\mathbf{A}})\sum_{i=1}^n\mathbf{C}_{i, i}\\&\geq\sum_{i=1}^{n-1}(\lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}})-\lambda_n(\boldsymbol{\Lambda}_{\mathbf{A}})) \lambda_{n-i+1}({\mathbf{C}})+\lambda_n(\boldsymbol{\Lambda}_{\mathbf{A}})\sum_{i=1}^n\lambda_{n-i+1}(\mathbf{C})\\&=\sum_{i=1}^{n}\lambda_i(\boldsymbol{\Lambda}_{\mathbf{A}}) \lambda_{n-i+1}({\mathbf{C}})=\sum_{i=1}^n \lambda_i(\mathbf{A})\lambda_{n-i+1}(\mathbf{B}) \end{aligned} i=1nλi(ΛA)Ci,i=i=1n1λi(ΛA)Ci,i+λn(ΛA)(i=1nCi,ii=1n1Ci,i)=i=1n1(λi(ΛA)λn(ΛA))Ci,i+λn(ΛA)i=1nCi,ii=1n1(λi(ΛA)λn(ΛA))λni(C )+λn(ΛA)i=1nCi,ii=1n1(λi(ΛA)λn(ΛA))λni+1(C)+λn(ΛA)i=1nλni+1(C)=i=1nλi(ΛA)λni+1(C)=i=1nλi(A)λni+1(B)

即: tr ⁡ ( A B ) ≥ ∑ i = 1 n λ i ( A ) λ n − i + 1 ( B ) \operatorname{tr}(\mathbf{A B})\geq\sum_{i=1}^n \lambda_i(\mathbf{A})\lambda_{n-i+1}(\mathbf{B}) tr(AB)i=1nλi(A)λni+1(B)文章来源地址https://www.toymoban.com/news/detail-628155.html

  • :第一个不等式利用了数学归纳法证明的不等式,第二个不等式利用了前面的柯西中值定理。

到了这里,关于冯诺依曼(Von Neumann)迹不等式证明的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 马尔可夫不等式、切比雪夫不等式

    在概率论中,马尔可夫不等式给出了随机变量的非负函数大于或等于某个正常数 ϵ epsilon ϵ 的概率的上限 下图来自:Markov inequality 下图为任一分布的概率密度函数图像 图片来自:Mathematical Foundations of Computer Networking: Probability a a a 越大,阴影部分的面积越小,即概率越小 使

    2024年02月04日
    浏览(35)
  • 优化问题----等式约束与不等式约束问题求解

    目录 先总结一波: 1. 等式约束问题求解 (1)一阶必要条件 (2)二阶充分条件 2.不等式约束问题求解 2.1 可行下降方向 2.2 KTT条件(Kuhn-Tucker条件) (1)Gordan定理 (2)Fritz John定理 (3)KTT条件  (4)KTT的一个应用实例 对于无约束极值问题,可以采用解析方法和直接方法两

    2024年02月05日
    浏览(51)
  • Hoeffing不等式

    设 X 1 , X 2 , . . . , X N X_1,X_2,...,X_N X 1 ​ , X 2 ​ , ... , X N ​ 是独立随机变量,且 X i ∈ [ a i , b i ] , i = 1 , 2 , . . . , N ; S N = ∑ i = 1 N X i X_iin[a_i,b_i],i=1,2,...,N;S_N=sum_{i=1}^NX_i X i ​ ∈ [ a i ​ , b i ​ ] , i = 1 , 2 , ... , N ; S N ​ = ∑ i = 1 N ​ X i ​ ,则对任意t0,以下不等式成立:

    2024年02月07日
    浏览(42)
  • 放缩不等式推导

    放缩不等式推导 1 )   a x x + 1 ( 1 a ≤ e , x 0 ; a ≥ e , x 0 ) ; 1) a^xx+1left(1aleq e,x0;ageq e,x0right); 1 )   a x x + 1 ( 1 a ≤ e , x 0 ; a ≥ e , x 0 ) ; p r o o f : proof: p roo f : f 01 ( x ) = a x − ( x + 1 ) ⇒ f 01 ′ ( x ) = a x ln ⁡ a − 1 f_{01}left(xright)=a^{x}-left(x+1right)Rightarrow f_{01}^{\\\'}left(xright) =

    2023年04月22日
    浏览(45)
  • 切比雪夫(Chebyshev)不等式

    设随机变量x具有数学期望 E ( x ) = μ E(x) = mu E ( x ) = μ ,方差 D ( x ) = σ 2 D(x) = sigma^{2} D ( x ) = σ 2 。记 X ∗ = X − μ σ X^{* } =frac{X-mu }{sigma } X ∗ = σ X − μ ​ , 则X*的期望和方差为: E ( X ∗ ) = 1 σ E ( X − μ ) = 1 σ [ E ( X ) − μ ] = 0 E(X^{*})= frac{1}{sigma} E(X-mu)=frac{1}{sigma

    2024年01月16日
    浏览(46)
  • 四边形不等式学习笔记

    四边形不等式是一种 dp 优化策略。多用于 2D DP。 对于区间 ([l,r]) 带来的贡献 (w(l,r)) ,如果其满足: 对于 (Lleq lleq r leq R) , (w(L,r)+w(l,R)leq w(L,R)+w(l,r)) 则称 (w) 满足 四边形不等式 。特别地,如果上式符号取等,则称其满足 四边形恒等式 。 注:上面的不等式可以记

    2023年04月10日
    浏览(48)
  • 冶炼金属【暴力枚举 + 二分 + 二元不等式】

    😊😊 😊😊 不求点赞,只求耐心看完,指出您的疑惑和写的不好的地方,谢谢您。本人会及时更正感谢。希望看完后能帮助您理解算法的本质 😊😊 😊😊 小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V V V , V V V 是

    2024年02月02日
    浏览(40)
  • 线性矩阵不等式(LMI)(一):简单介绍

    主要从以下三个方面介绍: 什么是线性矩阵不等式(LMI) 为什么要用线性矩阵不等式(LMI) 线性矩阵不等式的发展(控制系统中) 1. 线性矩阵不等式 如名字所示线性矩阵不等式三要素为: 线性 - 注意双线性时,LMI不好求解(非凸问题);例:在不等式中出现 P A K PAK P A K 形式,其

    2024年01月20日
    浏览(44)
  • 切比雪夫不等式,大数定律及极限定理。

    1.定理 若随机变量X的期望EX和方差DX存在,则对任意ε 0,有    P{ |X - EX| = ε } = DX/ε 2 或 P{ |X - EX| ε } = 1 - DX/ε 2 2.解析定理 ①该定理对 X 服从什么分布不做要求,仅EX DX存在即可。 ②“| |” 由于X某次试验结果可能大于期望值,也可能小于期望值,但总在其旁边波动,所 以加

    2024年02月06日
    浏览(63)
  • 不等式约束二次规划——有效集法

    这个其实很好理解,通过以下两张图片就可以很清晰的明白这句画的意思: 黑色箭头是约束的区域,蓝色五角星是是全局最优点。对于左边的图,最优点在不等式范围之内,但是这个最优点有没有这个约束都可以求出来,所以这个约束可以看成无效的约束,也就是加不加这个

    2024年02月04日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包