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

资 源 简 介

本项目通过MATLAB环境下实现了线性规划中两种核心的内点算法：原仿射内点法（Primal Affine Scaling Method）和对偶仿射内点法（Dual Affine Scaling Method）。 原仿射内点法主要针对处于标准型的线性规划原问题，其核心逻辑是在可行域的内部进行迭代。算法在每一步迭代中利用当前的内部可行点构造一个对角缩放矩阵，将当前点映射到仿射空间的中心，随后在该变换后的空间内沿目标函数下降最快的投影梯度方向移动，并通过步长控制参数确保新点始终保持在可行域内部，从而避免触碰边界

详 情 说 明

基于MATLAB的原仿射与对偶仿射内点法优化求解器

项目介绍

本项目是一个用于求解线性规划问题的数学优化工具箱。它实现了内点法中最为经典的两种改进策略：原仿射内点法和对偶仿射内点法。不同于传统单纯形法沿着可行域的边界（定点）移动，本求解器通过从可行域内部出发，利用仿射变换和投影梯度技术直接穿过可行域内部寻找最优解。该工具适用于中等规模线性规划问题的数值解法验证、算法收敛性研究以及最优化理论的教学演示。

功能特性

1. 模块化设计：独立实现了针对原问题空间的仿射缩放逻辑和针对对偶问题空间的缩放逻辑。
2. 稳健的数值计算：在求解线性系统时采用左除运算符，确保了在矩阵求逆过程中的数值稳定性。
3. 可视化分析：程序自动生成求解过程的收敛曲线，直观展示目标函数值随迭代次数的下降（或上升）趋势。
4. 步长保护机制：内置步长缩放因子，确保在每一次迭代中新生成的数据点始终严格处于可行域内部，防止触碰边界导致的数值发散。

系统要求

1. 软件环境：MATLAB R2016b 或更高版本。
2. 硬件要求：通用办公电脑配置即可。
3. 依赖项：无需安装额外的工具箱，仅依赖MATLAB基础矩阵运算库。

实现逻辑与功能说明

程序通过一个主控函数引导，按照以下流程执行：

#### 1. 参数初始化 程序预设了一个标准型线性规划问题。原问题定义为最小化 $c^T x$，约束条件为 $Ax = b$ 且 $x geq 0$。用户需配置收敛容差（epsilon）、步长因子（alpha）以及最大迭代次数。此外，用户需要手动提供一个满足约束条件的初始严格内点。

#### 2. 原仿射内点法逻辑 算法在每一步迭代中执行以下关键操作：

• 构造缩放矩阵：利用当前可行点 $x$ 构造对角缩放矩阵 $X$。
• 计算对偶估计量：通过求解线性方程组 $(AX^2A^T)w = AX^2c$ 获取对偶变量的估计值 $w$。
• 确定下降方向：在原空间计算投影梯度方向 $d = X^2(c - A^T w)$。该方向代表了在保持等式约束的前提下，目标函数下降最快的方向。
• 步长控制：通过比例测试确定最大允许步长，并结合缩放因子确保新点 $x = x - text{step} cdot d$ 满足严格大于零的约束。

#### 3. 对偶仿射内点法逻辑 该部分将逻辑应用于对偶线性规划问题，最大化 $b^T y$，约束条件为 $A^T y + s = c$ 且 $s geq 0$：

• 计算松弛变量：根据当前的对偶变量 $y$ 计算松弛量 $s = c - A^T y$。
• 构造对偶缩放矩阵：利用松弛变量的倒数构造缩放矩阵。
• 搜索方向计算：求解 $(AS^{-2}A^T)dy = b$ 得到对偶变量的变化方向 $dy$，并同步推导出松弛变量的变化方向 $ds$。
• 迭代更新：采用类似的步长控制逻辑，确保松弛变量 $s$ 在更新后依然保持严格正性，从而实现对偶目标函数值的稳步提升。

#### 4. 收敛判断与输出 算法通过监测梯度向量的范数或搜索方向的模长来判断是否达到最优。一旦满足收敛精度或达到最大迭代次数，程序将停止运行，并输出两种方法的迭代次数、最终最优目标函数值，并绘制对比曲线。

关键函数与算法细节分析

#### 投影梯度算法 在原仿射内点法中，核心难点在于如何保证移动方向 $d$ 既能降低目标函数值，又不破坏 $Ax=b$ 的约束。代码中通过正交投影矩阵的思想，利用对角缩放矩阵 $X$ 将非球形的可行域转化为近似球形，从而使得在变换空间内的梯度下降更加有效。

#### 步长缩放因子 (Alpha) 代码中统一使用了 $alpha = 0.9$ 的比例。这是一个安全系数，用于防止迭代点直接落在可行域的边界上。因为一旦某个变量分量变为 0，缩放矩阵将变得奇异，导致算法崩溃。

#### 数值灵敏度处理 在计算 $w$ 或 $dy$ 时，涉及到 $AX^2A^T$ 或 $AS^{-2}A^T$ 的求逆过程。代码没有直接调用 inv() 函数，而是使用了 MATLAB 的反斜杠运算符（），这在由于可行点接近边界而导致矩阵病态时，能显著提高计算的精度和成功率。

#### 结果呈现 程序最终通过双子图布局展示收敛历程。原仿射法展示的是最小化过程中的值下降，而对偶仿射法展示的是最大化过程中的值上升，两者共同指向最优解，体现了原-对偶对称性的美感。