$min\ \ f(x), \\ s.t.\ \ x \in \chi \tag{1.1.1}$
其中：
$x=(x_1,x_2,\cdots,x_n)^T \in \mathbb{R}^n$ 是决策变量
$f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是目标函数
$\chi \subseteq \mathbb{R}^n$ 是约束集合或可行域，可行域包含的点，称为可行解或可行点，记号：$s.t.$ 是 $subject\ to$ 的缩写，专指约束条件
当 $\chi = \mathbb{R}^n$ 时，问题 $(1.1.1)$ 称为无约束优化问题
集合 $\chi$
约束函数 $c_i(x):\mathbb{R}^n \rightarrow \mathbb{R},\ \ i=1,2,\cdots,m+1$
具体形式：
$\chi = \{ x \in \mathbb{R}^n |\ c_i(x) \leq 0, i=1,2,\cdots,m, \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ c_i(x)=0,i=m+1,m+2,\cdots,m+l \}$
在所有满足约束条件的决策变量中，使目标函数取最小值的变量 $x^{*}$ 称为优化问题 $(1.1.1)$ 的最优解，即对任意 $x \in \chi$ 都有 $f(x) \geq f(x^{*})$
如果我们求解在约束集合 $\chi$ 上目标函数 $f(x)$ 的最大值，则问题 $(1.1.1)$ 的“$min$”替换为“$max$”．
当目标函数的最小 (最大）值不存在时，我们便关心其下（上）确界，即将问题 $(1.1.1)$ 中的“$min(max)$”改为“$inf(sup)$”。
线性方程组求解问题：
$$Ax=b \tag{1.2.1}$$其中，向量 $x \in \mathbb{R}^n, b\in \mathbb{R}^m$，矩阵 $A\in \mathbb{R}^{m\times n}$
且向量 $b$ 的维数远小于向量 $x$ 的维数，即 $m\ll n$
在自然科学和工程中常常遇到已知向量 $b$ 和矩阵 $A$，想要重构向量 $x$ 的问题
$\color{red}{tips}:$
$\color{red}{tips}:$
$\color{red}{tips}:$
$\color{red}{tips}:$
$\color{red}{tips}:$
$L_0$ 范数、$L_1$ 范数与稀疏
$L1$ 范数是什么？它为什么可以实现稀疏？
既然 $L_0$ 可以实现稀疏，为什么不用 $L_0$ ，而要用 $L_1$ 呢？
示例：
$\min\limits_{x\in \mathbb{R}^n} \ \ ||x||_0, \\ s.t.\ \ Ax = b. \tag{1.2.2}$
其中 $||x||_0$ 是指 $x$ 中非零元素的个数
$\min\limits_{x\in \mathbb{R}^n} \ \ ||x||_1, \\ s.t.\ \ Ax = b. \tag{1.2.3}$
定义 $ℓ_1$ 范数：$||x||_1 = \sum\limits_{i=1}^{n}{|x_i|}$，并将其替换到问题 $(1.2.2)$ 当中，得到另一个形式上非常相似的问题（又称 $ℓ_1$ 范数优化问题，基追踪问题）：
可以从理论上证明：若 $A,b$ 满足一定的条件，向量 $u$ 也是 $ℓ_1$ 范数优化问题 $(1.2.3)$ 的唯一最优解．
虽然问题 $(1.2.3)$ 仍没有显式解，但与问题 $(1.2.2)$ 相比难度已经大大降低．
$\min\limits_{x\in \mathbb{R}^n} \ \ ||x||_2, \\ s.t.\ \ Ax = b. \tag{1.2.4}$
$||x||_2 = \bigg (\sum\limits_{i=1}^{n}{x_i^2}\bigg )^{\frac{1}{2}}$
问题 $(1.2.4)$ 实际上就是原点到仿射集 $Ax = b$ 的投影。遗憾的是，$u$ 并不是问题 $(1.2.4)$ 的解
这时因为 $ℓ_1$ 范数优化问题的解具有稀疏性而 $ℓ_2$ 范数优化问题的解不具有该性质
$\min\limits_{x\in \mathbb{R}^n} \ \ \ \ \mu ||x||_1 + \frac{1}{2}||Ax - b||_2^2 \tag{1.2.5}$
其中 $µ > 0$ 是给定的正则化参数。问题 $(1.2.5)$ 又称为 $LASSO（least\ absolute\ shrinkage\ and\ selection\ operator）$
低秩矩阵恢复 $（low\ rank\ matrix\ completion）$
$\min\limits_{X\in \mathbb{R}^{m\times n}} \ \ \ \ \ \ \ rank(X), \\ s.t.\ \ X_{ij} = M_{ij}. (i,j)\in \Omega \tag{1.3.1}$
$\min\limits_{X\in \mathbb{R}^{m\times n}} \ \ \ \ \ \ \ ||X||_{*}, \\ s.t.\ \ X_{ij} = M_{ij}. (i,j)\in \Omega \tag{1.3.2}$
矩阵 $X$ 的核范数 $（nuclear\ norm）$： $||X||_∗ = \sum\limits_{i}\sigma_i(X)$
问题 $(1.3.2)$ 是一个凸优化问题，并且在一定条件下它与问题 $(1.3.1)$ 等价
考虑到观测可能出现误差，对于给定的参数 $µ > 0$，我们也写出该问题的二次罚函数形式：
$\min\limits_{x\in \mathbb{R}^{m\times n}} \ \ \ \ \mu ||x||_{*} + \frac{1}{2} \sum\limits_{(i,j)\in \Omega}(X_{ij}-M_{ij})^2 \tag{1.3.3}$
令参数 $x = (x^{(1)} ,x^{(2)} ,\cdots ,x^{(L+1)})$ 表示网络中所有层之间的权重
则在第 $l$ 隐藏层中，第 $i$ 个单元 $(i>1$，当 $l = L + 1$ 时可取为 $i ⩾ 1)$ 计算输出信息 $y_{i}^{(l)}$ 为:
这里函数 $t(·)$ 称为激活函数，常见的类型有
整个过程可以描述为 $$y^{(0)} \stackrel{x^{1}}{\longrightarrow} z^{(1)} \stackrel{t}{\longrightarrow} y^{(1)} \stackrel{x^{2}}{\longrightarrow} \cdots \stackrel{t}{\longrightarrow} y^{(L+1)}$$
多层感知机的每一层输出实际就是由其上一层的数值作线性组合再逐分量作非线性变换得到的
若选择平方误差为损失函数，则我们得到多层感知机的优化模型：
$\min\limits_{x} \sum\limits_{i=1}^{m} || h(a_i;x) - b_i||_2^2 + \lambda r(x), \tag{1.4.3}$
其中
卷积神经网络 $（convolutional\ neural\ network，CNN）$ 是一种深度前馈人工神经网络，专门用来处理如时间序列数据或是图像等网格数据．
卷积是两个变量在某范围内相乘后求和的结果
与全连接网络-相邻两层之间的节点都是相连或相关的 不同，卷积神经网络的思想是通过局部连接以及共享参数的方式来大大减少参数量，从而减少对数据量的依赖以及提高训练的速度．
典型的 $CNN$ 网络结构通常由一个或多个
组成．
给定一个二维图像 $I\in \mathbb{R}^{n\times n}$ 和卷积核 $K\in \mathbb{R}^{k\times k}$ ，我们定义一种简单的卷积操作 $S = I ∗ K$，它的元素是 $$S_{i,j} = ⟨ I(i:i + k − 1,j:j + k−1) ,K⟩ , \tag{1.4.4}$$
其中
两个矩阵 $X,Y$ 的内积是它们相应元素乘积之和，即 $⟨X,Y⟩ = \sum\limits_{i,j}X_{ij}Y_{ij}$，
$I(i:i+k−1,j:j+k−1)$ 是矩阵 $I$ 从位置 $(i,j)$ 开始的一个 $k\times k$ 子矩阵．
给定一个训练集 $D = \{\{ a_1 ,b_1 \} , \{ a_2 ,b_2 \} , ··· , \{ a_m ,b_m \}\}$ ，
卷积神经网络对应的优化问题的形式仍可套用 $(1.4.3)$，
在实际中离散优化问题往往比连续优化问题更难求解．实际中的离散优化问题往往可以转化为一系列连续优化问题来进行求解．
可以通过将约束$（ \chi \neq \mathbb{R}^n ）$ 罚到目标函数上转化为无约束问题，所以在某种程度上，约束优化问题就是无约束优化问题．
很多约束优化问题的求解也是转化为一系列的无约束优化问题来做，常见方式有增广拉格朗日函数法、罚函数法等．
但约束优化问题的理论以及算法研究仍然是非常重要的，因为借助于约束函数，我们能够更好地描述可行域的几何性质，进而更有效地找到最优解
随机优化问题是指目标或者约束函数中涉及随机变量而带有不确定性的问题
不像确定性优化问题中目标和约束函数都是确定的，随机优化问题中总是包含一些未知的参数．
随机优化问题的目标函数是关于一个未知参数的期望的形式
因为参数的未知性，实际中常用的方法是通过足够多的样本来逼近目标函数，得到一个新的有限和形式的目标函数．
目前，求解线性规划问题最流行的两类方法依然是单纯形法和内点法．
线性规划是指问题 $(1.1.1)$ 中目标函数和约束函数都是线性的．当目标函数和约束函数至少有一个是非线性的，那么对应的优化问题的称为非线性规划问题．
凸优化问题是指最小化问题 $(1.1.1)$ 中的目标函数和可行域分别是凸函数和凸集．
如果其中有一个或者两者都不是凸的，那么相应的最小化问题是非凸优化问题．
因为凸优化问题的任何局部最优解都是全局最优解，其相应的算法设计以及理论分析相对非凸优化问题简单很多．
若问题 $(1.1.1)$ 中的 $min$ 改为 $max$，且目标函数和可行域分别为凹函数和凸集，我们也称这样的问题为凸优化问题．这是因为对凹函数求极大等价于对其相反数（凸函数）求极小．
凸函数是数学函数的一类特征。凸函数就是一个定义在某个向量空间的凸子集C（区间）上的实值函数。
在问题 $(1.1.1)$ 的求解中，我们想要得到的是其全局最优解，但是由于实际问题的复杂性，往往只能够得到其局部最优解
定义 $1.1$ (最优解) 对于可行点 $\overline{x}$ (即 $\overline{x} \in X $ )，定义如下概念：
$(1)$ 如果 $f (\overline{x})\leq f(x), \forall x \in \chi$ ，那么称 $\overline{x}$ 为问题 $(1.1.1)$ 的全局极小解（点），有时也称为（全局）最优解或最小值点；
$(2)$ 如果存在 $\overline{x}$ 的一个 $ε$ 邻域 $N_{ε}(\overline{x})$ 使得$f(\overline{x})\leq f(x) , \forall x \in N_{ε}(\overline{x}) ∩ \chi$ , 那么称 $\overline{x}$ 为问题 $(1.1.1)$ 的局部极小解（点），有时也称为局部最优解；
(3) 进一步地，如果有 $f(\overline{x}) < f(x), ∀x ∈ N_ε(\overline{x})∩X , x \neq \overline{x}$ 成立，则称 $\overline{x}$ 为问题 $(1.1.1)$ 的严格局部极小解（点）．
如果一个点是局部极小解，但不是严格局部极小解，我们称之为非严格局部极小解．
我们想要得到的是其全局最优解，但是由于实际问题的复杂性，往往只能够得到其局部最优解
在给定优化问题之后，我们要考虑如何求解．
根据优化问题的不同形式，其求解的困难程度可能会有很大差别．
对于一个优化问题，如果能用代数表达式给出其最优解，那么这个解称为显式解，
但实际问题往往是没有办法显式求解的，因此常采用迭代算法．
迭代算法的基本思想：
为了使算法能在有限步内终止，一般会通过一些收敛准则来保证迭代停在问题的一定精度逼近解上．
对于无约束优化问题，常用的收敛准则有：
$$\frac{f(x^k)-f^*}{max\{|f^*|,1\}} \leq \varepsilon_{1},\ \ \ ||\nabla f(x^k)|| \leq \varepsilon_{2} \tag{1.5.1} $$其中：
其中：
由于一般情况下事先并不知道最优解，在最优解唯一的情形下一般使用某种基准算法来得到 $x^∗$ 的一个估计，之后计算其与 $x^k$ 的距离以评价算法的性能．
因为约束的存在，我们不能简单地用目标函数的梯度来判断最优性，实际中采用的判别准则是点的最优性条件的违反度
对于一个具体的算法，根据其设计的出发点，我们不一定能得到一个高精度的逼近解．此时，为了避免无用的计算开销，我们还需要一些停机准则来及时停止算法的进行
在算法设计中，一个重要的标准是算法产生的点列是否收敛到优化问题的解．
在设计优化算法时，我们有一些基本的准则或技巧．对于复杂的优化问题，基本的想法是将其转化为一系列简单的优化问题（其最优解容易计算或者有显式表达式）来逐步求解．常用的技巧有：
在设计和比较不同的算时，另一个重要的指标是算法的渐进收敛速度．
与收敛速度密切相关的概念是优化算法的复杂度 $N(ε)$ ，