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 .


Contents | Prev | Next

Desktop view | Switch to Mobile