A Backtracking Line Search Method for Nonlinear Semidefinite Programming

二阶连续可微函数f(x)的梯度和Hesse矩阵分别记为▽f(x)和▽² f(x). 二阶连续可微向量函数h(x)：=(h₁(x)，h₂(x)，…，h_p(x))^T，则称矩阵Dh(x)=(▽h₁(x)，▽h₂(x)，…，▽h_p(x))^T∈ $\mathbb{R}$^p×n为h(x) 的雅可比矩阵. 二阶连续可微矩阵函数G(x)，记其微分算子DG(x)为

且对任意的d∈ $\mathbb{R}$ⁿ

记其伴随算子DG(x)^*为

其中Z∈ $\mathbb{S}$^m.

记NLSDP(1)的拉格朗日函数为

其中x ∈ $\mathbb{R}$ⁿ，λ ∈ $\mathbb{R}$^p，Y ∈ $\mathbb{S}$^m.

定义1  若x^*∈ $\mathbb{R}$ⁿ是NLSDP(1)的可行点，且存在向量λ^*∈ $\mathbb{R}$^p和矩阵Y_*∈ $\mathbb{S}$^m满足如下条件：

则称(x^*，λ^*，Y_*)是NLSDP(1)的一个KKT点对，(λ^*，Y_*)是在x^*处相对应的拉格朗日乘子.

定义2  若x^*∈ $\mathbb{R}$ⁿ是NLSDP(1)的可行点，{▽h_i(x^*)}_i=1^p线性无关，且存在向量d∈ $\mathbb{R}$ⁿ使得Dh(x^*)d= 0，G(x^*)+DG(x^*)d$ \prec $ 0，则称NLSDP(1)在x^*处满足MFCQ约束规格.

本文采用线搜索型序列半定规划方法框架，设当前迭代点为x^k∈ $\mathbb{R}$ⁿ，定义产生搜索方向的二次半定子问题QSD(x^k，B_k) 如下：

其中矩阵B_k∈ $\mathbb{R}$^n×n是NLSDP(1)的拉格朗日函数的Hesse阵或其近似阵. 若QSD(x^k，B_k)存在最优解，则记其解为d^k. 同时，为了度量NLSDP(1)的约束可行性，下面给出其约束违反度函数的定义：

其中λ₁(A)表示矩阵A的最大特征值，(α)₊=max{0，α}，(λ₁(G(x)))₊简记为λ₁(G(x))₊. 显然，若θ(x)=0，则x为NLSDP(1) 的可行解.

此外，回溯线搜索技术保证目标函数值或约束违反度函数值有所下降，故令试探点为$\mathit{\boldsymbol{\hat x}}$=x^k+α_k，ld^k，其中α_k，l∈(0，1]为给定的步长. 下面讨论试探点$\mathit{\boldsymbol{\hat x}}$基于何种情况下被算法接受. 首先，下面给出目标函数f(x)的非单调实际下降量和预估下降量. 记目标函数f(x)的非单调实际下降量为

其中$\hat f$(x^k+1)更新方式为$\hat f$(x⁰)=f(x⁰)，$\hat f$(x^k+1)= $\frac{1}{2}$ (f(x^k+1)+ $\hat f$(x^k)). 记目标函数f(x)的预估下降量为

因此，定义目标函数f(x)的非单调充分下降性条件：

其中η∈(0，1)，这不同于单调充分下降性条件：

而(5)式更容易接受试探点$\mathit{\boldsymbol{\hat x}}$.

其次，在算法迭代过程中，为了防止约束违反度函数值反弹过大，故需给出其一个上界，记为Θ_k^max，其更新方式如下：

其中$\hat \theta $(x^k+1)的更新方式为$\hat \theta $(x⁰)=θ(x⁰)，$\hat \theta $(x^k+1)= 1 2 (θ(x^k+1)+ $\hat \theta $(x^k)). 同时，下面给出约束违反度函数θ(x)的非单调充分下降性条件：

