Topics in constrained optimisation
Symposium organised by Casper Albers, Department of Mathematics and Statistics, The Open University, UK
Chair: Casper Albers, Tuesday 21st July, 15.25 - 16.45, Palmeston Lecture Theatre, Fisher Building.
Mike Powell, Department of Applied Mathematics & Theoretical Physics,
Frank Critchley, Department of Mathematics and Statistics, the Open University, UK. Explicit minimisation of a convex quadratic under a general quadratic constraint.
Casper Albers, Department of Mathematics and Statistics, The Open University, UK. Missing values in general forms of Procrustes Analysis.
John C. Gower, Department of Mathematics & Statistics, The Open University, UK. Canonical Variate Analysis: Ranks, Ratios and Fits.
ABSTRACTS
Mike Powell
Many algorithms for minimizing a general function F are iterative, a quadratic approximation Q to F being employed on each iteration. It is assumed the approximation is useful within a spherical region R of the space of the variables, the centre v of R being such that F(v) is the least calculated value of F so far. In the unconstrained trust region subproblem, one seeks the point w of R at which Q is least, in the hope that most of the reduction Q(v) - Q(w) is going to be inherited by F(v) - F(w). The two main techniques for this task are the solution of the first order Karush-Kuhn-Tucker conditions of the subproblem and the application of the conjugate gradient method to Q, beginning at v and ending usually on the boundary of R. They are considered briefly, noting that the conjugate gradient approach is more suitable when less accuracy and less computation are required. Attention is given also to the generalization that allows the shape of R to be elliptical. Topic area: COM (Computational Methods). Keywords: trust region subproblem; quadratic optimisation.
Explicit minimisation of a convex quadratic under a general quadratic constraint
Frank Critchley
An analytical solution is provided to the problem of minimising a convex quadratic under a general quadratic (inequality) constraint, additional affine constraints being easily accommodated. This problem may arise by itself or as a component of a larger problem as, for example, when iteratively minimising a smooth convex objective function under a smooth constraint. As will be clear, instances of this problem occur widely in psychometrics, statistics, optimisation and elsewhere. A complete, explicit resolution of the problem is described. Completeness comes via identification of a set of mutually exclusive and exhaustive special cases in each of which the (possibly non-singleton) solution set is obtained explicitly, depending at most on a specified, readily computed, real root of a known polynomial. The treatment given affords analytical insight into the diverse nature both of the special cases identified and of their solution sets, shedding light on algorithm performance and design, intrinsically unstable problems being a particular focus. The underlying geometry illuminates the development. Simplifying nonsingular affine transformations (coordinate changes) are exploited, there being points of contact with simultaneous diagonalisation and extreme eigenvalue results.Topic area: STA (Statistical Methods),
Casper Albers
For given configuration matrices Xk, the aim of the General Procrustes Problem is to find transformations Tk such that the Euclidean distance between the transformed configurations XkTk, is minimised. The Tk are restricted to some class of matrix. When missing values occur in Xk, these need to be estimated before standard Procrustes algorithms can be applied. Previous work in this field worked on special cases, e.g. when the Tk are required to be orthogonal or when complete rows in Xk are missing. In this talk, a more general approach is taken. An iterative algorithm alternating between an algorithm from constrained quadratic optimisation (Albers, Critchley, Gower, 2009) and a general Procrustes algorithm is developed. This algorithm is shown to be applicable to a very broad class of missing values Procrustes problems. This class includes those problems were isotropic scaling, centring and /or standardisation is required. Topic area: MIS (Missing data), APP (Applications), Keywords: Procrustes analysis, constrained optimisation
Canonical Variate Analysis: Ranks, Ratios and Fits
John Gower
Canonical Analyses of several kinds have long been used in data analysis. Maximising a ratio of Between (B) to Within (W) group variation leads immediately to the two-sided eigenvalue problem with a unidimensional solution. Multidimensional solutions may be justified by defining a metric (e.g. Mahalanobis or χ2 distance) and appealing to the Eckart-Young theorem (weighted?) for an r-dimensional approximation. The classical case, where the number of variables (p) is less than the number of samples/units/cases (n), is straightforward. Increasingly, applications require p>>n and the classical approach fails. The General Canonical Form (Albers, Critchley & Gower, 2009) throws light on the fundamental general structure, expressed in terms of the null space of W and its intersection with the range space of the total variation. In the classical case W has full rank p and its range space contains the range space of B. When p>>n the range spaces may be orthogonal or they may intersect. When the range spaces are orthogonal, ratio criteria are undefined but, given a suitable metric, Eckart-Young fits remain valid. The analysis justifies some pragmatic approaches but also raises new possibilities that remain to be fully assessed.Topic area: STA (Statistical Methods), APP (Applications), Keywords: canonical variate analysis, quadratic optimisation, p>n-problems. (47)