计算科学 - 目标函数中具有最大值和绝对值的约束优化 - 吾爱随笔录

计算科学优化线性规划

2021-12-04 12:18:50

我想找到最佳集合 $\{ x_i \}$ 给定 $L$ 和 $\{ a_i \}$ 最大限度地减少下面的问题。我的第一个想法是使用线性规划。是否有使之成为可能的转换，还是我需要更通用的优化技术？

min_{x_{i}} [2 \sum_{i} | x_{i} | + max_{i} | x_{i} + a_{i} |]

$\min_{x_i} \left[ 2\sum_i | x_i | + \max_i | x_i + a_i | \right]$

s . t . \sum_{i} (x_{i} + a_{i}) \leq L

$\mathrm{s.t.} \sum_i (x_i + a_i) \le L$

1个回答

你还没有告诉我们的范围是什么，所以我假设。 $i$ $i=1, 2, \ldots, n$

LP 公式化绝对值问题的一个标准技巧是引入辅助变量和约束，其基本思想是

$\min | x |$

相当于

$\min t$

$t \geq x$

$t \geq -x$

将这个想法应用于您的问题，引入辅助变量、和。然后将问题表述为： $t_{i}$ $i=1, 2, \ldots n$ $s$

$\min 2 \sum_{i=1}^{n} t_{i} + s$

受制于

$t_{i} \geq x_{i}$ ,。 $i=1, 2, \ldots n$

$t_{i} \geq -x_{i}$ ,。 $i=1, 2, \ldots n$

$s \geq x_{i}+a_{i}$ ,。 $i=1, 2, \ldots, n$

$s \geq -(x_{i}+a_{i})$ ,。 $i=1, 2, \ldots, n$

$\sum_{i=1}^{n} (x_{i}+a_{i}) \leq L$

其它你可能感兴趣的问题