《Convex Optimization》

在介紹下降方法之前，我們需要先看一些預(yù)備的知識(shí)啃洋。

預(yù)備知識(shí)

我們假設(shè)目標(biāo)函數(shù)在下水平集上是強(qiáng)凸的欢嘿，這是指存在，使得

對(duì)于任意成立揩局。
注意毫玖，這個(gè)廣義不等式，是指半正定凌盯，即付枫，的最小特征值大于等于。
對(duì)于驰怎，我們有廣義泰勒展開：


利用強(qiáng)凸性假設(shè)阐滩，可以推得不等式（同時(shí)可知，是有界的）：

通過县忌，不等式右邊是關(guān)于的二次凸函數(shù)掂榔，令其關(guān)于的導(dǎo)數(shù)等于零，可以得到該二次函數(shù)的最優(yōu)解症杏，所以

是的全局最優(yōu)解装获，，因?yàn)樯鲜霾坏仁綄?duì)于任意都成立厉颤，所以：

由此可見穴豫，任何梯度足夠小的點(diǎn)都是近似最優(yōu)解。由于走芋，

我們可以將其解釋為次優(yōu)性條件绩郎。
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=S" alt="S" mathimg="1">有界，而的最大特征值是在上的連續(xù)函數(shù)翁逞，所以它在上有界，即存在常數(shù)使得：

關(guān)于Hessian矩陣的這個(gè)上界溉仑，意味著挖函，對(duì)任意的:

同樣，可以得到：

注意：

為矩陣的條件數(shù)的上界。通常怨喘，越薪蚧（越接近1），梯度下降收斂的越快必怜。這個(gè)條件會(huì)在收斂性分析中反復(fù)用到肉拓。

下降方法

由凸性知：意味著，因此一個(gè)下降方法中的搜索方向必須滿足：

我們并沒有限定下降方向必須為逆梯度方向梳庆，事實(shí)上這種選擇也僅僅是局部最優(yōu)的策略暖途。
所以算法是如此的：

下降方法

梯度下降方法的算法如下：

梯度下降

精確直線搜索

精確直線搜索需要我們求解下面的單元的優(yōu)化問題：

因?yàn)閱栴}是一元的，所以相對(duì)來說比較簡(jiǎn)單更米，可以通過一定的方法來求解該問題欺栗，特殊情況下，可以用解析方法來確定其最優(yōu)解征峦。

收斂性分析

在收斂性分析的時(shí)候迟几，我們選擇。
我們定義：栏笆，同時(shí)类腮，我們只考慮滿足的。通過預(yù)備知識(shí)竖伯，我們?nèi)菀椎玫较旅娴囊粋€(gè)上界：

上界

對(duì)上述不等式倆邊同時(shí)關(guān)于求最小存哲，左邊等于，右邊是一個(gè)簡(jiǎn)單的二次型函數(shù)七婴，其最小解為祟偷，因此我們有：

從該式倆邊同時(shí)減去，我們得到

又打厘，可以斷定：

重復(fù)進(jìn)行修肠，可以看出，

收斂性分析到這為止户盯，更多內(nèi)容翻看凸優(yōu)化嵌施。

回溯直線搜索

回溯直線搜索，不要求每次都減少最多莽鸭，只是要求減少足夠量就可以了吗伤。其算法如下:

在這里插入圖片描述

在這里插入圖片描述

在實(shí)際計(jì)算中，我們首先用乘直到巧号，然后才開始檢驗(yàn)停止準(zhǔn)則是否成立族奢。

參數(shù)的正常取值在0.01 和 0.3 之間表示我們可以接受的的減少量在基于線性外推預(yù)測(cè)的減少量的和之間。參數(shù)的正常取值在 0.1（對(duì)應(yīng)非常粗糙的搜索）和 0.8（對(duì)應(yīng)于不太粗糙的搜索）之間丹鸿。

收斂性分析

我們先證明越走，只要，就能滿足回溯停止條件：

首先靠欢，注意到：

由于（這也是為什么我們限定的原因）廊敌，所以可以得到：

在這里插入圖片描述

數(shù)值試驗(yàn)

我們選取初始點(diǎn)為

下圖是精確直線搜索：

精確直線搜索

下圖是回溯直線搜索，可以看出來薪缆，每一次的震蕩的幅度比上面的要大一些秧廉。

在這里插入圖片描述

下面采用的是回溯直線搜索，,初始點(diǎn)為

