Projected Hessian algorithm with backtracking interior point technique for linear constrained optimization

Abstract

In this paper, we propose a new trust-region-projected Hessian algorithm with nonmonotonic backtracking interior point technique for linear constrained optimization. By performing the QR decomposition of an affine scaling equality constraint matrix, the conducted subproblem in the algorithm is changed into the general trust-region subproblem defined by minimizing a quadratic function subject only to an ellipsoidal constraint. By using both the trust-region strategy and the line-search technique, each iteration switches to a backtracking interior point step generated by the trustregion subproblem. The global convergence and fast local convergence rates for the proposed algorithm are established under some reasonable assumptions. A nonmonotonic criterion is used to speed up the convergence in some ill-conditioned cases.

Keywords

trust-region method / interior point backtracking / nonmonotone / 90C30 / 65K05 / 49M40

References

[1] Coleman T. F., Li Y. An interior trust region approach for minimization subject to bounds. SIAM J Optim, 1996, 6(3): 418-445.

[2] Nocedal J., Yuan Y. Yuan Y. Combining trust region and line search techniques. Advances in Nonlinear Programming, 1998, Dordvechat: Kluwer, 153-175.

[3] Grippo L., Lampariello F., Lucidi S. A nonmonotonic line search technique for Netwon’s methods. SIAM J Numer Anal, 1986, 23: 707-716.

[4] Deng N. Y., Xiao Y., Zhou F. J. A nonmonotonic trust region algorithm. J. Optim Theory Appl, 1993, 76: 259-285.

[5] Sorensen D. C. Newton’s method with a model trust region modification. SIAM J Numer Anal, 1982, 19: 409-426.

[6] Zhu D. T. Curvilinear paths and trust region methods with nonmonotonic back tracking technique for unconstrained optimization. J Comput Math, 2001, 19: 241-258.