仿射集是一种特殊的凸集。

对于一个集合$S$，$S$内任意两点$A$和$B$，如果直线$AB$也在集合$S$内，那么这个集合就是仿射集。

对于一个集合$S$，$S$内任意两点$A$和$B$，如果线段$AB$也在集合$S$内，那么这个集合就是凸集。

仿射集包括直线、超平面等等。

要判断一个（光滑）函数的凹凸性，只要对它求二阶导就可以了，二阶导小于等于0，说明是凹；大于等于0，说明是凸的。。

比如某个函数$f(x)$，我们想知道$\log f(x)$的凹凸性，就只需要对$\log f(x)$求导。

$$\left(\log f(x)\right)''=\left(\frac{f'(x)}{f(x)}\right)'=\frac{f(x)f''(x)-(f'(x))^2}{f^2(x)}$$

因为$f(x)$能够被取log，所以肯定是正数。

如果$f(x)$是凹函数，那么$\log f(x)$还是凹函数。

如果$f(x)$是凸函数，那么$\log f(x)$不一定是凸函数。

如果likelihood function是凹的，那么log likelihood function肯定也是凹的，导数为0的点就是最大值点。

sasa已经讲得挺清楚的了，我就补充一个小例子

左边是凸函数，右边是取对数后，变成了凹函数

坐标轴下降法顾名思义，是沿着坐标轴的方向去下降，这和梯度下降不同。梯度下降是沿着梯度的负方向下降。不过梯度下降和坐标轴下降的共性就都是迭代法，通过启发式的方式一步步迭代求解函数的最小值。

　　　　坐标轴下降法的数学依据主要是这个结论（此处不做证明）：一个可微的凸目标函数$J(\theta)$, 其中$\theta$是$nx\times 1$的向量，即有$n$个维度。如果在某一点$\bar \theta$，使得$J(\theta)$在每一个坐标轴$\bar \theta_i$，($i = 1,2,\cdots,n$)上都是最小值，那么$J(\bar \theta_i)$就是一个全局的最小值。

　　　　于是我们的优化目标就是在$\theta$的$n$个坐标轴上(或者说向量的方向上)对损失函数做迭代的下降，当所有的坐标轴上的$\theta_i$($i = 1,2,\cdots,n$)都达到收敛时，我们的损失函数最小，此时的$\theta$即为我们要求的结果。

　　　　下面我们看看具体的算法过程：

　　　　1. 首先，我们把$\theta$向量随机取一个初值。记为$\theta^{(0)}$ ，上面的括号里面的数字代表我们迭代的轮数，当前初始轮数为0.

　　　　2. 对于第$k$轮的迭代。我们从$\theta^{(k)}_1$开始，到$\theta^{(k)}_n$为止，依次求$\theta^{(k)}_i$。$\theta^{(k)}_i$的表达式如下：

　　　　$$\theta^{(k)}_i = \text{argmin}_{\theta_i} J(\theta^{(k)}_1,\theta^{(k)}_2,\cdots,\theta^{(k)}_{i−1},\theta_i,\theta^{(k−1)}_{i+1},\cdots,\theta^{(k−1)}_n)$$

也就是说$\theta^{(k)}_i$是使$J(\theta^{(k)}_1,\theta^{(k)}_2,\cdots,\theta^{(k)}_{i−1},\theta_i,\theta^{(k−1)}_{i+1},\cdots,\theta^{(k−1)}_n)$最小化时候的$\theta_i$的值。此时$J(\theta)$只有$\theta^{(k)}_i$是变量，其余均为常量，因此最小值容易通过求导求得。

如果上面这个式子不好理解，我们具体一点，在第$k$轮，$\theta$向量的$n$个维度的迭代式如下：

　　　　$$\theta^{(k)}_1=\text{argmin}_{\theta_1} J(\theta_1,\theta^{(k−1)}_2,...,\theta^{(k−1)}n)$$

　　　　$$\theta^{(k)}_2=\text{argmin}_{\theta_2} J(\theta^{(k)}_1,\theta_2,\theta^{(k−1)}_3...,\theta^{(k−1)}_n)$$

　　　　$$\cdots$$

　　　　$$\theta^{(k)}_n=\text{argmin}_{\theta_n} J(\theta^{(k)}_1,\theta^{(k)}_2,...,\theta^{(k)}_{n−1},\theta_n)$$

　　　　3. 检查$\theta^{(k)}$向量和$\theta^{(k−1)}$向量在各个维度上的变化情况，如果在所有维度上变化都足够小，那么$\theta^{(k)}$即为最终结果，否则转入2，继续第$k+1$轮的迭代。

以上就是坐标轴下降法的求极值过程，可以和梯度下降做一个比较：

a) 坐标轴下降法在每次迭代中在当前点处沿一个坐标方向进行一维搜索 ，固定其他的坐标方向，找到一个函数的局部极小值。而梯度下降总是沿着梯度的负方向求函数的局部最小值。

b) 坐标轴下降优化方法是一种非梯度优化算法。在整个过程中依次循环使用不同的坐标方向进行迭代，一个周期的一维搜索迭代过程相当于一个梯度下降的迭代。

c) 梯度下降是利用目标函数的导数来确定搜索方向的，该梯度方向可能不与任何坐标轴平行。而坐标轴下降法法是利用当前坐标方向进行搜索，不需要求目标函数的导数，只按照某一坐标方向进行搜索最小值。

d) 两者都是迭代方法，且每一轮迭代，都需要$O(mn)$的计算量($m$为样本数，$n$为系数向量的维度)

