Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

def armijo(f, xatual, d, gamma, eta): t = 1 gradatual = [sp.diff(f, var).subs({x[i]:…

  1. User

    def armijo(f, x_atual, d, gamma, eta): t = 1 grad_atual = [sp.diff(f, var).subs({x[i]: x_atual[i] for i in range(len(x_atual))}) for i, var in enumerate(x)]

    # Avaliando f1 e f2 inicialmente
    f1 = f.subs({x[i]: x_atual[i] + t * d[i] for i in range(len(x_atual))}).evalf()
    f2 = f.subs({x[i]: x_atual[i] for i in range(len(x_atual))}).evalf() + eta * t * sum(grad_atual[i] * d[i] for i in range(len(x_atual))).evalf()
    
    while f1 > f2:
        t = gamma * t
        f1 = f.subs({x[i]: x_atual[i] + t * d[i] for i in range(len(x_atual))}).evalf()
        f2 = f.subs({x[i]: x_atual[i] for i in range(len(x_atual))}).evalf() + eta * t * sum(grad_atual[i] * d[i] for i in range(len(x_atual))).evalf()
    #print(t)
    return t
    

    eta = 0.25 gamma = 0.8 def metodo_gradiente(f, variables, pto_0): x_atual = pto_0 k = 0 grad_f = [sp.diff(f, var) for var in variables] grad_atual = [g.subs({variables[i]: x_atual[i] for i in range(len(x_atual))}) for g in grad_f]

    while all(abs(g.evalf()) > 1e-6 for g in grad_atual):
        d_atual = [-g for g in grad_atual]
        print(f, x_atual, d_atual)
        t = armijo(f, x_atual, d_atual, eta, gamma)
        x_atual = [x_atual[i] + t * d_atual[i] for i in range(len(x_atual))]
        k += 1
    
        grad_atual = [g.subs({variables[i]: x_atual[i] for i in range(len(x_atual))}) for g in grad_f]
    
    return x_atual, k
    

    xf2 = sp.symbols('x0:100') # Cria x0, x1, ..., x99 f2_sym = sum(xf2[i]**4 - 16xf2[i]**2 + 5xf2[i] for i in range(100)) # Somatório de i=0 a 99 (100 elementos) resultado, iteracoes = metodo_gradiente(f2_sym, xf2, [0 for i in range(100)]) print(f"Resultado: {resultado}, Iterações: {iteracoes}")

  2. Assistant

    Certainly! It looks like you're attempting to implement the gradient descent method with Armijo line search for optimizing a function of 100 variables using SymPy.

    However, there are several issues in your code that might prevent it from working as expected. Let me help you identify and fix these issues step by step.

    1. Missing Imports

    Firstly, you are using SymPy functions (sp.diff, sp.symbols, etc.) but haven't imported SymPy in your code. You need to import SymPy at the beginning:

    import sympy as sp
    

    2. Evaluating Gradient Components

    In your armijo function, when computing grad_atual, you have:

    grad_atual = [sp.diff(f, var).subs({x[i]: x_atual[i] for i in range(len(x_atual))}) for i, var in enumerate(x)]
    

    But x is not defined in this scope. You need to make sure that x (the list of symbolic variables) is passed to the armijo function or accessible within it.

    Similarly, in metodo_gradiente, you're using variables[i], but in the gradient evaluation, you have:

    grad_atual = [g.subs({variables[i]: x_atual[i] for i in range(len(x_atual))}) for g in grad_f]
    

    This will cause an index mismatch because you're iterating over g (the gradient components) and then indexing variables[i], but i comes from the loop over g.

    3. Symbolic vs Numeric Computation

    SymPy is designed for symbolic computation, and while it can handle numerical evaluations, it's not optimized for numerical optimization algorithms like gradient descent, especially with large-scale problems (like 100 variables).

    Using evalf() within loops can be very slow. For better performance, it's advisable to use numerical libraries like NumPy for numerical computations.

    4. Modifying the Code for Numerical Computation

    To efficiently perform gradient descent on large-scale numerical problems, you should use NumPy for array operations and SciPy for optimization. Here's how you can modify your code:

    Use NumPy Arrays

    Replace lists with NumPy arrays for efficient computation:

    import numpy as np
    

    Define the Function and Gradient Numerically

    Instead of using SymPy to define f2_sym symbolically, define it as a Python function that operates on NumPy arrays:

    def f2(x):
        return np.sum(x**4 - 16*x**2 + 5*x)
    

    Compute the gradient numerically:

    def grad_f2(x):
        return 4*x**3 - 32*x + 5
    

    Armijo Line Search Implementation

    Rewrite the Armijo function to work with NumPy arrays:

    def armijo(f, x_current, d, gamma, eta):
        t = 1.0
        while True:
            x_new = x_current + t * d
            if f(x_new) <= f(x_current) + eta * t * np.dot(grad_f2(x_current), d):
                break
            t *= gamma
        return t
    

    Gradient Descent Method

    Update the gradient descent method:

    def gradient_descent(f, grad_f, x0, eta=0.25, gamma=0.8, tol=1e-6, max_iter=1000):
        x_current = x0
        for k in range(max_iter):
            grad_current = grad_f(x_current)
            if np.linalg.norm(grad_current, ord=np.inf) < tol:
                break
            d = -grad_current
            t = armijo(f, x_current, d, gamma, eta)
            x_current = x_current + t * d
        return x_current, k
    

    Running the Optimization

    Now, you can run the optimization:

    x0 = np.zeros(100)
    resultado, iteracoes = gradient_descent(f2, grad_f2, x0)
    print(f"Resultado: {resultado}, Iterações: {iteracoes}")
    

    Summary

    By switching to NumPy for numerical computations, your code will run much faster and be more suitable for this kind of numerical optimization.

    Complete Revised Code

    Here's the complete code with these modifications:

    import numpy as np
    
    def f2(x):
        return np.sum(x**4 - 16*x**2 + 5*x)
    
    def grad_f2(x):
        return 4*x**3 - 32*x + 5
    
    def armijo(f, x_current, d, gamma, eta):
        t = 1.0
        while True:
            x_new = x_current + t * d
            if f(x_new) <= f(x_current) + eta * t * np.dot(grad_f2(x_current), d):
                break
            t *= gamma
        return t
    
    def gradient_descent(f, grad_f, x0, eta=0.25, gamma=0.8, tol=1e-6, max_iter=1000):
        x_current = x0
        for k in range(max_iter):
            grad_current = grad_f(x_current)
            if np.linalg.norm(grad_current, ord=np.inf) < tol:
                break
            d = -grad_current
            t = armijo(f, x_current, d, gamma, eta)
            x_current = x_current + t * d
        return x_current, k
    
    x0 = np.zeros(100)
    resultado, iteracoes = gradient_descent(f2, grad_f2, x0)
    print(f"Resultado: {resultado}, Iterações: {iteracoes}")
    

    Potential Issues with the Original SymPy Code

    • Performance: SymPy is not designed for high-performance numerical computations.
    • Indexing and Variable Scope: The variables like x, variables, and their scopes may cause issues.
    • Convergence: Depending on the function's characteristics, the gradient may not converge to zero, or the method might require many iterations.

    Tips for Numerical Optimization

    • Use Appropriate Libraries: For numerical optimization, prefer libraries like NumPy and SciPy.
    • Monitor Convergence: Implement checks for convergence to avoid infinite loops.
    • Function and Gradient Evaluation: Ensure that your function and its gradient are correctly implemented and efficiently evaluated.

    Conclusion

    By modifying your code to use numerical computations with NumPy, you should be able to efficiently perform gradient descent on your function with 100 variables. If you have any further questions or need help with specific parts of the code, feel free to ask!