A line search filter secant method for nonlinear equality constrained optimization
Tóm tắt
This paper formulates and analyzes a line search method for general nonlinear equality constrained optimization based on filter methods for step acceptance and secant methods for search direction. The feature of the new algorithm is that the secant algorithm is used to produce a search direction, a backtracking line search procedure is used to generate step size, some filtered rules are used to determine step acceptance, second order correction technique is used to reduce infeasibility and overcome the Maratos effect. Global convergence properties of this method are analyzed: under mild assumptions it is showed that every limit point of the sequence of iterates generated by the algorithm is feasible, and that there exists at least one limit point that is a stationary point for the problem. Moreover, it is also established that the Maratos effect can be overcome in our new approach by adding second order correction steps so that fast local superlinear convergence to a second order sufficient local solution is achieved. Finally, the results of numerical experiments are reported to show the effectiveness of the line search filter secant method.
Tài liệu tham khảo
M. C. Pinar and S. A. Zenios, On smooth exact penalty functions for convex constrained optimization, SIAM J. Optim., 1994, 4: 486–511.
X. J. Tong and D. H. Li, A trust region algorithm with null space technique for equality constrained optimization, Journal of Systems Science & Complexity, 2004, 17(1): 54–63.
J. L. Zhang and X. S. Zhang, An SQP method based on smoothing penalty function for nonlinear optimization with inequality constraint, Journal of Systems Science & Complexity, 2001, 14(2): 212–217.
R. Fletcher and S. Leyffer, Nonlinear programming without a penaty function, J. Math. Program., 2002, 91(2): 44–59.
R. Fletcher, N. I. M. Gould, S. Leyffer, Ph. L. Toint, and A. Wächter, Global convergence of a trust-region SQP-filter for general nonlinear programming, SIAM J. Optim., 2002, 13(3): 635–659.
C. Audet and J. E. Dennis, Jr., A pattern search filter method for nonlinear programming without derivatives, SIAM J. Optim., 2004, 14(4): 980–1010.
A. Wächter and L. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 2006, 106: 25–27.
A. Wächter and L. T. Biegler, Line search filter methods for nonlinear programming: Motivation and global convergence, SIAM J. Comput., 2005, 16(1): 1–31.
A. Wächter and L. T. Biegler, Line search filter methods for nonlinear programming: Local convergence, SIAM J. Optim., 2005, 16(1): 32–48.
R. Fontecilla, Local convergence of secant method for nonlinear constrained optimization, SIAM J. Numer. Anal., 1988, 25(2): 692–712.
R. Fletcher, Practical Methods of Optimization, John Wiley and Sons, New York, 1987.
A. R. Conn, N. I. M. Gould, and Ph. L. Toint, Trust Region Methods, Number 01 in MPS-SIAM Series on Optimization, SIAM, Philadelphia, USA, 2000.
R. Fontecilla, T. Steihaug, and R. A. Tapia, A convergence theory for a class of quasi-Newton methods for constrained optimization, SIAM J. Numer. Anal., 1987, 24(4): 1133–1151.
C. B. Gurwitz, Local convergence of two-piece update of a projected Hessian matrix, SIAM J. Optim., 1994, 4(4): 461–485.