非线性半定规划的一个可行SSDP算法

A Feasible SSDP Algorithm for Nonlinear Semidefinite Programming

摘要: 本文提出了一个求解非线性半定规划的可行序列半定规划(SSDP)算法。该算法的初始点和迭代点均是可行点，在每次迭代中通过求解两个二次半定规划子问题确定搜索方向，步长由满足目标函数下降性和约束函数可行性的线搜索产生，在某些假设条件下本文证明了算法的全局收敛性。

Abstract: This paper proposes a feasible SSDP algorithm for solving nonlinear semidefinite programming. The initial point and iteration points are feasible. The search direction is determined by solving two quadratic semidefinite programming subproblems. The step size is obtained by calculating the line search that satisfies the descent property of the objective function and the feasibility of the constraint function. The global convergence of the algorithm is proved under mild conditions.

1. 引言

本文研究如下仅带半负定矩阵约束的非线性半定规划问题(NLSDP)：

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{.}G\left(x\right)\preccurlyeq 0,\end{array}$ (1.1)

其中，函数 $f\mathrm{<mo>\; :\; </mo>}{ℝ}^n\to ℝ$ 和 $G\mathrm{<mo>\; :\; </mo>}{ℝ}^n\to {\mathbb{S}}^m$ 是光滑的函数， ${\mathbb{S}}^m$ 表示m阶实对称矩阵空间， $\preccurlyeq$ 表示半负定偏序，即 $A\preccurlyeq B$ 表示 $A-B$ 是半负定矩阵。

非线性半定规划问题在最优控制、结构设计、经济金融等领域有广泛应用 [1] [2] [3]。非线性半定规划带有半定矩阵约束，结构复杂，不能直接用传统的非线性规划的算法求解，目前求解非线性半定规划问题的主要方法有增广Lagrange法 [4]，原始–对偶内点法 [5] [6]，序列半定规划法 [7] [8] [9]，QP-free法 [10]，交替方向乘子法 [11] 等。

本文基于文 [12] 的求解非线性规划的可行SQP算法的思想，建立了非线性半定规划的一个可行SSDP算法。算法产生的迭代点均满足可行性；在每次迭代中算法的搜索方向是通过求解两个二次半定规划子问题产生；目标函数直接作为效益函数用于线搜索，线搜索保证目标函数下降和满足可行性。在适当的假设条件下算法具有全局收敛性。

2. 算法

定义2.1：对于可微矩阵函数 $G\left(x\right)\mathrm{<mo>\; :\; </mo>}{ℝ}^n\to {\mathbb{S}}^m$， $G\left(x\right)$ 在 $x\in {ℝ}^n$ 处的微分算子 $DG\left(x\right)$ 定义如下：

$DG\left(x\right)\mathrm{<mo>\; :\; </mo>}={\left(\frac{\partial G\left(x\right)}{\partial x_1}\mathrm{,}\frac{\partial G\left(x\right)}{\partial x_2}\mathrm{,}\cdots \mathrm{,}\frac{\partial G\left(x\right)}{\partial x_n}\right)}^{\text{T}},$

$G\left(x\right)$ 在x处沿着 $d={\left(d_1,d_2,\cdots ,d_n\right)}^n\in {ℝ}^n$ 的方向导数 $DG\left(x\right)d$ 为

$DG\left(x\right)d={\displaystyle \underset{i=1}{\overset{n}{\sum }}}{d}_i\frac{\partial G\left(x\right)}{\partial x_i},$

相对应的伴随算子 $DG{\left(x\right)}^{\mathrm{<mo>\; *\; </mo>}}$ 定义为

$DG{\left(x\right)}^{\mathrm{<mo>\; *\; </mo>}}Y\mathrm{<mo>\; =\; </mo>}{\left(\langle \frac{\partial G\left(x\right)}{\partial x_1}\mathrm{,}Y\rangle \mathrm{,}\langle \frac{\partial G\left(x\right)}{\partial x_2}\mathrm{,}Y\rangle \mathrm{,}\cdots \mathrm{,}\langle \frac{\partial G\left(x\right)}{\partial x_n}\mathrm{,}Y\rangle \right)}^{\text{T}}\mathrm{,}\forall Y\in {\mathbb{S}}^m,$

