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