转自这里

另外两位说得很清楚了，我就插个图。简单地说就是按照坐标轴方向下降的。

Gradient descent是Coordinate descent的特殊情况。每一个待求变量都是个坐标。n个变量就形成在n维空间找最优解的问题。CD每一步只计算一个或一部分待求变量上的gradient，其余变量保持不变。如果每步都改变全部变量，就是GD。

CD最大的优点是第k步计算都用了之前最新的值，而GD相当于每n步才更新一次数据。

至于CD和GD有同一最优解，是靠把问题“设计”成凸优化来实现的。

极小值是local minimum，也就是局部的最小值；最小值是global minimum，也就是全局的最小值。

最小值肯定也是极小值，极小值不一定唯一，最小的极小值就是最小值。

在整个定义域上的最小值就是最小值

一个点在它的一个小邻域内是最小值就是极小值

如果是凸函数，那么极小值一定是最小值。反过来，如果极小值就是最小值，那么这个函数不一定是凸函数。

比如这个例子，在$x=3$处是这个函数唯一的极小值，显然也是最小值，但是这个函数显然不是凸的。

这个说法不太严谨，很容易找出反例。比如$f(x)=sin(x)$，有无数个极小值，同时是最小值，但$sin(x)$明显在$x$超过$2\pi$范围时不是凸函数。

当然一定没有鞍点。凸函数没有鞍点，凹函数也没有鞍点。

你看下鞍点的定义就知道了。

不一定。极值定理说一个连续函数在有界闭集上才会有最大值和最小值。所以凸优化不一定有最优解。

此外，即使有最优解，也不一定唯一。

严格凸的话，应该是有唯一的解的。

混合整数规划不要求所有的决策变量都是整数。

普通的整数规划例如：

$$\text{maximize }f(x_1, x_2, x_3, x_3) \\ \text{subject to } g(x_1, x_2, x_3, x_4)\geq 0 \text{ and } x_1,x_2,x_3,x_4 \in \mathbb{Z}$$

混合整数规划例如：

$$\text{maximize }f(x_1, x_2, x_3, x_3) \\ \text{subject to } g(x_1, x_2, x_3, x_4)\geq 0 \text{ and } x_1,x_2 \in \mathbb{Z} \text{ and }x_3,x_4\in \mathbb{R}$$

普通整数规划决策变量都是整数，混合整数规划决策变量有一些是整数有一些是实数。

找离重心（x,y取平均值）最近的点，因为均值离所有点的距离平方和MSE最小。题外话，median离所有点距离的绝对值和MAE最小。