## 非线性数学规划求解

**作者：荣斋居士**

在数学规划问题中，经常会遇到非线性的目标函数或者约束。本文采用手工线性化的方法对模型进行处理后，利用Lingo软件进行求解。

## 1 问题描述

考虑如下最小化问题：

$$

\begin{array}{cl}

\min & f(x, y) \\

\text { s.t. } & (x-1)^{2}+(y-1)^{2}-1 \leqslant 0 \\

& |x|+y-2 \leqslant 0

\end{array}

$$

其中，$f(x,y)=max\{|x|,y+4\}$.

可知，目标函数中的`max`函数、第一个约束中涉及的2次方、第二个约束中的绝对值函数都是非线性函数。一般条件下是难以进行有效求解的。幸运的是，`绝对值`和`max`都可直接等价线性化，转化为传统的线性约束的，从而大大减小求解难度。但是针对二次方函数的等价线性化方法暂难以找到，暂不进行处理了。

## 2 求解过程

求解的过程如下：

引入辅助变量$z$表示$|x|$，进一步引入下面约束

$$

z \ge x\\

z \ge -x

$$

> 注意，由于目标函数并不是$min |x|$，因此这个线性化并不是完全等价的线性化，但是这种线性化却不改变最优值。如果最后$|x|>y+4$，则一定有$z=|x|$，但是如果最后的最优解是$y+4>|x|$，则$z$的取值就不一定等于$|x|$了，因为$z \ge x$和$z \ge -x$这两个约束此时不是`binding`的。

-   虽然取值上会有问题，但是最优值是可以保证的。

-   如果想要取值也都符合$z = |x|$，则可以进行相应的操作来处理该问题。

再引入辅助变量$w$，表示$max \{|x|,y+4\}$，引入下面约束即可

$$

w \ge z\\

w \ge y+4

$$

由于目标函数为$max$，因此这个线性化是等价线性化。因此，上述数学规划其实是可以等价为下面的形式：

$$

\begin{array}{ll}

\min & w \\

s . t . & (x-1)^{2}+(y-1)^{2}-1 \leqslant 0 \\

& z+y-2 \leqslant 0 \\

& z \geqslant x \\

& z \geqslant-x \\

& w \geqslant z \\

& w \geqslant y+4 \\

& w, z \geqslant 0

\end{array}

$$

## 3 Lingo代码

下面用Lingo来求解该数学规划。

完整代码如下

```Lingo

model:

min = w;

(x-1)^2 + (y-1)^2 -1 <=0;

z + y - 2<=0;

z >= x;

z >= -x;

w >= z;

w >= y +4;

@gin(w);

@gin(z);

end

```

## 4 结果分析

求解日志及最优解如下：

```

  Global optimal solution found.

  Objective value:                                4.0000

  Objective bound:                                4.0000

  Infeasibilities:                                0.0000

  Extended solver steps:                               0

  Total solver iterations:                             7

  Elapsed runtime seconds:                          0.81

  Model is convex quadratic

```

可见，经过7次的迭代，得到了全局最优值，最优值为4，计算耗时0.81秒，其中约束共7个，非线性约束1个。


要查看求解模型更详细的信息，可通过改变Lingo的输出设置进行查看。结果如下：

```

 Model Class:                                      MIQP

  Total variables:                      4

  Nonlinear variables:                  2

  Integer variables:                    2

  Total constraints:                    7

  Nonlinear constraints:                1

  Total nonzeros:                      13

  Nonlinear nonzeros:                   2

                                                      Variable         Value

                                                             W        4.0000

                                                             X       0.99983

                                                             Y        0.0000

                                                             Z        2.0000

                                                           Row  Slack or Surplus

                                                             1        4.0000

                                                             2        0.0000

                                                             3        0.0000

                                                             4        1.0002

                                                             5        2.9998

                                                             6        2.0000

                                                             7        0.0000

```

## 5 参考文献

参考文献链接：[非线性优化 | 非线性问题线性化以及求解的详细案例及Python+Gurobi求解](https://mp.weixin.qq.com/s?__biz=MzI3NTI2NzcxOA==&mid=2247488044&idx=1&sn=f0fbead1f499326ee26676b3d801ae5b&scene=21#wechat_redirect)

Linggo.pdf

LingoCode.7z