【凸优化学习笔记1】什么是优化、优化的数学表达形式、优化问题的分类 |
您所在的位置:网站首页 › 优化照片什么意思 › 【凸优化学习笔记1】什么是优化、优化的数学表达形式、优化问题的分类 |
参考资料: 1.凌青老师的凸优化课(b站) 2.Stephen Boyd的《凸优化》中译本(清华大学出版社) 文章目录 什么是优化(Optimization)优化问题的数学表达形式举例1举例2(数据拟合问题) 优化问题的分类线性规划、非线性规划凸规划、非凸规划其他分类 什么是优化(Optimization)优化(optimization)又叫数学规划(Mathematical Programming)。 优化:从一个可行解的集合中,寻找出最优的元素。 三要素缺一不可:可行解的集合、寻找的方法、有最优的元素。 优化问题的数学表达形式minimize f 0 ( x ) subject to f i ( x ) ⩽ b i , i = 1 , ⋯ , m \begin{array}{ll} \operatorname{minimize} & f_{0}(x) \\ \text {subject to} & f_{i}(x) \leqslant b_{i}, \quad i=1, \cdots, m \end{array} minimizesubject tof0(x)fi(x)⩽bi,i=1,⋯,m 其中: x x x 称为优化变量(Optimization Variable),是一个向量 x = ( x 1 , ⋯ , x n ) x=\left(x_{1}, \cdots, x_{n}\right) x=(x1,⋯,xn) f 0 ( x ) f_{0}(x) f0(x) 称为目标函数(Objective Function),它是一个n维空间到1维空间的映射,即 f 0 : R n → R f_{0}: \mathbf{R}^{n} \rightarrow \mathbf{R} f0:Rn→R。 f i ( x ) f_{i}(x) fi(x) 是一组不等式约束(Inequality Constraint), f i : R n → R f_{i}: \mathbf{R}^{n} \rightarrow \mathbf{R} fi:Rn→R 我们的目标是找到一个 x ⋆ x^{\star} x⋆,是一个最优解(Optimal)。 如果 x ⋆ x^{\star} x⋆是一个Optimal,那么它等价于: 存在任意向量 z z z,满足所有的约束条件 z ∈ { f 1 ( z ) ⩽ b 1 , ⋯ , f m ( z ) ⩽ b m } z\in\{ f_{1}(z) \leqslant b_{1}, \cdots, f_{m}(z) \leqslant b_{m}\} z∈{f1(z)⩽b1,⋯,fm(z)⩽bm}的情况下,有: f 0 ( z ) ⩾ f 0 ( x ⋆ ) f_{0}(z) \geqslant f_{0}\left(x^{\star}\right) f0(z)⩾f0(x⋆) 上面 { f 1 ( z ) ⩽ b 1 , ⋯ , f m ( z ) ⩽ b m } \{ f_{1}(z) \leqslant b_{1}, \cdots, f_{m}(z) \leqslant b_{m}\} {f1(z)⩽b1,⋯,fm(z)⩽bm}集合称为可行解集(feasible set)。 最优解同样可能存在最优解集,即不止有一个最优解。 举例1以一元函数举例,图: 求[-1,1]区间内函数最小值。 转化为优化问题: 目标函数: f 0 ( x ) = x 2 + 1 f_{0}(x)=x^2+1 f0(x)=x2+1 可行解集: x ⩽ 1 , − x ⩽ 1 x\leqslant1,-x\leqslant1 x⩽1,−x⩽1 求最优解(解得 x = 0 x=0 x=0) 举例2(数据拟合问题)有一组样本点(二维坐标系为例),需要拟合出一条线。 我们设这条线为一个二项式 y = a x 2 + b x + c y=ax^2+bx+c y=ax2+bx+c,各项的系数a、b、c为待估参数,设为向量 w = ( a , b , c ) w=(a,b,c) w=(a,b,c)。 目标函数: f 0 ( w ) = ∑ i = 1 n [ y i − ( a x i 2 + b x i + c ) ] 2 f_{0}(w)=\sum_{\mathrm{i}=1}^{\mathrm{n}} [y_i-(ax_i^2+bx_i+c)]^2 f0(w)=∑i=1n[yi−(axi2+bxi+c)]2, i i i为各样本点。 求最优解,这是一个典型的最小二乘问题。 优化问题的分类 线性规划、非线性规划若优化问题中,目标函数和约束函数 f 0 , . . . , f m f_0,...,f_m f0,...,fm 都是线性函数,即对任意的 x , y ∈ R n x,y \in\mathbf{R}^{n} x,y∈Rn 和 α , β ∈ R \alpha,\beta\in\mathbf{R} α,β∈R,都有: f i ( α x + β y ) = α f i ( x ) + β f i ( y ) , i = 0 , 1 , . . . , m f_{i}(\alpha x+\beta y)=\alpha f_{i}(x)+\beta f_{i}(y),i=0,1,...,m fi(αx+βy)=αfi(x)+βfi(y),i=0,1,...,m 那么这样的优化问题称为线性规划。 如果 f 0 , . . . , f m f_0,...,f_m f0,...,fm 中有一个不是线性函数,那么该问题称为非线性规划。 给个线性规划的图例:
曾经人们把线性规划和非线性规划问题定义成简单问题和困难问题,后面发现把凸规划定义成简单问题,非凸规划定义成困难问题更好。 任意的线性规划问题一定是凸规划。凸规划可看成线性规划的扩展。 如果目标函数和约束函数都是凸函数,即对任意的 x , y ∈ R n x,y \in\mathbf{R}^{n} x,y∈Rn 和 α , β ∈ R \alpha,\beta\in\mathbf{R} α,β∈R,且满足 α + β = 1 , α ⩾ 0 , β ⩾ 0 \alpha+\beta=1,\alpha\geqslant0,\beta\geqslant0 α+β=1,α⩾0,β⩾0,下列不等式成立: f i ( α x + β y ) ⩽ α f i ( x ) + β f i ( y ) , i = 0 , 1 , . . . , m f_{i}(\alpha x+\beta y)\leqslant\alpha f_{i}(x)+\beta f_{i}(y),i=0,1,...,m fi(αx+βy)⩽αfi(x)+βfi(y),i=0,1,...,m 这样的函数即为凸函数。 目标函数和约束函数都是凸函数的问题就是凸规划问题,也叫凸优化问题。 以上可见凸性是较线性更为一般的性质。因为它只需要满足不等式就行了。仅仅加上了一个α和β的取值限制。 其他分类①光滑优化问题、非光滑优化问题 光滑和非光滑针对目标函数 f 0 f_0 f0而言。 光滑函数意味目标函数 f 0 f_0 f0在定义域上所有点都可微。 ②连续优化问题、非连续优化问题 正对可行域而言。 如果可行域是连续的,为连续优化问题(如上面的五边形图)。 可行域是离散的,即为非连续优化问题。离散问题一般都是困难问题。 ③单目标问题、多目标问题 对于多目标问题,比如我们想要优化两个目标函数: minimize f 1 ( x ) , f 2 ( x ) \operatorname{minimize} f_{1}(x), f_{2}(x) minimizef1(x),f2(x) 这就是多目标问题。 对于
f
1
,
f
2
f_{1}, f_{2}
f1,f2,我们常可画出两个函数值的曲线: 这条线又称帕累托曲面(Pareto front),我们难以找到一个点让两者最优,一般需要找个折中点。 所以我们一般需要将两者取加权,将多目标转化成单目标问题: minimize α 1 f 1 ( x ) + α 2 f 2 ( x ) \operatorname{minimize} \alpha_1 f_{1}(x)+\alpha_2 f_{2}(x) minimizeα1f1(x)+α2f2(x) 这只是一种解决方法,可能不一定有效。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |