<a href="https://colab.research.google.com/github/Taylor-X01/Optimization-Algorithms/blob/main_project/Line_search.ipynb" target="_parent"></a>


```python
from sympy import *
from sympy.abc import x,y
# from sympy.plotting import plot as symplot
from scipy.misc import derivative
from scipy.linalg import *
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from mpl_toolkits import mplot3d
dx = 1e-6
```


```python
def plot2D(f,lb,ub,points_x=None,points_y=None,Lambdify=False):

  if Lambdify:
    f_lambda = lambdify(x,f)
  else:
    f_lambda = f
  fig = plt.figure(figsize=(30, 10))
  X = np.linspace(lb, ub, 5500)
  ax = fig.gca()

  plt.plot(X,f_lambda(X))
  if (points_x != None) or (points_y != None):
    plt.plot(points_x,points_y,'xr',ms=10)
  plt.grid(b=True, which='major', color='#666666', linestyle='-')
  plt.minorticks_on()
  plt.grid(b=True, which='minor', color='#999999', linestyle='-', alpha=0.2)

  plt.show()
```

## Bissection Method

$$
Let\ f:\mathbb{R}\rightarrow\mathbb{R}\ and\ a<b \in\mathbb{R} : f'(a) \times f'(b)<0\\
  \  
$$


```python
def bissection(fct,a,b,err=0.005, verbose=False):

  f = fct
  f_prime_a = derivative(fct,a,dx=dx) 
  f_prime_b = derivative(fct,b,dx=dx)

  result = [[a,b],[f(a),f(b)]]
  if np.dot(f_prime_a,f_prime_b)<0:
    print("Hypothesis match : Success")
    while (abs(b-a)>err) and (f_prime_a < 0 and f_prime_b > 0):
      c = (a+b)/2
      result[0].append(c)
      result[1].append(f(c))
      if verbose:
        print("c = ",c)

      f_prime_c = derivative(fct,c,dx=dx)
      if verbose:
        print("f'(c) = ",f_prime_c)

      if f_prime_c <= 0 : a = c
      else: b = c

    if verbose:  
      print("2D: [x,f(x)] == ",[a,f(a)])
    return result

  else: print(f"Hypothesis match : Failed for a = {a} and b = {b}")

```

### Test functions :
$$
f(x)=x^2+5x+2
$$


```python

f1 = lambda x: x**2+5*x+2

results = bissection(f1,-5,5,0.02)
print("[x*,f(x*)] = ",[results[0][-1],results[1][-1]])


plot2D(f1,-5,5,results[0],results[1])


```

## Secant Method

