Problem 1

Part 1
Here is the MATLAB code for solving the spin glass problem:

```% set the number of spins in the glass
N = 100;

% random energies from a gaussian distribution with mean 0 and variance 1
J = randn(1, N);

% print out the minimum possible energy
-sum(abs(J))

% construct a symmetric energy matrix A
D = diag(J);
D1 = [D(:,end) D(:,1:end-1)];
D2 = [D(end,:); D(1:end-1,:)];
A = 0.5 * (D1 + D2);

% allocate a symmetrix matrix for the spins
Z = sdpvar(N);

% constrain the spin matrix to be psd and have 1's on the diagonal
F = set(Z > 0) + set(diag(Z) == 1);

% solve the semidefinite program
solvesdp(F, trace(A*Z));

% print out the energy obtained
trace(A * double(Z))
```
On the first run, this technique found a configuration with the minimal energy, as indicated by the following ouput:
```ans =

-78.2133

ans =

-78.2133
```
Simulated annealing, though solved much faster, does not reach as good a solution. Here are the energies it finds for three cooling rates:
 Rate Energy 0.1 -64.1778 0.01 -66.7326 0.001 -73.2866

Part 2
For this part, I did the same as above, except I wrote this ugly nested for loop to obtain the energy matrix A:

```A = zeros(N);

for i = [1:N]
col1 = mod(i - 1, S) + 1;
row1 = (i - col1) / S + 1;

down  = mod(row1, S) + 1;
right = mod(col1, S) + 1;

up    = mod(row1 + S - 2, S) + 1;
left  = mod(col1 + S - 2, S) + 1;

for j = [i + 1:N]
col2 = mod(j - 1, S) + 1;
row2 = (j - col2) / S + 1;

if ((row1 == row2 && (col2 == right || col2 == left)) || (col1 == col2 && (row2 == down || row2 == up)))
r = 0.5 * randn(1,1);
A(i, j) = r;
A(j, i) = r;
end
end
end
```
I kept running out of memory on 10x10 matrices, so I did 9x9 instead. On one trial, the minimum possible energy was -128.6243 and the SDP relaxation found a minimal energy of -107.5701. For the same energy matrix, simulated annealing did almost as well at the lowest cooling rate:
 Rate Energy 0.1 -81.1302 0.01 -88.8959 0.001 -94.6923

edit