无穷范数最小化线性规划问题

### 使用线性规划求解无穷范数最小化问题

对于无穷范数最小化问题，可以将其转化为一个标准形式的线性规划(LP)问题。具体来说，给定一个线性方程组 \(Ax=b\)，其中\(A \in R^{m\times n}\)，\(b\in R^m\)，目标是最小化向量\(x\)的无穷范数。

为了实现这一点，可以通过引入一个新的变量\(t\)来表示各个分量的最大绝对值，并构建如下LP模型：

\[ \min t \]

受制于:

\[ Ax = b \]
\[ -te_i \leq x_i \leq te_i,\quad i=1,...,n \]

这里，\(e_i\)代表第i个单位向量。上述不等式确保了所有\(x_i\)都在范围\([-t,t]\)内变化，从而使得最终得到的结果满足无穷范数的要求。

下面是在MATLAB环境中利用`linprog`函数解决此类问题的一个简单例子[^1]：

% 定义参数
A = rand(5, 3); % 随机生成系数矩阵
b = sum(A, 2);  % 构造右侧常数项使至少存在一组可行解

f = [ones(size(A, 2), 1); 1]; % 目标函数系数向量
Aeq = [A zeros(size(b))];     % 等式约束左侧扩展后的系数矩阵
beq = b;                      % 等式约束右侧不变
lb = [-inf*ones(size(A, 2), 1); 0]; % 下界设置为负无穷大和零
ub = inf * ones(length(f), 1);       % 上界设为正无穷大

% 调用 linprog 函数解决问题并获取结果
[x_optimal, fval] = linprog(f,[],[],Aeq, beq, lb, ub);

disp('最优解:');
disp(x_optimal);
disp(['最小化的无穷范数值:', num2str(fval)]);

这段程序首先定义了一个随机产生的线性系统作为测试案例，接着按照前述理论转换成对应的线性规划格式，最后调用了内置的`linprog`函数完成实际计算过程。