My DFP algorithm doesn't converge at all and generates a lot of curvature errors. I'll…
- User
My DFP algorithm doesn't converge at all and generates a lot of curvature errors. I'll send you my implementation. Then, I send you the implementation that I want to follow: # Define DFP Optimization def DFP(f, func_grad, x0, tol=1e-6, max_iter=10000, time_limit=100, stop="time", H0=None): """ Performs the DFP (Davidon-Fletcher-Powell) optimization algorithm with Armijo line search.
Parameters: - f: objective function. - func_grad: gradient function. - x0: initial point as a NumPy array. - tol: tolerance for the gradient norm. - max_iter: maximum number of iterations. - time_limit: time limit for optimization (in seconds). - stop: stopping criterion ("time" or "max_iter"). - H0: initial Hessian approximation matrix. Defaults to identity matrix. Returns: - x_k: optimized variable. - k: number of iterations performed. - total_armijo: total Armijo iterations. - f_current: final function value. - f_list: list of function values per iteration. - error_ratios: list of error ratios per iteration. - total_time: total time taken for optimization. """ k = 0 x_k = copy.deepcopy(x0) f_current = f(x_k) f_list = [f_current] # Initialize with the initial function value f_prev = f_current error_ratios = [] n = len(x0) H_k = np.eye(n) if H0 is None else H0 start_time = time.time() total_armijo = 0 grad_k = func_grad(x_k) while True: # Check stopping conditions elapsed_time = time.time() - start_time if stop == "time" and elapsed_time >= time_limit: break if stop == "max_iter" and k >= max_iter: break if np.linalg.norm(grad_k) <= tol: break # Compute search direction d_k = -H_k @ grad_k # Perform Armijo line search step, armijo_iter = armijo_line_search(f, func_grad, x_k, d_k) total_armijo += armijo_iter # Update position x_next = x_k + step * d_k p_k = x_next - x_k grad_next = func_grad(x_next) q_k = grad_next - grad_k # Compute denominator to avoid division by zero p_q = np.dot(p_k, q_k) if p_q == 0: print(f"Violation of curvature condition at iteration {k}.") break # Update Hessian approximation using DFP formula H_k = H_k + np.outer(p_k, p_k) / p_q - (H_k @ np.outer(q_k, p_k) + np.outer(p_k, q_k) @ H_k) / np.dot(q_k, H_k @ p_k) # Update variables for next iteration x_k = x_next grad_k = grad_next k += 1 # Compute new function value f_current = f(x_k) f_list.append(f_current) # Calculate error ratio if k > 1: if abs(f_prev) > 1e-12: error_ratio = abs(f_current - f_prev) / abs(f_prev) else: error_ratio = np.nan error_ratios.append(error_ratio) else: error_ratios.append(np.nan) f_prev = f_current total_time = time.time() - start_time return x_k, k, total_armijo, f_current, f_list, error_ratios, total_time - Assistant
It sounds like you're experiencing convergence issues and curvature condition violations with your DFP (Davidon-Fletcher-Powell) optimization implementation. Let's walk through the provided DFP implementation to identify potential issues and suggest improvements to ensure proper convergence.
1. Understanding the DFP Update Formula
The core of the DFP algorithm lies in updating the approximation of the inverse Hessian matrix ( H_k ). The standard DFP update formula is:
[ H_{k+1} = H_k + \frac{s_k s_k^T}{s_k^T y_k} - \frac{H_k y_k y_k^T H_k}{y_k^T H_k y_k} ]
where:
- ( s_k = x_{k+1} - x_k )
- ( y_k = \nabla f_{k+1} - \nabla f_k )
2. Analyzing the Provided Implementation
Let's closely inspect the Hessian update step in your implementation:
H_k = H_k + np.outer(p_k, p_k) / p_q - (H_k @ np.outer(q_k, p_k) + np.outer(p_k, q_k) @ H_k) / np.dot(q_k, H_k @ p_k)Here:
- ( p_k ) corresponds to ( s_k )
- ( q_k ) corresponds to ( y_k )
- ( p_q = p_k^T q_k )
Issue Identified:
The denominator in the second term of the update formula is incorrect. In the standard DFP formula, the denominator for the second term is ( y_k^T H_k y_k ), whereas in your implementation, it is ( y_k^T H_k p_k ). This discrepancy can lead to incorrect Hessian updates, causing curvature condition violations and preventing convergence.
3. Correcting the Hessian Update
To align your implementation with the standard DFP formula, modify the denominator of the second term to use ( p_q = s_k^T y_k ). Here's the corrected update step:
# Correct Hessian update H_k = H_k + np.outer(p_k, p_k) / p_q - (H_k @ np.outer(q_k, p_k) + np.outer(p_k, q_k) @ H_k) / p_qExplanation:
- First Term: Remains as ( \frac{s_k s_k^T}{s_k^T y_k} )
- Second Term: Should be ( \frac{H_k y_k s_k^T + s_k y_k^T H_k}{s_k^T y_k} )
By using ( p_q = s_k^T y_k ) in both terms, you ensure that the Hessian update adheres to the standard DFP formulation.
4. Additional Recommendations
-
Ensure Positive Definiteness:
- After each update, verify that ( H_k ) remains positive definite. This is crucial for maintaining a valid search direction.
- You can add a check using, for example, NumPy's
np.linalg.eigvalsto ensure all eigenvalues of ( H_k ) are positive.
-
Handle Division by Zero:
- While you already check for ( p_q == 0 ), consider adding a small epsilon to the denominator to prevent numerical instability:
epsilon = 1e-10 if abs(p_q) < epsilon: print(f"Near-zero curvature condition at iteration {k}.") break
- While you already check for ( p_q == 0 ), consider adding a small epsilon to the denominator to prevent numerical instability:
-
Debugging and Logging:
- Implement detailed logging to monitor the values of ( H_k ), ( s_k ), ( y_k ), and ( p_q ) at each iteration. This can help identify where and why the algorithm fails to converge.
- Example:
print(f"Iteration {k}: p_q = {p_q}, ||grad|| = {np.linalg.norm(grad_k)}")
-
Alternative Update Formulas:
- If issues persist, consider switching to the BFGS update formula, which tends to be more numerically stable and widely used in practice.
5. Revised DFP Implementation
Here's the revised version of your DFP function with the corrected Hessian update:
import numpy as np import copy import time def DFP(f, func_grad, x0, tol=1e-6, max_iter=10000, time_limit=100, stop="time", H0=None): """ Performs the DFP (Davidon-Fletcher-Powell) optimization algorithm with Armijo line search. Parameters: - f: objective function. - func_grad: gradient function. - x0: initial point as a NumPy array. - tol: tolerance for the gradient norm. - max_iter: maximum number of iterations. - time_limit: time limit for optimization (in seconds). - stop: stopping criterion ("time" or "max_iter"). - H0: initial Hessian approximation matrix. Defaults to identity matrix. Returns: - x_k: optimized variable. - k: number of iterations performed. - total_armijo: total Armijo iterations. - f_current: final function value. - f_list: list of function values per iteration. - error_ratios: list of error ratios per iteration. - total_time: total time taken for optimization. """ k = 0 x_k = copy.deepcopy(x0) f_current = f(x_k) f_list = [f_current] # Initialize with the initial function value f_prev = f_current error_ratios = [] n = len(x0) H_k = np.eye(n) if H0 is None else H0 start_time = time.time() total_armijo = 0 grad_k = func_grad(x_k) epsilon = 1e-10 # Small value to prevent division by zero while True: # Check stopping conditions elapsed_time = time.time() - start_time if stop == "time" and elapsed_time >= time_limit: break if stop == "max_iter" and k >= max_iter: break if np.linalg.norm(grad_k) <= tol: break # Compute search direction d_k = -H_k @ grad_k # Perform Armijo line search step, armijo_iter = armijo_line_search(f, func_grad, x_k, d_k) total_armijo += armijo_iter # Update position x_next = x_k + step * d_k p_k = x_next - x_k grad_next = func_grad(x_next) q_k = grad_next - grad_k # Compute denominator to avoid division by zero p_q = np.dot(p_k, q_k) if abs(p_q) < epsilon: print(f"Near-zero curvature condition at iteration {k}.") break # Update Hessian approximation using the corrected DFP formula H_k = H_k + np.outer(p_k, p_k) / p_q \ - (H_k @ np.outer(q_k, p_k) + np.outer(p_k, q_k) @ H_k) / p_q # Optionally, ensure H_k remains symmetric H_k = (H_k + H_k.T) / 2 # Update variables for next iteration x_k = x_next grad_k = grad_next k += 1 # Compute new function value f_current = f(x_k) f_list.append(f_current) # Calculate error ratio if k > 1: if abs(f_prev) > 1e-12: error_ratio = abs(f_current - f_prev) / abs(f_prev) else: error_ratio = np.nan error_ratios.append(error_ratio) else: error_ratios.append(np.nan) f_prev = f_current total_time = time.time() - start_time return x_k, k, total_armijo, f_current, f_list, error_ratios, total_time6. Testing the Revised Implementation
After making these changes, it's essential to test the revised implementation on known benchmark functions to ensure that it now converges correctly. Here's an example using the Rosenbrock function:
def rosenbrock(x): return sum(100.0*(x[1:] - x[:-1]**2.0)**2.0 + (1 - x[:-1])**2.0) def rosenbrock_grad(x): xm = x[1:-1] xm_m1 = x[:-2] xm_p1 = x[2:] grad = np.zeros_like(x) grad[1:-1] = 200*(xm - xm_m1**2) - 400*xm*(xm_p1 - xm**2) - 2*(1 - xm) grad[0] = -400*x[0]*(x[1] - x[0]**2) - 2*(1 - x[0]) grad[-1] = 200*(x[-1] - x[-2]**2) return grad # Initial guess x0 = np.array([-1.2, 1.0]) # Run DFP Optimization result = DFP(rosenbrock, rosenbrock_grad, x0) print("Optimized x:", result[0]) print("Iterations:", result[1]) print("Final function value:", result[3])7. Conclusion
By correcting the denominator in the Hessian update formula, you align your implementation with the standard DFP algorithm, which should help eliminate curvature condition violations and promote convergence. Ensure to perform thorough testing and consider adding additional safeguards and debugging statements as needed.
If problems persist after these corrections, consider exploring alternative quasi-Newton methods like BFGS, which often exhibit better numerical stability and performance in practice.