Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations. (English) Zbl 0846.49017

Stern, Ronald J.; Wolkowicz, Henry

SIAM J. Optim. 5, No. 2, 286-313 (1995).

The following problem arises in trust region numerical methods for minimization problems: \[ \min \mu(y):= y^t By- 2\psi^t y \quad \text{subject to } Ay= b,\;\;y^t Dy\leq \delta,\;y\in \mathbb{R}^n, \tag{P*} \] where \(y\in \mathbb{R}^n\), \(b\in \mathbb{R}^{n\times n}\) is symmetric, \(A\) is \(m\times n\), \(b\in \mathbb{R}^m\), \(D\) is a positive definite scaling matrix, and \(\delta> 0\) is the trust region radius.
In this paper (P*) is generalized in two ways and such trust region subproblems are related to eigenvalue perturbation theory. Specifically, the authors consider the problem \[ \min \mu (y):= y^t By- 2\psi^t y \quad \text{subject to } \beta\leq y^t Cy\leq \alpha,\;\;y\in \mathbb{R}^n, \tag{P} \] where \(B\) and \(C\) are symmetric matrices with no definiteness assumed, and \(-\infty \leq \beta\leq \alpha\leq \infty\). The motivation is “to extend the existing theory of trust region subproblems in the hope that this will be a step in the direction of solving general problems with quadratic objectives and quadratic constraints”. Section 2 contains necessary and sufficient optimality conditions for (P), as well as a general existence theorem. A further analysis is undertaken in section 3: (P) is transformed to a “standard form” where the matrix pencil \(B- \lambda C\) satisfies a certain regularity condition, and this form is used to catalogue the various conditions under which an optimum for (P) can exist. In section 4 the results are applied to obtain spectral information regarding the completely general parametric border perturbation of \(B\) under the assumption that the spectral decomposition of \(B\) is known. In section 5 a general dual program for (P) is discussed which is a true concave maximization problem. It is shown that these trust region subproblems are implicitly convex. Moreover, this dual program provides bounds on the optimal value of (P) which yields stopping criteria for algorithms for (P) that are based on duality gap considerations. The authors conclude with an appendix to show how the algorithm and results in D. M. Gay [SIAM J. Sci. Stat. Comput. 2, 186-197 (1981; Zbl 0467.65027)] and J. J. More and D. C. Sorensen [ibid. 4, 552-572 (1983; Zbl 0551.65042)] can be extended to their more general two-sided indefinite trust region subproblems.

Reviewer: R.Euler (Brest)

MSC:

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

Keywords:

infinite trust region subproblems; nonsymmetric eigenvalue perturbation theory; minimization problems; necessary and sufficient optimality conditions; existence

Citations:

Zbl 0467.65027; Zbl 0551.65042