Solving Karush--Kuhn--Tucker Systems via the Trust Region and the Conjugate Gradient Methods
Solving Karush--Kuhn--Tucker Systems via the Trust Region and the Conjugate Gradient Methods
复制标题
DOI：
10.1137/s105262340038256x
复制
发表时间：
2003-02
期刊：
影响因子：
--
通讯作者：
H. Qi;L. Qi;Defeng Sun
中科院分区：
文献类型：
--
作者：
H. Qi;L. Qi;Defeng Sun
一个流行的方法来解决Karush-Kuhn-Tucker（KKT）系统，主要是由变分不等式问题，是将其转化为一个约束最小化问题与简单的界限。在本文中，我们提出了一个信赖域方法来解决与信赖域子问题的截断共轭梯度（CG）方法，这是有效的成本解决的重新制定的问题。与现有方法相比，该方法的其他优点包括：可以通过截断CG方法找到信赖域子问题的良好近似解，并且以简单的方式进行判断;此外，每次迭代中的工作矩阵是H，而不是凝聚HTH，其中H是在重新表述中使用的函数的广义雅可比矩阵元素。事实上，所使用的矩阵是降维的。我们特别注意确保截断CG方法的成功以及简单约束条件下迭代的可行性。所提出的方法的另一个特点是，我们允许的价值函数值增加在一些迭代，以加快收敛。全球和超线性/二次收敛的标准假设下。数值结果报告的一个子集的问题，从MCPLIB收集[S。P. Dirkse和M. C.费里斯，奥普蒂姆。方法采用计算机软件，5（1995），pp. 319- 345]。
A popular approach to solving the Karush--Kuhn--Tucker (KKT) system, mainly arising from the variational inequality problem, is to reformulate it as a constrained minimization problem with simple bounds. In this paper, we propose a trust region method for solving the reformulation problem with the trust region subproblems being solved by the truncated conjugate gradient (CG) method, which is cost effective. Other advantages of the proposed method over existing ones include the fact that a good approximated solution to the trust region subproblem can be found by the truncated CG method and is judged in a simple way; also, the working matrix in each iteration is H, instead of the condensed HTH, where H is a matrix element of the generalized Jacobian of the function used in the reformulation. As a matter of fact, the matrix used is of reduced dimension. We pay extra attention to ensure the success of the truncated CG method as well as the feasibility of the iterates with respect to the simple constraints. Another feature of the proposed method is that we allow the merit function value to be increased at some iterations to speed up the convergence. Global and superlinear/quadratic convergence is shown under standard assumptions. Numerical results are reported on a subset of problems from the MCPLIB collection [S. P. Dirkse and M. C. Ferris, Optim. Methods Softw., 5 (1995), pp. 319--345].