/

### Constrained Quadratic Optimisation: 1. The canonical problem

Next page

1.            The canonical problem

Constrained quadratic optimisation involves finding the value of a vector that minimises a given penalty function (or maximises it, the two are interchangeable by replacing with ) subject to some (normally linear) constraints, where: The constraints, in canonical form, are normally of two types. There are lower limit constraints of the form (by which we mean that each for ) and there are further constraints of the form (by which we mean that each for ).

In these definitions is a scalar, is a vector (or matrix) and is an symmetric matrix, which is assumed to be non-positive definite if the problem is a minimisation, and non-negative definite if the problem is a maximisation. A non-negative definite (symmetric) matrix is one whose eigenvalues are all at least zero.

The value of is irrelevant to the optimal value of so without loss of generality can be taken as zero.

Problems with lower limits on each that are non-zero, say can be restated into the above form by a change of variables to resulting in a new penalty function:  Here where , and . We therefore merely need to alter appropriately, and unwind the change of variables at the end of the optimisation process.

Problems that involve ‘greater than’ or ‘equals’ type constraints, e.g. or as well as (or instead of) ‘less than’ type constraints can be converted into the above canonical form by:

(a)    converting each ‘equality’ constraint into two equivalent constraints, one being the corresponding ‘greater than’ constraint and one being the corresponding ‘less than’ constraint, altering accordingly (since if then and , and then

(b)   inverting each ‘greater than’ constraint present into a ‘less than’ constraint by noting that if then .