<jupyter_start><jupyter_text>Gradient descent Let $\boldsymbol{x} = \left[\begin{array}{c}x_1 \\x_2\\\end{array}\right]$ be a two-dimensional vector. Consider the following algorithm: **Algorithm:** `gradient_descent()`**Goal:** Minimize the function $f(\boldsymbol{x})$.1. Choose a tolerance $\epsilon>0$, a scale factor $ \Theta > 0$, and a small number $\Delta > 0$2. Guess on $\boldsymbol{x}_0$ and set $n=1$3. Compute a numerical approximation of the jacobian for $f$ by    $$    \nabla f(\boldsymbol{x}_{n-1}) \approx \frac{1}{\Delta}\left[\begin{array}{c}    f\left(\boldsymbol{x}_{n-1}+\left[\begin{array}{c}    \Delta\\    0    \end{array}\right]\right)-f(\boldsymbol{x}_{n-1})\\    f\left(\boldsymbol{x}_{n-1}+\left[\begin{array}{c}    0\\    \Delta    \end{array}\right]\right)-f(\boldsymbol{x}_{n-1})    \end{array}\right]    $$4. Stop if the maximum element in $|\nabla f(\boldsymbol{x}_{n-1})|$ is less than $\epsilon$5. Set $\theta = \Theta$ 6. Compute $f^{\theta}_{n} = f(\boldsymbol{x}_{n-1} - \theta \nabla f(\boldsymbol{x}_{n-1}))$7. If $f^{\theta}_{n} < f(\boldsymbol{x}_{n-1})$ continue to step 98. Set $\theta = \frac{\theta}{2}$ and return to step 6     9. Set $x_{n} = x_{n-1} - \theta \nabla f(\boldsymbol{x}_{n-1})$10. Set $n = n + 1$ and return to step 3 **Question:** Implement the algorithm above such that the code below can run. Define the rosenbrock function<jupyter_code>def _rosen(x1,x2):
    f = (1.0-x1)**2 + 2*(x2-x1**2)**2

x1 = sm.symbols('x_1')
x2 = sm.symbols('x_2')
f = (1.0-x1)**2 + 2*(x2-x1**2)**2


def gradient_descent(f,x0,epsilon=1e-6,Theta=0.1,Delta=1e-8,max_iter=10_000):

    # step 1: initialize
    x = x0
    fx = f(x0)
    n = 1
    
    # step 2-6: iteration
    while n < max_iter:

        x1_variable=[x[0]+Delta,x[1]]
        x2_variable=[x[0],x[1]+Delta]
        # step 2: function and derivatives
        def rosen_jac(x):
            jac = np.zeros(2)
            jac[0] = f(x1_variable)-f(x)
            jac[1] = f(x2_variable)-f(x)
            return jac*(1/Delta)
        # step 3: check convergence
        if np.max(np.array(abs(rosen_jac(x)))) < epsilon:
            break

        x_prev = x
        fx_prev = fx
        
        # step 2: evaluate gradient
        jacx = rosen_jac(x)
       
        # step 3: find good step size (line search)

        fx_ast = np.inf
        theta_ast = Theta
        theta = Theta / 2
        if fx < fx_ast:
            fx_ast = fx
            theta_ast = theta
        
        # step 4: update guess
        x = x_prev - theta_ast * jacx
                            
        # step 5: check convergence
        fx = f(x)
        if fx > fx_prev:
            break
            
        # d. update i
        n += 1
        
    return x,n<jupyter_output><empty_output><jupyter_text>**Test case:**<jupyter_code>def rosen(x):
    return (1.0-x[0])**2+2*(x[1]-x[0]**2)**2

x0 = np.array([1.1,1.1])
try:
    x,it = gradient_descent(rosen,x0)
    print(f'minimum found at ({x[0]:.4f},{x[1]:.4f}) after {it} iterations')
    assert np.allclose(x,[1,1])
except:
    print('not implemented yet')
gradient_descent(rosen,x0)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1778693722257451, 'fraction_numerical': 0.03836398224476855, 'mean_word_length': 2.5016648168701443, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, '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': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '31659', 'license': 'MIT', 'n_tokens_mistral': 1225, 'n_tokens_neox': 1164, 'n_words': 267, 'path': 'Exam project/Anton/Exam 3 final.ipynb', 'repo_name': 'notnasobe666/BlackHatGang', 'size': '3154'}