青州做网站的公司,网站的大图标怎么做的,wps上怎么做网站点击分析表,北京的网络公司有哪些目录 3. 约束优化问题的全局解3.1 凸优化问题3.2 二次优化问题3.3 无约束二次优化问题3.4 一个典型的二次等式约束二次优化问题 Reference 3. 约束优化问题的全局解
3.1 凸优化问题
局部解成为全局解的一类重要的优化问题是所谓凸优化问题. 我们称优化问题 ( f , D ) (f,\ma… 目录 3. 约束优化问题的全局解3.1 凸优化问题3.2 二次优化问题3.3 无约束二次优化问题3.4 一个典型的二次等式约束二次优化问题 Reference 3. 约束优化问题的全局解
3.1 凸优化问题
局部解成为全局解的一类重要的优化问题是所谓凸优化问题. 我们称优化问题 ( f , D ) (f,\mathcal{D}) (f,D) 是凸的/拟凸的是指 f : D → R ‾ f:\mathcal{D}\to\overline{\mathbb{R}} f:D→R 是凸函数/拟凸函数. 称优化问题 { min f 0 ( x ) s.t. f i ( x ) ≤ 0 , i 1 , ⋯ , p , h j ( x ) 0 , j 1 , ⋯ , q , x ∈ Ω , \begin{cases}\min f_0(x)\\[1ex]\text{s.t.} f_i(x)\le0,\quad i1,\cdots,p,\\[1ex]h_j(x)0,\quad j1,\cdots,q,\\[1ex]x\in\Omega,\end{cases} ⎩ ⎨ ⎧minf0(x)s.t.fi(x)≤0,i1,⋯,p,hj(x)0,j1,⋯,q,x∈Ω,是凸的/拟凸的 是指它满足如下条件 ( i ) (i) (i) f 0 f_0 f0 是凸函数/拟凸函数 ( i i ) (ii) (ii) { f i } i 1 p \{f_{i}\}_{i1}^{p} {fi}i1p是凸函数; ( i i i ) (iii) (iii) { h j } j 1 q \{h_j\}_{j1}^q {hj}j1q 是仿射函数 ( i v ) (iv) (iv) Ω \Omega Ω 为 R n \mathbb{R}^n Rn 中凸集.
显然此时可行集 D \mathcal{D} D 是凸集( f 0 , D ) f_0,\mathcal{D}) f0,D) 是凸问题/拟凸问题.
命题 4.3.1 (凸问题的局部解是全局解)
(1) 凸优化问题 ( f , D ) (f,\mathcal{D}) (f,D) 的局部解必为全局解.
(2) 拟凸问题 ( f , D ) (f,\mathcal{D}) (f,D) 的严格局部解必为严格全局解.
证.(1) 反证法若 x ∗ x^* x∗ 是凸优化问题 ( f , D ) (f,\mathcal{D}) (f,D) 的局部解而不是全局解则必存在 x ∈ D x\in\mathcal{D} x∈D, 使得 f ( x ) f ( x ∗ ) f(x)f(x^*) f(x)f(x∗).对任意的 θ ∈ ( 0 , 1 ) \theta\in(0,1) θ∈(0,1),令 x θ : x ∗ θ ( x − x ∗ ) x_\theta:x^*\theta(x-x^*) xθ:x∗θ(x−x∗).显然 x θ ∈ D x_\theta\in\mathcal{D} xθ∈D,且当 θ \theta θ 充分小时 x θ x_{\theta} xθ 充分接近 x ∗ x^* x∗,从而 f ( x ∗ ) ≤ f ( x θ ) f(x^*)\leq f(x_\theta) f(x∗)≤f(xθ).于是 f ( x ∗ ) ≤ f ( x θ ) ≤ ( 1 − θ ) f ( x ∗ ) θ f ( x ) ( 1 − θ ) f ( x ∗ ) θ f ( x ∗ ) f ( x ∗ ) . \begin{aligned}f(x^*)\leq f(x_\theta)\leq(1-\theta)f(x^*)\theta f(x)(1-\theta)f(x^*)\theta f(x^*)f(x^*).\end{aligned} f(x∗)≤f(xθ)≤(1−θ)f(x∗)θf(x)(1−θ)f(x∗)θf(x∗)f(x∗).矛盾.上式中第二个不等号利用了凸函数的定义.所以 x ∗ x^* x∗ 是全局解.
(2) 若 x ∗ x^* x∗ 是拟凸优化问题的 ( f , D ) (f,\mathcal{D}) (f,D) 的严格局部解而不是严格全局解则存在 x ∈ D x\in\mathcal{D} x∈D 使得 f ( x ) ≤ f ( x ∗ ) f(x)\leq f(x^*) f(x)≤f(x∗).沿用上面的符号类似地当 θ 0 \theta0 θ0 充分小时有 f ( x ∗ ) f ( x θ ) ≤ max { f ( x ∗ ) , f ( x ) } f ( x ∗ ) . f(x^*)f(x_\theta)\leq\max\{f(x^*),f(x)\}f(x^*). f(x∗)f(xθ)≤max{f(x∗),f(x)}f(x∗).矛盾. 上式中第二个不等号利用了拟凸函数的定义.
注对于拟凸问题非严格局部解未必是全局解. 例如函数 f ( x ) : { x 1 x ≤ − 1 0 x ∈ ( − 1 , 1 ) x − 1 x ≥ 1 f(x):\begin{cases}x1x\leq-1\\0x\in(-1,1)\\x-1x\geq1\end{cases} f(x):⎩ ⎨ ⎧x10x−1x≤−1x∈(−1,1)x≥1位于区间 (-1,1) 中每一点都是 ( f , R ) (f,\mathbb{R}) (f,R) 的局部最优解但它们都不是全局最优解如下图所示 命题 3.1.2 (全局解与平稳点的等价性) 设凸优化问题 ( f , D ) (f,\mathcal{D}) (f,D) 的目标函数 f f f 在 x ∗ ∈ D x^*\in\mathcal{D} x∗∈D 处一阶可微 x ∗ ∈ D x^*\in\mathcal{D} x∗∈D,那么 x ∗ x^* x∗ 是 ( f , D ) (f,\mathcal{D}) (f,D) 的一个全局最优解当且仅当 ∇ f ( x ∗ ) T ( x − x ∗ ) ≥ 0 , ∀ x ∈ D . \begin{align}\nabla f(x^*)^T(x-x^*)\ge0,\quad\forall x\in\mathcal{D}.\end{align} ∇f(x∗)T(x−x∗)≥0,∀x∈D. 证. 必要性. x ∗ ∈ D x^*\in\mathcal{D} x∗∈D 是一个最优解因为 D \mathcal{D} D 是凸集由优化问题笔记 (1)中的命题 1.2.1有 ∇ f ( x ∗ ) T d 0 , d T ∇ 2 f ( x ∗ ) d ≥ 0 , ∀ d ∈ V D \nabla f(x^{*})^{T}d0,\quad d^{T}\nabla^{2}f(x^{*})d\geq0,\quad\forall d\in V_{\mathcal{D}} ∇f(x∗)Td0,dT∇2f(x∗)d≥0,∀d∈VD以及由引理 1.2.2有 ξ T ( x − x ∗ ) ≥ 0 , ∀ x ∈ D ⟺ ξ T d ≥ 0 , ∀ d ∈ S F D ( x ∗ ) \xi^T(x-x^*)\ge0,\forall x\in\mathcal{D} \iff \xi^Td\ge0,\forall d\in\mathbf{SFD}(x^*) ξT(x−x∗)≥0,∀x∈D⟺ξTd≥0,∀d∈SFD(x∗)于是可以推出(1)成立.
充分性. 设(1)成立. 则 ∀ x ∈ D \forall x\in\mathcal{D} ∀x∈D,利用凸函数笔记 (1)中的命题 2.2.1,下文直接引用不再以链接形式给出笔记出处 f 是凸函数当且仅当 f ( y ) ≥ f ( x ) ∇ f ( x ) T ( y − x ) , ∀ x , y ∈ d o m ( f ) . f\text{ 是凸函数当且仅当}f(y)\geq f(x)\nabla f(x)^T(y-x),\quad\forall x,y\in\mathbf{dom}(f). f 是凸函数当且仅当f(y)≥f(x)∇f(x)T(y−x),∀x,y∈dom(f).
于是有 f ( x ) ≥ f ( x ∗ ) ∇ f ( x ∗ ) T ( x − x ∗ ) ≥ f ( x ∗ ) . \begin{aligned}f(x)\geq f(x^*)\nabla f(x^*)^T(x-x^*)\geq f(x^*).\end{aligned} f(x)≥f(x∗)∇f(x∗)T(x−x∗)≥f(x∗).所以 x ∗ x^* x∗ 是 ( f , D ) (f,\mathcal{D}) (f,D) 的一个最优解.
注当 x ∗ ∈ r i ( D ) x^*\in\mathbf{ri}(\mathcal{D}) x∗∈ri(D) 时由引理 1.2.2 可知 (1)等价于 ∇ f ( x ∗ ) ⊥ V D \nabla f(x^*)\perp V_\mathcal{D} ∇f(x∗)⊥VD. 这意味着 x ∗ x^* x∗ 约束在 V D V_\mathrm{D} VD上是 f f f 的一个平稳点( 满足 ∇ f ( x ∗ ) 0 \nabla f(x^*)0 ∇f(x∗)0 的点称为 f f f 的平稳点).这一性质在优化问题的数值计算中非常重要因为判断一个点是否为平稳点比判断其为局部极小点要容易得多.
例 3.1.1 设 A ∈ R m × n , b ∈ R m A\in\mathbb{R}^{m\times n},\quad b\in\mathbb{R}^m A∈Rm×n,b∈Rm 使得集合 { x ∈ R n ∣ A x b } \{x\in\mathbb{R}^n|Axb\} {x∈Rn∣Axb} 非空. 又设函数 f : R n → R f:\mathbb{R}^n\to\mathbb{R} f:Rn→R 是可微的凸函数.那么 x ∗ ∈ R n x^*\in\mathbb{R}^n x∗∈Rn 是等式约束凸优化问题 { min f ( x ) s . t A x b \begin{align} \begin{cases}\min f(x)\\\mathrm{s.t}\quad Axb\end{cases}\end{align} {minf(x)s.tAxb的解当且仅当 ∇ f ( x ∗ ) ∈ r a n ( A T ) , A x ∗ b . \nabla f(x^*)\in\mathbf{ran}(A^T),\quad Ax^*b. ∇f(x∗)∈ran(AT),Ax∗b.证.在 例 1.2.1 中已证明该可行集 D \mathcal{D} D 满足 r i ( D ) D \mathbf{ri}(D)\mathcal{D} ri(D)D 且 V D n u l l ( A ) r a n ( A T ) ⊥ . V_D\mathbf{null}(A)\mathbf{ran}(A^T)^\perp. VDnull(A)ran(AT)⊥. 由命题 3.1.2 可知 x ∗ ∈ D x^*\in\mathcal{D} x∗∈D 是优化问题 (2)的一个最优解当且仅当 ∇ f ( x ∗ ) ∈ V D ⊥ \nabla f(x^*)\in V_\mathcal{D}^\perp ∇f(x∗)∈VD⊥, 即 ∇ f ( x ∗ ) ∈ r a n ( A T ) . \nabla f(x^*)\in\mathbf{ran}(A^T). ∇f(x∗)∈ran(AT).
3.2 二次优化问题
当目标函数和约束函数都是二次 (不超过二次) 函数时, L ( x , λ , µ ) L(x, λ, µ) L(x,λ,µ) 关于 x x x也是二次函数,因而其 Taylor 展开式展开到二次项时余项为 0. 此时, 有如下全局解的充分条件.
命题 3.2.1 (二次优化问题全局解的充分条件) 对于不含约束集的约束优化问题 { min f 0 ( x ) s . t f i ( x ) ≤ 0 , i 1 , ⋯ , p , h j ( x ) 0 , j 1 , ⋯ , q . \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.\end{cases} ⎩ ⎨ ⎧minf0(x)s.tfi(x)≤0,i1,⋯,p,hj(x)0,j1,⋯,q., 设 { f i } i 0 p , { h j } j 1 q \{f_i\}_{i0}^p,\{h_j\}_{j1}^q {fi}i0p,{hj}j1q 均为二次函数 x ∗ ∈ R n x^*\in\mathbb{R}^n x∗∈Rn,存在 λ ∗ ∈ R p , μ ∗ ∈ R q \lambda^*\in\mathbb{R}^p,\mu^*\in\mathbb{R}^q λ∗∈Rp,μ∗∈Rq,满足 K K T KKT KKT 条件 { x ∗ ∈ D ; λ i ∗ ≥ 0 , i 1 , ⋯ , p ; λ i ∗ f i ( x ∗ ) 0 , i 1 , ⋯ , p ; ∇ x L ( x ∗ , λ ∗ , μ ∗ ) 0. \begin{cases}x^*\in\mathcal{D};\\\lambda_i^*\geq0,\quad i1,\cdots,p;\\\lambda_i^*f_i(x^*)0,\quad i1,\cdots,p;\\\nabla_xL(x^*,\lambda^*,\mu^*)0.\end{cases} ⎩ ⎨ ⎧x∗∈D;λi∗≥0,i1,⋯,p;λi∗fi(x∗)0,i1,⋯,p;∇xL(x∗,λ∗,μ∗)0.,且有下式 ( x − x ∗ ) T ∇ x 2 L ( x ∗ , λ ∗ , μ ∗ ) ( x − x ∗ ) ≥ 0 , ∀ x ∈ D \begin{align} (x-x^*)^T\nabla_x^2L(x^*,\lambda^*,\mu^*)(x-x^*)\geq0,\quad\forall x\in\mathcal{D}\end{align} (x−x∗)T∇x2L(x∗,λ∗,μ∗)(x−x∗)≥0,∀x∈D则 x ∗ x^* x∗ 是一个全局最优解.
证.对任意的 x ∈ D x\in\mathcal{D} x∈D,记 d : x − x ∗ d:x-x^* d:x−x∗,那么 f 0 ( x ) ≥ L ( x , λ ∗ , μ ∗ ) L ( x ∗ , λ ∗ , μ ∗ ) d T ∇ x L ( x ∗ , λ ∗ , μ ∗ ) 1 2 d T ∇ x 2 L ( x ∗ , λ ∗ , μ ∗ ) T d ≥ L ( x ∗ , λ ∗ , μ ∗ ) f 0 ( x ∗ ) . \begin{aligned} \begin{aligned}f_0(x)\geq L(x,\lambda^*,\mu^*)\end{aligned} L(x^*,\lambda^*,\mu^*)d^T\nabla_xL(x^*,\lambda^*,\mu^*)\frac12d^T\nabla_x^2L(x^*,\lambda^*,\mu^*)^Td \\ \geq L(x^{*},\lambda^{*},\mu^{*})f_{0}(x^{*}). \end{aligned} f0(x)≥L(x,λ∗,μ∗)L(x∗,λ∗,μ∗)dT∇xL(x∗,λ∗,μ∗)21dT∇x2L(x∗,λ∗,μ∗)Td≥L(x∗,λ∗,μ∗)f0(x∗). 所以 x ∗ x^* x∗ 是一个全局最优解.
注当 x ∗ x^* x∗ 是一个正则点时根据 定义 2.1.3 有 T ( x ∗ ) ∩ ∂ B ( 0 , 1 ) ⊂ L F D ( x ∗ ) S F D ( x ∗ ) ‾ \mathcal{T}(x^*)\cap\partial B(0,1)\subset\mathbf{LFD}(x^*)\mathbf{SFD}(\overline{x^*)} T(x∗)∩∂B(0,1)⊂LFD(x∗)SFD(x∗).根据 引理 1.2.2 可知本命题的条件(3) 比局部解的二阶必要条件 d T ∇ x 2 L ( x ∗ , λ ∗ , μ ∗ ) d ≥ 0 , ∀ d ∈ T ( x ∗ ) d^T\nabla_x^2L(x^*,\lambda^*,\mu^*)d\geq0,\quad\forall d\in\mathcal{T}(x^*) dT∇x2L(x∗,λ∗,μ∗)d≥0,∀d∈T(x∗) 要强.
3.3 无约束二次优化问题
命题 3.3.1 (二次函数之最优解的条件) 设 f ( x ) : 1 2 x T A x b T x f(x):\frac12x^TAxb^Tx f(x):21xTAxbTx, 其中 A A A 是 n n n 阶实对称矩阵 x ∗ ∈ R n x^*\in\mathbb{R}^n x∗∈Rn.那么对于无约束优化问题 ( f , R n ) (f,\mathbb{R}^n) (f,Rn),即问题 { min f 0 ( x ) s . t f i ( x ) ≤ 0 , i 1 , ⋯ , p , h j ( x ) 0 , j 1 , ⋯ , q . \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.\end{cases} ⎩ ⎨ ⎧minf0(x)s.tfi(x)≤0,i1,⋯,p,hj(x)0,j1,⋯,q.,如下三条相互是等价的 ( 3.3.1.1 ) x ∗ (3.3.1.1)\:x^* (3.3.1.1)x∗ 是 f f f 的一个全局极小点 ( 3.3.1.2 ) x ∗ (3.3.1.2)\:x^* (3.3.1.2)x∗ 是 f f f 的一个局部极小点 ( 3.3.1.3 ) A (3.3.1.3)A (3.3.1.3)A 是半正定矩阵且 A x ∗ b 0. Ax^*b0. Ax∗b0.
证.根据全局最小点和局部极小点的定义可以知道 (3.3.1.1) 蕴含 (3.3.1.2). 对 f f f 计算可得 ∇ f ( x ∗ ) A x ∗ b , ∇ 2 f ( x ∗ ) A . \begin{align} \begin{aligned}\nabla f(x^*)Ax^*b,\quad\nabla^2f(x^*)A.\end{aligned}\end{align} ∇f(x∗)Ax∗b,∇2f(x∗)A.因此若 (3.3.1.2) 成立那么由 必要性命题 1.2.1若 f f f 在 x ∗ x^* x∗ 处二阶连续可微且 x ∗ ∈ r i ( D ) x^*\in\mathbf{ri}(\mathcal{D}) x∗∈ri(D),则 ∇ f ( x ∗ ) T d 0 , d T ∇ 2 f ( x ∗ ) d ≥ 0 , ∀ d ∈ V D . \nabla f(x^{*})^{T}d0,\quad d^{T}\nabla^{2}f(x^{*})d\geq0,\forall d\in V_{\mathcal{D}}. ∇f(x∗)Td0,dT∇2f(x∗)d≥0,∀d∈VD.即知 (3.3.1.3) 成立.
设 (3.3.1.3)成立. 利用(4)可知 ∇ f ( x ∗ ) 0 \nabla f(x^*)0 ∇f(x∗)0,且 ∇ 2 f ( x ∗ ) \nabla^2f(x^*) ∇2f(x∗) 半正定. 于是 ∀ x ∈ R n \forall x\in\mathbb{R}^n ∀x∈Rn,做Taylor 展开有 f ( x ) f ( x ∗ ) 1 2 ( x − x ∗ ) T A ( x − x ∗ ) ≥ f ( x ∗ ) . f(x)f(x^*)\frac12(x-x^*)^TA(x-x^*)\geq f(x^*). f(x)f(x∗)21(x−x∗)TA(x−x∗)≥f(x∗).所以 x ∗ x^* x∗ 是 f f f 在 R n \mathbb{R}^n Rn 上的最小点. 即(3.3.1.1) 成立.
注二次函数 f ( x ) : 1 2 x T A x b T x f(x):\frac12x^TAxb^Tx f(x):21xTAxbTx 未必总存在极小值点. 事实上当 A A A 不是半正定矩阵时或者 A A A半正定但 A x b 0 Ax b 0 Axb0 无解时 f ( x ) f(x) f(x) 就不存在极小值点. 此时 inf x ∈ R n f ( x ) − ∞ \inf_{x\in\mathbb{R}^n}f(x)-\infty infx∈Rnf(x)−∞.例如对于 A [ 0 0 0 1 ] , b : [ b 1 0 ] , c 0 , A\begin{bmatrix}00\\01\end{bmatrix},\quad b:\begin{bmatrix}b_1\\0\end{bmatrix},\quad c0, A[0001],b:[b10],c0,有 f ( x ) 1 2 x 2 2 b 1 x 1 , x : ( x 1 , x 2 ) T ∈ R 2 f(x)\frac12x_2^2b_1x_1,\:x:(x_1,x_2)^T\in\mathbb{R}^2 f(x)21x22b1x1,x:(x1,x2)T∈R2.当 b 1 ≠ 0 b_1\neq0 b10 时 f ( x ) f(x) f(x) 不存在最小值点.
推论 3.3.1 (二次函数之全局最优解存在的条件) 设 A A A 是 n n n 阶实对称矩阵那么二次函数 f ( x ) : 1 2 x T A x b T x f(x):\frac12x^TAxb^Tx f(x):21xTAxbTx 在 R n \mathbb{R}^n Rn 上有最小值点当且仅当 f ( x ) f(x) f(x) 在 R n \mathbb{R}^n Rn 上有下界.
证.将 A A A做特征分解 A U Λ U T AU\Lambda U^T AUΛUT ,其中 U U U 是一个 n n n 阶正交矩阵 Λ d i a g ( λ 1 , . . . , λ n ) \Lambda\mathbf{diag}(\lambda_1,...,\lambda_n) Λdiag(λ1,...,λn), 其中 λ 1 ≥ . . . ≥ λ n \lambda_1\geq...\geq\lambda_n λ1≥...≥λn 是 A A A 的全部特征值. 令 y : U T x , q : U T b y:U^Tx,~q:U^Tb y:UTx, q:UTb, 那么 f ( x ) 1 2 y T Λ y q T y 1 2 ∑ i 1 n ( λ i y i 2 2 q i y i ) . f(x)\frac12y^T\Lambda yq^Ty\frac12\sum_{i1}^n(\lambda_iy_i^22q_iy_i). f(x)21yTΛyqTy21i1∑n(λiyi22qiyi).所以 f ( x ) f(x) f(x) 在 R n \mathbb{R}^n Rn 上有下界当且仅当对每一个 1 ≤ i ≤ n 1\leq i\leq n 1≤i≤n, 单变量函数 g i ( y ) : λ i y 2 2 q i y g_i(y):\lambda_iy^22q_iy gi(y):λiy22qiy在 R 上有下界.即 λ i ≥ 0 \lambda_i\geq0 λi≥0 且 λ i 0 \lambda_i0 λi0 时有 q i 0 q_i0 qi0. 此时当 y i : { − q i λ i λ i 0 , 任意值 λ i 0 , i 1 , . . . , n . y_i:\begin{cases}-\frac{q_i}{\lambda_i}\lambda_i0,\\\text{任意值}\lambda_i0,\end{cases}\quad i1,...,n. yi:{−λiqi任意值λi0,λi0,i1,...,n.时 x U y x Uy xUy是 f ( x ) f(x) f(x) 在 R n \mathbb{R} ^n Rn 上的一个最小值点.
例 3.3.1 (最小二乘问题 (LSP: Least Square Problem)) 给定矩阵 A ∈ R m × n A\in\mathbb{R}^{m\times n} A∈Rm×n 和向量 b ∈ R m b\in\mathbb{R}^m b∈Rm, 如下无约束优化问题 min ∥ A x − b ∥ 2 2 \begin{align} \min\|Ax-b\|_2^2\end{align} min∥Ax−b∥22称为最小二乘问题. x ∗ x^* x∗ 是其最优解当且仅当 ( A T A ) x ∗ A T b (A^TA)x^*A^Tb (ATA)x∗ATb. 该问题的解一定存在且构成一个 n − r n-r n−r 维仿射空间其中 r : r a n k ( A ) r: \mathbf{rank}( A) r:rank(A)
证.计算可得 ∥ A x − b ∥ 2 2 x T ( A T A ) x − 2 b T A x ∥ b ∥ 2 2 , \|Ax-b\|_2^2x^T(A^TA)x-2b^TAx\|b\|_2^2, ∥Ax−b∥22xT(ATA)x−2bTAx∥b∥22,根据线性代数的内容假设 A A A 的列向量分别是 α 1 , ⋯ , α n \alpha_1,\cdots,\alpha_n α1,⋯,αn那么有 ∣ A X 0 − b ∣ 最小 ⟺ 对于任意的 X 都有 ∣ A X 0 − b ∣ ≤ ∣ A X − b ∣ ⟺ A X 0 − b ⊥ U 其中 U { A X ∣ X ∈ R n } L ( α 1 , ⋯ , α n ) ⟺ A X 0 − b ⊥ α i ( i 1 , 2 , ⋯ , n ) ⟺ α i ′ ( A X 0 − b ) 0 ( i 1 , 2 , ⋯ , n ) ⟺ ( α 1 ′ ⋮ α n ′ ) ( A X 0 − b ) 0 ⟺ A ′ ( A X 0 − b ) 0 ⟺ A ′ A X 0 A ′ b . \begin{aligned} |AX_{0}-b|\text{ 最小} \Longleftrightarrow\text{对于任意的 }X\text{ 都有 }|AX_0-b|\leq|AX-b| \\ \Longleftrightarrow AX_0-b\perp U\text{ 其中 }U\{AX|X\in\mathbb{R}^n\}L(\alpha_1,\cdots,\alpha_n) \\ \Longleftrightarrow AX_0-b\perp\alpha_i(i1,2,\cdots,n) \\ \Longleftrightarrow\alpha_i(AX_0-b)0(i1,2,\cdots,n) \\ \left.\Longleftrightarrow\left(\begin{array}{c}\alpha_1\\\vdots\\\alpha_n\end{array}\right.\right)(AX_0-b)0 \\ \Longleftrightarrow A^{\prime}(AX_{0}-b)0 \\ \Longleftrightarrow A^{\prime}AX_{0}A^{\prime}b. \end{aligned} ∣AX0−b∣ 最小⟺对于任意的 X 都有 ∣AX0−b∣≤∣AX−b∣⟺AX0−b⊥U 其中 U{AX∣X∈Rn}L(α1,⋯,αn)⟺AX0−b⊥αi(i1,2,⋯,n)⟺αi′(AX0−b)0(i1,2,⋯,n)⟺ α1′⋮αn′ (AX0−b)0⟺A′(AX0−b)0⟺A′AX0A′b.记 r : r a n k ( A ) r: \mathbf{rank}( A) r:rank(A)即 r r r表示矩阵的秩
一方面 r ( A ′ A , A ′ b ) r ( A ′ ( A , b ) ) ≤ r ( A ′ ) r ( A ) . r(A^{\prime}A,A^{\prime}b)r(A^{\prime}(A,b))\leq r(A^{\prime})r(A). r(A′A,A′b)r(A′(A,b))≤r(A′)r(A).另一方面 r ( A ′ A , A ′ b ) ≥ r ( A ′ A ) r ( A ) , r(A^{\prime}A,A^{\prime}b)\geq r(A^{\prime}A)r(A), r(A′A,A′b)≥r(A′A)r(A),这就说明 r ( A ′ A , A ′ b ) r ( A ) r ( A ′ A ) . r(A^{\prime}A,A^{\prime}b)r(A)r(A^{\prime}A). r(A′A,A′b)r(A)r(A′A).
所以线性方程组 ( A T A ) x A T b (A^TA)x\:\:A^Tb (ATA)xATb 有解且其解就是上述最小二乘问题的解.
根据上面的推导可以知道该线性方程组的增广矩阵 ( A T A , A T b ) A T ( A , b ) (A^TA,A^Tb)A^T(A,b) (ATA,ATb)AT(A,b) 的秩就等于 r a n k ( A T ) r r a n k ( A T A ) , \mathbf{rank}(A^T)r\mathbf{rank}(A^TA), rank(AT)rrank(ATA), 所以该线性方程组有解其有 n − r n-r n−r 个基向量且解空间构成一个 n − r n-r n−r 维仿射空间.
3.4 一个典型的二次等式约束二次优化问题
给定 n n n阶对称矩阵 A B AB AB考虑如下的优化问题 { min x T A x s . t x T x 1 , x T B x 1. \begin{align}\begin{cases}\min x^TAx\\\mathrm{s.t~}x^Tx1,\\x^TBx1.\end{cases}\end{align} ⎩ ⎨ ⎧minxTAxs.t xTx1,xTBx1.记 D : { x ∈ R n ∣ x T x 1 , x T B x 1 } \mathcal{D}:\{x\in\mathbb{R}^n|x^Tx1,x^TBx1\} D:{x∈Rn∣xTx1,xTBx1}当 D \mathcal{D} D 非空时, 根据函数的连续性可知该优化问题的全局最优解是存在的.
若 x ∗ ∈ D x^∗ ∈ \mathcal{D} x∗∈D 是问题(6)的全局解, 且 { x ∗ , B x ∗ } \left \{ x^∗, Bx^∗ \right \} {x∗,Bx∗} 线性无关, 根据局部解的二阶必要条件 (命题 2.2.5),存在 α ∗ , β ∗ ∈ R \alpha^*,\beta^*\in\mathbb{R} α∗,β∗∈R, 使得 H x ∗ 0 , d T H d ≥ 0 , ∀ d ∈ T ( x ∗ ) , \begin{align} Hx^*0,\quad d^THd\geq0,\quad\forall d\in\mathcal{T}(x^*),\end{align} Hx∗0,dTHd≥0,∀d∈T(x∗),其中 T ( x ∗ ) : ( s p a n { x ∗ , B x ∗ } ) ⊥ \mathcal{T}(x^*):\left(\mathbf{span}\{x^*,Bx^*\}\right)^\perp T(x∗):(span{x∗,Bx∗})⊥ 是问题(6) 的约束条件的切空间而根据命题 3.2.1当 H x ∗ 0 , d T H d ≥ 0 , ∀ d ∈ D − x ∗ , \begin{align} Hx^*0,\quad d^THd\geq0,\quad\forall d\in\mathcal{D}-x^*,\end{align} Hx∗0,dTHd≥0,∀d∈D−x∗,时 x ∗ x^* x∗ 是问题(6)全局解.
下面命题则可以说明必要条件可以加强为 H x ∗ 0 , H ⪰ 0. Hx^*0,~H\succeq0. Hx∗0, H⪰0.
命题 3.4.1 (Bar-on and Grasse) 设 x ∗ ∈ D x^*\in\mathcal{D} x∗∈D,且使得 { x ∗ , R x ∗ } \{x^*,Rx^*\} {x∗,Rx∗} 线性无关则 x ∗ x^* x∗ 是问题(6)的全局解当且仅当存在 α ∗ , β ∗ ∈ R \alpha^*,\beta^*\in\mathbb{R} α∗,β∗∈R, 使得(8)所定义的 H H H 满足 H x ∗ 0 , H ⪰ 0. \begin{align} Hx^*0,\quad H\succeq0.\end{align} Hx∗0,H⪰0.
Reference
包括但不限于以下内容 (1)Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. (2) JR Bar-On and KA Grasse. Global optimization of a quadratic functional with quadratic equality constraints. Journal of Optimization Theory and Applications, 82(2):379–386, 1994. (3) JR Bar-On and KA Grasse. Global optimization of a quadratic functional with quadratic equality constraints, part 2. Journal of Optimization Theory and Applications, 93(3):547–556, 1997.
