数学建模学习笔记（二）：非线性规划

本篇文章是 非线性规划 的内容

1 定义

非线性规划是指目标函数或约束条件中存在非线性函数，就是非线性规划问题。非线性规划要复杂的多，不存在通解，其一般形式为：

线性规划的最优解只能在其可行域的边界达到，而非线性规划的最优解却可以在可行域内的 任一点 达到。

2 解法

Matlab中非线性规划的标准型如下：

Matlab函数为：

[x, fval] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)

🔑 Info: 参数说明

与线性规划的函数类似，但是这里要定义一个函数 fun ，也就是这里的目标函数 为可以为非线性函数。x0 可以写 random(i, 1)，后面的几个都是线性的部分，如果没有可以写 [] ，然后非线性的约束条件都写在一个函数里放在 nonlcon 这部分里。

3 求解非线性规划的迭代方法

对于 非线性规划模型（NP），可以用迭代方法来求解。其基本思想是：从一个初始点出发，按照 一定的规则 产生一个点列 ，如果是有穷点列，则 最后一个点 是最优解，如果是无穷有极限点列，则 极限点 是最优解。

3.1 几个概念

下面是几个概念：

当然也存在不严格的整体最优解

3.2 一般步骤

迭代法基本格式为：

其中 是模为 1 的向量，指的是搜索方向； 为实数，指的是步长。求解（NP）的一般步骤如下：

4 无约束问题

4.1 一维搜索方法

沿某一已知方向搜索求目标函数值的极小点，常用的方法有：

• 试探法
  • “成功-失败”
  • 菲波那契法：利用菲波那契数列来得到探索点，缩短区间进而求得最优解
  • 0.618法
• 插值法：在搜索区间内，不断用低次（一般不超过三次）的多项式来近似目标函数，并逐步用插值多项式的极小点来逼近最优解。
  • 抛物线插值法
  • 三次插值法
• 微积分中的求根法
  • 切线法
  • 二分法

4.2 Matlab 解法

在 Matlab 中求解无约束极值问题的函数有 fminunc 和 fminsearch。

💡 Note:

可以用 doc 查看具体操作。

5 约束极值问题

带有约束条件的的极值问题称为约束极值问题，求解时要将约束问题化为无约束问题；将非线性化为线性。

5.1 Matlab 解法

在 Matlab 中求解二次规划的标准型为：

🔑 Info: 二次规划

目标函数是自变量 x 的二次函数，而约束条件全为线性的，这种叫做二次规划

求解二次规划的命令是：

[x, fval] = quadprog(H, f, A, b, Aeq, beq, LB, UB, X0, OPTIONS)

可用 doc 命令获得更详细的说明。

5.2 罚函数法

罚函数法求解非线性规划问题的思想是,利用问题中的约束函数作出适当的罚函数,由此构造出带参数的增广目标函数,把问题转化为无约束非线性规划问题。主要有两种形式,一种叫 外罚函数法,另一种叫 内罚函数法。

5.3 Matlab 中的其他函数

在 Matlab 优化工具箱中,用于求解约束最优化问题的函数有 fminbnd、fmincon、quadprog、fseminf、fminimax。