用变尺度法求解无约束优化问题,并绘制程序框图,编写matlab或python程序(逐行注释)

变尺度法是一种常见的无约束优化方法，它通过缩小搜索范围逐步逼近最优解，通常可将问题转化为一系列具有“确定性可导的几何意义”的子问题。具体流程如下：

1.选择合适的起点$x_0$和尺度参数$t_0$

2.对于给定的$x_k$和$t_k$，求解在$x_k$点尺寸为$t_k$的球面内的最小二乘解$x_{k+1}$，并且令$t_{k+1}=\frac{t_k}{2}$

3.若$\| \nabla f(x_{k+1}) \|<\epsilon$，则$x_{k+1}$为最优解，停止迭代；否则令$k=k+1$，并返回步骤2

绘制程序框图如下：

输入：起点$x_0$，收敛精度$\epsilon$
输出：最优解$x^*$

初始化：设$k=0,t_0$为初始尺度参数

while $\| \nabla f(x_{k}) \|>\epsilon$：

设$y_k$为$t_k$尺度下$x_k$点的邻域内的解，即$y_k$是在$\|x_k-y_k\|\leq t_k$范围内求解的最小函数值点

设$x_{k+1}$为子问题的最优解

若$\| \nabla f(x_{k+1}) \|<\epsilon$，则停止迭代，输出$x_{k+1}$

令$k=k+1$，$t_{k}=\frac{t_{k-1}}{2}$

输出x_{k+1}

以下是matlab的代码实现（注释详尽）：

function [x_star] = variableScale(f, gradf, Hessianf, x0, epsilon) %输入：函数、梯度、海森矩阵、初始点、精度 %输出：最优解

k = 0; %设置迭代次数

t0 = 1; %设置初始尺度参数

while true %进入while循环

g = gradf(x0); %计算梯度

if norm(g) < epsilon %若梯度小于精度值，最优解为x0，直接输出

x_star = x0;

break;

end

t = t0/2^k; %计算当前尺度参数

d = 1; %定义小区域半径

while true %进入子阶段1：寻找解y

[V,D] = eig(Hessianf(x0)); %求Hessian的特征值和特征向量

D = diag(D);

rho = 1/max(D); %计算最优步长

delta = 1/(1+rho); %计算线性搜索步长

y = x0 - g*rho + d*V*delta*V'*g; %计算解y

if abs(f(y)-f(x0)) <= t*d*norm(g) %若小区域内无解，调整半径并重新搜索

d = d*2;

continue;

end

break;

end

while true %进入子阶段2：一维搜索

lambda = 1;

while true %进入子阶段2.1：寻找合适的一维搜索步长

if f(x0+lambda*(y-x0)) <= f(x0) + lambda*0.5*(g'*(y-x0)) %当前步长满足要求，继续搜索

break;

end

lambda = 0.5*lambda; %当前步长不满足要求，缩小步长值

end

if norm(gradf(x0+lambda*(y-x0))) < (1-t)*norm(g) %检查是否符合停机准则

x_star = x0 + lambda*(y-x0); %拟合最优解

break; %结束while循环

else

x0 = x0 + lambda*(y-x0); %迭代，继续下一次搜索

end

end

k = k + 1; %迭代次数+1

end

end