求解线性约束最优化问题的有效集算法  

An Active Set Algorithm for Nonlinear Programming with Linear Constraints

作　　者：高旅端[1] 陈志[1] 李苏祥[1] 

机构地区：[1]北京工业大学应用数理学院,北京100022

出　　处：《北京工业大学学报》2006年第3期283-288,共6页Journal of Beijing University of Technology

摘　　要：为了保持投影梯度求解法的线性约束系数矩阵的稀疏性,且不降低算法的效率。在确定可行点处的可行方向时,使用了矩阵的隐式LU分解技术,构造有效约束的零空间．本文提出了求解线性约束最优化问题的有效集算法,对于线性约束系数矩阵是稀疏矩阵时,能较好地保持稀疏性,提高了算法的效率．与数值试验的结果吻合．The projected gradient method is an efficient method for solving nonlinear programming problems with linear constraints. However, it cannot maintain the sparsity of the coefficient matrix of linear constraints, which results in lower calculation efficiency. This article presented a new method to solve the problem, by which the author generated the null space of active constraints by applying technique of the implicit LU decomposition of a matrix in the process of determining the feasible direction on feasible points. Numerical test results show that the active set algorithm for nonlinear programming with linear constraints provided in this article can not only maintain the sparsity of coefficient matrix of linear constrains, but also improve the calculation efficiency.

关 键 词：算法 矩阵代数 非线性规划 隐式LU分解 稀疏矩阵 

分 类 号：O221.2[理学—运筹学与控制论]