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