其中 $\langle ·,·\rangle$ 表示矩阵的内积，定义如下：

$\langle A\mathrm{,}B\rangle =\text{Tr}\left(B^{\text{T}}A\right)={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{a}_{ij}{b}_{ij},}}\forall A=\left[a_{ij}\right],B=\left[b_{ij}\right]\in {ℝ}^{m\times n}.$

定义2.2：设 $x\in {ℝ}^n$ 是NLSDP(1.1)的一个可行点，若存在矩阵 $M\in {\mathbb{S}}^m$ 使得以下条件成立：

$\nabla f\left(x\right)+DG{\left(x\right)}^{\ast }M=0,$

$G\left(x\right)\preccurlyeq 0,M\succcurlyeq 0,\text{Tr}\left(MG\left(x\right)\right)=0,$

则称x是NLSDP(1.1)的一个KKT点，M是相应的拉格朗日乘子，上式称为NLSDP(1.1)的KKT条件。

定义2.3：NLSDP(1.1)的约束违反度函数定义如下：

$P\left(x\right)={\lambda }_1{\left(G\left(x\right)\right)}_{+}=\max \left\{0,{\lambda }_1\left(G\left(x\right)\right)\right\},$

其中， ${\lambda }_1\left(A\right)$ 表示矩阵A的最大特征值。

显然， $P\left(x\right)=0$ 当且仅当x为NLSDP(1.1)的一个可行点。

令 $x^k$ 为当前迭代点，构造如下的二次半定规划子问题(简记为QSDP)：

$\begin{array}{cc}\min & \nabla f{\left(x^k\right)}^{\text{T}}d+\frac{1}{2}{d}^{\text{T}}{H}_{k}d\\ \text{s}\text{.t}\text{.}& G\left(x^k\right)+DG\left(x^k\right)d\preccurlyeq 0,\end{array}$ (2.1)

其中 $H_k$ 为NLSDP(1.1)的Lagrange函数的Hesse阵或近似阵。

子问题QSDP(2.1)的解 $d_0^k$ 为目标函数的下降方向，但不一定是可行方向，因此需对其进行修正，以便得到一个可行下降方向 $d^k$。

利用 $d_0^k$ 对子问题QSDP(2.1)的约束不等式的右边进行扰动，得到如下的二次半定规划子问题：

$\begin{array}{l}\min \nabla f{\left(x^k\right)}^{\text{T}}d+\frac{1}{2}{d}^{\text{T}}{H}_{k}d\\ \text{s}\text{.t}\text{.}G\left(x^k\right)+DG\left(x^k\right)d\preccurlyeq -{\Vert d_0^k\Vert }^v{E}_m,\end{array}$ (2.2)

其中 $E_m$ 为一个m阶的单位矩阵。

记NLSDP(1.1)的可行集为 $\Omega =\left\{x\in {ℝ}^n|G\left(x\right)\preccurlyeq 0\right\}$。本文需作以下基本假设：

假设1：集合 $\Omega$ 是非空的。

假设2：函数 $f\left(x\right)$， $G\left(x\right)$ 是连续可微的。

假设3：存在正的常数a和b，使得

$a{\Vert d\Vert }^2\le d^{\text{T}}{H}_{k}d\le b{\Vert d\Vert }^2,\forall d\in R^n.$

求解NLSDP(1.1)的可行SSDP算法描述如下：

算法A：

步骤0：(初始化)选取参数 $\alpha \in \left(0,\frac{1}{2}\right)$， $\beta \in \left(0,1\right)$， $v>2$。初始点 $x^0\in \Omega$， $H_0\in {ℝ}^{n\times n}$ 正定，令 $k=0$。

步骤1：(计算搜索方向)

