On fast trust region methods for quadratic models with linear constraints

Mathematical Programming Computation - Tập 7 Số 3 - Trang 237-267 - 2015
M. J. D. Powell1
1Department of Applied Mathematics and Theoretical Physics, Centre for Mathematical Sciences, Wilberforce Road, Cambridge, CB3 0WA, England

Tóm tắt

Abstract Quadratic models $$Q_k ( \underline{x}), \underline{x}\in \mathcal{R}^n$$ Q k ( x ̲ ) , x ̲ ∈ R n , of the objective function $$F ( \underline{x}), \underline{x}\in \mathcal{R}^n$$ F ( x ̲ ) , x ̲ ∈ R n , are used by many successful iterative algorithms for minimization, where k is the iteration number. Given the vector of variables $$\underline{x}_k \in \mathcal{R}^n$$ x ̲ k ∈ R n , a new vector $$\underline{x}_{k+1}$$ x ̲ k + 1 may be calculated that satisfies $$Q_k ( \underline{x}_{k+1} ) < Q_k ( \underline{x}_k )$$ Q k ( x ̲ k + 1 ) < Q k ( x ̲ k ) , in the hope that it provides the reduction $$F ( \underline{x}_{k+1} ) < F ( \underline{x}_k )$$ F ( x ̲ k + 1 ) < F ( x ̲ k ) . Trust region methods include a bound of the form $$\Vert \underline{x}_{k+1} - \underline{x}_k \Vert \le \Delta _k$$ ‖ x ̲ k + 1 - x ̲ k ‖ ≤ Δ k . Also we allow general linear constraints on the variables that have to hold at $$\underline{x}_k$$ x ̲ k and at $$\underline{x}_{k+1}$$ x ̲ k + 1 . We consider the construction of $$\underline{x}_{k+1}$$ x ̲ k + 1 , using only of magnitude $$n^2$$ n 2 operations on a typical iteration when n is large. The linear constraints are treated by active sets, which may be updated during an iteration, and which decrease the number of degrees of freedom in the variables temporarily, by restricting $$\underline{x}$$ x ̲ to an affine subset of $$\mathcal{R}^n$$ R n . Conjugate gradient and Krylov subspace methods are addressed for adjusting the reduced variables, but the resultant steps are expressed in terms of the original variables. Termination conditions are given that are intended to combine suitable reductions in $$Q_k ( \cdot )$$ Q k ( · ) with a sufficiently small number of steps. The reason for our work is that $$\underline{x}_{k+1}$$ x ̲ k + 1 is required in the LINCOA software of the author, which is designed for linearly constrained optimization without derivatives when there are hundreds of variables. Our studies go beyond the final version of LINCOA, however, which employs conjugate gradients with termination at the trust region boundary. In particular, we find that, if an active set is updated at a point that is not the trust region centre, then the Krylov method may terminate too early due to a degeneracy. An extension to the conjugate gradient method for searching round the trust region boundary receives attention too, but it was also rejected from LINCOA, because of poor numerical results. The given techniques of LINCOA seem to be adequate in practice.

Từ khóa


Tài liệu tham khảo

Broyden, C.G., Dennis, J.E., Moré, J.J.: On the local and superlinear convergence of quasi-Newton methods. J. Inst. Math. Appl. 12, 223–245 (1973)

Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods. MPS/SIAM Series on Optimization, SIAM (Philadelphia) (2000)

Fletcher, R.: Practical Methods of Optimization. Wiley, Chichester (1987)

Gill, P.E., Murray, W.: Numerical Methods for Constrained Optimization. Academic Press, London (1974)

Goldfarb, D., Idnani, A.: A numerically stable dual method for solving strictly quadratic programs. Math. Program. 27, 1–33 (1983)

Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, 553–572 (1983)

Powell, M.J.D.: A tolerant algorithm for linearly constrained optimization calculations. Math. Program. B 45, 547–566 (1989)

Powell, M.J.D.: On trust region methods for unconstrained minimization without derivatives. Math. Program. B 97, 605–623 (2003)

Powell, M.J.D.: Least Frobenius norm updating of quadratic models that satisfy interpolation conditions. Math. Program. B 100, 183–215 (2004)

Powell, M.J.D.: The NEWUOA software for unconstrained optimization without derivatives. In: Di Pillo, G., Roma, M. (eds.) Large-Scale Optimization, pp. 255–297. Springer, New York (2006)

Powell, M.J.D.: Beyond symmetric Broyden for updating quadratic models in minimization without derivatives. Math. Program. B 138, 475–500 (2013)

Powell, M.J.D.: LINCOA. http://en.wikipedia.org/wiki/LINCOA (2013). Accessed 22 May 2015

Thông tin
Thông tin xuất bản

Mathematical Programming Computation

Tập 7 Số 3

237-267

Thông tin tác giả