计算科学 - 优化问题中的绝对差分约束之和 - 吾爱随笔录

优化问题中的绝对差分约束之和

计算科学优化约束优化约束

2021-12-06 20:56:02

我正在为优化问题编写模型。我需要编写以下约束：

\sum_{i}^{N - 1} | (a_{i} - a_{i + 1}) | \leq 2 .

$\sum^{N - 1}_i \lvert (a_i - a_{i+1}) \rvert \leq 2\, .$

如何编写此约束（或线性化）？
是否允许在优化问题中使用绝对值约束（即使对于非线性规划）？

经过我的搜索，我发现绝对值可以建模如下（没有和或差）：

$| a_{i} | \leq 2 to a_{i} \leq 2 and - a_{i} \leq 2$ $\lvert a_i \rvert \leq 2 \: \text{ to }\: a_i \leq 2 \: \text{ and }\: - a_i \leq 2$
这种类型的转换在这里适用吗？

1个回答

处理这种约束的方法是在您的系统中添加“松弛变量”。在你的情况下，让我们说你想解决这个问题

min_{a} c^{T} a subject to \sum_{i = 1}^{N - 1} | a_{i} - a_{i + 1} | \leq 2

$\min_a c^T a \\ \text{subject to}\; \sum_{i=1}^{N-1} |a_i - a_{i+1}| \le 2$ 那么你可以引入松弛变量以便然后解决这个问题：

y_{1}, \dots y_{N - 1}

$y_1,\ldots y_{N-1}$

y_{i} \geq | a_{i} - a_{i + 1} |

$y_i \ge |a_i-a_{i+1}|$

min_{a} c^{T} a subject to \sum_{i = 1}^{N - 1} y_{i} \leq 2, y_{i} \geq | a_{i} - a_{i + 1} |

$\min_a c^T a \\ \text{subject to}\; \sum_{i=1}^{N-1} y_i \le 2, \\ \qquad \qquad \quad y_i \ge |a_i - a_{i+1}|$

接下来，识别等同于两个条件因此您的初始问题等同于以下问题，其中现在是一个完全线性约束的线性优化问题：

y_{i} \geq | a_{i} - a_{i + 1} |

$y_i \ge |a_i-a_{i+1}|$

y_{i} \geq + (a_{i} - a_{i + 1}) y_{i} \geq - (a_{i} - a_{i + 1})

$y_i \ge +(a_i-a_{i+1}) \\ y_i \ge -(a_i-a_{i+1}) \\$

min_{a} c^{T} a subject to \sum_{i = 1}^{N - 1} y_{i} \leq 2, y_{i} \geq + (a_{i} - a_{i + 1}), y_{i} \geq - (a_{i} - a_{i + 1}) .

$\min_a c^T a \\ \text{subject to}\; \sum_{i=1}^{N-1} y_i \le 2, \\ \qquad \qquad \quad y_i \ge +(a_i - a_{i+1}), \\ \qquad \qquad \quad y_i \ge -(a_i - a_{i+1}).$

其它你可能感兴趣的问题

上一篇数值模型的网格依赖性下一篇LAMMPS 中 Lennard Jones 的自定义指数