⾮线性规划author: lunardate: Tue 01 Sep 2020 04:31:18 PM CST⾮线性规划如果⽬标函数中包含⾮线性函数, 就称这种规划问题为⾮线性规划问题.⽬前解决⾮线性规划还没有⼀种通⽤⽅法.线性规划和⾮线性规划的区别如果线性规划的最优解存在, 其最优解只能在其可⾏域的边界上达到(特别是可⾏域的顶点上达到); ⽽⾮线性规划的最优解可能在可⾏域的任意⼀点达到.⾮线性规划的MATLAB解法⾸先可以将⾮线性规划表⽰为如下形式:minC(x), Ceq(x)是⾮线性向量函数.MATLAB计算⾮线性规划的函数为x = fmincon(fun, x0, A, B, Aeq, Beq, LB, UB, NONLCON, OPTIONS)fun是⽤.m⽂件定义的⽬标函数; x0表⽰决策变量的初始值; NONLCON是⽤.m⽂件定义的⾮线性向量函数; OPTIONS定义了优化参数; 其余参数与线性规划⼀致.⽰例求解下列⾮线性规划问题\min f(x) = x_1^2 + x_2^2 + x_3^2 + 8\\ \begin{aligned} s.t.\quad &x_1^2 - x_2 + x_3^2 \ge 0\\&x_1 + x_2^2 + x_3^2 \le 20\\ &-x_1 - x_2^2 + 2 = 0\\ &x_2 + 2x_3^2 = 3\\ &x_1, x_2, x_3 \ge 0\end{aligned}⽤MATLAB代码求解为编写⽬标函数的.m⽂件target.mfunction f = target(x);f = sum(x.^2) + 8;编写⾮线性约束条件的.m⽂件nonlinear.mfunction [g,h] = nonlinear(x);g = [-x(1)^2 + x(2) - x(3)^2x(1) + x(2)^2 + x(3)^3 - 20]; %⾮线性不等式约束f = [-x(1) - x(2)^2 + 2x(2) + 2x(3)^2 - 3]; %⾮线性等式约束主程序⽂件main.moptions = optimset('largescale', 'off');[x, y] = fmincon('target', rand(3,1), [], [], [], [], zeros(3,1),[], 'nonlinear', options)求解⾮线性规划的基本迭代格式(难点)由于线性规划的⽬标函数为线性函数, 可⾏域为凸集, 所以求出的最优解就是整个可⾏域上的最优解. ⾮线性规划则不然, 有时求出的解虽然是⼀部分可⾏域上的极值点, 但不⼀定是整个可⾏域上的全局最优解.对于⾮线性规划模型(NP), 可以采⽤迭代⽅法求最优解. 基本思想为: 从⼀个选定的初始点出发, 按照⼀个特定的迭代规则产⽣⼀个点列{x k}; 使得当{x k}是有穷点列时, 其最后⼀个点是(NP)的最优解; 为⽆穷点列时, 它有极限点, 并且极限点是(NP)的最优解;设x^k\in R^n是某迭代⽅法的第k轮迭代点, x^{k+1}\in R^n是第n+1轮迭代点, 记x^{k+1} = x^k + t_kp^k\\ t_k\in R^1, p^k\in R^n, \lvert p^k\rvert = 1通常将基本迭代格式中的p^k称为第k轮搜索⽅向, t_k为沿p^k⽅向的步长. 有机器学习那味⼉了.对于向量p, 如果存在t\in (0, +\infty)使得f(\overline x + tp) < f(\overline x)\\ \overline x + tp \in KK即为可⾏域, 则称p为\overline x关于K的可⾏⽅向.凸函数, 凸规划凸函数的定义为: 若对区间(0,1)内的任何实数\alpha, 恒有f(\alpha x_1 + (1-\alpha)x_2) \le \alpha f(x_1) + (1-\alpha)f(x_2)的函数为定义在R上的严格凸函数.⽬标函数为凸函数, 约束函数也为凸函数的⾮线性规划为凸规划.可以证明, 凸规划的可⾏域为凸集, 其局部最优解即为全局最优解, ⽽且其最优解的集合形成⼀个凸集. 当凸规划的⽬标函数f(x)为严格凸函数时, 其最优解必定唯⼀.⽆约束问题⽆约束问题即没有约束条件的问题, 即求解函数极⼩值的问题⼀维搜索⽅法当⽤迭代法求函数的极⼩点时, 常常⽤到⼀维搜索, 即沿⼀已知⽅向求⽬标函数的极⼩点.⼀种⽐较⼀个区间上两端函数值的⽅法, 原理⾮常简单, 不讲了.但是这种⽅法⼀般只能⽤于单极值区间, 对于⼀个多极值的函数. 可以尝试先画出函数图, 然后找出所有只有单个极值的区间分别求解.斐波那契法上⾯那种⽅法本是随机选取区间的两个点, 斐波那契法能够保证区间按照按照斐波那契数进⾏缩⼩.即t_1 = a + \frac{F_{n-1}}{F_n}(b-a),t_2 = a + \frac{F_{n-2}}{F_n}(b-a)根据需要求解的精度\delta, 确定迭代次数的⽅式\frac{b-a}{F_n} \le \delta也可以⽤黄⾦⽐例数代替斐波那契数列.⼆次插值法对极⼩化问题, 当f(t)在[a,b]上连续时, 可以考虑⽤多项式插值来进⾏⼀维搜索. 基本思想为: 在搜索区间内,不断⽤低次(不超过三次)多项式来近似⽬标函数, 并逐步⽤插值多项式的极⼩点来逼近极⼩化问题的最优解.⽆约束问题的解法梯度下降法总是朝着梯度下降最快的⽅向前进⽜顿法⾸先需要了解⼀下什么是考虑⽬标函数f在x^k处的⼆次逼近式f(x)\approx Q(x) = f(x^k) + \nabla f(x^k)^T(x-x^k) + \frac12(x-x^k)^T\nabla^2f(x^k)(x-x^k)假设⿊塞矩阵\nabla^2 f(x^k) = \begin{bmatrix} \frac{\partial^2 f(x^k)}{\partial x_1^2} & \cdots & \frac{\partial^2f(x^k)}{\partial x_1\partial x_n}\\ \vdots & \cdots & \vdots \\ \frac{\partial f(x^k)}{\partial x_n\partial x_1} & \cdots & \frac{\partial^2 f(x^k)}{\partial x_n^2} \end{bmatrix}正定由于\nabla^2 f(x^k)正定, 函数Q的驻点x^{k+1}是Q(x)的极⼩点. 令\nabla Q(x^{k+1}) = \nabla f(x^k) + \nabla^2 f(x^k)(x^{k+1} - x^k) = 0解得x^{k+1} = x^k - [\nabla^2 f(x^k)]^{-1}\nabla f(x^k)所以从x^k出发的搜索⽅向为p^k = -[\nabla^2 f(x^k)]^{-1}\nabla f(x^k)⽜顿法的优点是收敛速度快; 缺点是有时不好⽤⽽需采取改进措施, 当维度很⾼时, 计算矩阵的逆矩阵计算量将会很⼤.变尺度法变尺度法由于能够避免计算⼆阶导数矩阵及其逆矩阵, 对于⾼纬度问题具有显著的优越性.为了不计算⼆阶导数矩阵[\nabla^2 f(x^k)]及其逆矩阵, 我们设法构造另⼀个矩阵, 来逼近⼆阶导数矩阵, 这⼀类也称为拟⽜顿法(Quasi-Newton Method).当f(x)是⼆次函数时, 任两点x^k和x^{k+1}的梯度之差为\nabla f(x^{k+1}) - \nabla f(x^k) = A(x^{k+1} - x^k)因此, 我们构造⿊塞矩阵的第k+1次近似\overline H^{k+1}满⾜关系式x^{k+1} - x^k = \overline H^{(k+1)}[\nabla f(x^{(k+1)}) - \nabla f(x^k)]这就是拟⽜顿条件.令\begin{cases} \Delta G^{(k)} = \nabla f(x^{k+1}) - \nabla f(x^k)\\ \Delta x^k = x^{k+1} - x^k\end{cases}记\Delta \overline H^{(k)} = \overline H^{(k+1)} - \overline H^{(k)}称为校正矩阵.省略中间过程, 可求得校正矩阵\Delta \overline H^{(k)} = \frac{\Delta x^k(\Delta x^k)^T}{(\Delta G^{(k)})^T\Delta x^k} -\frac{\overline H^{(k)}\Delta G^{(k)}(G^{(k)})^T\Delta H^{(k)}}{(\Delta G^{(k)})^T\overlineH^{(k)}\Delta G^{(k)}} \tag{17}从⽽有\overline H^{(k+1)} = \overline H^{(k)} + \frac{\Delta x^k(\Delta x^k)^T}{(\Delta G^{(k)})^T\Delta x^k} - \frac{\overline H^{(k)}\Delta G^{(k)}(G^{(k)})^T\Delta H^{(k)}}{(\Delta G^{(k)})^T\overlineH^{(k)}\Delta G^{(k)}} \tag{18}以上矩阵称为尺度矩阵, 取第⼀个尺度矩阵\overline H^{(0)}为单位矩阵.由此可得DFP变尺度法的计算步骤为:给定初始点x_0以及梯度允许误差\varepsilon > 0若\lvert\nabla f(x^{(0)})\rvert \le\varepsilon, 则x_0为近似点, 停⽌迭代.否则转下⼀步.令\overline H^{(0)} = I (单位矩阵)\\ p^0 = -\overline H^{(0)}\nabla f(x^0)在p^0⽅向进⾏⼀维搜索, 确定最佳步长\lambda_0\min_\lambda f(x^0+\lambda p^0) = f(x^0 + \lambda_0p^0)于是可以得到下⼀个近似点x^1 = x^0 + \lambda_0p^0对于近似点x^k, 计算其梯度, 若有\lvert\nabla f(x^k)\rvert\le \varepsilon则停⽌迭代, 最终解为x^k; 否则根据式(18)计算\overline H^{(k)}, 令p^k = -\overline H^{(k)}\nablaf(x^k). 在p^k⽅向进⾏⼀维搜索, 得到\lambda_k, 从⽽得到下⼀个近似点x^{k+1} = x^k + \lambda_kp^k不断重复第4步直到满⾜允许误差.约束极值问题带有约束条件的极值问题称为约束极值问题, 也叫规划问题.⼆次规划问题⽬标函数为⾃变量的⼆次函数的问题称为⼆次规划问题.⼆次规划的模型可以表述为\min \frac12x^THx + f^Tx,\\ s.t.\quad \begin{cases} Ax\le b\\Aeq\dot x = beq\\ \end{cases} MATLAB中求解⼆次规划的函数为[x, f] = quadprog(H, f, A, b, Aeq, beq, LB, UB, X0, OPTIONS)罚函数法利⽤罚函数法, 可将⾮线性规划问题转化为⼀系列⽆约束机制问题. 因此也称这种⽅法为序列⽆约束最⼩化技术, SUMT(Sequential Unconstrained Minization Technique).罚函数法的基本思想是利⽤问题中的约束函数作出适当的罚函数, 由此构造出带参数的增⼴⽬标函数, 把问题转化为⽆约束线性规划问题.罚函数法分为外罚函数法和内罚函数法. 现在介绍外罚函数法.对于问题:\min f(x)\\ s.t.\quad \begin{cases} g_i(x)\le 0, i = 1,\dots,r,\\ h_j(x)\ge 0, j = 1,\dots,s,\\ k_m(x) = 0, m = 1,\dots,t \end{cases}取⼀个充分⼤的正数M, 构造函数P(x, M) = f(x) + M\sum_{i=1}^r\max(g_i(x), 0) - M\sum_{i=1}^s\min(h_i(x), 0) +M\sum_{i=1}^t|k_i(x)|MATLAB 求约束极值问题fminbnd 函数求单变量⾮线性函数在区间[x_1, x_2]上的最⼩值语法格式[x, f] = fminbnd(fun, x1, x2, options)fminimax 函数可以⽤来求解带有⾮线性约束条件的问题x = fminimax(fun, x0, A, B, Aeq, Beq, LB, UB, NONLCON) Loading [MathJax]/jax/element/mml/optable/BasicLatin.js。
