服务器网站建设,东莞做公司网站,合肥专门做网站的公司有哪些,照片编辑软件app5.7 约束优化最优性理论应用实例
5.7.1 仿射空间的投影问题
考虑优化问题 min x ∈ R n 1 2 ∣ ∣ x − y ∣ ∣ 2 2 , s . t . A x b \min_{x{\in}R^n}\frac{1}{2}||x-y||_2^2,\\ s.t.{\quad}Axb x∈Rnmin21∣∣x−y∣∣22,s.t.Axb 其中 A ∈ R m n , b ∈ R m …5.7 约束优化最优性理论应用实例
5.7.1 仿射空间的投影问题
考虑优化问题 min x ∈ R n 1 2 ∣ ∣ x − y ∣ ∣ 2 2 , s . t . A x b \min_{x{\in}R^n}\frac{1}{2}||x-y||_2^2,\\ s.t.{\quad}Axb x∈Rnmin21∣∣x−y∣∣22,s.t.Axb 其中 A ∈ R m × n , b ∈ R m , y ∈ R n A{\in}R^{m \times n},b{\in}R^m,y{\in}R^n A∈Rm×n,b∈Rm,y∈Rn为给定的矩阵和向量这里不妨设矩阵A是行满秩的这个问题可以看成仿射平面 { x ∈ R n ∣ A x b } \{x{\in}R^n|Axb\} {x∈Rn∣Axb}的投影问题 对于等式约束我们引入拉格朗日乘子 λ ∈ R m \lambda{\in}R^m λ∈Rm构造拉格朗日函数 L ( x , λ ) 1 2 ∣ ∣ x − y ∣ ∣ 2 λ T ( A x − b ) L(x,\lambda)\frac{1}{2}||x-y||^2\lambda^T(Ax-b) L(x,λ)21∣∣x−y∣∣2λT(Ax−b) 因为只有仿射约束估 S l a t e r Slater Slater条件满足 x ∗ x^* x∗为一个全局最优解当且仅当存在 λ ∗ ∈ R m \lambda^*{\in}R^m λ∗∈Rm使得 { x ∗ − y A T λ 0 A x ∗ b \left\{ \begin{matrix} x^*-yA^T\lambda0\\ Ax^*b \\ \end{matrix} \right. {x∗−yATλ0Ax∗b 由上述KKT条件第一式等号左右两边同时左乘 A A A可得 A x ∗ − A y A A T λ 0 Ax^*-AyAA^T\lambda0 Ax∗−AyAATλ0 注意到 A x ∗ b Ax^*b Ax∗b以及 A A T AA^T AAT是可逆矩阵因此可以解出乘子 λ ( A A T ) − 1 ( A y − b ) \lambda(AA^T)^{-1}(Ay-b) λ(AAT)−1(Ay−b) 代入回去可以得到 x ∗ y − A T ( A A T ) − 1 ( A y − b ) x^*y-A^T(AA^T)^{-1}(Ay-b) x∗y−AT(AAT)−1(Ay−b)
5.7.2 线性规划问题
考虑线性规划问题 min x ∈ R n c T x , s . t . A x b , x ≥ 0 (5.7.1) \min_{x{\in}R^n}{\quad}c^Tx,\\ s.t.{\quad}Axb,\\ x{\ge}0\tag{5.7.1} x∈RnmincTx,s.t.Axb,x≥0(5.7.1) 其中 A ∈ R m × n , b ∈ R m , c ∈ R n A{\in}R^{m \times n},b{\in}R^m,c{\in}R^n A∈Rm×n,b∈Rm,c∈Rn分别为给定的矩阵和向量 拉格朗日函数可以写为 L ( x , s , v ) c T x v T ( A x − b ) − s T x − b T v ( A T v − s c ) T x , s ≥ 0 L(x,s,v)c^Txv^T(Ax-b)-s^Tx\\ -b^Tv(A^Tv-sc)^Tx,s{\ge}0 L(x,s,v)cTxvT(Ax−b)−sTx−bTv(ATv−sc)Tx,s≥0 其中 s ∈ R n , v ∈ R m s{\in}R^n,v{\in}R^m s∈Rn,v∈Rm由于线性规划是凸问题且满足 S l a t e r Slater Slater条件的因此对于任意一个全局最优解 x ∗ x^* x∗我们有如下KKT条件 { c A T v ∗ − s ∗ 0 , A x ∗ b x ∗ ≥ 0 s ∗ ≥ 0 s ∗ x ∗ 0 (5.7.2) \left\{ \begin{matrix} cA^Tv^*-s^*0,\\ Ax^*b \\ x^*{\ge}0\\ s^*{\ge}0\\ s^*x^*0 \end{matrix} \right.\tag{5.7.2} ⎩ ⎨ ⎧cATv∗−s∗0,Ax∗bx∗≥0s∗≥0s∗x∗0(5.7.2) 我们设原始问题和对偶问题最优解函数值分别为 p ∗ p^* p∗和 d ∗ d^* d∗则根据 p ∗ p^* p∗取值情况有如下三种可能 1如果 − ∞ p ∗ ∞ ( 有界 ) -\inftyp^*\infty(有界) −∞p∗∞(有界)那么原始问题可行而且存在最优解由 S l a t e r Slater Slater条件知强对偶原理成立因此有 d ∗ p ∗ d^*p^* d∗p∗即对偶问题也是可行的且存在最优解 2如果 p ∗ − ∞ p^*-\infty p∗−∞那么原始问题可行但目标函数值无下界由弱对偶原理知 d ∗ ≤ p ∗ − ∞ d^*{\le}p^*-\infty d∗≤p∗−∞即 d ∗ − ∞ d^*-\infty d∗−∞因为对偶问题是对目标函数极大化所以此时对偶问题不可行 3如果 p ∗ ∞ p^*\infty p∗∞那么原始问题无可行解注意到 S l a t e r Slater Slater条件对原始问题不成立此时对偶问题既可能是函数值无界 d ∗ ∞ d^*\infty d∗∞也可能无可行解 d ∗ − ∞ d^*-\infty d∗−∞我们说不可能出现 − ∞ d ∗ ∞ -\inftyd^*\infty −∞d∗∞的情形这是因为如果对偶问题可行且存在最优解那么可对对偶问题应用强对偶原理进而导出原始问题也存在最优解这矛盾了
5.7.3 基追踪 min x ∈ R n ∣ ∣ x ∣ ∣ 1 , s . t . A x b (5.7.3) \min_{x{\in}R^n}||x||_1,\\ s.t.{\quad}Axb\tag{5.7.3} x∈Rnmin∣∣x∣∣1,s.t.Axb(5.7.3) 利用分解 x i x i − x i − x_ix_i^-x_i^- xixi−xi−其中 x i m a x { x i , 0 } , x i − max { − x i , 0 } x_i^max\{x_i,0\},x_i^-\max\{-x_i,0\} ximax{xi,0},xi−max{−xi,0}分别表示 x x x的正部和负部问题5.7.3的一种等价形式可以写成 min ∑ i x i x i − , s . t . A x − A x − b , x , x − ≥ 0 \min{\sum_i}x_i^x_i^-,\\ s.t.{\quad}Ax^-Ax^-b,\\ x^,x^-{\ge}0 mini∑xixi−,s.t.Ax−Ax−b,x,x−≥0 进一步的令 y [ x i , x i − ] T ∈ R 2 n y[x_i^,x_i^-]^T{\in}R^{2n} y[xi,xi−]T∈R2n我们将问题5.7.3转化为如下线性规划问题 min y ∈ R 2 n 1 T y , s . t . [ A , − A ] y b , y ≥ 0 \min_{y{\in}R^{2n}}1^Ty,\\ s.t.{\quad}[A,-A]yb,\\ y{\ge}0 y∈R2nmin1Ty,s.t.[A,−A]yb,y≥0 其中 1 ( 1 , 1 , ⋯ , 1 ) T ∈ R 2 n 1(1,1,\cdots,1)^T{\in}R^{2n} 1(1,1,⋯,1)T∈R2n 那么根据一般线性规划的最优性条件等价于求解 { 1 [ A , − A ] T v ∗ − s ∗ 0 , [ A , − A ] y ∗ b y ∗ ≥ 0 s ∗ ≥ 0 s ∗ y ∗ 0 (5.7.4) \left\{ \begin{matrix} 1[A,-A]^Tv^*-s^*0,\\ [A,-A]y^*b \\ y^*{\ge}0\\ s^*{\ge}0\\ s^*y^*0 \end{matrix} \right.\tag{5.7.4} ⎩ ⎨ ⎧1[A,−A]Tv∗−s∗0,[A,−A]y∗by∗≥0s∗≥0s∗y∗0(5.7.4) 同样的我们也可以直接推导5.7.3的最优性条件拉格朗日函数为 L ( x , v ) ∣ ∣ x ∣ ∣ 1 v T ( A x − b ) L(x,v)||x||_1v^T(Ax-b) L(x,v)∣∣x∣∣1vT(Ax−b) x ∗ x^* x∗为全局最优解当且仅当存在 v ∗ ∈ R m v^*{\in}R^m v∗∈Rm使得 { 0 ∈ ∂ ∣ ∣ x ∗ ∣ ∣ 1 A T v ∗ , A x ∗ b (5.7.5) \left\{ \begin{matrix} 0{\in}\partial||x^*||_1A^Tv^*,\\ Ax^*b \\ \end{matrix} \right.\tag{5.7.5} {0∈∂∣∣x∗∣∣1ATv∗,Ax∗b(5.7.5) 最优性条件5.7.4和5.7.5本质上是等价的
