proximal gradient（近端梯度法）

4 人贊了文章

1.proximal mapping的概念及性質

[1]基本概念

(1)定義

(2)幾個實例

{1}常數函數

{2}仿射函數

{3}二次函數

{4}L_1範數

[2]性質

(1)分離函數

實例，

(2)仿射函數的分解

(3)第一投影定理

(4)第二鄰近定理

(5)莫洛定理

(6)Moreau envelope

================================================

2.proximal gradient方法

[1]方法描述

[2]簡要分析

[3]收斂性分析

迭代後是否會收斂，及收斂速度如何。

是一個下降方法，

收斂速度，

[4]演算法：固定步長和回溯步長

固定步長：

回溯步長：

在回溯搜索過程中，需要計算回溯不等式，檢驗當前點及當前步長是否滿足回溯不等式，若滿足，則變小步長；直到不滿足，則停止迭代。

==============================================

3.例子+分析+編程

問題：

分析：

編程（用的python）：

固定步長

# -*- coding: utf-8 -*-import numpy as npimport scipy as spyfrom scipy.sparse import csc_matriximport matplotlib.pyplot as pltimport time#=======模擬數據======================m = 512n = 1024#稀疏矩陣的產生u= spy.sparse.rand(n,1,density=0.1,format=csc,dtype=None)u1 = u.nonzero()row = u1[0]col = u1[1]data = np.random.randn(int(0.1*n))u = csc_matrix((data, (row, col)), shape=(n,1)).toarray() #其它項a = np.random.randn(512,1024)b = np.dot(a,u)v = 1e-3 #v為題目裡面的miudef f(x0): #目標函數 return 1/2*np.dot((np.dot(a,x0)-b).T,np.dot(a,x0)-b)+v*sum(abs(x0))y = []time1 = []start = time.clock()#==========初始值=============================x0 = np.zeros((n,1))#採用固定步長t = 1/np.max(np.linalg.eigvals(np.dot(a.T,a))).realfor i in range(1000): y.append(f(x0)) x1 = x0-t*np.dot(a.T,np.dot(a,x0)-b) x1[x1 >= t*v] = x1[x1 >= t*v] - t*v x1[np.abs(x1) < t*v] = 0 x1[x1 <= -t*v] = x1[x1 <= -t*v] + t*v x0 = x1 end = time.clock() time1.append(end)y = np.array(y).reshape((1000,1)) plt.plot(y)time1 = np.array(time1)time1 = time1 - starttime2 = time1[np.where(y - y[999] < 10e-4)[0][0]]# if i % 5 == 0: # f = 1/2*np.dot((np.dot(a,x0)-b).T,np.dot(a,x0)-b)+v*sum(abs(x0))# print(f)

目標函數值圖

回溯步長

# -*- coding: utf-8 -*-"""Created on Fri May 25 17:28:01 2018@author: acer"""import numpy as npimport scipy as spyfrom scipy.sparse import csc_matriximport matplotlib.pyplot as pltimport time#=======模擬數據======================m = 512n = 1024#稀疏矩陣的產生u= spy.sparse.rand(n,1,density=0.1,format=csc,dtype=None)u1 = u.nonzero()row = u1[0]col = u1[1]data = np.random.randn(int(0.1*n))u = csc_matrix((data, (row, col)), shape=(n,1)).toarray() #其它項a = np.random.randn(512,1024)b = np.dot(a,u)v = 1e-3 #v為題目裡面的miu#==========初始值=============================x0 = np.zeros((n,1))beta = 0.8t = 0.001 #初始值為0.1時f數值先變得很大，後減小，但仍然很大e+14左右；初始值設為0.01,0.001均可以取得 #較好結果。def f(x0): #目標函數 return 1/2*np.dot((np.dot(a,x0)-b).T,np.dot(a,x0)-b)+v*sum(abs(x0))def g(x0): return 1/2*np.dot((np.dot(a,x0)-b).T,np.dot(a,x0)-b) y = [] time1 = []start = time.clock() #採用回溯步長for i in range(1000): y.append(f(x0)) x1 = x0-t*np.dot(a.T,np.dot(a,x0)-b) x1[x1 >= t*v] = x1[x1 >= t*v] - t*v x1[np.abs(x1) < t*v] = 0 x1[x1 <= -t*v] = x1[x1 <= -t*v] + t*v G = 1/t*(x0 - x1) if g(x0-t*G) > g(x0) - t*np.dot(np.dot(a.T,np.dot(a,x0)-b).T,G)+t/2*np.dot(G.T,G): t = beta*t #最終t都會變為特徵np.dot(a.T,a)的最大特徵值導數 x0 = x1 end = time.clock() time1.append(end)y = np.array(y).reshape((1000,1)) plt.plot(y) time1 = np.array(time1)time1 = time1 - starttime2 = time1[np.where(y - y[999] < 10e-4)[0][0]] # if i % 50 == 0: # print(f(x1))

目標函數值圖

肉眼看起來一樣，但實際上回溯步長會快一些，兩幅圖在一起就可以看出來

推薦閱讀：