步骤1.1：求解子问题QSDP(2.1)得 $d_0^k$。如果 $\Vert d_0^k\Vert =0$，则停止；否则，进入步骤1.2。

步骤1.2：求解子问题QSDP(2.2)得 $d^k$，令 ${\theta }_k=\nabla f{\left(x^k\right)}^{\text{T}}{d}^k$。

步骤2：(线搜索)计算序列 $\left\{\mathrm{1,}\beta \mathrm{,}{\beta }^2\mathrm{,}\cdots \right\}$ 中第一个满足如下两个条件的步长 $t_k$ ：

$f\left(x^k+t{d}^k\right)\le f\left(x^k\right)+\alpha t{\theta }_k,$ (2.3)

$G\left(x^k+t{d}^k\right)\preccurlyeq 0.$ (2.4)

步骤3：(更新)令 $x^{k+1}=x^k+t_k{d}^k$，用某种技术产生新的对称正定阵 $H_{k+1}$，令 $k=k+1$，返回步骤1。

为分析的简便，现作如下进一步假设：

假设4：子问题QSDP(2.2)有解 $d^k$，且 $d^k$ 满足如下条件：

$\Vert d^k\Vert \le L,\nabla f{\left(x^k\right)}^{\text{T}}{d}^k\le \min \left\{-{\Vert d_0^k\Vert }^{\sigma },-{\Vert d^k\Vert }^{\sigma }\right\}.$

其中 $L>0$， $\sigma >2$。

假设5：算法A生成的迭代点列 $\left\{x^k\right\}$ 有界。

基于假设条件1~3，易知下面引理成立。

引理2.1：假设1~3成立，则子问题QSDP(2.1)有唯一解 $d_0^k$，并且存在矩阵 $M_k\in {\mathbb{S}}^m$ 满足QSDP(2.1)的KKT条件，即

$\nabla f\left(x\right)+DG{\left(x^k\right)}^{\ast }{M}_k+H_k{d}_0^k=0,$ (2.5a)

$G\left(x^k\right)+DG\left(x^k\right)d_0^k\preccurlyeq 0,$ (2.5b)

$M_k\succcurlyeq 0,$ (2.5c)

$\text{Tr}\left(M_k\left(G\left(x^k\right)+DG\left(x^k\right)d_0^k\right)\right)=0.$ (2.5d)

引理2.2：假设1~3成立，如果 $d_0^k=0$，则当前迭代点 $x^k$ 为NLSDP(1.1)的一个KKT点。

证明：将 $d_0^k=0$ 代入(2.5)，结合定义2.2即知当前迭代点 $x^k$ 为NLSDP(1.1)的一个KKT点。

引理2.3：假设1~4成立，算法A的线搜索在有限次计算中生成步长 $t_k$，即算法A是适定的。

证明：由Taylor展开式知

$f\left(x^k+t{d}^k\right)=f\left(x^k\right)+t\nabla f{\left(x^k\right)}^{\text{T}}{d}^k+o\left(t\right),$

$G\left(x^k+t{d}^k\right)=G\left(x^k\right)+tDG\left(x^k\right)d^k+o\left(t\right),$

由假设4知 ${\theta }_k=\nabla f{\left(x^k\right)}^{\text{T}}{d}^k<0$。因为 $\alpha \in \left(0,\frac{1}{2}\right)$，所以存在 ${\bar{t}}_k>0$，使得对任意 $t\in \left(0,{\bar{t}}_k\right)$，有

$f\left(x^k+t{d}^k\right)\le f\left(x^k\right)+\alpha t{\theta }_k,$

因为 $G\left(x\right)$ 是连续可微函数，由子问题QSDP(2.2)的约束条件知

$G\left(x^k\right)+DG\left(x^k\right)d^k\preccurlyeq -{\Vert d_0^k\Vert }^v{E}_m\prec 0,$

从而有

${\lambda }_1\left(G\left(x^k\right)+DG\left(x^k\right)d^k\right)<0,$ (2.6)

而由 ${\lambda }_1(\cdot )$ 的凸性可得

