[最优化技术] 第三章 无约束优化方法

第三章 无约束优化方法

无约束优化方法是有约束优化方法的基础，而其中一维问题的优化方法（一维搜索）是所有优化方法的基础。
一维搜索法

对于求解一元函数凸函数的极小值，采用一维搜索来解决。一维搜索一般分为两步，确定初始搜索区间 和 迭代逼近极小值。
1. 确定搜索区间（进退法/外推法）

这个方法用来从初始点确定初始搜索区间。具体步骤如下：

• ① 取初始点和初始步长。
  
• ② 计算 \(f(a_0)\) 和 \(f(a_0 + h)\)，根据比较结果，向左或向右搜索，步长每次加倍，直到得到 “大-小-大” 的结构。
  

动画演示

C++代码实现[code]#include #include #include #include using namespace std;// 进退法求初始区间pair bracket_minimum(function func, double a0, double h) {        // 进退法最大搜索次数        const int MAX_ITER = 1e4;        if (h  MAX_ITER)                                throw runtime_error("Max iterations exceeded in right expansion");                        printf("[debug] step %d: (%.2lf, %.2lf, %.2lf)\n", iter, x0, x1, x2);                        x0 = x1;                        x1 = x2;                        h *= 2;                        x2 = x1 + h; // 步长加倍                }                printf("[debug] step %d: (%.2lf, %.2lf, %.2lf)\n", iter + 1, x0, x1, x2);                return make_pair(x0, x2);        }}int main() {        // 定义一个一元凸函数        auto f = [](double x) {                return x * x - 2 * x - 5;        };                double a0, h;        cout > a0;        cout > h;                try {                auto r = bracket_minimum(f, a0, h);                cout