Note: The lecture from cxt. 对偶问题基础   为什么要构造原问题的对偶问题？  非凸问题NP-hard：对偶问题便于计算分析； 对偶问题解与原问题解的关联； 对偶将一系列约束优化转化成更少的约束优化甚至无约束优化； 对偶提供一些新的解法；    如何构造对偶  拉格朗日对偶 Fenchel对偶    对偶问题与原问题的关系   对偶   对偶不仅适用于连续优化，整数规划等也适用对偶理论；   鲁棒优化、锥优化很需要对偶分析     拉格朗日对偶   拉格朗日函数 L(x,λ,μ)x∈X=f(x)+∑imλigi(x)+∑ilμihi(x), λi≥0L(x...

凸函数定义  在凸集上定义的关系；  几何意义：输入两点凸组合的值在两点函数值的凸组合下方 凹凸关系：一般极大化凹函数问题转化成极小化凸问题；   严格凸：取等，想象输入两点线段上的值，输出等于两点的凸组合，如线性函数，而不是想象函数值水平相等（极特殊情形）；  常见凸函数  线性函数：既是凹函数也是凸函数，常作为非凸的近似 二次函数：xTQx+ax+bx^TQx+ax+bxTQx+ax+b，QQQ半正定 最小二乘∣∣Ax−b∣∣22||Ax-b||^2_2∣∣Ax−b∣∣22​：有ATAA^TAATA半正定 范数：p≥1p\geq 1p≥1，一般在优化问题中，考虑1-范数和2范数较多；  凸...

Note: The lecture from cxt. 引入：凸优化问题  可行域凸集； 局部最优即是全局最优; 最优点处的负梯度方向与凸可行集上任意方向的夹角大于90°，非凸集未必成立；  −∇f(x∗)T(x−x∗)≤0,∀x∈S-\nabla f(x^*)^T(x-x^*)\leq0, \forall x\in S−∇f(x∗)T(x−x∗)≤0,∀x∈S 上式也是最优点成立的等价条件； 基本定义  凸集：集合中两点的连线仍在集合内；  对∀x,y∈C, ∀λ∈[0,1]\forall x,y\in C,\ \forall \lambda\in[0,1]∀x,y∈C,&nbsp...

日

线性规划的解   可行解：满足约束条件和变量非负要求的解 ；   可行域（集）：全体可行解构成的区域（集合）；   最优解：使目标函数取得最值的可行解；   基：线性约束方程组的系数矩阵A∈Rm∗n,m≤nA\in R^{m*n},m\leq nA∈Rm∗n,m≤n的秩为m，则AAA的满秩子阵B∈Rm∗mB\in R^{m*m}B∈Rm∗m为一个基；   基变量   非基变量   基向量   基解：通过一确定的基，令非基变量为0，由约束方程组解出来的基变量，称为基解；   基可行解：满足变量非负条件的基解，基解不一定是基可行解；   可行基：对应于基可行解的基；     图解法   适用二维的...

规划问题的数学模型三要素  决策变量 目标函数 约束条件  线性规划 1. 定义  目标函数式决策变量的线性函数 约束条件是决策变量的线性不等式或线性等式  2. 标准型 max cTxmax\ c^Txmax cTx s.t. Ax=bs.t.\ Ax=bs.t. Ax=b x≥0x\geq 0x≥0  极大化目标 全部约束为等式约束，且右端为非负 决策变量非负  3. 转换成标准型的操作  不等约束的转换：  加松弛变量 减剩余变量 松弛变量和剩余变量在目标函数中的系数为0   乘负号操作  min2max 变量为负 b为负   无约束变量的双替换

标准线性优化问题 max cTxmax\ c^Txmax cTx s.t. Ax=b, A∈Rm∗n,n≥ms.t.\ Ax=b,\ A\in R^{m*n},n\geq ms.t. Ax=b, A∈Rm∗n,n≥m x≥0x\geq 0x≥0 S1：改写问题成标准型  极大化目标问题； 引入松弛变量转换不等式为等式； 对任意取值的变量引入两个非负变量表示；  S2：写出单纯形表  将约束方程组的系数按增广矩阵写出； 最后一行写目标函数的系数，增广右侧为0； 确定基变量（个数为约束方程组行数m）、非基变量（n-m），从基变量中选择pi...

凸集  仿射集：集合内任意两不同点构成的直线集    直线：x=θx1+(1−θ)x2, θ∈Rx=\theta x_1+(1-\theta)x_2,\ \theta\in Rx=θx1​+(1−θ)x2​, θ∈R   从方向向量角度理解直线的形成：如上式，x2x_2x2​作为一点，x1−x2x_1-x_2x1​−x2​构成一个方向向量   OC=αOB+(1−λ)OAOC=\alpha OB+(1-\lambda)OAOC=αOB+(1−λ)OA的推导：点C\mathcal{C}C在线段AB内，点O\mathcal{O}O为直线AB外一点  AC=OC−OA\mathc...

1. 数学优化问题的定义和组成 2. 数学优化问题的求解  一般的优化问题不容易求解：计算时间长，不能总是找到解等因素； 有一些问题容易求解：  最小二乘 线性规划 凸优化    3. 最小二乘问题 min∣∣Ax−b∣∣22min ||Ax-b||_2^2min∣∣Ax−b∣∣22​  有解析解； 可靠有效的算法； 时间复杂度与Am∗nA^{m*n}Am∗n相关，为n2mn^2mn2m； 容易识别最小二乘问题，可以有一些调整，如正则、权重等；  4. 线性规划 min cTxmin\ c^Txmin cTx s.t. aTx≤bs.t.\ a^Tx\leq bs...

概率空间/三元组（Ω\OmegaΩ,F\mathcal{F}F,P\mathcal{P}P）  样本空间：一个非空的任意集合Ω≠∅\Omega\neq \emptysetΩ​=∅，一个实验的所有可能的输出构成的集合； 事件空间：σ\sigmaσ代数，事件是样本空间中一些样本的集合； 概率测度：将事件空间中的事件映射到[0,1][0,1][0,1]；  σ\sigmaσ代数 令Ω≠∅\Omega\neq \emptysetΩ​=∅，P(Ω)\mathbf{P}(\Omega)P(Ω)是其幂集，如果F⊆P(Ω)\mathcal{F}\subseteq\mathbf{P}(\Omega)F⊆P(...

张量 高阶矩阵，可以想象一个长方体  操作  fiber：从一个张量中抽取一个向量的操作 slice：从一个张量中抽取一个矩阵的操作  参考链接

什么是流形 一类光滑的几何曲面 特点  有任意维度 光滑 形状不定  如何理解流形 蚂蚁在一个三维流形上爬，可能是弯曲的，扭曲的，有洞的，但从蚂蚁的观点看，走的是个平面 流形样例 球面就是一个三维流形的例子  哪些不是流形？  立方体（尖点和切边） 两个对接的沙漏 山峰  如何理解流形将一个复杂空间的表示转换到简单空间的表示? 想象将一个三维卷曲的数据，拉到二维平面上表示