其中β∈(0，1).

最后，下面给出算法的接受准则. 如果约束违反度函数θ(x)满足非单调充分下降性条件，即(7)式成立，或目标函数f(x)具有适当的下降量且约束违反度函数值有个合理的上界，即

成立，其中γ∈(0，1). 那么考虑以下两种情况.

1) 若

且

成立，其中τ∈(2，3)，ξ∈(0，$\frac{1}{2}$]，则算法接受试探点$\mathit{\boldsymbol{\hat x}}$. 令α_k=α_k，l，x^k+1= $\mathit{\boldsymbol{\hat x}}$，并且采用(6)式更新Θ_k+1^max.

2) 若

且试探点$\mathit{\boldsymbol{\hat x}}$满足目标函数f(x)的非单调充分下降性条件，即(5)式成立，则算法接受试探点$\mathit{\boldsymbol{\hat x}}$，令α_k=α_k，l，x^k+1=$\mathit{\boldsymbol{\hat x}}$且Θ_k+1^max=Θ_k^max.

然而，在回溯线搜索中，如果步长α_k，l不满足上述条件，那么为了保证算法的适定性，故需要给其设置一个下界α_k^min，更新方式如下：

其中γ_α∈(0，1)，s_θ≥1.

当子问题QSD(x^k，B_k)不相容或步长α_k，l < α_k^min时，算法需进入可行性恢复阶段，寻找一个试探点$\mathit{\boldsymbol{\hat x}}$满足如下条件：

(A1) 子问题QSD($\mathit{\boldsymbol{\hat x}}$，B_k)是相容的;

(A2) θ($\mathit{\boldsymbol{\hat x}}$)≤ $\hat \theta $(x^k).

可行性恢复阶段的具体细节见文献[10].

综上所述，在(7)式或(8)式成立的条件下，若(9)式和(10)式成立，则称第k次迭代为θ型迭代. 若(5)式和(11)式成立，则称第k次迭代为f型迭代. 另外，如果可行性恢复阶段产生的试探点$\mathit{\boldsymbol{\hat x}}$满足(A1)和(A2)，那么称第k次迭代为θ型迭代.

基于以上讨论，下面给出求解NLSDP(1)的算法描述：

算法1

步骤0  (初始步)给定初始点x⁰∈ $\mathbb{R}$ⁿ，B₀= I_n(单位阵)，参数ρ，η，β，γ，γ_α∈(0，1)，τ∈(2，3]，ξ∈ (0，$\frac{1}{2}$]，s_θ≥1，及充分大的Θ₀^max，令k=0.

步骤1  令flag=0，求解子问题QSD(x^k，B_k). 若QSD(x^k，B_k)存在最优解，则记为d^k，否则算法进入可行性恢复阶段，转步骤7. 若d^k=0，则算法停止.

步骤2  通过(12)式计算步长下界α_k^min.

步骤3  (回溯线搜索)

步骤3.1  令l=0，α_k，0=1.

步骤3.2  若α_k，l < α_k^min，则转步骤7，否则令试探点为$\mathit{\boldsymbol{\hat x}}$=x^k+α_k，ld^k.

步骤3.3  若(7)式和(8)式不成立，则转步骤3.5.

步骤3.4  若(9)式和(10)式成立，则令flag=1，转步骤4. 若(5)式和(11)式成立，则转步骤4.

步骤3.5  令α_k，l+1=ρα_k，l，l=l+1，转步骤3.2.

步骤4  令α_k=α_k，l，x^k+1=x^k+α_kd^k.

步骤5  使用如下式子更新Θ_k+1^max，$\hat f$(x^k+1)，$\hat \theta $(x^k+1).

步骤6  (更新步)利用某种方法，更新B_k为对称正定矩阵B_k+1. 令k=k+1，转步骤1.

