Lindo Systems

! The educational testing problem, illustrating @POSD.
! We are given a covariance matrix, thus it is positive definite.
We want to 
 maximize the sum of decrements to the diagonal of the matrix
 such that the adjusted matrix is still positive semi-definite.
Application:
  A comprehensive test consists of N subtests on different topics.
The overall score of a student who takes the test is the sum of the scores
on the N subtests. 
If a large number of students take a test,
one measure of the goodness of the test is
how large the covariances among different subtests are relative
to the variances (the diagonal) in scores on a test. 
The scores on the subtests of a well prepared test taker 
taking a well prepared test should be positively correlated. 
On the otherhand, if none of the test takers can understand 
the questions, then the variances in scores will be large,
but the covariances between subtest scores will be close to zero. 
  Thus, a measure of interest is how large the variances are
relative to the covariances. One measure of this is to ask
how much we can decrease the diagonal terms (the variances on each test)
so the matrix remains positive semi-definite.  For a good test,
the diagonal (variances) should be small relative to the off-diagonal (covariances);
! Make sure to turn on 
   Solver --> Options --> Nonlinear Solver --> Quadratic Recognition;
! Ref.
  Fletcher, R.(1981), "A nonlinear programming problem in 
statistics(Educational testing)", SIAM J. of Scientific and
Statistical Computing, vol. 2, no. 3, pp. 257-267.;

! Keywords: Positive definite, Test evaluation, Statistics, Covariance, POSD, SDP;
SETS:
  TOPIC: DECR;
  TXT( TOPIC, TOPIC) | &1 #GE# &2: COV, DCOV;
ENDSETS
DATA:
 TOPIC = 1..8;
! The covariances between scores on subtest topics
Data set 4 (subtests 1-8) of Fletcher;
 COV =
    415.0494
    145.0295   358.5970
    137.5789   253.4598   329.5784
    203.4454   176.1280   132.2877   317.3929
     54.44370   20.89211   16.58185   25.02679  145.1069
     27.21131    4.179563   20.10516  13.21825   -0.7390873  51.71032
    273.4955    84.07490   103.2530  120.0655    28.45883    16.54960  329.8482
    241.9898    97.65253   121.0947  108.8581    27.29688    21.10020  204.0749  275.5652
 ;         
ENDDATA

! Maximize the sum of the decreases to the variances;
 MAX = @SUM( TOPIC(k): DECR(k));

! The covariance matrix with decremented diagonal;
 @FOR( TOPIC(k): DCOV(k,k) = COV(k,k) - DECR(k));
! The off-diagonal terms remain unchanged;
 @FOR( TXT(j,k) | k #NE# j: 
    DCOV(j,k) = COV(j,k);
    @FREE( DCOV(j,k));
     );

! It must be a valid covariance matrix;
 @POSD( DCOV);

DATA:
! For a nice display, click on: 
    LINGO -> Options -> Interface -> Page size -> 100;
 @TEXT() = 'The sub-test Covariance matrix:';
 @TEXT() = @TABLE(COV);
 @TEXT() = ' ';
 @TEXT() = 'A Positive Semi-Definite matrix with smaller diagonal:';
 @TEXT() = @TABLE(DCOV);
 @TEXT() = ' ';

 @TEXT() = 'The decreases to the diagonal:';
 @TEXT() = @TABLE(DECR);
 @TEXT() = ' ';

ENDDATA