一维搜索法-- 进退法与黄金分割法求一元二次函数最小值(Java实现)

墨蓝 2022-05-23 23:54 161阅读 0赞

### 说明： ###

1.  进退法 – 用于确定函数最值搜索范围
2.  黄金分割法– 在确定范围内搜索函数最值

> 算法比较简单，基本通过代码就能理解

public class 进退法 { 
        /** * 求解最小值的函数 * * @param x * @return */
        public static double f(double x) {
            double y = (x + 3) * (x - 3);
            System.out.println(String.format("f(%f)=%f", x, y));
            return y;
        }
    
        /** * 进退法求函数极值范围 * * <pre> * 初始化a0=0, 步长 h0=0 * 1. h=h0, a1=a0,a2=a1+h * 2. 若g(a2)<=g(a1) goto 4 * 3. 交换a1 和a2， 并令 h=-h * 4. h=2h, 令a3=a2+h * 5. 若g(a3)>g(a2) 已找到极小架子{ a1, a2, a3} ； 否则令a1=a2, a2=a3 goto 4 * </pre> * * @param x0 * @param h * @return */
        public static double[] jtf(double x0, double h) {
            System.out.println("进退法------确定函数最小值范围！");
            double x1 = x0, x2 = x1 + h, x3;
            double y2 = f(x2);
            if (f(x1) < y2) {
       // 如果y2 > y1 表明方向反了，通过h符号修改方向，同时交换x1与x2
                h = -h;
                x1 = x2;
                x2 = x0;
            }
            // 前进
            while (true) {
                x3 = x2 + 2 * h;
                double y3 = f(x3);
                if (y3 > y2) {
       // 说明已经找到了符合条件的点（高-低-高）
                    break;
                }
                x1 = x2; // 每次前进都要重新修改范围（ x1 与x2 前进1布）
                x2 = x3;
                y2 = y3;// 临时变量，避免重复计算
            }
            System.out.println(String.format("x1=%f,x2=%f,x3=%f", x1, x2, x3));
            return new double[] { Math.min(x1, x3), Math.max(x1, x3) };
        }
    
        public static void goldSearch(double start, double end, double eps) {
            System.out.println("黄金分割法------根据范围搜索函数最小值！");
            // 初始化初始搜索范围
            double a, b;
            b = Math.max(start, end);
            a = Math.min(start, end);
    
            double t1, t2, f1, f2;
            double ranta = 0.618034f;
    
            // 黄金分割点 t1 和 t2
            t1 = b - ranta * (b - a);
            t2 = a + ranta * (b - a);
            f1 = f(t1);
            f2 = f(t2);
    
            while (t2 - t1 > eps) {
                if (f1 <= f2)
                    b = t2;
                else
                    a = t1;
                t1 = b - ranta * (b - a);
                t2 = a + ranta * (b - a);
                f1 = f(t1);
                f2 = f(t2);
            }
    
            double x, y;
            if (f1 > f2) {
                x = t2;
                y = f2;
            } else {
                x = t1;
                y = f1;
            }
            System.out.println(String.format("点：%f 处取最小值：%f", x, y));
        }
    
        public static void main(String[] args) {
            double[] range = jtf(10, 1d);
            System.out.println(String.format("函数最小值范围：(%f,%f)", range[0], range[1]));
            goldSearch(range[0], range[1], 0.01);
        }
    }

结果：

进退法------确定函数最小值范围！
    f(11.000000)=112.000000 f(10.000000)=91.000000 f(8.000000)=55.000000 f(6.000000)=27.000000 f(4.000000)=7.000000 f(2.000000)=-5.000000 f(0.000000)=-9.000000 f(-2.000000)=-5.000000 x1=2.000000,x2=0.000000,x3=-2.000000 函数最小值范围：(-2.000000,2.000000) 黄金分割法------根据范围搜索函数最小值！ f(-0.472136)=-8.777088 f(0.472136)=-8.777088 f(-1.055728)=-7.885438 f(-0.472136)=-8.777088 f(-0.472136)=-8.777088 f(-0.111456)=-8.987578 f(-0.111456)=-8.987578 f(0.111456)=-8.987578 f(-0.249224)=-8.937888 f(-0.111456)=-8.987578 f(-0.111456)=-8.987578 f(-0.026311)=-8.999308 f(-0.026311)=-8.999308 f(0.026311)=-8.999308 f(-0.058834)=-8.996539 f(-0.026311)=-8.999308 f(-0.026311)=-8.999308 f(-0.006211)=-8.999961 f(-0.006211)=-8.999961 f(0.006211)=-8.999961 f(-0.013889)=-8.999807 f(-0.006211)=-8.999961 点：-0.006211 处取最小值：-8.999961

参考资料：  
1. [Matlab代码，一维搜索用进退法确定搜索区间][Matlab]  
2. [最优化第二讲——一维搜索法（黄金分割法和java实现）][java]

[Matlab]: https://blog.csdn.net/robert_chen1988/article/details/53253378
[java]: https://blog.csdn.net/nwpuwyk/article/details/28471265