$$
\max \ z = c_1x_1 + c_2x_2 + \cdots + c_nx_n \\
\\
s.t. \begin{cases}
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1 \\
a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \le b_2 \\
\cdots \\
a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \le b_m \\
x_1 \ge 0, x_2 \ge 0, \cdots, x_n \ge 0
\end{cases}
$$
用矩阵表示为
$$
\max \ z = c^Tx \\
\\
s.t. \begin{cases}
Ax \le b \\
x \ge 0
\end{cases}
$$
可行域：满足约束条件的所有解构成的集合
可行解：满足约束条件的解
$$
\min f(x), \\
s.t. \begin{cases}
g_i(x) \le 0, i = 1, 2, \cdots, m \\
h_j(x) = 0, j = 1, 2, \cdots, p
\end{cases}
$$
使用向量表示：
$$
\min f(x) \\
s.t. \begin{cases}
G(x) \le 0 \\
H(x) = 0
\end{cases} \\
G(x) = [g_1(x), g_2(x), \cdots, g_p(x)]^T \\
H(x) = [h_1(x), h_2(x), \cdots, h_q(x)]^T
$$
对于所有满足条件的$x$，其构成的集合称为可行域，或者约束集。
$$ K={x \in R^n | g_i(x) \le 0, i=1,2,\cdots,p; h_j(x)=0, j=1,2,\cdots,q} $$
对于$x \in K$，$x$称为可行解。
根据一般形式，无约束线性规划问题可以表示为：
$$ \min f(x) , x \in R^n $$
梯度：对于一元函数$f(x)$，其梯度为$f'(x)$，对于多元函数$f(x_1, x_2, \cdots, x_n)$，其梯度为：
$$ \nabla f(x) = \left[ \frac{\partial f(x)}{\partial x_1}, \frac{\partial f(x)}{\partial x_2}, \cdots, \frac{\partial f(x)}{\partial x_n} \right] $$
对于一个局部极小值点$x^$，有$\nabla f(x^) = 0$。
Hessian矩阵：对于多元函数$f(x_1, x_2, \cdots, x_n)$，其Hessian矩阵为：
$$ \nabla^2 f(x) = \begin{bmatrix}
\frac{\partial^2 f(x)}{\partial x_1^2} & \frac{\partial^2 f(x)}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f(x)}{\partial x_1 \partial x_n} \\
\frac{\partial^2 f(x)}{\partial x_2 \partial x_1} & \frac{\partial^2 f(x)}{\partial x_2^2} & \cdots & \frac{\partial^2 f(x)}{\partial x_2 \partial x_n} \\
\vdots & \vdots & \ddots & \vdots \\
\frac{\partial^2 f(x)}{\partial x_n \partial x_1} & \frac{\partial^2 f(x)}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f(x)}{\partial x_n^2}
\end{bmatrix} $$
无约束优化问题存在局部最优解的充分条件是：目标函数$f(x)$在$x^$处连续可微，且$\nabla f(x^) = 0$，$\nabla^2 f(x^)$是正定矩阵。此时，$x^$是$f(x)$的局部极小值点。
正定矩阵：对于一个$n \times n$的矩阵$A$，如果对于任意非零向量$x \in R^n$，都有$x^TAx > 0$，则称$A$是正定矩阵。
二次型：对于一个$n$元二次齐次多项式$f(x) = x^TAx$，如果$A$是正定矩阵，则称$f(x)$是正定二次型。
简单证明：
对于一个$n$元二次齐次多项式$f(x) = x^TAx$，有
$$ f(x) = \sum_{i=1}^n \sum_{j=1}^n a_{ij}x_ix_j $$
对于一个非零向量$x = [x_1, x_2, \cdots, x_n]^T$，有
$$ x^TAx = \sum_{i=1}^n \sum_{j=1}^n a_{ij}x_ix_j = \sum_{i=1}^n \sum_{j=1}^n a_{ij}x_ix_j + \sum_{i=1}^n \sum_{j=1}^n a_{ji}x_jx_i = \sum_{i=1}^n \sum_{j=1}^n a_{ij}x_ix_j + \sum_{i=1}^n \sum_{j=1}^n a_{ij}x_ix_j = 2 \sum_{i=1}^n \sum_{j=1}^n a_{ij}x_ix_j $$
对于一个正定矩阵$A$，有$x^TAx > 0$。
对于有约束非线性规划问题：
$$ \min f(x) \\
s.t. \begin{cases}
h_i(x) = 0, i = 1, 2, \cdots, p \\
x \in R^n
\end{cases} $$
可以通过拉格朗日乘子法将其转化为无约束非线性规划问题。
拉格朗日定理：对于在可行点 $x^*$ 处连续可微的函数 $f(x)$ ，向量组 $h(x) = [h_1(x), h_2(x), \cdots, h_p(x)]^T$ 线性无关，令
$$ L(x, \lambda) = f(x) + \lambda^T h(x) $$
其中 $\lambda = [\lambda_1, \lambda_2, \cdots, \lambda_p]^T$ 。若 $x^$ 是 $f(x)$ 在约束条件下的极值点，则存在 $\lambda^ = [\lambda_1^, \lambda_2^, \cdots, \lambda_p^*]^T$ 使得
$$ \nabla L(x^, \lambda^) = 0 $$
即
$$ \nabla f(x^) + \sum_{i=1}^p \lambda_i^ \nabla h_i(x^*) = 0 $$
用人话讲就是，如果 $x^$ 是 $f(x)$ 在约束条件下的极值点，那么 $f(x)$ 在 $x^$ 处的梯度 $\nabla f(x^)$ 与约束条件 $h_i(x)$ 在 $x^$ 处的梯度 $\nabla h_i(x^*)$ 的线性组合为 $0$。
对于有约束非线性规划问题，可以通过罚函数法将其转化为无约束非线性规划问题。即是说，对于那个所需求极值点的函数，加上一个惩罚项，使得在约束条件下，偏离约束条件的程度越大，惩罚越大。因而可以将结果“纠正”到约束条件下。
凸集：对于一个集合 $C$ ，如果对于任意两个点 $x_1, x_2 \in C$ ，连接 $x_1, x_2$ 的线段上的任意一点 $x$ 也在 $C$ 中，则称 $C$ 是凸集。
凸函数：对于一个函数 $f(x)$ ，如果对于任意两个点 $x_1, x_2$ ，有
$$ f(\theta x_1 + (1-\theta)x_2) \le \theta f(x_1) + (1-\theta)f(x_2) $$
其中 $0 \le \theta \le 1$ ，则称 $f(x)$ 是凸函数。
直观上，凸函数的图像是上凸的，即对于任意两点 $x_1, x_2$ ，连接 $x_1, x_2$ 的线段上的任意一点 $x$ 都在 $f(x)$ 的上方或者在 $f(x)$ 上。
对于凸函数的判定，有以下几个方法：
- 一阶条件：对于任意 $x_1, x_2$ ，有 $f(x_2) \ge f(x_1) + \nabla f(x_1)^T(x_2 - x_1)$
- 二阶条件：如果 $f(x)$ 在 $\Omega$ 上二次可微，且 $\nabla^2 f(x)$ 在 $\Omega$ 上处处是半正定矩阵，则 $f(x)$ 是凸函数。
人话解释：对于半正定矩阵，有结论：对于任意非零向量 $x$ ，都有 $x^TAx \ge 0$ 。对于一元函数很显然，累加之后，可以得到二阶导大于等于零。则 $f(x)$ 是凸函数。多元函数同理。
凸规划问题的：
-
$f(x)$ 是凸函数
- g_i(x) 是凸函数
- h_j(x) 是线性函数
对于某个非线性规划问题，引入拉格朗日乘子 $\lambda$ 和 $\mu$：
$$ L(x, \lambda, \mu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \mu_j h_j(x) $$
对于局部最优解 $x^$ ，且其所有起作用的梯度 $\nabla g_i(x^)$ 和 $\nabla h_j(x^)$ 线性无关，则存在 $\lambda^$ 和 $\mu^*$ 使得：
$$ \begin{cases}
\nabla L(x^, \lambda^, \mu^) = 0 \
\lambda_i^ \ge 0, i = 1, 2, \cdots, m \
\lambda_i^* g_i(x^*) = 0, i = 1, 2, \cdots, m
\end{cases} $$
满足上式称为库恩-塔克点；所有的库恩-塔克点都是全局最优解。