Subspace choices for the Celis-Dennis-Tapia problem. (English) Zbl 1384.49028

Zhao, Xin; Fan, Jin Yan

Sci. China, Math. 60, No. 9, 1717-1732 (2017).

Summary: G. N. Grapiglia et al. [J. Oper. Res. Soc. China 1, No. 4, 425–451 (2013; Zbl 1329.90137)] proved subspace properties for the Celis-Dennis-Tapia (CDT) problem. If a subspace with lower dimension is appropriately chosen to satisfy subspace properties, then one can solve the CDT problem in that subspace so that the computational cost can be reduced. We show how to find subspaces that satisfy subspace properties for the CDT problem, by using the eigendecomposition of the Hessian matrix of the objective function. The dimensions of the subspaces are investigated. We also apply the subspace technologies to the trust region subproblem and the quadratic optimization with two quadratic constraints.

MSC:

49M37	Numerical methods based on nonlinear programming
65K05	Numerical mathematical programming methods
90C20	Quadratic programming

Keywords:

subspace properties; subspace choices; Celis-Dennis-Tapia (CDT) problem

References:

[1]	Ai, W; Zhang, S, Strong duality for the CDT subproblem: A necessary and sufficient condition, SIAM J Optim, 19, 1735-1756, (2009) · Zbl 1187.90290
[2]	Bomze, I M; Overton, M L, Narrowing the difficulty gap for the celis-dennis-tapia problem, Math Program, 151, 459-476, (2015) · Zbl 1328.90095
[3]	Celis, M R; Dennis, J E; Tapia, R A, A trust region strategy for nonlinear equality constrained optimization, Numer Optim, 1984, 71-82, (1985) · Zbl 0566.65048
[4]	Chen, X; Yuan, Y X, On local solutions of the celis-dennis-tapia subproblem, SIAM J Optim, 10, 359-383, (2000) · Zbl 0957.65060
[5]	Dhillon, I S; Parlett, B N, Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices, Linear Algebra Appl, 387, 1-28, (2004) · Zbl 1055.65048
[6]	Grapiglia, G N; Yuan, J; Yuan, Y X, A subspace version of the powell-yuan trust-region algorithm for equality constrained optimization, J Oper Res Soc China, 1, 425-451, (2013) · Zbl 1329.90137
[7]	Gu, M; Eisenstat, S C, A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem, SIAM J Matrix Anal Appl, 16, 172-191, (1995) · Zbl 0815.65050
[8]	Li, G D; Yuan, Y X, Compute a celis-dennis-tapia step, J Comput Math, 23, 463-478, (2005) · Zbl 1080.65048
[9]	Peng, J M; Yuan, Y X, Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM J Optim, 7, 579-594, (1997) · Zbl 0891.90150
[10]	Powell, M J D; Yuan, Y X, A trust region algorithm for equality constrained optimization, Math Program, 49, 189-211, (1990) · Zbl 0816.90121
[11]	Sakaue S, Nakatsukasa Y, Takeda A, et al. A polynomial-time algorithm for nonconvex quadratic optimization with two quadratic constraints. Http://www.keisu.t.u-tokyo.ac.jp/research/techrep/data/2015/METR15-03.pdf, 2015
[12]	Sturm, J F; Zhang, S, On cones of nonnegative quadratic functions, Math Oper Res, 28, 246-267, (2003) · Zbl 1082.90086
[13]	Wang, Z H; Yuan, Y X, A subspace implementation of quasi-Newton trust region methods for unconstrained optimization, Numer Math, 104, 241-269, (2006) · Zbl 1101.65066
[14]	Yuan, Y X, On a subproblem of trust region algorithms for constrained optimization, Math Program, 47, 53-63, (1990) · Zbl 0711.90062
[15]	Yuan, Y X, A dual algorithm for minimizing a quadratic function with two quadratic constraints, J Comput Math, 9, 348-359, (1991) · Zbl 0758.65050
[16]	Yuan, Y X, Subspace methods for large scale nonlinear equations and nonlinear least squares, Optim Eng, 10, 207-218, (2009) · Zbl 1171.65040
[17]	Yuan, Y X, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numer Algebra Control Optim, 1, 15-34, (2011) · Zbl 1226.65045
[18]	Zhang, Y, Computing a celis-dennis-tapia trust-region step for equality constrained optimization, Math Program, 55, 109-124, (1992) · Zbl 0773.90056