基于BB步长的一类原始-对偶算法①

郑代秀

四川师范大学 数学科学学院， 成都 610066

对于带线性等式约束的凸优化问题

min{f(x)|Ax-c=0}

(1)

ALM算法本质上是一类原始-对偶算法，更新乘子λ的过程本质上是用梯度法求解对偶问题，其中参数ρ是梯度算法的下降步长.而在优化问题的梯度类算法中，Barzilai-Borwein算法(以下简记为BB算法[8])的表现比较好(具有拟牛顿性质).所以可以考虑用BB算法的步长去替代ALM中固定步长ρ， 得到一个新的凸优化问题的原始-对偶算法，我们将其简记为ALM-BB算法.该思想首先由文献[9]在研究大数值优化问题的乘子交替方向法[10-11]的改进型算法时提出，但没给出算法的收敛性证明.本文在目标函数f为强凸二次函数，约束函数中矩阵A行满秩的条件下证明了ALM-BB算法收敛性.

范数最优控制问题本质上是无穷维的二次凸优化问题，通过适当的离散格式可以获得其有限维框架的近似问题，且其近似问题为一类二次凸优化问题.由此可以利用本文的算法进行数值求解.通过求解范数最优控制问题的数值算例发现，ALM-BB算法收敛速度更快.

本文的结构如下： 在第1节中给出一些记号和预备知识； 在第2节中介绍ALM-BB算法并证明其收敛性； 在第3节中给出范数最优控制的离散格式，并利用实际算例说明ALM-BB算法的有效性； 在第4节中作总结.

1 预备知识

考虑如下二次凸优化问题：

s. t.Ax-c=0

(P)

其中S∈Rn×n，b∈Rn，c∈Rm，A∈Rm×n.在本文中，我们作出如下假设：

(A1)S∈Rn×n为对称正定矩阵；

(A2) rank(A)=m.

向量λ称为对偶变量或者原问题(P)的Lagrange乘子向量.

Lagrange对偶函数定义为

问题(P)的对偶问题定义为

(D)

引理1[2]对于凸优化问题(P)，若条件(A1)-(A2)成立，那么x*，λ*分别是原、对偶问题的全局最优解当且仅当

(2)

称满足(2)式的(x*，λ*)为KKT对. 由引理1知求解凸优化问题(P)的KKT对等价于求解原问题与对偶问题的最优解.

优化问题(P)的增广Lagrange函数为：

(3)

其中ρ>0是罚参数. 同样，可利用其增广Lagrange函数定义对偶函数：

引理2[12]若x*，λ*分别为增广Lagrange函数Lρ(x，λ)对应的原始、对偶问题的解，则(x*，λ*)为Lagrange函数L(x，λ)的KKT对.

下面我们回顾经典的增广Lagrange乘子算法.求解问题(P)的增广Lagrange乘子法(ALM)的迭代格式如下：

算法1: ALM1. 给定初始点x0与λ0, ρ>0, 终止误差ε, 令k=0; 2. 计算xk+1=arg minx∈RnLρ(x, λk); 3. 若‖Axk+1-c‖<ε, 停止; 否则转第4步; 4. 计算λk+1=λk-ρ(Axk+1-c); 5. 令k=k+1, 转第2步.

该算法中的步长ρ是固定的，而罚参数若选取不当，会显著增加求解时间.为改进算法，考虑用BB算法的步长αBB去替代固定的步长ρ.给定xk，xk-1，λk，λk-1， 定义

算法2: ALM-BB1. 给定初始点x0与λ0, ρ>0, 终止误差ε, 令k=0; 2. 计算xk+1=arg minx∈RnLρ(x, λk); 3. 若‖Axk+1-c‖<ε, 停止; 否则转第4步;4. 若k=0, 计算λ1=λ0-ρ(Ax1-c); 否则计算λk+1=λk-αkBB(Axk+1-c); 5. 令k=k+1, 转第2步.

2 ALM-BB算法的收敛性

在本节，我们证明算法2的收敛性.首先， 我们证明算法2中更新Lagrange乘子的过程等价于求增广Lagrange函数对应的对偶问题的BB算法.

定理1若条件(A1)-(A2)成立，则算法2中更新Lagrange乘子的过程等价于求增广Lagrange函数对应的对偶问题的BB算法.

证由条件(A1)，对任意给定的λ∈Rm，存在唯一的x∈Rn使得

dρ(λ)=Lρ(x，λ)

xLρ(x，λ)=Sx-b-ATλ+ρAT(Ax-c)=0

由此可得x的显式表达式：

x=R-1ATλ+R-1h

其中R=S+ρATA，h=ρATc+b. 因此对偶函数

(4)

其中C为与x，λ无关的常数项.

由(4)式，增广Lagrange函数对应的对偶问题可写为如下无约束凸二次优化问题(为简单起见，我们将常数项C省略，它对对偶问题最优解的求解不会产生影响)：

(5)

在假设条件(A1)-(A2)下，矩阵AR-1AT是对称正定矩阵，因此优化问题(5)的解存在唯一.

