/Practical-Optimization-Algorithm

Some useful optimization algorithms. Implemented with c++.

Primary LanguageC++GNU General Public License v2.0GPL-2.0

实用优化算法 代码库

这是一个使用纯c++编写的实用优化算法库,仍在持续更新。现有内容如下:

  • 0.基础运算包
    • 浮点矩阵运算库 matrix.h
    • 高精度整数运算库 bigint.h
    • 高精度分数运算库 fraction.h
    • 高精度分数矩阵运算库 matrix_fraction.h
    • 数值方法求导运算库 derivation.h
  • 1.线搜索 (linear_search.h)
    • Fibonacci分割法
    • Newton单点插值法
    • Armijo-Goldstein不精确线搜索法
    • Wolfe-Powell不精确线搜索法
  • 2.最速下降法与牛顿法 (steepest_descent.h, newton.h)
    • 最速下降法
    • 牛顿法
    • Gill-Murray稳定牛顿法
  • 3.共轭梯度法 (conjugate_gradient.h, conjugate_gradient_accurate.h)
    • 共轭梯度法
    • 重启动FR非线性共轭梯度法
    • 精确共轭梯度法
    • 预优共轭梯度法
  • 4.拟牛顿法 (quassi_newton.h)
    • 采用简单准则的BFGS校正法
    • 采用Wolfe准则的BFGS校正法(表现最好)
    • 采用Goldestein准则的BFGS校正法(通常不使用)
    • 采用Wolfe准则的DFP校正法
    • 采用Wolfe准则的Broyden族校正法
  • 5.信赖域法 (trust_region.h)
    • 采用Dogleg方法的信赖域法
  • 6.非线性最小二乘问题 (least_square.h)
    • Levenberg-Marquardt方法
  • 7.线性规划问题 (linprog.h)
    • 单纯形方法
  • 8.凸二次规划问题 (quadric_programming.h)
    • 求解带等式约束的凸二次规划问题的拉格朗日乘子法
    • 求解一般凸二次规划的有效集方法
  • 9.一般约束最优化问题 (general_constraint.h)
    • 求解一般约束优化问题的乘子法(PHR算法)

有一些方法有原始版本和对应的gradfree版本,后者利用数值方法自动求导,当待优化函数由人工求导过于复杂时可以使用。但对于方便求导的函数,还是建议使用原始版本,因为虽然数值方法求导对计算精度影响不大,但速度较慢,影响效率。

使用模式

提供了两个编译选项:DEBUGSILENCE,使用宏定义可以选择模式. 其中通常模式下只输出最优化结果,DEBUG模式提供较为详细的中间步骤信息,SILENCE模式将不输出任何信息与结果.

测试函数集

在func文件夹下有以下几个常用测试函数,直接引用函数名对应的.h文件即可,每个文件都包含函数f(x)、梯度grad(x)、Hessian矩阵hessian(x)、初始迭代位置initial()

高维Rosenbrock函数

$$ f(x)=\sum_{i=1}^{n-1} [100(x_{i+1}-x_i^2)^2+(1-x_i)^2] $$

Powell奇异函数

$$ f(x)=(x_1+10x_2)^2+5(x_3-x_4)^2+(x_2-2x_3)^4+10(x_1-x_4) $$

Beale函数

$$ f(x) = (1.5-x_1+x_1x_2)^2 + (2.25-x_1+x_1x_2^2)^2 + (2.625-x_1+x_1x_2^3)^2 $$