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

资 源 简 介

该项目提供了一个完整的MATLAB程序，用于实现原对偶内点算法以求解标准形式的线性规划问题。程序的核心在于同时处理原问题和对偶问题的变量，通过构建并求解KKT系统的线性近似来寻找下降方向。具体实现步骤包括：初始化原变量、对偶变量和松弛变量；在每次迭代中，计算对偶残差、原残差和互补松弛度；应用牛顿法求解线性方程组以获取搜索方向；利用比率测试确定步长，以确保所有变量在迭代过程中始终保持在可行域的内部；通过引入中心参数逐步向最优解逼近。该程序适用于解决中大规模的线性优化问题，具有收敛速度快、多项式时间复杂度等优点，常用于电力系统优化、物流调度、金融组合投资以及各类工程设计中的约束优化分析。

详 情 说 明

基于MATLAB的原对偶内点算法实现

项目介绍

本项目实现了一个基于原对偶内点算法（Primal-Dual Interior Point Method）线性规划求解器。该程序旨在解决标准形式的线性规划问题：最小化目标函数 $c^T x$，满足约束条件 $Ax = b$ 且变量 $x ge 0$。该算法的核心思想是同时优化原问题和对偶问题的解，通过牛顿法逼近KKT（Karush-Kuhn-Tucker）条件的解，并利用中心参数和步长策略确保迭代路径始终在可行域的内部（即保证变量严格大于零）。

主要功能特性

• 自动生成测试数据：程序能够随机构造具有满秩约束矩阵、已知最优解及对偶变量的可行测试用例，方便验证算法。
• 高效的KKT系统求解：采用舒尔补（Schur Complement）方法压缩线性方程组，提高了计算搜索方向的数值稳定性与效率。
• 动态步长控制：通过比率测试（Ratio Test）计算原变量和对偶变量的最大允许步长，并应用缩放因子确保变量的严格正性。
• 收敛过程可视化：程序在迭代过程中实时打印残差和目标值，并在结束后生成直观的收敛曲线图。
• 多准则终止判定：结合原问题残差、对偶问题残差以及互补间隙（Duality Gap）作为收敛标准。

算法实现逻辑

程序遵循标准的预测-校正内点法流程，具体步骤如下：

1. 环境初始化：定义矩阵规模，生成随机但保证可行的 $A, b, c$ 矩阵，并初始化变量 $x, y, s$ 为全1或全0向量。
2. 迭代计算：

- 残差评估：计算原约束残差 $r_p = Ax - b$ 和对偶约束残差 $r_d = A^T y + s - c$。 - 互补间隙：计算当前均值互补间隙 $mu = (x^T s) / n$。 - 牛顿方向求解：构建KKT系统，通过舒尔补方法先求解对偶变量增量 $Delta y$，进而推导出松弛变量增量 $Delta s$ 和原变量增量 $Delta x$。在此过程中引入中心参数 $sigma$ 以引导搜索方向向中心路径靠拢。 - 步长确定：分别针对 $x$ 和 $s$ 进行比率测试，寻找不破坏非负性约束的最大步长，并乘以缩放因子 $gamma$。 - 变量更新：更新 $x, y, s$ 的值。

1. 检查终止条件：当残差范数和互补间隙均小于设定的容差 $epsilon$ 时，停止迭代。
2. 结果输出：打印最终目标值、残差、迭代次数，并绘制收敛历程图。

核心细节分析

• 线性方程组优化：代码通过 M = A * (repmat(D2', m, 1) .* A') 高效计算系数矩阵，其中 $D^2 = X S^{-1}$，这种处理方式避免了直接操作大型对角矩阵，节省了内存并提升了速度。
• 牛顿方向右端项：构造了包含中心项和残差项的复合向量，利用 dy = M v 求解线性系统。
• 鲁棒步长策略：通过 min(-x(idx) ./ dx(idx)) 的逻辑检索最严格的步长限制，确保算法在向边界逼近时不会跳出可行域。
• 结果展示：利用 semilogy 绘制对数坐标下的残差下降曲线，能够清晰反映算法在接近最优解时的线性收敛特性。

系统要求

• 软件环境：MATLAB R2016a 或更高版本。
• 核心依赖：无需外部工具箱，仅依赖MATLAB内置的矩阵运算函数和绘图功能。
• 硬件要求：由于采用矩阵化运算，支持处理中等规模（变量数在千级以内）的线性规划问题。

使用说明

1. 启动方式：在MATLAB命令行窗口中直接运行名为 main 的函数。
2. 流程说明：

- 运行后，终端将实时显示每一轮迭代的序号、目标函数值、原残差范数和对偶残差范数。 - 迭代结束后，将自动弹出图形窗口，展示目标函数随迭代次数的变化以及残差/间隙的对数收敛图。 - 终端最后会输出算法是否成功收敛、总迭代次数、最终最小化目标值以及决策变量 $x$ 的前十个分量示例。

1. 参数调整：可以通过修改程序初期的 max_iter（最大迭代步数）、epsilon（容差精度）或 sigma_val（中心化参数）来观察不同配置对算法收敛性能的影响。

结果输出内容说明

• 算法状态：明确提示“算法成功收敛”或“达到最大迭代次数”。
• 数值统计：包括最小化后的目标函数 $c^T x$ 的精确值。
• 收敛指标：最终的原对偶综合残差范数。
• 曲线图表：

- 上图：目标函数演变曲线。 - 下图：对偶间隙、原残差、对偶残差随迭代步数下降的综合曲线。