最小无穷范数问题（Minimize|| Ax-b||∞）和 l∞ norm: ||x||∞=max{|xi|}这两个问题怎么利用等价转换为线性规划问题？

最小无穷范数问题 (Minimize ||Ax - b||_∞) 是指寻找一组向量 x 的解，使得 Ax - b 中所有元素绝对值之和尽可能小，其中 A 是矩阵，b 是常数向量，||·||_∞ 表示 L∞ 范数，它是最大的元素绝对值。

将此问题转化为线性规划问题，首先需要注意到 L∞ 范数实际上是在寻找那些使得 Ax - b 中某个分量有最大绝对值，并使其等于目标函数值的问题。我们可以设这个最大绝对值为变量，然后构造辅助变量和约束条件：

1. **引入辅助变量**：对于 Ax - b 中的每个元素，我们引入一个变量 u_i，表示对应分量的绝对值。因此，||Ax - b||_∞ 可以表示为 max(u_1, ..., u_n)。

2. **构建约束条件**：对于每一个分量 i，我们有约束条件 |a_ij*x_j - b_i| <= u_i，这意味着 Ax - b 的第i个元素的绝对值不大于 u_i。这里 a_ij 是矩阵 A 的元素，x_j 是向量 x 的相应元素。

3. **目标函数**：我们的目标是找到满足上述约束的 x 和 u，使得 u_1 + ... + u_n 最小。这可以写作 Minimize z（目标变量），s.t. 对于所有 i，u_i >= |a_ij*x_j - b_i|。

4. **线性规划形式**：将上面的非线性约束通过松弛处理成线性形式，得到线性规划模型：

-- 目标函数: Minimize z
-- 约束条件: u_i >= |a_ij*x_j - b_i| 对于 i = 1...n
-- 自由变量: x_j (j = 1...m), u_i (i = 1...n)

这样的线性规划问题可以用标准的优化工具求解，如单纯形法、内点法等。