Constrained Quadratic Optimisation: 3. Setting up the ‘super’-problem

[this page | pdf | references | back links]

Return to Abstract and Contents

Next page


3.            Setting up the ‘super’-problem


To set up the superset of the original problem as described in Solving the canonical problem, we multiply through each row in the above tableau (both left and right hand sides) by  if the relevant element of  or  is negative. This means that the right-hand side of the tableau is all now non-negative. Simultaneously we introduce a further series of ‘artificial’ variables , all elements of which are , the first  elements of which, , are artificial variables corresponding to the  and the remaining  elements are artificial variables corresponding to the . To be more precise, if we want the speediest algorithm, we only introduce only such elements of these variables that are needed to achieve a starting feasible solution.


The starting solution is then given by  and:



The starting ‘basic’ variables, i.e. those whose opening values are greater than zero are each of the  and whichever of the  and the  is non-zero in the above formulae.


The complete starting tableau is then:



Subject to  for ,  and  where  means multiply through relevant row of the matrix by  if ,  means multiply through relevant row of the matrix by  if  and  is the  identity matrix with each 1 replaced by a zero if the corresponding value of  is greater than zero.


N.B. We have ignored for the purposes of this discussion the possibility that any of the entries on the right-hand side of the tableau are identically zero. This degenerate case can be handled by adding a very small number to make them positive.


We need to know which variables ‘correspond’ to each other (i.e. appear jointly in the constraints , although these correspondences do not change as the iteration progresses.


In addition to the Tableau, which is an  array we also need to keep track of the following as the iteration proceeds:


Two rows:


(a)    BasicRow, indicates with, say, a 1 whether the variable in question is ‘basic’


(b)   ObjectiveRow, initially calculated as:



Two columns:


(c)    SolutionColumn, contains the current feasible solution, i.e. the right hand side of the above tableau ‘equation’; and


(d)   BasicColumn, contains integers indicating to which variables the entries in the SolutionColumn currently apply (and thus which variables are basic, so there is some overlap here with BasicRow). BasicColumn starts as:



Contents | Prev | Next

Desktop view | Switch to Mobile