回溯直線搜索

初始點(diǎn)為

回溯直線搜索

回溯直線搜索

代碼

import numpy as np

class GradDescent:
    """
    梯度下降方法
    """
    def __init__(self, f, x):
        assert hasattr(f, "__call__"), \
            "Invalid function {0}".format(f)
        self.__f = f
        self.x = x
        self.y = self.__f(x)
        self.__process = [(self.x, self.y)]

    @property
    def process(self):
        """獲得梯度下降過程"""
        return self.__process

    def grad1(self, update_x, error=1e-5):
        """精確收縮算法
        update_x: 用來更新x的函數(shù)拣帽，這個(gè)我們沒辦法在這里給出
        error: 梯度的誤差限疼电，默認(rèn)為1e-5
        """
        assert hasattr(update_x, "__call__"), \
            "Invalid function {0}".format(update_x)
        error = error if error > 0 else 1e-5
        while True:
            x = update_x(self.x)
            if (x - self.x) @ (x - self.x) < error:
                break
            else:
                self.x = x
                self.y = self.__f(self.x)
                self.__process.append((self.x, self.y))

    def grad2(self, gradient, alpha, beta, error=1e-5):
        """回溯直線收縮算法
        gradient: 梯度需要給出
        alpha: 下降的期望值 (0, 0.5)
        beta:每次更新的倍率 (0, 1)
        error: 梯度的誤差限，默認(rèn)為1e-5
        """
        assert hasattr(gradient, "__call__"), \
            "Invalid gradient"
        assert 0 < alpha < 0.5, \
            "alpha should between (0, 0.5), but receive {0}".format(alpha)
        assert 0 < beta < 1, \
            "beta should between (0, 1), but receive {0}".format(beta)
        error = error if error > 0 else 1e-5
        def search_t(alpha, beta):
            t = 1
            t_old = 1
            grad = -gradient(self.x)
            grad_module = grad @ grad
            while True:
                newx = self.x + t * grad
                newy = self.__f(newx)
                if newy < self.y - alpha * t * grad_module:
                    return t_old
                else:
                    t_old = t
                    t = t_old * beta
        while True:
            t = search_t(alpha, beta)
            x = self.x - t * gradient(self.x)
            if (t * gradient(self.x)) @ (t * gradient(self.x)) < error:
                break
            else:
                self.x = x
                self.y = self.__f(self.x)
                self.__process.append((self.x, self.y))



r = 10.

def f(x):
    vec = np.array([1., r], dtype=float)
    return 0.5 * (x ** 2) @ vec

def f2(x):
    x0 = x[0]
    x1 = x[1]
    return np.exp(x0+3*x1-0.1) \
            + np.exp(x0-3*x1-0.3) \
            + np.exp(-x0-0.1)
def gradient2(x):
    x0 = x[0]
    x1 = x[1]
    grad1 = np.exp(x0+3*x1-0.1) \
            + np.exp(x0-3*x1-0.3) \
            - np.exp(-x0-0.1)
    grad2 = 3 * np.exp(x0+3*x1-0.1) \
            -3 * np.exp(x0-3*x1-0.3)
    return np.array([grad1, grad2])


def update(x):
    t = -(x[0] ** 2 + r ** 2 * x[1] ** 2) \
            / (x[0] ** 2 + r ** 3 * x[1] ** 2)
    x0 = x[0] + t * x[0]
    x1 = x[1] + t * x[1] * r
    return np.array([x0, x1])

def gradient(x):
    diag_martix = np.diag([1., r])
    return x @ diag_martix

x_prime = np.array([7, 3.], dtype=float)
ggg = GradDescent(f2, x_prime)
#ggg.grad1(update)
ggg.grad2(gradient2, alpha=0.2, beta=0.7)
process = ggg.process
import matplotlib.pyplot as plt
import matplotlib.path as mpath
fig, ax = plt.subplots(figsize=(10, 6))
w1 = 4
w2 = 10
Y, X = np.mgrid[-w1:w1:300j, -w2:w2:300j]
U = X
V = r * Y
ax.streamplot(X, Y, U, V)
process_x = list(zip(*process))[0]
print(process_x)
path = mpath.Path(process_x)
x0, x1 = zip(*process_x)
ax.set_xlim(-8, 8)
ax.set_ylim(-4, 4)
ax.plot(x0, x1, "go-")
plt.show()