凸函数最优化调研

一、 问题定义

在给定的约束条件下， 选择最优的参数和方案，来使得目标函数最大化/最小化的问题。

最优化问题的主要形式是

$$ \left\{\begin{matrix} & min f(x) \\ s.t. &g_i(x) \geq 0, i = 1, ..., m \\ & h_i(x) = 0, i = 1, ..., l \\\end{matrix}\right. $$

其中$f(x）$表示目标函数，$g_i(x)$表示不等式约束，$h_i(x)$表示等式约束。

二、问题分类

1. 根据目标函数进行划分：连续最优化问题、离散最优化问题
2. 根据限制条件的种类划分：无约束最优化问题、等式约束最优化问题，不等式约束最优化问题和混合约束优化问题

三、最优化问题解决流程

可以分为两大步骤：第一步将有约束的最优化问题转化为无约束的最优化问题，第二步对无约束的最优化问题进行求解。

四、无约束最优化问题解决方法

基于线搜索的下降算法基本思路

1. 给定初始点$x^0, k=0$
2. 判断$x^k$是否满足终止条件；是，则终止
3. 寻找$x^k$处的下降方向$d^k$
4. 选择合适的步长$\alpha_k$$>0$，使得$f(x^k+\alpha_kd^k)< f(x^k)$
5. 令$x^{k+1}=x^k+\alpha_kd^k; k=k+1$，转第2步

三个比较核心的问题：终止条件、下降方向和步长