求解广义Fermat-Torricelli问题的多层邻近梯度算法

2019-07-25 08:29马丽丽谢秋玲胡清洁
桂林电子科技大学学报 2019年2期
关键词:算例广义正方体

马丽丽,谢秋玲,胡清洁

(桂林电子科技大学 数学与计算科学学院,广西 桂林 541004)

Fermat-Torricelli问题最初由法国数学家Pierre de Fermat提出,即给定平面上的3点,找到1个点,使其与3点的欧几里德距离之和最小。这个问题引发了对位置科学的研究兴趣,意大利数学家Evangelista·Torricelli最早研究该问题。随后这个问题被称为Fermat-Torricelli问题。该问题一直是优化领域中的一个研究热点,在优化网络[1]、设施选址[2]、计算几何[3]、定位科学、物流等方面具有广泛应用。l2范数下广义Fermat-Torricelli问题模型为

(1)

其中:ai∈Rn,i=1,2,…,m;Ω为Rn上的非空闭凸集。集合的广义Fermat-Torricelli问题模型为

(2)

其中:Ωi(i=1,2,…,m)为目标集。

近年来,Fermat-Torricelli问题得到广泛关注。Weiszfeld[4]首次提出求解Fermat-Torricelli问题的算法,随后,许多研究者对该算法进行了修正和改进[5-7]。Nam等[8]提出用Nesterov光滑技术求解广义Fermat-Torricelli问题,其主要思想是对原目标函数构造光滑逼近,利用加速梯度法求解,并用数值实验说明算法的有效性。Parpas等[9]基于多层优化方法,提出用多层加速梯度镜面下降算法求解大规模人脸识别问题,并用数值实验验证了该算法的可行性。

为求解广义Fermat-Torricelli问题,基于文献[9-10],提出多层邻近梯度算法,并给出相关收敛速度分析和数值实验。

1 预备知识

定义1给定集合Ω⊆Rn,则

称为集合Ω的示性函数。

定义2[8]点x到Rn上非空闭凸集Ω的欧式投影为

π(x;Ω)={w∈Ω|d(x;Ω)=‖x-w‖}。

特别地,点x到以δ为中心、r为半径的立方体集合Ω上的投影为

PΩ(x)=max{δi-r,min{xi,δi+r}}。

2 算法描述

对模型(1)的目标函数进行μ光滑[11]和引入示性函数,则原问题可转化为

同样地,模型(2)的问题可转化为

将上述2个问题的一般形式记为

(3)

其中:f:Rn→R为光滑凸函数;g:Rn→R为连续凸函数不一定光滑。

QL(x,y)=f(x)+〈y-x,f(x)〉+

定义PL(x)=argmin{QL(x,y),y∈Rn}。

多层算法需要在层次之间使用适当的信息传递机制。为了在层次之间传递信息,引入线性限制算子R:Rn×nH和延拓算子P:RnH×n,其中nH

σP=RT,

其中σ>0,不失一般性,假设σ=1。算子的选取参见文献[12]。

为求解粗糙子问题,引入一个光滑参数ε>0,对g(x)进行光滑化得到gε(x),光滑后的目标函数为

Fε(x)=f(x)+gε(x)。

粗糙模型的关键属性是初始点xH,0处2个模型的最优性条件相匹配,可通过在粗略模型的目标函数中引入线性项来实现。粗糙模型的目标函数为

FH,ε(xH)=fH(xH)+gH,ε(xH)+〈vH,xH〉。

其中:fH(xH)、gH,ε(xH)均为光滑函数;vH=RFε(x)-(fH(Rx)+gH,ε(Rx))。

迭代过程中,算法是否使用粗糙模型构建搜索方向取决于当前迭代点xk的最优性条件。进行粗糙迭代应满足以下2个条件:

(4)

为满足相容性,用xH,0=Rxk开始粗糙迭代,通过一阶优化方法求解粗糙模型并构造搜索方向,

dk(xk)=P(xH,NH-Rxk),

其中xH,NH∈RnH为执行NH次迭代后粗糙模型的近似解。由于通常找不到精确解,利用Nesterov加速梯度算法[8]求解该子问题,得到一个可接受的解xH,NH。

多层邻近梯度算法的步骤为:

1)选取L>0,τ>0,ε>0,0

2)若粗糙条件(4)不满足,转步骤3),否则执行NH次粗糙迭代得xH,NH,计算dk=P(xH,NH-Rxk)。由Armijo线搜索求得步长sk,

Fε(xk+skdk)≤Fε(xk)+cskFε(xk)Tdk。

3)计算yk=PL(xk),若‖xk-yk‖<τ,迭代终止,输出yk作为近似极小点,否则转步骤4)。

3 收敛速度分析

为了分析多层邻近梯度算法的收敛速度,首先给出如下4个引理。

引理1若x∈Rn,存在L>0,使得

Fε(PL(x))≤Q(PL(x),x)

成立,则对∀y∈Rn,有

L〈x-y,PL(x)-x〉。

引理2设{xk}和{yk}是由多层邻近梯度算法产生的序列,则对∀k≥1,有

其中

vk=Fε(yk)-Fε(y*),uk=tkyk-(tk-1)yk-1-1。

2〈xk+1-yk,yk+1-xk+1〉。

(5)

