<jupyter_start><jupyter_text>Home work 4In this homework we're going to implement log barrier and interior point methods for solving a general QP optimization problem.I've implemented the log barrier and interior point methods in the `algorithms.py` file and imported them along with some required libraries here.<jupyter_code>import numpy as np
from pylab import rcParams
from matplotlib import pyplot as plt
from algorithms import log_barrier_for_qp, interior_point_for_qp

%matplotlib inline
rcParams['figure.figsize'] = 10, 5<jupyter_output><empty_output><jupyter_text>Generating a random QP problem wich is convexHere we generate a random convex problem with a 100-dimensioned input vector and 200 constraints.We assure convexity by constrainting `P` to be a positive semi definite matrix.<jupyter_code>n = 100
m = 200
p_helper = np.random.rand(n, n)
P = np.dot(p_helper, p_helper.T)
q = np.random.rand(n, 1)
A = np.random.rand(m, n)
b = np.random.rand(m, 1)<jupyter_output><empty_output><jupyter_text>Log Barrier MethodWe use the `log_barrier_for_qp` method to solve the generated QP problem and plot the duality gaps on each iteration.<jupyter_code>gaps = log_barrier_for_qp(P, q, A, b, alpha=0.01, beta=0.5, mu=20, iterations=200)

rcParams['figure.figsize'] = 10, 5
plt.plot(list(range(1, len(gaps) + 1)), gaps)
plt.yscale('log')
plt.xlabel('Iterations')
plt.ylabel('Duality gap')
plt.title('Log barrier method applied on the random convex QP')<jupyter_output>Iteration: 62 - final gap: 0.000063<jupyter_text>Interior Point MethodThen we apply the `interior_point_for_qp` method on the generated QP problem to solve it using interior point method.We then plot the surrogate duality gap and dual residual on each step to check the method's performance.<jupyter_code>surrogates, dual_residuals = interior_point_for_qp(P, q, A, b, alpha=0.01, beta=0.5, mu=10, iterations=200, tol=1e-4, eps=1e-6)
iterations = list(range(1, len(surrogates) + 1))

rcParams['figure.figsize'] = 15, 5

plt.subplot(1, 2, 1)
plt.plot(iterations, surrogates)
plt.yscale('log')
plt.xlabel('Iterations')
plt.ylabel('Surrogate duality gap')
plt.title('Interior point method applied on the random convex QP')

plt.subplot(1, 2, 2)
plt.plot(iterations, dual_residuals)
plt.yscale('log')
plt.xlabel('Iterations')
plt.ylabel('Dual residual')
plt.title('Interior point method applied on the random convex QP')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10314830157415078, 'fraction_numerical': 0.02775476387738194, 'mean_word_length': 6.362804878048781, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 16, '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': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '228166', 'license': 'MIT', 'n_tokens_mistral': 885, 'n_tokens_neox': 804, 'n_words': 260, 'path': 'example_usage.ipynb', 'repo_name': 'mohamad-amin/ConstrainedOptimization-QP', 'size': '2414'}