Constrained Quadratic Optimisation: 1.
The canonical problem
[this page | pdf | references | back links]
Return to
Abstract and Contents
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 .
NAVIGATION LINKS
Contents | Prev | Next