2〈xk+1-y*,yk+1-xk+1〉。

(6)

‖tk+1(yk+1-xk+1)‖2+2tk+1×

〈tk+1xk+1-(tk+1-1)yk-y*,yk+1-xk+1〉=

‖tk+1yk+1-(tk+1-1)yk-y*‖2-

‖tk+1xk+1-(tk+1-1)yk-y*‖2=

‖tk+1yk+1-(tk+1-1)yk-y*‖2-

‖tkyk-(tk-1)yk-1-y*‖2。

由uk的定义得

引理得证。

引理3[10]设{ak}和{bk}都是正实数序列,假设对于∀k≥1,a1+b1≤c,c>0,ak-ak+1≥bk+1-bk成立,则对∀k≥1,ak≤c也成立。

引理4[10]设{tk}是由多层邻近梯度算法产生的序列,且t1=1,则对∀k≥1,tk≥(k+1)/2成立。

基于上述4个引理,估计该算法的收敛速度。

定理1设{yk}是由多层邻近梯度算法产生的序列,则对∀k≥1,a1+b1≤c,c>0,有

Fε(y*)-Fε(y1)=Fε(y*)-Fε(PL(y1))≥

等价于

‖y1-y*‖2-‖x1-y*‖2。

即a1+b1≤c成立,由引理2得ak-ak+1≥bk+1-bk成立,由引理3得

从而可得

定理得证。

4 数值实验

为检验算法的有效性,考虑文献[8]的数值算例,采用Matlab编制程序,其测试环境为Window 10操作系统,Intel (R) Core (TM) i5-6500 CPU @ 3.20 GHz,8.00 GB RAM。

算例1给定1217个美国城市的经纬度,其数据可从文献[8]提供的网址找到。为更符合实际分布情况,将其经度乘以-1由正转负。现在需要找到一个点,使得该点到给定美国城市点的距离之和最小。选取初始点y0=(20,-100),限制算子R=[1/4 1/2],粗糙参数η=0.2,θ=0.8,M=30,利普希茨常数L=70,精度τ=10-5,得到近似最优解y*≈(38.63,-97.35)。美国各城市及其最优点的分布结果如图1所示。将多层邻近梯度算法(MPGA)与迭代收缩阈值算法(FISTA)算法进行比较,结果如表1所示。从表1可看出,在相同的初始值和最优解达到相同精度时,多层邻近梯度算法迭代次数和运行时间较少。

图1 美国城市及其最优点的分布结果图

算法迭代数运行时间/s近似最优解y*MPGA161.43(38.63,-97.35)FISTA222.21(38.63,-97.35)

算例2与算例1的设置相同,以上述1217个美国城市为中心点,半径r=1.5的1217个正方形,现在需要在直线x-y=180上找到一个点,使得该点到1217个正方形的距离之和最小。选取初始点y0=(0,180),其他参数的选取同算例1,最后得到近似最优解y*≈(56.84,-123.16),各广场及其最优点的分布结果如图2所示。将多层临近梯度算法(MPGA)与迭代收缩阈值算法(FISTA)进行比较,结果如表2所示。从表2可看出,在相同的初始值和最优解达到相同精度时,多层邻近梯度算法迭代次数较少,但运行时间略多于FISTA算法。

图2 美国广场及其最优点的分布结果图

算法迭代数运行时间/s近似最优解y*MPGA381.51(56.84,-123.16)FISTA401.36(56.84,-123.16)

算例3考虑以(-6,6,-4),(-5,-3,-6),(2,3,4),(4,-4,-5),(5,6,-6),(-5,-2,4)六个点为中心,半径r=1.5的6个正方体,现在需要找到一个点,使得该点到6个正方体的距离之和最小。选取初始点y0=(-6,6,2),限制算子R=[1/4 1/2 1/4],粗糙参数和精度的选取与算例1相同,利普希茨常数L=0.8,得到近似最优解y*≈(-1.040 5,0.840 2,-1.432 2),正方体及其最优点的分布结果如图3所示。将多层邻近梯度算法(MPGA)与迭代收缩阈值算法(FISTA)进行比较,结果如表3所示。从表3可看出,在相同的初始值和最优解达到相同精度时,多层邻近梯度算法迭代次数和运行时间较少。

图3 正方体及其最优点的分布结果图

算法迭代数运行时间/s近似最优解y*MPGA110.027 6(-1.040 5,0.840 2,-1.432 2)FISTA160.028 1(-1.040 5,0.802 4,-1.432 2)

5 结束语

针对点和集合的广义Fermat-Torricelli问题,提出一种多层邻近梯度算法,采用μ光滑方法将原始目标函数转化为光滑函数,再利用多层邻近梯度算法求解,并从理论上证明该算法具有O(1/k2)的收敛速度。数值实验表明,多层邻近梯度算法求解广义Fermat-Torricelli问题是有效的。

猜你喜欢
算例广义正方体
Rn中的广义逆Bonnesen型不等式
给正方体涂色
多少个小正方体
近场脉冲地震下自复位中心支撑钢框架结构抗震性能评估
数小正方体
从广义心肾不交论治慢性心力衰竭
拼正方体
降压节能调节下的主动配电网运行优化策略
王夫之《说文广义》考订《说文》析论
广义RAMS解读与启迪