标题： 无矩阵的内点连续轨迹用于线性约束凸规划 显示英文标题

标题： A matrix-free interior point continuous trajectory for linearly constrained convex programming

摘要： 求解线性约束凸规划的内点方法在每次迭代中涉及一个变量投影矩阵以处理线性约束。 该矩阵在可行区域边界附近往往变得病态，导致错误的搜索方向和额外的计算成本。 因此，提出并研究了一种无矩阵的内点增广拉格朗日连续轨迹，用于求解线性约束凸规划。 建立了一个密切相关常微分方程（ODE）系统。 在这个ODE系统中，不再需要变量投影矩阵。 仅假设最优解的存在，我们证明了，从任何内部可行点出发，(i) 内点增广拉格朗日连续轨迹是收敛的；并且 (ii) 极限点确实是原始优化问题的最优解。 此外，在增加严格互补条件的情况下，我们证明相关的拉格朗日乘子收敛到拉格朗日对偶问题的最优解。 基于研究的ODE系统，提出了几种可能的离散算法搜索方向并进行了讨论。 显示英文摘要

摘要： Interior point methods for solving linearly constrained convex programming involve a variable projection matrix at each iteration to deal with the linear constraints. This matrix often becomes ill-conditioned near the boundary of the feasible region that results in wrong search directions and extra computational cost. A matrix-free interior point augmented Lagrangian continuous trajectory is therefore proposed and studied for linearly constrained convex programming. A closely related ordinary differential equation (ODE) system is formulated. In this ODE system, the variable projection matrix is no longer needed. By only assuming the existence of an optimal solution, we show that, starting from any interior feasible point, (i) the interior point augmented Lagrangian continuous trajectory is convergent; and (ii) the limit point is indeed an optimal solution of the original optimization problem. Moreover, with the addition of the strictly complementarity condition, we show that the associated Lagrange multiplier converges to an optimal solution of the Lagrangian dual problem. Based on the studied ODE system, several possible search directions for discrete algorithms are proposed and discussed.