1. 从线性规划到非线性规划
本系列的开篇我们介绍了线性规划 （Linear Programming） 并延伸到整数规划、0-1规划，以及相对复杂的固定费用问题、选址问题。这些问题的共同特点是，目标函数与约束条件都是线性函数。如果目标函数或约束条件中包含非线性函数，则是非线性规划。
通常，非线性问题都比线性问题复杂得多，困难得多，非线性规划也是这样。非线性规划没有统一的通用方法、算法来解决，各种方法都有特定的应用范围和适用条件。另一方面，很多非线性规划问题在实践中不能获得全局最优解，只能得到局部最优解或近似最优解。
这意味着什么？对于数学研究来说，这也许意味着存在新的课题和挑战，可以研究更有效的算法。确实如此，即便线性规划问题的研究也在不断前进，非线性规划问题的研究更是丰富多彩。但热闹是他们的，我什么也没有。
我所想到的，是数学建模学习/课程/竞赛的根本目的是什么？是掌握各种算法的推演，努力编程以实现，还是练习分析问题建立模型的能力，使用软件和工具求解问题的能力？显然是后者。可是，为什么培训课上老师讲的都是算法呢？到了例题例程，不是一带而过，就是跳步骤讲。听课时津津有味，下课了题目还是不会做，程序还是调不通。于是，…
不过，到了非线性规划这一课，我们发现老师也不再不厌其烦地讲算法了，不知道是讲不下去还是讲不过来了： 20世纪50年代，H.W.Kuhn 和 A.W.Tucker 提出了非线性规划的基本定理，为非线性规划奠定了理论基础 ；50、60 年代出现了许多解非线性规划问题的有效算法；80年代后，随着计算机技术的快速发展，非线性规划方法取得了长足进步，在信赖域法、稀疏拟牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。
所以，没关系的，都一样——参见章北海文集。
2. Scipy 库求解非线性规划问题
2.1 非线性规划问题的描述
首先，我们回顾线性规划问题的标准形式：
类似地，可以写出非线性规划的一般形式：
其中：x = [ x 1 , . . . , x n ] ^T
为决策变量，f ( x ) 为目标函数，h j ( x ) 和 g i ( x )为约束条件。
由此可见，非线性规划问题，实际上就是带有约束条件的非线性函数优化问题。
按照我们的学习模式，非线性规划问题的建模和求解与线性规划问题是类似的，按照以下步骤进行：
- 问题定义，确定决策变量、目标函数和约束条件；
- 模型构建，由问题描述建立数学方程，并转化为标准形式的数学模型；
- 模型求解，用标准模型的优化算法对模型求解，得到优化结果。
2.2 Scipy 求解非线性规划问题的函数
Scipy 是 Python 算法库和数学工具包，包括最优化、线性代数、积分、插值、特殊函数、傅里叶变换、信 和图像处理、常微分方程求解等模块。
scipy.optimize 模块中提供了多个用于非线性规划问题的方法，适用于不同类型的问题。
2.3 scipy.optimize.brent() 求解单变量无约束优化问题
非线性规划最简单的形式是一维搜索，一维搜索的常用方法是函数逼近法和区间收缩法。
brent() 函数是 SciPy.optimize 模块中求解单变量无约束优化问题最小值的首选方法。这是牛顿法和二分法的混合方法，既能保证稳定性又能快速收敛。
scipy.optimize.brent(func, args=(), brack=None, tol=1.48e-08, full_output=0, maxiter=500)optimize.brent() 的主要参数：
optimize.brent() 的主要返回值：
optimize.brent() 的使用例程：
from scipy.optimize import brent, fmin_ncg, minimizeimport numpy as np# 1. Demo1：单变量无约束优化问题(Scipy.optimize.brent)def objf(x): # 目标函数 fx = x**2 - 8*np.sin(2*x+np.pi) return fxxIni = -5.0xOpt= brent(objf, brack=(xIni,2))print("xIni={:.4f}tfxIni={:.4f}".format(xIni,objf(xIni))print("xOpt={:.4f}tfxOpt={:.4f}".format(xOpt,objf(xOpt)))例程运行结果：
xIni=-5.0000 fxIni=29.3522xOpt=-0.7391 fxOpt=-7.41952.4 scipy.optimize.fmin() 求解多变量无约束优化问题
多变量无约束优化问题的算法很多，分类方式也很多。从使用者的角度来说可以分为：只使用目标函数值、使用导数（梯度下降法）、使用二阶导数。大体来说，使用导数的算法收敛较快，使用二阶导数收敛更快，但是收敛快也容易陷入局部最优。
fmin() 函数是 SciPy.optimize 模块中求解多变量无约束优化问题（最小值）的首选方法，采用下山单纯性方法。下山单纯性方法又称 Nelder-Mead 法，只使用目标函数值，不需要导数或二阶导数值，是最重要的多维无约束优化问题数值方法之一。
scipy.optimize.fmin(func, x0, args=(), xtol=0.0001, ftol=0.0001, maxiter=None, maxfun=None, full_output=0, disp=1, retall=0, callback=None, initial_simplex=None)optimize.fmin() 的主要参数：
optimize.fmin() 的主要返回值：
**xopt: ** 返回最小值时的 x 值。**fopt: ** 返回最小值时的目标函数值，fopt=func(xopt)。optimize.fmin() 的使用例程：
from scipy.optimize import brent, fmin, minimizeimport numpy as np# 2. Demo2：多变量无约束优化问题(Scipy.optimize.brent)# Rosenbrock 测试函数def objf2(x): # Rosenbrock benchmark function fx = sum(100.0 * (x[1:] - x[:-1] ** 2.0) ** 2.0 + (1 - x[:-1]) ** 2.0) return fxxIni = np.array([-2, -2])xOpt = fmin(objf2, xIni)print("xIni={:.4f},{:.4f}tfxIni={:.4f}".format(xIni[0],xIni[1],objf2(xIni)))print("xOpt={:.4f},{:.4f}tfxOpt={:.4f}".format(xOpt[0],xOpt[1],objf2(xOpt)))例程运行结果：
xIni=-2.0000,-2.0000 fxIni=3609.0000xOpt=1.0000,1.0000 fxOpt=0.00003. scipy.optimize.minimize() 求解非线性规划问题
3.1 scipy.optimize.minimize() 函数说明
minimize() 函数是 SciPy.optimize 模块中求解多变量优化问题的通用方法，可以调用多种算法，支持约束优化和无约束优化。
scipy.optimize.minimize(fun, x0, args=(), method=None, jac=None, hess=None, hessp=None, bounds=None, constraints=(), tol=None, callback=None, options=None)optimize.minimize() 的主要参数：
optimize.minimize() 的主要返回值：
optimize.minimize() 的优化算法选项：
optimize.minimize() 的默认算法为 BFGS, L-BFGS-B, SLSQP（取决于问题有没有边界条件和约束条件），可以通过 “method=None” 选项调用多种算法：
无约束问题优化算法
边界约束条件问题优化算法
带有约束条件问题优化算法
https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html#scipy.optimize.minimize
我们还是针对数学建模的常用需求和小白的特点，结合实际案例来学习基本应用。
3.2 scipy.optimize.minimize() 函数使用例程
编程步骤说明：
1.导入 scipy、numpy 包；
2.定义目标函数 objf3(x)，输入变量 x 表示向量，返回值 fx 是目标函数的计算结果 。
3.定义边界约束，即优化变量的上下限：
4.定义 x 的初值。
5.求解最小化问题 resRosen，其中目标函数 objf3 和搜索的初值点 xIni 是必需的，指定优化方法和边界条件是可选项。如果优化问题是求最大值 maxFx，可以通过 minFx = – maxFx 的变换来实现。
6.通过调用最小化问题的返回值 resRosen.x 得到最优点 xOpt。
Python 例程：
from scipy.optimize import brent, fmin, minimizeimport numpy as np# 3. Demo3：多变量边界约束优化问题(Scipy.optimize.minimize)# 定义目标函数def objf3(x): # Rosenbrock 测试函数 fx = sum(100.0 * (x[1:] - x[:-1] ** 2.0) ** 2.0 + (1 - x[:-1]) ** 2.0) return fx# 定义边界约束（优化变量的上下限）b0 = (0.0, None) # 0.0 <= x[0] <= Infb1 = (0.0, 10.0) # 0.0 <= x[1] <= 10.0b2 = (-5.0, 100.) # -5.0 <= x[2] <= 100.0bnds = (b0, b1, b2) # 边界约束# 优化计算xIni = np.array([1., 2., 3.])resRosen = minimize(objf3, xIni, method='SLSQP', bounds=bnds)xOpt = resRosen.xprint("xOpt = {:.4f}, {:.4f}, {:.4f}".format(xOpt[0],xOpt[1],xOpt[2]))print("min f(x) = {:.4f}".format(objf3(xOpt)))例程运行结果：
xOpt = 1.0000, 1.0000, 1.0000min f(x) = 0.00004. 约束非线性规划问题实例
4.1 非线性规划问题的数学模型：
由于 minimize() 函数中对约束条件的形式定义为 f(x)>=0，因此要将问题的数学模型转换为标准形式：
4.2 Python 例程 1：
程序说明：
1.在本例程中，目标函数中的参数 a, b, c, d 在子程序中直接赋值，这种实现方式最简单；
2.定义边界约束，即优化变量的上下限，与 3.2 中的例程相同，用 minimize() 函数中的选项 bounds=bnds 进行定义。
3.定义约束条件：
4.求解最小化问题 res，其中目标函数 objF4 和搜索的初值点 x0 是必需的，指定优化方法和边界条件、约束条件是可选项。
5.通过调用最小化问题的返回值可以得到优化是否成功的说明（res.message）、自变量的优化值（res.x）和目标函数的优化值（res.fun）。
Python 例程：
from scipy.optimize import brent, fmin, minimizeimport numpy as np# 4. Demo4：约束非线性规划问题(Scipy.optimize.minimize)def objF4(x): # 定义目标函数 a, b, c, d = 1, 2, 3, 8 fx = a*x[0]**2 + b*x[1]**2 + c*x[2]**2 + d return fx# 定义约束条件函数def constraint1(x): # 不等式约束 f(x)>=0 return x[0]** 2 - x[1] + x[2]**2def constraint2(x): # 不等式约束 转换为标准形式 return -(x[0] + x[1]**2 + x[2]**3 - 20)def constraint3(x): # 等式约束 return -x[0] - x[1]**2 + 2def constraint4(x): # 等式约束 return x[1] + 2*x[2]**2 -3# 定义边界约束b = (0.0, None)bnds = (b, b, b)# 定义约束条件con1 = {'type': 'ineq', 'fun': constraint1}con2 = {'type': 'ineq', 'fun': constraint2}con3 = {'type': 'eq', 'fun': constraint3}con4 = {'type': 'eq', 'fun': constraint4}cons = ([con1, con2, con3,con4]) # 3个约束条件# 求解优化问题x0 = np.array([1., 2., 3.]) # 定义搜索的初值res = minimize(objF4, x0, method='SLSQP', bounds=bnds, constraints=cons)print("Optimization problem (res):t{}".format(res.message)) # 优化是否成功print("xOpt = {}".format(res.x)) # 自变量的优化值print("min f(x) = {:.4f}".format(res.fun)) # 目标函数的优化值例程 1 运行结果：
Optimization problem (res): Optimization terminated successfullyxOpt = [0.6743061 1.15138781 0.96140839]min f(x) = 13.87904.3 Python 例程 2：
程序说明：
1.本例程的问题与 4.2 中的例程 1 是相同的，结果也相同，但编程实现的方法进行了改进；
2.本例程中目标函数中的参数 a, b, c, d 在主程序中赋值，通过 args 把参数传递到子程序，这种实现方式使参数赋值更为灵活，特别是适用于可变参数的问题；注意目标函数的定义不是 def objF5(x,args)，而是 def objF5(args)，要特别注意目标函数的定义和实现方法。
3.定义约束条件：
4.通过调用最小化问题的返回值可以得到优化是否成功的说明（res.message）、自变量的优化值（res.x）和目标函数的优化值（res.fun）。
Python 例程 2：
from scipy.optimize import brent, fmin, minimizeimport numpy as np# 5. Demo5：约束非线性规划问题(Scipy.optimize.minimize)def objF5(args): # 定义目标函数 a,b,c,d = args fx = lambda x: a*x[0]**2 + b*x[1]**2 + c*x[2]**2 + d return fxdef constraint1(): # 定义约束条件函数 cons = ({'type': 'ineq', 'fun': lambda x: (x[0]**2 - x[1] + x[2]**2)}, # 不等式约束 f(x)>=0 {'type': 'ineq', 'fun': lambda x: -(x[0] + x[1]**2 + x[2]**3 - 20)}, # 不等式约束 转换为标准形式 {'type': 'eq', 'fun': lambda x: (-x[0] - x[1]**2 + 2)}, # 等式约束 {'type': 'eq', 'fun': lambda x: (x[1] + 2*x[2]**2 - 3)}) # 等式约束 return cons# 定义边界约束b = (0.0, None)bnds = (b, b, b)# 定义约束条件cons = constraint1()args1 = (1,2,3,8) # 定义目标函数中的参数# 求解优化问题x0 = np.array([1., 2., 3.]) # 定义搜索的初值res1 = minimize(objF5(args1), x0, method='SLSQP', bounds=bnds, constraints=cons)print("Optimization problem (res1):t{}".format(res1.message)) # 优化是否成功print("xOpt = {}".format(res1.x)) # 自变量的优化值print("min f(x) = {:.4f}".format(res1.fun)) # 目标函数的优化值例程 2 运行结果：
Optimization problem (res1): Optimization terminated successfullyxOpt = [0.6743061 1.15138781 0.96140839]min f(x) = 13.87904.4 Python 例程 3：
程序说明：
- 本例程的问题与 4.3 中的例程 2 是相同的，结果也相同，但编程实现的方法进行了改进；
- 本例程中约束条件中的参数在主程序中赋值，通过 args 把参数传递到约束条件定义的子程序，这种实现方式使参数赋值更为灵活，特别是适用于可变参数的问题。
- 本例程中将边界约束条件即自变量的取值范围作为不等式约束条件处理，不另作边界条件设置。
- 通过调用最小化问题的返回值可以得到优化是否成功的说明（res.message）、自变量的优化值（res.x）和目标函数的优化值（res.fun）。
Python 例程 3：
from scipy.optimize import brent, fmin, minimizeimport numpy as np# 6. Demo6：约束非线性规划问题(Scipy.optimize.minimize)def objF6(args): 声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！