Newton and quasi-Newton methods for normal maps with polyhedral sets

被引:31
作者
Han, J
Sun, D
机构
[1] Institute of Applied Mathematics, Academia Sinica, Beijing, P.R. China
[2] Institute of Applied Mathematics, Academia Sinica, Beijing
基金
中国国家自然科学基金;
关键词
normal maps; Newton methods; quasi-Newton methods; Q-superlinear convergence;
D O I
10.1023/A:1022653001160
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We present a generalized Newton method and a quasi-Newton method for solving H(x):=F(Pi(c)(x))+x-Pi(c)(x)=0, when C is a polyhedral set. For both the Newton and quasi-Newton methods considered here, the subproblem to be solved is a linear system of equations per iteration. The other characteristics of the quasi-Newton method include: (i) a Q-superlinear convergence theorem is established without assuming the existence of H' at a solution x* of H(x)= 0; (ii) only one approximate matrix is needed; (iii) the linear independence condition is not assumed; (iv) Q-superlinear convergence is established on the original variable x; and (v) from the QR-factorization of the kth iterative matrix, we need at most O((1 + 2\J(k)\ + 2\L-k\)n(2)) arithmetic operations to get the QR-factorization of the (k + 1)th iterative matrix.
引用
收藏
页码:659 / 676
页数:18
相关论文
共 21 条
[1]  
BROYDEN CG, 1965, MATH COMPUT, V19, P557
[2]  
CHEN X, 1994, COMPUT OPTIM APPL, V3, P157, DOI DOI 10.1007/BF01300972
[3]  
Dennis, 1996, NUMERICAL METHODS UN
[4]  
DENNIS JE, 1974, MATH COMPUT, V28, P549, DOI 10.1090/S0025-5718-1974-0343581-1
[5]  
Gill P. E., 1972, Journal of the Institute of Mathematics and Its Applications, V9, P91
[6]  
Golub GH, 2013, Matrix Computations, V4
[7]   FINITE-DIMENSIONAL VARIATIONAL INEQUALITY AND NONLINEAR COMPLEMENTARITY-PROBLEMS - A SURVEY OF THEORY, ALGORITHMS AND APPLICATIONS [J].
HARKER, PT ;
PANG, JS .
MATHEMATICAL PROGRAMMING, 1990, 48 (02) :161-220
[8]   LOCAL CONVERGENCE OF QUASI-NEWTON METHODS FOR B-DIFFERENTIABLE EQUATIONS [J].
IP, CM ;
KYPARISIS, J .
MATHEMATICAL PROGRAMMING, 1992, 56 (01) :71-89
[9]  
Josephy N.H., 1979, Technical summary report
[10]  
JOSEPHY NH, 1979, QUASINEWTON METHODS