步骤7  (可行性恢复阶段)可行性恢复阶段产生的试探点$\mathit{\boldsymbol{\hat x}}$满足(A1)和(A2)，那么令x^k+1=$\mathit{\boldsymbol{\hat x}}$，flag=1，转步骤5.

本节将分析算法1的全局收敛性，为此，需作如下合理假设：

(B1) 迭代点列{x^k}和{x^k+α_k，ld^k}在紧凸集χ中.

(B2) f(x)，h(x)，G(x)在紧凸集χ中二阶连续可微.

(B3) 矩阵B_k为对称正定矩阵，且存在常数a，b>0，对任意的d∈ $\mathbb{R}$ⁿ有a‖d‖²≤d^TB_k d≤b‖d‖².

注1  不失一般性，由假设B可知，对于任意x∈χ，‖▽² f(x)‖≤b，‖D²h(x)‖≤b，‖D²G(x)‖≤b.

引理1  对于任意的k，以下不等式成立：

证  采用数学归纳法，当第0次迭代时，由算法机制可知，Θ₀^max充分大，故θ(x⁰)≤Θ₀^max成立. 假设第k次迭代时，θ(x^k)≤Θ_k^max成立，现证明θ(x^k+1)≤Θ_k+1^max成立.

若第k+1次迭代为f型迭代，则Θ_k+1^max=Θ_k^max. 由(8)式可得θ(x^k+1)≤Θ_k^max=Θ_k+1^max.

若第k+1次迭代为θ型迭代，则由(10)式和(6)式得θ(x^k+1)≤βΘ_k^max≤Θ_k+1^max.

综上所述，对于任意的k，θ(x^k)≤Θ_k^max成立，同理可证$\hat \theta $(x^k)≤Θ_k^max成立.

引理2  算法产生的序列{Θ_k^max}是单调非增的.

证  假设第k次迭代到第k+1次迭代为θ型迭代. 若βΘ_k^max>$\hat \theta $(x^k+1)，则由(6)式可得Θ_k+1^max=βΘ_k^max < Θ_k^max. 若βΘ_k^max≤$\hat \theta $(x^k+1)，则由(6)，(10)式及引理1可得

最后一个不等式成立的原因在于$\frac{1}{2}$(β+1)∈($\frac{1}{2}$，1).

假设第k次迭代到第k+1次迭代为f型迭代：Θ_k+1^max=Θ_k^max.

综上所述，序列{Θ_k^max}单调非增.

引理3  考虑算法产生的迭代点列{x^k}，若序列{θ(x^k)}>0和序列{f(x^k)}有下界，则$\mathop {\lim }\limits_{k \to \infty } \theta $(x^k)=0.

证  1) 假定θ型迭代发生有限次，故存在常数k₁>0，使得当k>k₁时，f型迭代发生. 对于充分大的k(>k₁)，若θ(x^k+1)≤β$\hat \theta $(x^k)，则结论成立. 否则存在无穷指标集$\mathscr{K}$₁，使得当k∈ $\mathscr{K}$₁且k>k₁时，nared(x^k)≥γθ(x^k+1)成立. 采用反证法. 不失一般性，假设当k∈ $\mathscr{K}$₁且k>k₁时，存在正常数ε使得θ(x^k+1)≥ε. 因此，有max{f(x^k)，$\hat f$(x^k)}-f(x^k+1)≥γε.

若f(x^k)≥$\hat f$(x^k)，则f(x^k)-f(x^k+1)≥γε，结合$\hat f$(x^k+1)的定义可导出

于是有

因此，当k充分大时

这与序列{f(x^k)}有下界矛盾. 若f(x^k) < $\hat f$(x^k)，同理可证出矛盾.

2) 假定θ型迭代发生无限次，那么存在指标k₂，使得当k>k₂时，θ型迭代发生，由(10)式和引理2，可知结论成立.

引理4  在假设B条件下，子问题QSD(x^k，B_k)的可行解d满足以下不等式：

