python 공 액 경사도 법 실현

공 액 경사도 법 은 최 속 하강 법 과 뉴턴 법 사이 에 있 는 방법 으로 1 단계 도체 정 보 를 이용 해 야 하지만 최 속 하강 법 수렴 이 느 린 단점 을 극복 하고 뉴턴 법 은 Hesse 행렬 을 저장 하고 계산 하 며 역 효 과 를 구 해 야 한 다 는 단점 을 피 했다.공 액 경사도 법 은 대형 선형 방정식 을 해결 하 는 가장 유용 한 방법 중 하나 일 뿐만 아니 라대형 비 선형 최적화 에 가장 효과 적 인 알고리즘 중 하나 이기 도 하 다. 각종 최적화 알고리즘 중에서 공 액 경사도 법 은 매우 중요 한 것 이다.필요 한 저장량 이 적 고 수렴 성 이 있 으 며 안정성 이 높 으 며 외부 매개 변수 가 필요 없다 는 장점 이 있다.
알고리즘 단계:

import random
import numpy as np
import matplotlib.pyplot as plt
 
def goldsteinsearch(f,df,d,x,alpham,rho,t):
 '''
        
  f，  df，     x       d，t    >1，
 '''
 flag = 0
 
 a = 0
 b = alpham
 fk = f(x)
 gk = df(x)
 
 phi0 = fk
 dphi0 = np.dot(gk, d)
 alpha=b*random.uniform(0,1)
 
 while(flag==0):
  newfk = f(x + alpha * d)
  phi = newfk
  # print(phi,phi0,rho,alpha ,dphi0)
  if (phi - phi0 )<= (rho * alpha * dphi0):
   if (phi - phi0) >= ((1 - rho) * alpha * dphi0):
    flag = 1
   else:
    a = alpha
    b = b
    if (b < alpham):
     alpha = (a + b) / 2
    else:
     alpha = t * alpha
  else:
   a = a
   b = alpha
   alpha = (a + b) / 2
 return alpha
 
 
def Wolfesearch(f,df,d,x,alpham,rho,t):
 '''
        
  f，  df，     x       d
 σ∈(ρ,1)=0.75
 '''
 sigma=0.75
 
 flag = 0
 
 a = 0
 b = alpham
 fk = f(x)
 gk = df(x)
 
 phi0 = fk
 dphi0 = np.dot(gk, d)
 alpha=b*random.uniform(0,1)
 
 while(flag==0):
  newfk = f(x + alpha * d)
  phi = newfk
  # print(phi,phi0,rho,alpha ,dphi0)
  if (phi - phi0 )<= (rho * alpha * dphi0):
   # if abs(np.dot(df(x + alpha * d),d))<=-sigma*dphi0:
   if (phi - phi0) >= ((1 - rho) * alpha * dphi0):
    flag = 1
   else:
    a = alpha
    b = b
    if (b < alpham):
     alpha = (a + b) / 2
    else:
     alpha = t * alpha
  else:
   a = a
   b = alpha
   alpha = (a + b) / 2
 return alpha
 
def frcg(fun,gfun,x0):
 
 
 # x0    ，fun gfun          
 # x,val            ，k     
 # dk     ，gk     
 # epsilon     ，np.linalg.norm(gk)        
 maxk = 5000
 rho = 0.6
 sigma = 0.4
 k = 0
 epsilon = 1e-5
 n = np.shape(x0)[0]
 itern = 0
 W = np.zeros((2, 20000))
 
 f = open("  .txt", 'w')
 
 while k < maxk:
   W[:, k] = x0
   gk = gfun(x0)
   itern += 1
   itern %= n
   if itern == 1:
    dk = -gk
   else:
    beta = 1.0 * np.dot(gk, gk) / np.dot(g0, g0)
    dk = -gk + beta * d0
    gd = np.dot(gk, dk)
    if gd >= 0.0:
     dk = -gk
   if np.linalg.norm(gk) < epsilon:
    break
 
   alpha=goldsteinsearch(fun,gfun,dk,x0,1,0.1,2)
   # alpha=Wolfesearch(fun,gfun,dk,x0,1,0.1,2)
   x0+=alpha*dk
 
   f.write(str(k)+' '+str(np.linalg.norm(gk))+"
")
   print(k,alpha)
   g0 = gk
   d0 = dk
   k += 1
 
 W = W[:, 0:k+1] #      
 return [x0, fun(x0), k,W]
 
def fun(x):
 return 100 * (x[1] - x[0] ** 2) ** 2 + (1 - x[0]) ** 2
def gfun(x):
 return np.array([-400 * x[0] * (x[1] - x[0] ** 2) - 2 * (1 - x[0]), 200 * (x[1] - x[0] ** 2)])
 
 
if __name__=="__main__":
 X1 = np.arange(-1.5, 1.5 + 0.05, 0.05)
 X2 = np.arange(-3.5, 4 + 0.05, 0.05)
 [x1, x2] = np.meshgrid(X1, X2)
 f = 100 * (x2 - x1 ** 2) ** 2 + (1 - x1) ** 2 #      
 plt.contour(x1, x2, f, 20) #      20    
 
 x0 = np.array([-1.2, 1])
 x=frcg(fun,gfun,x0)
 print(x[0],x[2])
 # [1.00318532 1.00639618]
 W=x[3]
 # print(W[:, :])
 plt.plot(W[0, :], W[1, :], 'g*-') #           
 plt.show()

코드 에서 가장 좋 은 걸음 길 이 를 구 하 는 것 은 Goldsteinsearch 방법 이 고 다른 Wolfesearch 는 시험 적 인 부분 으로 이 프로그램 에서 역할 을 하지 않 습 니 다.
반복 궤적:


세 가지 최 적 화 된 방법의 교체 횟수 비교:
최적화 방법
최 속 하강 법
공 액 경사도 법
뉴턴 법
반복 횟수
1702
240
5
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.