中科大-凸优化 笔记（lec1）-综述、简介优化问题
本文共 2148 字，大约阅读时间需要 7 分钟。
全部笔记的汇总贴（视频也有传送门）：
一、优化问题的一般形式
优化/数学规划（optimization/Mathematical Programming）
从一个可行解的集合中，寻找最优的元素。从数学上看，任意一个优化问题都可以写成这样的形式，
min x f 0 ( x ) s u b j e c t t o f i ( x ) ≤ b i , i = 1 , ⋯ , m x = [ x 1 , ⋯ , x n ] T 优 化 变 量 （ O p t i m i z a t i o n V a r i a b l e ） f 0 : R n → R 目 标 函 数 （ O b j e c t i v e F u n c t i o n ） f i : R n → R 不 等 式 约 束 （ I n e q u a l i t y C o n s t r a n t ） x ∗ 最 优 （ o p t i m a l ） ⟺ ∀ z , z ∈ { f i ( z ) ≤ b i , i = 1 , ⋯ , m } （ 可 行 解 集 f e a s i b l e s e t ） f 0 ( z ) ≥ f 0 ( x ∗ ) \min_x f_0(x)\\subject\;to\;f_i(x)\le b_i,i=1,\cdots,m\\x=[x_1,\cdots,x_n]^T\;\;优化变量（Optimization\;Variable）\\f_0:\R^n\rightarrow\R\;\;目标函数（Objective\;Function）\\f_i:\R^n\rightarrow\R\;\;不等式约束（Inequality\;Constrant）\\x^*\;最优（optimal）\Longleftrightarrow \forall z,z\in\{f_i(z)\le b_i,i=1,\cdots,m\}（可行解集\;feasible\;set）\;\;f_0(z)\ge f_0(x^*) xminf0(x)subjecttofi(x)≤bi,i=1,⋯,mx=[x1,⋯,xn]T优化变量（OptimizationVariable）f0:Rn→R目标函数（ObjectiveFunction）fi:Rn→R不等式约束（InequalityConstrant）x∗最优（optimal）⟺∀z,z∈{ fi(z)≤bi,i=1,⋯,m}（可行解集feasibleset）f0(z)≥f0(x∗)
- 数据拟合问题
y = a x 2 + b x + c m i n i m i z e ε 1 2 + ε 2 2 + ⋯ + ε n 2 ε i = y i − ( a x i 2 + b x i + c ) , i = 1 , ⋯ , n y=ax^2+bx+c\\minimize\;\;\varepsilon^2_1+\varepsilon^2_2+\cdots+\varepsilon^2_n \\\varepsilon_i=y_i-(ax_i^2+bx_i+c),i=1,\cdots,n y=ax2+bx+cminimizeε12+ε22+⋯+εn2εi=yi−(axi2+bxi+c),i=1,⋯,n
（后面讲的都是专业不想关的例子，就直接跳过了…线性二次调节器、多用户能量控制问题、极大化网络流量、图像处理（TV范数）、超大规模集成电路设计）
- 最短路径问题
{ V , E } \{V,E\} { V,E} min ∑ ( i . j ) ∈ E w i j x i j s . t . x i j = 0 o r 1 ( 是 否 选 择 边 ( i , j ) ) ( x i j ≥ 0 ) ∑ j x i j − ∑ j x j i = ( 出 边 − 进 边 = ) { 1 i = s ( 源 结 点 ) − 1 i = d ( 目 标 结 点 ) 0 o t h e r w i s e \min\sum_{(i.j)\in E}w_{ij}x_{ij}\\s.t.\;\;x_{ij}=0\;or\;1(是否选择边(i,j))(x_{ij}\ge0)\\\sum_jx_{ij}-\sum_jx_{ji}=(出边-进边=)\left\{\begin{matrix}1\;\;i=s(源结点)\;\;\;\;\;\;\;\\-1\;\;i=d(目标结点)\\0\;\;otherwise\;\;\;\;\;\;\;\;\;\; \end{matrix}\right. min(i.j)∈E∑wijxijs.t.xij=0or1(是否选择边(i,j))(xij≥0)j∑xij−j∑xji=(出边−进边=)⎩⎨⎧1i=s(源结点)−1i=d(目标结点)0otherwise
下一章传送门：
转载地址：http://mvpq.baihongyu.com/
你可能感兴趣的文章