Successive linearization methods for large-scale nonlinear programming problems
Successive linearization methods for large-scale nonlinear programming problems
复制标题
大规模非线性规划问题的逐次线性化方法
DOI：
10.1007/bf03167197
复制
发表时间：
1992
影响因子：
0.9
通讯作者：
T. Ibaraki
中科院分区：
文献类型：
--
作者：
M. Fukushima;Keiichi Takazawa;S. Ohsaki;T. Ibaraki
我们提出了一种稀疏性保持算法来解决大规模非线性规划问题。该算法在每次迭代时求解一个子问题，其中包含由简单二次项和线性化约束增强的线性化目标函数。线性化目标函数中添加的二次项起到步长限制的作用，这对于确保算法的全局收敛至关重要。如果使用共轭梯度法或逐次过松弛法来求解子问题，则原始问题的稀疏性得以保留，因为这些方法只需要对约束矩阵的行进行简单的操作。因此，当约束矩阵足够稀疏以能够以紧凑形式存储时，可以处理大规模问题。描述了算法的实际实现并报告了计算结果。
We propose a sparsity preserving algorithm for solving large-scale, nonlinear programming problems. The algorithm solves at each iteration a subproblem, which contains a linearized objective function augmented by a simple quadratic term and linearized constraints. The quadratic term added to the linearized objective function plays the role of step restriction which is essential in ensuring global convergence of the algorithm. If the conjugate gradient method or successive over-relaxation method is used to solve the subproblems, the sparsity of the original problem is preserved, because those methods only require simple operations on the rows of the constraint matrix. Thus, large-scale problems can be dealt with when the constraint matrices are sparse enough to be stored in a compact form. Practical implementation of the algorithm is described and computational results are reported.