宁波网站建设宁波,表情包做旧网站,中华室内设计协会,网站建设 三网凸优化问题 凸优化问题的广义定义#xff1a; 目标函数为凸函数约束集合为凸集 一、优化问题
基本用语
一般优化问题的描述#xff1a; minimizef0(x)subject to fi(x)⩽0,i1,⋯,mhi(x)0,i1,⋯,p(1)\begin{array}{ll} \operatorname{minimize} f_0(x) \\ \text { s…凸优化问题 凸优化问题的广义定义 目标函数为凸函数约束集合为凸集 一、优化问题
基本用语
一般优化问题的描述 minimizef0(x)subject to fi(x)⩽0,i1,⋯,mhi(x)0,i1,⋯,p(1)\begin{array}{ll} \operatorname{minimize} f_0(x) \\ \text { subject to } f_i(x) \leqslant 0, \quad i1, \cdots, m \\ h_i(x)0, \quad i1, \cdots, p \end{array}\tag{1} minimize subject to f0(x)fi(x)⩽0,i1,⋯,mhi(x)0,i1,⋯,p(1) 相关定义
x∈Rnx\in \R^nx∈Rn优化变量optimization variable
f0:Rn→Rf_0:\R^n\rightarrow Rf0:Rn→R目标函数/损失函数objective function/cost function
若是一个极大化问题那么称为 效用函数 utility function
fi(x)≤0:Rn→Rf_i(x)\leq 0:\R^n\rightarrow \Rfi(x)≤0:Rn→R不等式约束inequality constraint
hi(x)0h_i(x)0hi(x)0等式约束 equality constraint
mp0mp0mp0无约束 unconstraited
优化问题的域domain所有函数定义域的交集 D⋂i0mdomfi∩⋂i1pdomhi\mathcal{D}\bigcap_{i0}^m \operatorname{dom} f_i \cap \bigcap_{i1}^p \operatorname{dom} h_i Di0⋂mdomfi∩i1⋂pdomhi 可行解集feasible set使得问题约束满足的解的集合 注意还需要在目标函数的定义域内 最优点与局部最优点
最优点与局部最优点若可行解集合不是空集那么总是能在集合中找到一个X使得目标函数最优这个值称为最优值。 P∗inf{f0(x)∣X∈Xf}P^*\inf \{f_0(x)|X\in X_f\} P∗inf{f0(x)∣X∈Xf} 若XfX_fXf为空集那么P∗∞P^*\inftyP∗∞
最优解若X∗X^*X∗可行且f0(X∗)P∗f_0(X^*)P^*f0(X∗)P∗
最优解集最优解的集合 Xopt{X∣X∈Xf,f0(X)P∗}X_{opt}\{X|X\in X_f,f_0(X)P^*\} Xopt{X∣X∈Xf,f0(X)P∗} ϵ−\epsilon-ϵ−次优解集satisficing solution 约束一般要满足目标函数值不一定要达到最优值可以离最优值小一定的距离ϵ\epsilonϵ Xϵ{X∈Xf,f0(X)≤P∗ϵ}X_{\epsilon}\{X\in X_f,f_0(X)\leq P^*\epsilon\} Xϵ{X∈Xf,f0(X)≤P∗ϵ}
局部最优解 域、可行解集、全局最优解、局部最优解ϵ\epsilonϵ解集之间的关系 若x∈Xf,fi(x)0x\in X_f,f_i(x)0x∈Xf,fi(x)0则fi(x)≤0f_i(x)\leq 0fi(x)≤0为活动约束fi(x)0f_i(x)0fi(x)0为不活动约束。
排除临界点的方法 可行性优化问题
可行性优化问题一般可以写成下面的形式 find xsubject to fi(x)⩽0,i1,⋯,mhi(x)0,i1,⋯,p.\begin{array}{ll} \text { find } x \\ \text { subject to } f_i(x) \leqslant 0, \quad i1, \cdots, m \\ h_i(x)0, \quad i1, \cdots, p . \end{array} find subject to xfi(x)⩽0,i1,⋯,mhi(x)0,i1,⋯,p. 如何写成标准的形式写成最优化一个常数。
问题的标准表示
框约束 Box Constraints
minimizef0(x)subject tol1≤xi≤ui,i1,...,n\begin{array}{ll} \text{minimize} f_0(x)\\ \text{subject to} l_1\leq x_i\leq u_i,i1,...,n \end{array} minimizesubject tof0(x)l1≤xi≤ui,i1,...,n
即每个变量都有一个上界和下界那么可以转换为下面的标准形式 minimizef0(x)subject toli−xi≤0,i1,...,nxi−ui≤0,i1,...,n\begin{array}{ll} \text{minimize} f_0(x)\\ \text{subject to} l_i-x_i\leq 0,i1,...,n\\ x_i-u_i\leq 0,i1,...,n \end{array} minimizesubject tof0(x)li−xi≤0,i1,...,nxi−ui≤0,i1,...,n
等价问题
如果从一个问题的解很容易得到另一个问题的解并且反之亦然那么我们称两个问题是等价的。作为一个简单的例子考虑 minimizef~(x)α0f0(x)subject to f~i(x)αifi(x)⩽0,i1,⋯,mh~i(x)βihi(x)0,i1,⋯,p(2)\begin{array}{ll} \operatorname{minimize} \tilde{f}(x)\alpha_0 f_0(x) \\ \text { subject to } \tilde{f}_i(x)\alpha_i f_i(x) \leqslant 0, \quad i1, \cdots, m \\ \tilde{h}_i(x)\beta_i h_i(x)0, \quad i1, \cdots, p \end{array}\tag{2} minimize subject to f~(x)α0f0(x)f~i(x)αifi(x)⩽0,i1,⋯,mh~i(x)βihi(x)0,i1,⋯,p(2) 很多时候约束的量级不同量级过大导致约束的权重变化。通过等价转换可以将问题的约束进行标准化。
目标函数和约束函数的变换
设ψ0:R→R\psi_0:\R\rightarrow \Rψ0:R→R单增ψ1,...,ψm:R→R\psi_1,...,\psi_m:\R\rightarrow \Rψ1,...,ψm:R→R满足当且仅当u≤0u\leq 0u≤0时ψi(u)≤0;ψm1,...,ψmp:R→R\psi_i(u)\leq 0;\psi_{m1},...,\psi_{mp}:\R\rightarrow \Rψi(u)≤0;ψm1,...,ψmp:R→R满足当且仅当u0u0u0时ψi(u)0\psi_i(u)0ψi(u)0。我们定义函数f~i\tilde f_if~i和h~i\tilde h_ih~i为复合函数 f~i(x)ψ(fi(x)),i0,...,mh~i(x)ψmi(hi(x)),i1,...,p\tilde f_i(x)\psi(f_i(x)),i0,...,m\qquad \tilde{h}_i(x)\psi_{mi}(h_i(x)),i1,...,p f~i(x)ψ(fi(x)),i0,...,mh~i(x)ψmi(hi(x)),i1,...,p 显然问题 与标准形式式1等价且同解。并且式2是ψ\psiψ为线性函数的一种特例。 例最小函数和最小范数平方问题 min∣∣AX−b∣∣2\min ||AX-b||_2 min∣∣AX−b∣∣2 上述问题是一个无约束的优化问题等价于最小化二范数的平方。 min∣∣AX−b∣∣22\min ||AX-b||_2^2 min∣∣AX−b∣∣22 原因是原函数在实数域内单调递增。 松弛变量
fi(x)≤0f_i(x)\leq 0fi(x)≤0等价于∃si≥0,fi(x)si(x)0\exist s_i\geq 0,f_i(x)s_i(x)0∃si≥0,fi(x)si(x)0将问题进行转换得到 引入sis_isi后问题就不仅是关于x的优化问题了。对于问题的凸性需要对变量x和s同时验证。
进行松弛后将变量的维数和约束都增加了。但有些时候会通过松弛变量将问题的结构转换为更加通用的结构。
等式约束的消除
例等式约束的消除 对于优化问题而言约束的数目越多优化越复杂所以消除等式约束是降低优化问题难度的一个重要方法。 {hi(x)0,i1,...,p}(3)\{h_i(x)0,i1,...,p\}\tag{3} {hi(x)0,i1,...,p}(3)
是一组方程。假设我们能够得到这组方程的解那么用一组参数z∈Rkz\in \R^kz∈Rk来显式地参数化等式约束。设函数ϕ:Rk→Rn\phi:\R^k\rightarrow \R^nϕ:Rk→Rn是这样的函数xxx满足式3等价于存在一些z∈Rkz\in\R^kz∈Rk使得 xϕ(z)x\phi(z) xϕ(z) 那么优化问题 与原问题式1等价。求解出zzz后可由xϕ(z)x\phi(z)xϕ(z)得出最优解xxx。 相当于用变量z去表示x然后代入原目标函数和约束中。 等式定义了一组超平面可以表示为特解一组基的形式。 例消除线性等式约束AX−b0AX-b0AX−b0
A∈Rp×nA\in \R^{p\times n}A∈Rp×n是否能找到一组zzz表示X呢
分情况讨论
AX−b0AX-b0AX−b0无解那么原问题无可行解反之令x0x_0x0为等式约束的任意可行解那么通解可以表示为Fzx0Fzx_0Fzx0。即ϕ(z)Fzx0\phi (z)Fzx_0ϕ(z)Fzx0
二、凸优化
标准形式的凸优化问题
凸优化问题是形如 minimizef0(x)subject to fi(x)⩽0,i1,⋯,maixbi,i1,⋯,p(4)\begin{array}{ll} \operatorname{minimize} f_0(x) \\ \text { subject to } f_i(x) \leqslant 0, \quad i1, \cdots, m \\ a_i^xb_i, \quad i1, \cdots, p \end{array}\tag{4} minimize subject to f0(x)fi(x)⩽0,i1,⋯,maixbi,i1,⋯,p(4) 从广义上来说如果目标函数是一个凸函数约束的集合为凸集那么问题就是凸问题。
狭义上的凸问题
目标函数是凸函数不等式约束的函数也是凸函数等式约束函数是仿射函数 在这样的定义下凸优化问题的可行域一定是凸的因为他是问题定义域 D⋂i0mdomfi\mathcal{D}\bigcap_{i0}^m\bold{dom}f_i Di0⋂mdomfi 凸集m个下水平集以及p个超平面的交集。因此在凸优化问题中我们是在一个凸集上极小化一个凸的函数。
若目标函数变为拟凸函数那么该问题成为拟凸优化问题。但如果目标函数是凹函数或者其他函数那么我们统一称之为非凸优化问题。 例 minf0(x)x12x22s.t.{f1(x):x11x22≤0h1(x):(x1x2)20\min f_0(x)x_1^2x_2^2\\ \text{s.t.}\begin{cases}f_1(x):\frac{x_1}{1x_2^2}\leq 0\\ h_1(x):(x_1x_2)^20\end{cases} minf0(x)x12x22s.t.{f1(x):1x22x1≤0h1(x):(x1x2)20 表面上看不是狭义的凸问题可以转换为下面的形式 如果等式约束是一个放射约束那么可利用等式约束对问题进行降维 一般来说不对问题进行降维有必要的情况才会进行降维。
凹最大化问题
约束不变若目标是最大化一个凹函数那么等价于最小化一个凸函数即该情况下仍是凸优化问题。 maxf0(x)⇔min−f0(x)\max f_0(x)\Leftrightarrow \min -f_0(x) maxf0(x)⇔min−f0(x) 同理如果f0(x)f_0(x)f0(x)是拟凹的那么最大化该问题被称为拟凹的。
局部最优解与全局最优解
对于凸问题来说局部最优解一定是全局最优解。
局部最优∃R0,f0(x)inf{f0(z)∣z可行,x可行,∣∣x−z∣∣≤R}\exist R0,f_0(x)\inf \{f_0(z)|z可行,x可行,||x-z||\leq R\}∃R0,f0(x)inf{f0(z)∣z可行,x可行,∣∣x−z∣∣≤R}
证明
设xxx不是全局最优解即∃y\exists y∃y可行f0(y)f0(x)f_0(y) f_0(x)f0(y)f0(x)。
又因为xxx是局部最优的那么∣∣y−x∣∣2R||y-x||_2 R∣∣y−x∣∣2R那么可以构造出一个新的解z(1−θ)xθy,θR2∣∣y−x∣∣2∈[0,12]z(1-\theta)x\theta y,\theta\frac{R}{2||y-x||_2}\in[0,\frac{1}{2}]z(1−θ)xθy,θ2∣∣y−x∣∣2R∈[0,21]所以z是x和y的凸组合。又因为可行解集一定是个凸集所以z一定在可行解集内即zzz可行。
又因为f0(x)f_0(x)f0(x)是凸函数故 f0(z)≤θf0(x)(1−θ)f0(y)∣∣z−x∣∣2θ∣∣x−y∣∣2R2(2.2)f_0(z)\leq \theta f_0(x)(1-\theta)f_0(y)\\ ||z-x||_2\theta ||x-y||_2\frac{R}{2}\tag{2.2} f0(z)≤θf0(x)(1−θ)f0(y)∣∣z−x∣∣2θ∣∣x−y∣∣22R(2.2) 即zzz在x的邻域内。因为x是局部最优解故f0(x)f0(z)f_0(x)f_0(z)f0(x)f0(z)。
即综上所述需要满足下面的条件 f0(y)f0(x)f0(x)f0(z)f_0(y)f_0(x)\\ f_0(x)f_0(z) f0(y)f0(x)f0(x)f0(z) 即f f0(y)f0(x)f0(z)f_0(y)f_0(x)f_0(z) f0(y)f0(x)f0(z) 与式2.2矛盾。故x一定是全局最优解。
图形表示 可微函数f0f_0f0的最优性准则
可微凸问题目标函数的一阶条件 f0(y)≥f0(x)∇f0T(x)⋅(y−x)∀x,y∈domff_0(y)\geq f_0(x)\nabla f_0^T(x)\cdot (y-x)\qquad \forall x,y\in \bold{dom}f f0(y)≥f0(x)∇f0T(x)⋅(y−x)∀x,y∈domf 问题的可行域 Xf{x∣fi(x)≤0,i1,...,m;hi(x)0,i1,...,p}X_f\{x|f_i(x)\leq 0,i1,...,m;h_i(x)0,i1,...,p\} Xf{x∣fi(x)≤0,i1,...,m;hi(x)0,i1,...,p} 那么X∗∈XfX^*\in X_fX∗∈Xf最优等价于 ∇f0T(X∗)(y−X∗)≥0(2.3)\nabla f_0^T(X^*)(y-X^*)\geq 0\tag{2.3} ∇f0T(X∗)(y−X∗)≥0(2.3) 约束仅为等式约束
minf0(x)domf0Rns.t.AXb\min f_0(x)\\ \bold{dom}f_0\R^n\\ s.t. AXb minf0(x)domf0Rns.t.AXb
若∃x,AXb\exist x,AXb∃x,AXb那么X最优等价于∀y,Ayb,∇f0T(x)(y−x)≥0\forall y,Ayb,\nabla f_0^T(x)(y-x)\geq 0∀y,Ayb,∇f0T(x)(y−x)≥0成立。
又因为AXbAybAXbAybAXbAyb那么yXv,v∈N(A)yXv,v\in \mathcal{N}(A)yXv,v∈N(A)即A的化零空间中的一个向量。 y是方程组的解等于通解v加上特解X 因此最优性条件可表示为 ∇f0(x)v≥0,∀v∈N(A)\nabla f_0(x)v\geq 0,\forall v\in \mathcal N(A) ∇f0(x)v≥0,∀v∈N(A) 那么只有两种情况 子空间退化为零点那么yXyXyX即方程只有一个解矩阵A是可逆的。 ∇f0(x)\nabla f_0(x)∇f0(x)正交于子空间
约束仅为非负约束互补条件
minf0(x)s.t.x≥0\min f_0(x)\\ s.t.x\geq 0 minf0(x)s.t.x≥0
若∃x≥0\exist x\geq 0∃x≥0xxx最优等价于∀y≥0\forall y\geq 0∀y≥0 ∇f0T(x)(y−x)≥0即∇f0T(x)y−∇f0T(x)x≥0\nabla f_0^T(x)(y-x)\geq 0\\ 即\nabla f_0^T(x)y-\nabla f_0^T(x)x\geq 0 ∇f0T(x)(y−x)≥0即∇f0T(x)y−∇f0T(x)x≥0
①若∇f0T(x)≤0\nabla f_0^T(x)\leq 0∇f0T(x)≤0则∇f0T(x)y\nabla f_0^T(x)y∇f0T(x)y必可以取无穷小则必有∇f0(x)≥0\nabla f_0(x)\geq 0∇f0(x)≥0② ∀y\forall y∀y均有∇f0(x)T(y−x)≥0\nabla f_0(x)^T(y-x)\geq 0∇f0(x)T(y−x)≥0当y0时∇f0T(x)x≤0\nabla f_0^T(x)x\leq 0∇f0T(x)x≤0③ ∇f0T(x)≥0,x≥0\nabla f_0^T(x)\geq 0,x\geq 0∇f0T(x)≥0,x≥0则∇f0T(x)x≥0\nabla f_0^T(x)x\geq 0∇f0T(x)x≥0
由②和③可知f0T(x)x0f_0^T(x)x0f0T(x)x0
结论如果x是最优解那么一定满足下面的条件 {x≥0∇f0(x)≥0(∇f0(x))ixi0\begin{cases}x\geq 0\\ \nabla f_0(x)\geq 0\\ (\nabla f_0(x))_ix_i0\end{cases} ⎩⎨⎧x≥0∇f0(x)≥0(∇f0(x))ixi0 该条件称为互补条件。
几何解释