其中α_k，l∈[α_k^min，1].

证  由(3)式、(4)式、Taylor展开式和假设B可得

其中ξ₁介于x^k和x^k+α_k，l d之间. 类似地，由Taylor展开式可推出

其中ξ₂，ξ₃介于x^k与x^k+α_k，ld之间，进而有θ(x^k+α_k，ld)≤(1-α_k，l)θ(x^k)+α_k，l²b‖d‖².

引理5  在假设B成立下，NLSDP(1)的可行点x^*满足MFCQ条件，但不是KKT点. 那么存在x^*的邻域$\mathcal{N} $(x^*)及正常数η₁，使得当x^k∈ $ \mathcal{N} $(x^*)∩χ时，子问题QSD(x^k，B_k)的可行集非空，且其最优解d^k满足

证  类似文献[14]的引理4.7可证结论成立.

引理6  在假设B条件下，d^k是子问题QSD(x^k，B_k)的最优解，那么若

且

则α_k，l≥α_k^min，nared(x^k)≤η α_k，lpred(x^k)，nared(x^k)≥γθ(x^k+α_k，ld^k).

证  若

则由引理4和引理5得

故nared(x^k)≥η α_k，lpred(x^k)成立. 结合引理4和引理5，由(16)和(17)式有

故nared(x^k)≥γθ(x^k+α_k，l d^k)成立.

引理7  在假设B条件下，线搜索(步骤3)是有限步终止的.

证  采用反证法，假设线搜索(步骤3)是不会有限步终止的，故由算法机制可知，当l→∞时，α_k，l→0，下面考虑两种情形.

假定θ(x^k)=0，由(12)式推出α_k^min=0. 由引理4可知，pred(x^k，α_k，l)≥ξ(d^k)^T B_k d^k. 由引理6可知，若(17)式成立，则nared(x^k)≥η α_k，lpred(x^k)，nared(x^k)≥γθ(x^k+α_k，ld^k)成立. 若α_k，l² < $\frac{{\mathit{\Theta }_k^{\max }}}{{b{{\left\| {{\mathit{\boldsymbol{d}}^k}} \right\|}^2}}}$，则由(14)式可推出θ(x^k+α_k，ld^k)≤Θ_k^max.

综上所述，若

则x^k+α_k，ld^k被算法所接受，f型迭代发生，矛盾.

假定θ(x^k)>0. 由步骤3.2知，当l充分大时，α_k，l < α_k^min，从而退出线搜索，进入可行性恢复阶段，矛盾.

定理1  若假设B成立，则下面结论之一成立：

(C1) 可行性恢复阶段找不到试探点$\mathit{\boldsymbol{\hat x}}$，满足(A1)和(A2).

(C2) 算法有限步终止，即存在某个迭代点x^k为NLSDP(1)的KKT点.

(C3) 算法产生的迭代点列{x^k}收敛于聚点x^*且该聚点x^*为NLSDP(1)的可行解，那么x^*或是NLSDP(1)的KKT点，或是x^*不满足MFCQ条件.

证  不失一般性，假设结论(C1)和(C2)都不成立，下面讨论两种情况分别证明结论(C3)成立.

1) 假定序列{x^k}包含无限次θ型迭代，那么存在无穷指标集$\mathscr{K}$₂，使得当k∈ $\mathscr{K}$ ₂时，第k次迭代是θ型迭代. 由假设B可知，{x^k}是有界点列，因此存在一个聚点x^*，不妨假设$\mathop {\lim }\limits_{k \to \infty , k \in \mathscr{K}2} $x^k=x^*. 由引理3可知，

即x^*是NLSDP(1)的可行点.

