基于原仿射与对偶仿射内点法的线性规划求解器

资 源 简 介

本算法包实现了线性规划领域中两类核心的仿射尺度内点法，即原仿射内点法（Primal Affine Scaling Method）和对偶仿射内点法（Dual Affine Scaling Method）。原仿射内点法在原问题的可行域内部进行搜索，其核心原理是利用当前迭代点构造一个对角缩放矩阵，通过仿射变换将当前的内点变换到单位空间的中心，随后在该变换空间内沿目标函数下降最快的梯度方向移动，最后再通过逆变换映射回原空间，从而在保持可行性的同时快速接近最优解。对偶仿射内点法则是针对对偶问题设计的，它通过保持对偶

详 情 说 明

项目介绍：基于MATLAB的原仿射与对偶仿射内点法线性规划求解器

本算法包旨在实现线性规划（Linear Programming）中的两类核心仿射尺度内点算法：原仿射内点法（Primal Affine Scaling Method）与对偶仿射内点法（Dual Affine Scaling Method）。与传统的单纯形法沿可行域边界搜索的策略不同，该求解器在可行域内部进行迭代更新。通过仿射变换将当前的迭代点置于缩放空间的中心，该算法能够有效地利用梯度下降或对偶上升方向快速逼近最优解。该实现尤其适用于需要稳定收敛特性的线性规划学习与工程仿真场景。

---

功能特性

1. 双算法支持：内置完整的原空间与对偶空间仿射尺度搜索算法，用户可以对比观察两类方法在同一问题上的收敛路径。
2. 数值优化处理：在计算投影梯度和搜索方向时，采用MATLAB内置的矩阵左除运算符（）处理正定方程组，确保了大矩阵计算的数值稳定性。
3. 步长保护机制：引入步长缩放因子（通常设为0.9），严格保证迭代点在搜索过程中不会触碰可行域边界，从而维持内搜索的有效性。
4. 实时数据追踪：自动记录每一次迭代的目标函数值，以便进行后续的收敛性能分析。
5. 可视化展示：内置绘图功能，能够自动生成原法与对偶法的收敛轨迹图，直观展现目标函数值的下降或上升过程。

---

系统要求

• MATLAB R2016b 或更高版本。
• 环境无需额外安装工具箱（如 Optimization Toolbox），所有算法均基于核心矩阵运算手动实现。

---

算法逻辑与实现细节

1. 核心求解逻辑

程序遵循标准线性规划形式： 最小化： $c^T x$ 约束条件： $Ax = b$ 且 $x ge 0$

对应的对偶问题形式用于对偶仿射法中： 最大化： $b^T y$ 约束条件： $A^T y + s = c$ 且 $s ge 0$

2. 关键算法函数说明

原仿射尺度算法实现 该函数首先构造基于当前点 $x$ 的对角缩放矩阵 $X$。通过求解投影方程计算对偶乘子 $w$，随后在原空间计算下降方向 $dx$。算法检测 $dx$ 中的负分量，通过比例测试确定最大允许步长，并乘以缩放因子 $alpha$ 以确保下一迭代点仍为严格的正内点。当投影梯度的范数低于设定阈值时，认为达到最优性。

对偶仿射尺度算法实现 该函数通过维护对偶可行性进行迭代。它利用对偶松弛变量 $s$ 构造缩放矩阵，并计算对偶上升方向 $dy$ 和松弛变量的变化方向 $ds$。与原法类似，程序通过对 $ds$ 进行比例测试来限定步长。该方法通过不断提升对偶目标函数值 $b^T y$ 来从内部逼近原问题的最优解。

结果显示与报表 实现了一套格式化的输出逻辑，在计算完成后，程序会自动在命令行窗口输出算法的收敛状态、迭代总次数、最优目标函数值以及最终的最优解向量。

收敛性可视化 通过双子图布局对比展示：

• 左图：展示原仿射法目标函数值的下降曲线。
• 右图：展示对偶仿射法对偶目标值的上升轨迹。

---

使用方法

1. 参数配置：在主程序模块中，用户可以自定义目标函数系数 $c$、约束矩阵 $A$ 以及约束右端项 $b$。
2. 提供初始点：此类算法需要初始的可行内点。用户需要通过赋值操作提供满足 $Ax=b, x>0$ 的原点 $x_0$，以及满足 $A^T y < c$ 的对偶点 $y_0$。
3. 参数调整：

* 可以通过修改 alpha 来调整步长的进取程度（建议范围 0.9-0.99）。 * 通过 epsilon 设置收敛精度。 * 通过 max_iter 限制最大迭代尝试次数。

1. 运行：直接运行主脚本，程序将依次执行两种算法并自动弹出收敛分析图表。

---

性能分析

• 收敛效率：仿射尺度法通常比单纯形法在更高维的问题上表现出更少的迭代次数，但在每次迭代中需要进行矩阵乘法和线性方程组求解。
• 鲁棒性：通过 $alpha$ 因子限制，算法能够有效避免在极点处产生的数值振荡，确保收敛过程的平滑性。
• 终止条件：程序基于投影梯度模长进行判断，这在理论上等价于检查 KKT 条件的满足程度。