Type your name here
This assignment is a warmup to practice your Python skills. Your task is to write a Python program that optimizes a cost function that we're going to describe next.
Consider a system that contains $n$ units labeled $\{0,\ldots,n-1\}$ that are all connected. Each unit has a state associated with it, where unit $i$ has a state $x_i$, and the overall state is referred to as $\mathbf{x}$, i.e. $\mathbf{x} = \{x_0, x_1, \ldots, x_{n-1}\}$. Assume that $x_i$ takes on the values -1 or +1. All the units are interconnected and the weight of the connection between units $i$ and $j$ is given by $w_{ij}$. We assume that the connectivity matrix is symmetric, i.e. $w_{ij} = w_{ji}$. The state of the system is associated with a cost function, also referred to as energy, given by:
$$ E(\mathbf{x}) = - \frac{1}{2} \sum_{i,j=0}^{n-1} w_{ij} x_i x_j $$This energy function is the basis of the Hopfield neural network, which is a model of associative memory, and the Ising spin-glass model which has been extensively studied in statistical physics.
We are interested in finding the global minimum of $E(\mathbf{x})$, i.e. to find $\mathbf{x}^*$ such that $E(\mathbf{x}^*) \leq E(\mathbf{x})$ for all choices of $\mathbf{x}$, and return the value of $E(\mathbf{x}^*)$. The problem of finding this global minimum is NP-complete, i.e. there is no known efficient algorithm for computing it. Therefore, you will need to consider all possible assignments to the variables $x_i$ when searching for the global minimum of $E(\mathbf{x})$.
For example, with the matrix $$ W = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} $$ The optimal solution is $\mathbf{x}^* = (1, 1)$, with $E (1,1) = -\frac{1}{2} (1 + 1) = -1$; note that $(-1,-1)$ gives the same result. Your task is to complete the following function:
def ising_optimize(matrix) :
"""
Return the minimum value of E(x) with the matrix given as the input
parameter.
The matrix is provided either as a Python list-of-lists or as a
string which is the path to a CSV file.
"""
return 0
# the matrix shown above can be provided as input in one of two ways:
w = [[0,1], [1, 0]]
# as a list of lists:
ising_optimize(w)
# or can be read from a comma-delimited file:
f = open("matrix.csv", 'w')
_ = f.write("0,1\n1,0\n")
f.close()
!cat matrix.csv
#%more matrix.csv
ising_optimize("matrix.csv")
0
0
# recall that a list of lists can be accessed as W[i][j] for element i,j:
w[1][0]
1
Note that to determine the type of input provided to the function you can use the Python type
built-in function:
type([]) == list
type('cs440') == str
True
True
Our test cases will look something like:
if ising_optimize(w) == -1 :
print("test was successful")
else :
print("test failed")
test failed
In your code do not use the Python csv
module or code from the Numpy/pandas libraries.
Submit your code as a jupyter notebook named p1.ipynb
via Canvas.
Your notebook will be run and graded automatically. So make sure your code satisfies the specified API, i.e. correct naming and behavior of your methods and classes.