$$
Secant's\ Method\ :\ x_{k+1}=x_{k}-\frac{f(x_k)}{ \left[ \frac{f(x_k)-f(x_{k-1})}{x_k - x_{k-1}}\right]}\\
To\ find\ the\ minimal\ point\ of\ the\ function\ f:\mathbb{R}\rightarrow \mathbb{R}\\
x_{k+1}=x_{k}-\frac{f'(x_k)}{ \left[ \frac{f'(x_k)-f'(x_{k-1})}{f(x_k) - f(x_{k-1})}\right]}
$$


```python
def secant(fct,x0,x1,err=0.005,verbose=False):
  if verbose:
    print("Function :",fct) #fct must be lambda
  
  f = fct
  x_k = x1
  x_k_1 = x0

  f_prime_xk = derivative(f,x_k,dx=dx)
  f_prime_xk_1 = derivative(f,x_k_1,dx=dx)
  
  result = [[x_k_1,x_k],[f(x_k_1),f(x_k)]]

  while (abs(x_k - x_k_1) > err) and (abs(f_prime_xk) > err):

    x_k1 = x_k-(f_prime_xk/ ( (f_prime_xk-f_prime_xk_1)/(f(x_k) - f(x_k_1)) ) )
    x_k_1 = x_k
    x_k = x_k1
    result[0].append(x_k)
    result[1].append(f(x_k))
    f_prime_xk = derivative(fct,x_k,dx=dx)
    f_prime_xk_1 = derivative(fct,x_k_1,dx=dx)
    if verbose:
      print("x_k: ",x_k)
      print("x_k-1: ",x_k_1)
      print("f_prime_xk : ",f_prime_xk)
      print("f_prime_xk-1 : ",f_prime_xk_1) 


  if abs(f_prime_xk) < err:
    print([x_k,f(x_k)])
    return results
  print("ERREUR DE CALCUL")


```


```python
fun = lambda x: np.sin(np.cos(np.exp(x)))
results_sec = secant(fun,1,1.5)
plot2D(fun,-10,10,results_sec[0],results_sec[1])

```

## Newton-Raphson Method

$$
Newton's\ Method\ :\ x_{k+1}=x_{k}-\frac{f(x_k)}{f'(x_k)}\\
To\ find\ the\ minimal\ point\ of\ the\ function\ f:\mathbb{R}\rightarrow \mathbb{R}\\
x_{k+1}=x_{k}-\frac{f'(x_k)}{f''(x_k)}
$$


```python
def newton(fct,x0,err=0.005,verbose=False):
  cpt = 0
  x_k = x0
  f = fct 

  f_prime_xk = derivative(fct,x_k,dx=dx)
  f_second_xk =derivative(fct,x_k,dx=dx,n=2)
  results_nwtn = []
  if (np.any(f_prime_xk) != np.any(0)) and (np.any(f_second_xk) != np.any(0)):
 
    while abs(f_prime_xk) > err:
      results_nwtn = [[x_k],[f(x_k)]]
      if verbose:
        print ("cpt = ",cpt)

      cpt+=1
      x_k1 = x_k-(f_prime_xk/f_second_xk)
      x_k = x_k1
      results_nwtn[0].append(x_k)
      results_nwtn[1].append(f(x_k))
      f_prime_xk =derivative(fct,x_k,dx=dx)
      f_second_xk =derivative(fct,x_k,dx=dx,n=2) 
      
      if verbose :
        print("x_k: ",x_k)
        print("f(x_k) = ",f(x_k))
        print("f_prime_xk : ",f_prime_xk) 
        print("f_second_xk : ",f_second_xk)
        print("norm(f_prime(x_k)) : ",norm(f_prime_xk))
      
    if verbose:
      print("[x,f(x)] = ",[x_k,fct(x_k)])
    return results_nwtn
  print("ERREUR DE CALCUL")
```


```python
# f2 = lambda x : 1/(-np.sin(-x**2)+2)
# # f2 = lambda x: np.sin(np.cos(np.exp(x)))


results_newton = newton(f1,1,0.002)
print(results_newton)
print("[x*,f(x*)] = ",[results_newton[0][-1],results_newton[1][-1]])
plot2D(f1,-6,1,results_newton[0],results_newton[1])
# plot(f2,-1,1,results_newton[0],results_newton[1])


```

## False Position Method - Regula Falsi

$$
False\ Position's\ method\ :\  x_{k+1}=x_k-f'(x_k)\times\frac{(x_k-x_{k-1})}{f'(x_k)-f'(x_{k-1})}
$$


```python
def regula_falsi(fct,x0,x1,err=0.005,verbose=False):
  
  if verbose:
    print("f(x) = ",fct)

  f = fct
  x_k = x1
  x_k_1 = x0

  f_prime_xk = derivative(fct,x_k,dx=dx)
  f_prime_xk_1 = derivative(fct,x_k_1,dx=dx) 

  res = [[x_k_1,x_k],[f(x_k_1),f(x_k)]]
  while (abs(x_k - x_k_1) > err) and (abs(f_prime_xk) > err):
    x_k1 = x_k-(f_prime_xk * (x_k - x_k_1)/ (f_prime_xk-f_prime_xk_1)  )
    x_k_1 = x_k
    x_k = x_k1

    res[0].append(x_k)
    res[1].append(f(x_k))
    f_prime_xk = derivative(fct,x_k,dx=dx)
    f_prime_xk_1 = derivative(fct,x_k_1,dx=dx)
    
    if verbose:
      print("x_k: ",x_k)
      print("x_k-1: ",x_k_1)
      print("f_prime_xk : ",f_prime_xk)
      print("f_prime_xk-1 : ",f_prime_xk_1) 

  if abs(f_prime_xk) < err:
    print([res[0][-1],res[1][-1]])
    return res
  print("ERREUR DE CALCUL")

```


```python
# f2 = lambda x: np.sin(np.power(x,2))+1
# f2 = lambda x: np.sin(np.cos(np.log(1/np.power(x,2))))

results_falsi = regula_falsi(f1,2,2.5)
print(results_falsi)
print("[x*,f(x*)]",[results_falsi[0][-1],results_falsi[1][-1]])
plot2D(f1,-10,5,results_falsi[0],results_falsi[1])


```

## Bissection - Newton's Method (Hybrid)


```python
def bissection_newton(fct,a,b,err=.005):
  print("\n\nBissection :\n")
  results_biss = bissection(fct,a,b,err)
  # print(results_biss)
  [x0,f_x0] = [results_biss[0][-1],results_biss[1][-1]]
  print("\n\nNewton : \n")
  results_nwtn = newton(fct,x0,err)
  return results_nwtn
```

## Comparison < Newton, Bissection, Hybrid >


```python

f3 = lambda x: np.sin(np.cos(np.exp(x)))
f3_prime = lambda x: -exp(x)*sin(exp(x))*cos(cos(exp(x)))

print("\n\n\n ~~> Newton's Method \n")
nwtn = newton(f3,0.8)
print(f"f(x*={nwtn[0][-1]}) = {nwtn[1][-1]}")
  # result: 1.1494460852213106, -0.8414113953797868
  #         f'(x*) = 0.02533145117663931

print("\n\n\n ~~> Bissection's Method\n")
biss = bissection(f3,0,1.7)
print(f"f(x*={biss[0][-1]}) = {biss[1][-1]}")
  # result: 1.1421875, -0.8414537940888557
  #         f'(x*) = -0.013506376215777379

print("\n\n\n ~~> Bissection-Newton's Method\n")
biss_nwtn = bissection_newton(f3,-2,1.8) # Precise et nous donne une marge plus grande pour choisir les points initiaux 
print(f"f(x*={biss_nwtn[0][-1]}) = {biss_nwtn[1][-1]}" )
  # result: 1.1450208128703885, -0.8414707590717263
  #         f'(x*) = 0.0015520666672475564


plt.plot(nwtn[0][-1],nwtn[1][-1],'og',label="Newton") # Newton
plt.plot(biss[0][-1],biss[1][-1],'xb',label="Bissection")  # Bissection
plt.plot(biss_nwtn[0][-1],biss_nwtn[1][-1],'.r',label="Bissection-Newton") # Bissection-Newton
plt.legend()
plt.show()
# plot2D(f3,1.144,1.146,[nwtn[0][-1],biss[0][-1],biss_nwtn[0][-1]],[nwtn[1][-1],biss[1][-1],biss_nwtn[1][-1]])
plot2D(f3,0,2,[biss_nwtn[0]],[biss_nwtn[1]])
```

aa6f12940e92d26e8250522a09880851eea160d8
ipynb
Jupyter Notebook
Line_search.ipynb
Taylor-X01/Optimization-Algorithms
c21bcc8d16e344cbac1c6b65d12211075fd1ae2b
MIT
Line_search.ipynb
Taylor-X01/Optimization-Algorithms
c21bcc8d16e344cbac1c6b65d12211075fd1ae2b
MIT
Line_search.ipynb
Taylor-X01/Optimization-Algorithms
c21bcc8d16e344cbac1c6b65d12211075fd1ae2b
MIT
Qwen/Qwen-72B
1. YES
2. YES