Abstract
Trust-region methods are powerful optimization methods. The conic model method is a new type of method with more information available at each iteration than standard quadratic-based methods. Can we combine their advantages to form a more powerful method for constrained optimization? In this paper we give a positive answer and present a conic trust-region algorithm for non-linearly constrained optimization problems. The trust-region subproblem of our method is to minimize a conic function subject to the linearized constraints and the trust region bound. The use of conic functions allows the model to interpolate function values and gradient values of the Lagrange function at both the current point and previous iterate point. Since conic functions are the extension of quadratic functions, they approximate general nonlinear functions better than quadratic functions. At the same time, the new algorithm possesses robust global properties. In this paper we establish the global convergence of the new algorithm under standard conditions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K.A. Ariyawansa, Deriving collinear scaling algorithms as extensions of quasi-Newton methods and the local convergence of DFP and BFGS related collinear scaling algorithm, Math. Programming 49 (1990) 23–48.
K.A. Ariyawansa and D.T.M. Lau, Local and-superlinear convergence of a class of collinear scaling algorithms that extends quasi-Newton methods with Broyden's bounded-Q class of updates, Optimization 23 (1992) 323–339.
R.H. Byrd, R.B. Schnabel and G.A. Shultz, A trust region algorithm for nonlinear constrained optimization, SIAM J. Numer. Anal. 24 (1987) 1152–1170.
T.F. Coleman and A.R. Conn, Second order condition for an exact penalty function, Math. Programming 19 (1980) 178–185.
A.R. Conn, N.I.M. Could and Ph.L. Toint, Trust Region Methods (SIAM, Philadelphia, USA, 2000).
W.C. Davidon, Conic approximation and collinear scaling for optimizers, SIAM J. Numer. Anal. 17 (1980) 268–281.
S. Di and W. Sun, Trust region method for conic model to solve unconstrained optimization problems, Optimization Methods and Software 6 (1996) 237–263.
M. El-Alem, A robust trust region algorithm with a nonmonotonic penalty parameter scheme for constrained optimization, SIAM J. Optimization 5 (1995) 348–378.
R. Fletcher, Practical Methods of Optimization, 2nd edn. (Wiley, 1987).
D.M. Gay, Algorithm 611, subroutines for unconstrained minimization using a model/trust region approach, ACM Trans. Math. Softw. 9 (1983) 503–524.
P.E. Gill, W.Murray and M.H. Wright, Numerical Linear Algebra and Optimization, Vol. 1 (Addison-Wesley, Reading, MA, 1991).
G.E. Golub and C.F. Van Loan, Matrix Computations, 3rd edn. (Johns Hopkins University Press, Baltimore, 1996).
Q. Han, J. Han and W. Sun, A modified quasi-Newton method with collinear scaling for unconstrained optimization, J. Computational and Applied Mathematics, submitted.
S.P. Han, A globally convergent method for nonlinear programming, J. Optimization Theory and Applications 22 (1977) 297–309.
X. He and W. Sun, Introduction to Generalized Inverses of Matrices (Jiangsu Sci. & Tech. Publisher, Nanjing, 1991).
J.J.Moré, B.S. Garbow and K.E. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Software 7 (1981) 17–41.
Q. Ni and S.Hu, A new derivative free algorithm based on conic interpolation model, Technical report, Faculty of Science, Nanjing University of Aeronautics and Astronautics (2001).
J. Nocedal and Y. Yuan, Combining trust region and line search techniques, Report NAM 07, Department of EECS, Northwestern University (1991).
E.O. Omojokun, Trust region algorithms for optimization with nonlinear equality and inequality constraints, Ph.D. Thesis, University of Colorado at Boulder (1989).
M.J.D. Powell, Convergence properties of a class of minimization algorithms, in: Nonlinear Programming 2, eds. O.L. Mangasarian, R.R. Meyer and S.M. Robinson (Academic Press, New York, 1975).
M.J.D. Powell, Variable metric methods for constrained optimization, in: Mathematical Programming, The State of the Art, eds. M.G.A. Bachem and B. Korte (Springer, Berlin, New York, 1983) pp. 283–311.
M.J.D. Powell, On the global convergence of trust region algorithms for unconstrained minimization, Math. Programming 29 (1984) 297–303.
M.J.D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization, Math. Programming 49 (1991) 189–211.
L. Qi and W. Sun, An iterative method for the minimax problem, in: Minimax and Applications, eds. D.Z. Du and P.M. Pardalos (Kluwer Academic, Boston, 1995) pp. 55–67.
S. Sheng, Interpolation by conic model for unconstrained optimization, Computing 54 (1995) 83–98.
D.C. Sorensen, The q-superlinear convergence of a collinear scaling algorithm for unconstrained optimization, SIAM Journal of Numerical Analysis 17 (1980) 84–114.
W. Sun, On nonquadratic model optimization methods, Asia and Pacific Journal of Operations Research 13 (1996) 43–63.
W. Sun, R. Sampaio and J. Yuan, Trust region algorithm for nonsmooth optimization, Applied Mathematics and Computation 85 (1997) 109–116.
Ph.L. Toint, Global convergence of a class of trust region methods for nonconvex minimization in Hilbert space, IMA J. Numerical Analysis 8 (1988) 231–252.
A. Vardi, A trust region algorithm for equality constrained minimization: convergence properties and implementation, SIAM J. Numer. Anal. 22 (1985) 575–591.
Y. Yuan, Condition for convergence of trust region algorithm for nonsmooth optimization, Math. Programming 31 (1985) 220–228.
Y. Yuan, On the convergence of a new trust region algorithm, Numer. Math. 70 (1995) 515–539.
Y. Yuan and W. Sun, Optimization Theory and Methods (Science Press, Beijing, China, 1997).
J.Z. Zhang and D.T. Zhu, Projected quasi-Newton algorithm with trust region for constrained optimization, J. Optimization Theory and Application 67 (1990) 369–393.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sun, W., Yuan, Yx. A Conic Trust-Region Method for Nonlinearly Constrained Optimization. Annals of Operations Research 103, 175–191 (2001). https://doi.org/10.1023/A:1012955122229
Issue Date:
DOI: https://doi.org/10.1023/A:1012955122229