基于对偶仿射理论的线性规划内点法求解程序

资 源 简 介

该项目实现了线性规划领域中经典的基于对偶仿射理论的内点法。该算法通过在可行域内部寻找搜索方向，避免了单纯形法在多胞形外部边缘搜索的高复杂性。其核心逻辑是针对对偶规划问题，利用仿射缩放变换（Affine Scaling）将当前的内点映射到特定空间的中心位置，进而计算目标函数的最速下降方向，随后再通过逆变换回到原始空间进行迭代更新。该程序能够自动将一般形式的线性规划问题转换为标准形式进行求解，不仅支持约束条件的精确匹配，还设计了灵活的步长调节机制以保证各步迭代始终处于可行域内部。在工程应用中，它被广泛用于解决

详 情 说 明

对偶仿射内点法线性规划求解器项目文档

项目介绍

本项目是一个基于对偶仿射（Dual Affine）理论的内点法MATLAB实现，专门用于求解线性规划（LP）问题。该算法不同于传统的从可行域外部顶点搜索的单纯形法，而是通过深入可行域内部，沿着目标函数值增长（对偶问题为极大化）最快的方向进行搜索。利用仿射缩放变换技术，该程序能够有效地处理具有高维变量和复杂约束的优化问题，通过迭代映射与逆变换，在保证每一步都在可行域内的同时，快速逼近最优解。

功能特性

1. 启发式初始点生成：程序内置了初始对偶可行点的寻找逻辑，通过最小二乘法与启发式偏移量调整，确保初始点严格处于对偶可行域内部。
2. 仿射缩放机制：动态构造基于对偶松弛变量的缩放矩阵，将当前点映射到中心位置，以优化搜索方向。
3. 稳健的步长控制：通过比例测试（Ratio Test）计算最大步长，并配合缩减因子 $gamma=0.95$，严格防止迭代点触碰可行域边界。
4. 主变量恢复逻辑：利用KKT条件中的投影关系，在对偶问题求解完成后，精确计算并恢复出主问题的最优决策变量 $x$。
5. 多维收敛监控：实时追踪对偶目标函数值和互补松弛残差，并提供半对数坐标下的收敛曲线分析。

实现逻辑与算法细节

程序的执行核心遵循以下逻辑步骤，这些步骤在代码运行过程中严格按序执行：

1. 问题定义与参数初始化

程序首先定义标准形式的线性规划系数。通过设置最大迭代次数（100次）和收敛精度阈值（1e-8），建立计算的基准范围。

1. 对偶可行域的进入

为了满足对偶内点法的前置条件 $s > 0$ 且 $A^T y + s = c$，程序采用两步走策略：首先利用 $(AA^T)^{-1}Ac$ 计算一个初步的 $y$ 值，接着根据计算出的残差 $s$ 的正负情况进行偏移补偿（+10 偏移量），最后再次通过最小二乘投影修正 $y$，确保初始约束的精确匹配。

1. 核心迭代循环

程序的主体是一个 for 循环，每一轮迭代包含四个关键动作：

• 缩放矩阵构造：使用对偶松弛变量 $s$ 的倒数平方构造对角矩阵 $S^{-2}$。
• 搜索方向计算：通过求解线性方程组 $(A S^{-2} A^T) dy = b$ 获得对偶变量的更新方向 $dy$，并由于约束 $A^T y + s = c$，推导出松弛变量方向 $ds = -A^Td y$。
• 严格可行补偿：对 $ds$ 中的负元素进行比例测试，计算使得 $s$ 保持为正的最大允许步长。
• 状态更新：沿搜索方向更新 $y$ 和 $s$。

1. 主变量 $x$ 的精确恢复

在迭代结束或达到阈值后，程序利用公式 $x = D^2 A^T (A D^2 A^T)^{-1} b$ 进行末尾计算。这是对偶内点法的关键，它通过投影算子将对偶空间的信息映射回原始空间，从而得到满足主约束的最优解。

1. 收敛性评判与可视化

算法监控两个核心指标：一是步长的模长变化，二是互补松弛残差（Complementarity Gap）。当这两个指标降至 $10^{-8}$ 以下时，算法判定为收敛。最终通过绘图功能输出目标函数的变化轨迹图和残差收敛曲线图。

关键函数与计算公式说明

1. 缩放系统矩阵：代码中使用 M = A * S_inv2 * A'。这是算法的计算重心，其条件数直接影响求解精度。
2. 比例测试逻辑：利用 min(-s(neg_idx) ./ ds(neg_idx)) 寻找限制更新的临界分量。
3. 收敛指标：采用 norm(c - A' * y - s) 来衡量对偶约束的满足程度。

使用方法

1. 在MATLAB环境中打开主程序文件。
2. 在定义部分修改矩阵 $A$、目标向量 $c$ 以及约束右侧向量 $b$ 以匹配您的特定线性规划问题。
3. 运行该程序。
4. 在命令行窗口（Command Window）查看每轮迭代的目标函数值变化。
5. 程序结束后，会自动弹出分析图表，并输出主问题的最优解 $x$ 和最优目标函数值。

系统要求

• MATLAB R2016b 或更高版本。
• 操作系统支持 Windows、macOS 或 Linux。
• 无需额外安装特殊的数学优化工具箱，程序基于MATLAB基础线性代数运算库实现。