由文献[8]，求解无约束凸优化问题(5)的BB算法迭代格式为

(6)

在ALM-BB算法第2步中，利用凸优化问题的一阶最优性条件可得xk+1的精确解为

xk+1=R-1ATλk+R-1h

(7)

将(7)式代入ALM-BB算法第3步， 则有

对比算法2与对偶问题的BB算法，我们只需证明

其中xk+1为算法2中求得的子问题的最优解.

事实上，由凸优化问题的一阶最优性条件可知xk+1应满足

xLρ(xk+1，λk)=Sxk+1-b-ATλk+ρAT(Axk+1-c)=0

利用之前的记号可得

xx+1=R-1ATλk+R-1h

(8)

下面我们利用BB算法的收敛性结果证明算法2产生的迭代序列的收敛性.

定理2设条件(A1)-(A2)成立，则由算法2得到的迭代序列{(xk，λk)}收敛到原问题的KKT对(x*，λ*).特别地，x*为原问题的最优解.

证由条件(A1)-(A2)知x*为原问题的最优解等价于存在λ*使得(x*，λ*)为KKT对，即(x*，λ*) 满足

(9)

x*=R-1ATλ*+R-1h

(10)

结合(9)式和(10)式可得

Ax*=AR-1ATλ*+AR-1h=c

即(x*，λ*)满足条件λL(x*，λ*)=0.

进一步，

(11)

由(10)式和(11)式可得

xL(x*，λ*)=R(R-1ATλ*+R-1h)-ATλ*-h=0

故(x*，λ*)为原问题的KKT对.

此外，利用BB算法的R-线性收敛率， 知ALM-BB也具有R-线性收敛率.

3 范数最优控制问题及其离散格式

设T>0，Rn与Rm分别为n维与m维欧式空间，考虑如下线性控制系统：

(12)

其中：A∈Rn×n，B∈Rn×m；x(·)为系统的状态，u(·)为系统的控制，x0∈Rn是给定的初值，xT∈Rn为给定的终值. 称x(T)=xT为终端状态约束.定义性能指标：

由临时仰拱台阶法沿高铁盾构隧道方向地表沉降曲线图9可以看出，地表最大沉降位于地铁双区间隧道中心截面，越靠近中心施工引起变形叠加效应越明显，远离中心后叠加效应逐渐降低，在距地铁双区间中心截面20 m附近存在反弯点，随后地层变形主要受单线隧道施工影响。

(13)

(14)

下面，我们给出范数最优控制问题(14)的离散格式.对控制系统(12)中的线性微分方程，我们有x(T)的显示表达式：

记η=eATx0，M(t)=eA(T-t)B.则状态约束可表示为：

(15)

将(15)式中的积分表达式采用分段常量的逼近策略，取

M(t)=M(ti)，t∈[ti，ti-1)，i=0，1，…，N-1

其中0=t0

可得如下近似方程：

若记u=(uT(t0)，uT(t1)， …，uT(tN-1))T. 在适当的可积性条件下，可得：

其中

由此可得，范数最优控制问题(12)对应的离散优化问题为：

s.t.Mu+c=0

(16)

其中

我们对线性系统(12)作如下假设.

(A3)线性系统(12)完全能控，即秩条件rank(A，BA， …，Bn-1A)=n成立.

在条件(A3)下，最优控制问题(14)解存在唯一，并且其离散优化问题(16)中的矩阵S，M满足假设条件(A1)-(A2).

其中C为常数.

由引理3，求原范数最优控制问题(14)可转化为求凸优化问题(16). 进一步，在假设条件(A3)下，我们可用ALM-BB算法求解问题(16). 下面我们给出一个具体的算例，并用它对原始的ALM与ALM-BB算法进行比较.

例6设T=3，n=2，m=1，考虑如下控制系统：

及性能指标

图1 最优状态图

为了说明ALM-BB算法的有效性， 我们选择不同的罚参数和划分细度进行计算， 将ALM-BB和ALM算法的计算时间和迭代次数对比见表1.

表1 ALM-BB与ALM数值实验结果对比

由表1可以看出， 在划分细度与罚参数相同的情况下， ALB-BB算法迭代步数更少， 收敛速度更快. 但是当罚参数选取过大时， ALM与ALM-BB算法运行时间差别不大， 对罚参数的选取依然敏感.

4 总结

本文通过改变ALM算法中更新乘子这一迭代步的步长来提高算法的收敛速度. 范数最优控制问题本质上是无穷维的二次凸优化问题， 通过适当的离散格式可以将其转为有限维的二次凸优化问题. 通过求解范数最优控制问题的数值算例发现， ALM-BB算法较ALM计算效率更高. 从数值实验看出ALM-BB算法的数值表现仍依赖于参数的选取. 此外， 本文的收敛性证明依赖于凸二次规划问题的具体结构以及子问题可精确求解， 对于更一般的非精确的ALM-BB算法的收敛性有待进一步研究.