${\lambda }_1\left(G\left(x^k+t{d}^k\right)\right)\le \left(1-t\right){\lambda }_1\left(G\left(x^k\right)\right)+t{\lambda }_1\left(G\left(x^k\right)+DG\left(x^k\right)d^k\right)+o\left(t\right),$

所以由 $G\left(x^k\right)\preccurlyeq 0$，并结合(2.6)知存在 ${\tilde{t}}_k>0$，使得对任意 $t\in \left(0,{\tilde{t}}_k\right)$，有

${\lambda }_1\left(G\left(x^k+t{d}^k\right)\right)\le 0,$

从而

$G\left(x^k+t{d}^k\right)\preccurlyeq 0,$

综上所述知存在充分小的 $t>0$，使得不等式(2.3)和(2.4)成立，故算法A适定。

3. 全局收敛性

若算法A产生有限的迭代点列，则由引理2.2知当前迭代点 $x^k$ 为问题NLSDP(1.1)的KKT点，因此，我们不妨假设算法A产生无限的迭代点列 $\left\{x^k\right\}$，本节将证明在适当的假设条件下算法A是全局收敛的。

引理3.1：假设1~5成立， $x^{*}$ 是 $\left\{x^k\right\}$ 的一个聚点，即存在子列 $K\subseteq \left\{1,2,\cdots \right\}$，使得 $x^k\stackrel{K}{\to }{x}^{*}$，则 $d_0^k\stackrel{K}{\to }0$。

证明：(反证法)假设结论不成立，则存在子列 $\bar{K}\subseteq K$ 和常数 $\underset{\_}{d}>0$，使得当 $k\in \bar{K}$ 充分大时， $\Vert d_0^k\Vert \ge \underset{\_}{d}$。

下面首先证明存在正数 $\underset{\_}{t}>0$，使得

$t_k\ge \underset{\_}{t},\forall k\in \bar{K},$

由假设4及子问题QSDP(2.2)的约束条件知对充分大的 $k\in \bar{K}$，有

${\theta }_k=\nabla f{\left(x^k\right)}^{\text{T}}{d}^k\le -{\Vert d_0^k\Vert }^{\sigma }\le -{\underset{\_}{d}}^{\sigma },$ (3.1)

$G\left(x^k\right)+DG\left(x^k\right)d^k\preccurlyeq -{\Vert d_0^k\Vert }^v{E}_m\preccurlyeq -{\underset{\_}{d}}^v{E}_m.$ (3.2)

由假设4知 $\Vert d^k\Vert \le L$，即 $\left\{d^k\right\}$ 有界，于是由Taylor展开式有

$f\left(x^k+t{d}^k\right)=f\left(x^k\right)+t\nabla f{\left(x^k\right)}^{\text{T}}{d}^k+o\left(t\right),$

对充分大的，结合(3.1)知

所以对充分大的及充分小的，(2.3)成立。

同理，由Taylor展开式有

对充分大的，结合(3.2)知

所以对充分大的及充分小的，(2.4)成立。

综上所述，存在正数，使得，。

下面基于上述结论导出矛盾。对充分大的，由(2.3)知

(3.3)

因为单调下降，且，所以。在(3.3)式中令，得出矛盾，于是引理成立。

基于引理3.1以及子问题QSDP(2.1)的KKT条件(2.5)，可得算法A的全局收敛性，即：

定理3.1：假设1~5成立，是算法A产生的一个迭代点列，则的每一个聚点都是NLSDP(1.1)的一个KKT点。

4. 结束语

本文将非线性规划可行SQP算法进行了推广，提出了一个求解非线性半定规划的可行SSDP算法。该算法的搜索方向是通过求解两个二次半定规划子问题产生，目标函数直接作为效益函数，线搜索保证目标函数下降和满足可行性。在适当的假设条件下，证明了算法的适定性和全局收敛性。该算法可以应用于对可行性有严格要求的实际问题。

基金项目

获国家自然科学基金(No. 11561005)，广西自然科学基金(No. 2016GXNSFAA380248)资助。