最优化理论——信赖域方法

在无约束优化问题中，信赖域方法是一种重要的求解方法。它通过在以当前迭代点为中心的信赖域内逼近目标函数的最小值，逐步迭代找到全局最优解。本文将介绍信赖域方法的算法思想、算法步骤和子问题求解，并通过实例展示其应用。

一、信赖域方法的结构

信赖域方法的核心是在以当前迭代点为中心的信赖域内逼近目标函数的最小值。在每次迭代中，通过求解子问题来获得逼近最小值的解，并更新迭代点。子问题是在当前迭代点附近的二次近似问题，即 min_d ||grad(f)(x) + H(x) d - c||^2 s.t. ||d|| <= delta 其中 f(x) 是目标函数，c 是目标函数的下降方向，H(x) 是目标函数的Hessian矩阵，d 是待求的搜索方向，delta 是信赖域半径。

二、算法步骤

1. 初始化：设置初始值 x0、初始信赖域半径 delta、最大迭代次数 max_iter、收敛精度 tol 等参数。
2. 迭代：对于 k=0,1,2,…,max_iter-1，执行以下步骤：
   a. 计算目标函数在当前点的梯度 gk 和Hessian矩阵 Bk。
   b. 计算 ck = -gk + Bk dk-1。
   c. 求解子问题 min_d ||dk||^2 s.t. ||d|| <= delta，得到 dk 和最优值 val。
   d. 如果 ||dk|| <= tol，则停止迭代；否则更新 xk+1 = xk + dk。
3. 输出：返回最优解 xk+1 和最优值 val。

三、子问题求解

子问题的求解可以采用多种方法，如牛顿法、拟牛顿法等。这里我们介绍一种常用的方法——共轭梯度法。共轭梯度法是一种迭代算法，通过不断更新搜索方向来逼近最优解。在每一步迭代中，根据当前点和搜索方向，计算新的搜索方向，直到满足收敛条件为止。具体算法如下：

1. 初始化：设置初始点 x0 和初始搜索方向 d0。
2. 迭代：对于 k=0,1,2,…,max_iter-1，执行以下步骤：
   a. 计算梯度 gk = grad(f)(xk)。
   b. 如果 k=0，则令 dk = -gk；否则计算共轭方向 pk = -gk + beta pk-1 (gk - gk-1)，其中 beta 是共轭梯度参数。
   c. 计算步长 ak = min(delta / ||dk||, 1)，并将步长乘以搜索方向得到下一次迭代点 xk+1 = xk + ak * dk。
   d. 如果 ||xk+1 - xk|| <= tol，则停止迭代；否则更新 d0 = dk，继续迭代。
3. 输出：返回最优解 xk+1 和最优值 val。

四、应用实例

下面我们通过一个简单的二次函数优化问题来展示信赖域方法的应用。假设我们要最小化 f(x) = x^2 - 4x + 4，这是一个开口向上的抛物线，最小值点为 x=2。我们采用信赖域方法进行优化，初始点为 x0=1，初始信赖域半径为 delta=0.5，最大迭代次数为 max_iter=1000，收敛精度为 tol=1e-6。我们将使用共轭梯度法求解子问题。

在 MATLAB 中实现上述算法的代码如下：

```matlab
function [x_star, f_val] = trust_region()
% 初始化参数
x0 = 1; delta = 0.5; max_iter = 1000; tol = 1e-6;
g = @(x) 2*x - 4; B = @(x) 2; d = zeros(1, max_iter); x = x0;
mu = 0.05; lam = 0.05; d0 = ones(1, max_iter); z0 = [mu, lam, d0