假设x^*满足MFCQ条件，否则结论(C3)成立，采用反证法，如果x^*不是KKT点，若(18)式成立，则由引理4、引理5和引理6可知，f型迭代条件被满足. 当k充分大时，由于θ(x^k)≤Θ_k^max，α_k^min=O(θ(x^k)^τ)及平方根的作用，(18)式的左端的收敛速度快于右端，因此，在回溯线搜索中，步长α_k，l必存在且至少使得(18)式第二个不等号成立，这意味着f型迭代发生，故与当前点是θ型迭代矛盾.

2) 假定序列{x^k}中只包含有限次θ型迭代，那么存在正整数k₃，使得当k>k₃时，第k次迭代是f型迭代，于是有Θ_k^max不会更新，故为固定常数. 由引理3可知，$\mathop {\lim }\limits_{k > {k_3}} \theta $(x^k)=0=θ(x^*)，这说明x^*是NLSDP(1)的可行点.

假设x^*满足MFCQ条件，否则结论(C3)成立，采用反证法，如果x^*不是KKT点，类似于(1)式的讨论，若(18)式成立，f型迭代条件被满足. 此外，当k充分大时，因α_k^min=O(θ(x^k)^τ) 0，(18)式的右端大于左端，于是在回溯线搜索中，步长α_k，l将会落于(18)式内或其右端，f型迭代发生. 因此，存在α∈(0，1]，使得α_k>ρα成立. 由引理5得α_kpred(x^k)≥ $\frac{1}{2}$α_kη₂‖d^k‖≥ $\frac{1}{2}$ρα_kη₂‖d^k‖²>0，最后不等式成立的原因在于x^*不是KKT点，故‖d^k‖≠0. 由(5)式知

因此，当k充分大时，可推出f(x^k)→-∞，由假设B可知，这与{f(x^k)}有界矛盾. 综上所述，结论(C3)成立.

为了验证算法1的可行性，本节给出了算法的初步数值实验，采用MATLAB(2014a)软件实现算法，程序在配置Windows 10，8G RAM，3.60 GHz CPU的计算机上运行. 子问题QSD(x^k，B_k)使用文献[15] SDPT3求解. 算法采用BFGS公式对B_k更新为B_k+1，其更新公式见文献[16]. 下面给出算例问题如下：

1) Rosen-Suzuki问题：测试算例来源于文献[17]：

其数值结果见表 1.

2) SOFP问题. 测试算例来源于文献[18]：

其中：Q_F= C^TF^TFC + I; A_F=A+ BFC; 矩阵变量L为实对称的; 矩阵变量F不是方阵; A，B，C为常量矩阵. 该问题的数值结果见表 2.

3) NCMP问题. 测试算例来自于文献[9]：

其中：A=(a_ij)(∈ $\mathbb{S}$^m)是给定的，且其对角线元素a_ii=1(i=1，2，…，m)，其余元素随机取自[-1, 1]; 选取ε=10^-3. 数值结果见表 3.

在数值试验中，选取的参数如下：

终止准则为‖d^k‖≤10^-4，设置算法1的迭代次数上限为200. 下面给出表 1-3中的符号含义如下：x₀为初始点; Ndf为目标函数梯度计算次数; problem为COMPleib算例库算例名称; Iter为算法迭代次数; n为自变量维数; ri为可行性恢复阶段使用次数; p为等式约束的维数; θ^*为最优点约束违反度函数值; m为半定约束矩阵维数; f^*为最优目标函数值; Nf为目标函数计算次数; t为计算机运行时间(含可行性恢复阶段用时).

本文提出一种新的求解非线性半定规划的无罚无滤回溯线搜索型序列半定规划算法，新方法基于传统的二次规划子问题构建二次半定子问题，通过求解该子问题产生搜索方向，为了避免使用罚函数和滤子，采用回溯线搜索技术来保证目标函数值或约束违反度函数值充分下降. 而非单调的充分性下降条件使得试探点更加容易被算法接受. 同时在合理的假设条件下，证明了该算法的适定性以及全局收敛性，最后初步的数值试验结果表明了该算法的有效性.