<jupyter_start><jupyter_text>$$\max \frac14 x^{\top}Lx \quad \text{s.t. }x_i^2 = 1$$$$\max \frac14 trace(Lxx^{\top}) \quad \text{s.t. }x_i^2 = 1$$$$ X = xx^{\top}$$$$ \max_{X \succeq 0} \frac14 trace(LX) \quad \text{s.t. } \mathrm{diag}(X) = 1 $$  Create SDP relaxation<jupyter_code>X = cvx.Variable((n, n), PSD=True)
obj = 0.25 * cvx.trace(L.toarray() * X)
constr = [cvx.diag(X) == 1]
problem = cvx.Problem(cvx.Maximize(obj), constraints=constr)
problem.solve(verbose=True, solver=cvx.SCS, eps=1e-7, max_iters=5000)
X.value
u, s, v = np.linalg.svd(X.value)
np.linalg.norm(X.value - u @ np.diagflat(s) @ v)
s
plt.semilogy(s / s[0])
np.linalg.matrix_rank(X.value, tol=1e-8)
U = (v.T * np.sqrt(s)).T
print(np.linalg.norm(X.value - U.T @ U))
num_trials = 100000
average_gw_cut = np.zeros(num_trials)
for i in range(num_trials):
    r = np.random.randn(n)
    average_gw_cut[i] = cut(np.sign(U.T @ (r / np.linalg.norm(r))), L)
gw_cut = np.sign(U.T @ (r / np.linalg.norm(r)))
nx.draw(G, node_color=gw_cut)
print(np.mean(average_gw_cut), np.std(average_gw_cut), np.max(average_gw_cut))
_ = plt.hist(average_gw_cut, bins=30)
# Check theory
print(problem.value)
print(0.8785 * problem.value)
print(np.mean(average_gw_cut))
print(np.max(average_gw_cut))
print(1.1382 * np.max(average_gw_cut))
average_random_cut = np.zeros(num_trials)
for i in range(num_trials):
    cut_trial = 2 * np.random.randint(0, 2, n) - 1
    average_random_cut[i] = cut(cut_trial, L)
print(np.mean(average_random_cut), np.std(average_random_cut), np.max(average_random_cut))
_ = plt.hist(average_random_cut, bins=20, label="Random", alpha=0.5)
_ = plt.hist(average_gw_cut, bins=20, label="GW", alpha=1)
plt.legend(fontsize=18)
plt.tight_layout(rect=(0.1, 0.1, 1, 1))
plt.xticks(fontsize=24)
plt.yticks(fontsize=24)
plt.grid(True)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1976998904709748, 'fraction_numerical': 0.03614457831325301, 'mean_word_length': 5.235494880546075, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '290434', 'license': 'MIT', 'n_tokens_mistral': 918, 'n_tokens_neox': 843, 'n_words': 133, 'path': '13-SDP/demo.ipynb', 'repo_name': 'amkatrutsa/optimization-fivt', 'size': '1826'}