# 非线性半定规划的一个线搜索精确罚方法A Line Search Exact Penalty Method for Nonlinear Semidefinite Programming

DOI: 10.12677/AAM.2019.84071, PDF, HTML, XML, 下载: 493  浏览: 839  国家自然科学基金支持

Abstract: This paper presents a line search exact penalty method for nonlinear semidefinite programming. At each iteration, the search direction is determined by solving a quadratic semidefinite programming subproblem. Certain exact penalty function is used as merit function for line search and a step size is obtained. The penalty parameter is updated by the optimal solution of the trust region subproblem. Under some appropriate conditions, the global convergence of the proposed algorithm is proved.

1. 引言

$\begin{array}{ll}\mathrm{min}\hfill & f\left(x\right)\hfill \\ \text{s}\text{.t}\text{.}\hfill & h\left(x\right)=0,\hfill \\ \hfill & G\left(x\right)\preccurlyeq 0,\hfill \end{array}$ (0.1)

2. 算法

$DG\left(x\right):=\left(\frac{\partial G\left(x\right)}{\partial {x}_{1}},\frac{\partial G\left(x\right)}{\partial {x}_{2}},\cdots ,\frac{\partial G\left(x\right)}{\partial {x}_{n}}\right),$

$DG\left(x\right)d=\underset{i=1}{\overset{n}{\sum }}{d}_{i}\frac{\partial G\left(x\right)}{\partial {x}_{i}}.$

$DG\left(x\right)$ 的伴随算子为 $DG{\left(x\right)}^{*}$ ，且 $\forall Z\in {\mathbb{S}}^{m}$ ，有

$DG{\left(x\right)}^{*}Z:={\left(〈\frac{\partial G\left(x\right)}{\partial {x}_{1}},Z〉,〈\frac{\partial G\left(x\right)}{\partial {x}_{2}},Z〉,\cdots ,〈\frac{\partial G\left(x\right)}{\partial {x}_{n}},Z〉\right)}^{\text{T}},$

$L\left(x,\lambda ,Y\right)=f\left(x\right)+{\lambda }^{\text{T}}h\left(x\right)+〈Y,G\left(x\right)〉,$

$\nabla f\left({x}^{*}\right)+Dh{\left({x}^{*}\right)}^{\text{T}}{\lambda }^{*}+DG{\left({x}^{*}\right)}^{\ast }{Y}_{*}=0,$

$h\left({x}^{*}\right)=0,G\left({x}^{*}\right)\preccurlyeq 0,$

${Y}_{*}\succcurlyeq 0,\text{Tr}\left({Y}_{*}G\left({x}^{*}\right)\right)=0,$

$v\left(x\right)=‖h\left(x\right)‖+{\lambda }_{1}{\left(G\left(x\right)\right)}_{+},$ (1.1)

${P}_{\alpha }\left(x\right)=f\left(x\right)+\alpha v\left(x\right),$ (1.2)

${m}_{k}\left(d\right)=‖h\left({x}^{k}\right)+Dh\left({x}^{k}\right)d‖+{\lambda }_{1}{\left(G\left({x}^{k}\right)+DG\left({x}^{k}\right)d\right)}_{+}.$ (1.3)

${Q}_{k}^{\alpha }\left(d\right)=f\left({x}^{k}\right)+\nabla f{\left({x}^{k}\right)}^{\text{T}}d+\frac{1}{2}{d}^{\text{T}}{B}_{k}d+\alpha {m}_{k}\left(d\right),$ (1.4)

$\underset{d\in {ℝ}^{n}}{\mathrm{min}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{Q}_{k}^{\alpha }\left(d\right).$ (1.5)

$\begin{array}{l}\underset{d,{z}_{1},{z}_{2}}{\mathrm{min}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\nabla f{\left({x}^{k}\right)}^{\text{T}}d+\frac{1}{2}{d}^{\text{T}}{B}_{k}d+\alpha \left({‖{z}_{1}‖}^{2}+{z}_{2}\right)\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}h\left({x}^{k}\right)+Dh\left({x}^{k}\right)d={z}_{1},\\ \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{\hspace{0.17em}}G\left({x}^{k}\right)+DG\left({x}^{k}\right)d\preccurlyeq {z}_{2}{I}_{m},{z}_{2}\ge 0,\end{array}$ (1.6)

$\mathrm{min}{m}_{k}\left(d\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{s}\text{.t}\text{.}\text{\hspace{0.17em}}{‖d‖}_{\infty }\le {\Delta }_{k},$ (1.7)

$\begin{array}{ll}\underset{d,{z}_{1},{z}_{2}}{\mathrm{min}}\hfill & ‖{z}_{1}‖+{z}_{2}\hfill \\ \text{s}\text{.t}\hfill & h\left({x}^{k}\right)+Dh\left({x}^{k}\right)d={z}_{1},\hfill \\ \hfill & G\left({x}^{k}\right)+DG\left({x}^{k}\right)d\preccurlyeq {z}_{2}{I}_{m},\hfill \\ \hfill & {‖d‖}_{\infty }\le {\Delta }_{k},{z}_{2}\ge 0.\hfill \end{array}$ (1.8)

${m}_{k}\left({d}_{LM}^{k}\right)=v\left({x}^{k}\right)且v\left({x}^{k}\right)>0,$ (1.9)

${m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)=0,$ (1.10)

${m}_{k}\left(0\right)-{m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)\ge {ϵ}_{1}\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\right]$ (1.11)

${Q}_{k}^{{\stackrel{¯}{\alpha }}_{k}}\left(0\right)-{Q}_{k}^{{\stackrel{¯}{\alpha }}_{k}}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)\ge {ϵ}_{2}{\stackrel{¯}{\alpha }}_{k}\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\right]$ (1.12)

${\alpha }_{k}:=\frac{\nabla f{\left({x}^{k}\right)}^{\text{T}}{d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)+\frac{1}{2}{\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)}^{\text{T}}{B}_{k}{d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)}{{m}_{k}\left(0\right)-{m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)+{ϵ}_{2}\left[{m}_{k}\left({d}_{LM}^{k}\right)-{m}_{k}\left(0\right)\right]}+\rho ,$ (1.13)

${P}_{{\alpha }_{k}}\left({x}^{k}\right)-{P}_{{\alpha }_{k}}\left({x}^{k}+{t}_{k}{d}^{k}\left({\alpha }_{k}\right)\right)\ge \eta {t}_{k}\left[{Q}_{k}^{{\alpha }_{k}}\left(0\right)-{Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\alpha }_{k}\right)\right)\right],$ (1.14)

3. 全局收敛性

A1：函数 $f\left(x\right),h\left(x\right),G\left(x\right)$ 是二阶连续可微；

A2：算法A产生的序列 $\left\{{x}^{k}\right\}$ 包含于某个紧凸集中；

A3：存在正常数a和b，使得 $a{‖y‖}^{2}\le {y}^{\text{T}}{B}_{k}y\le b{‖y‖}^{2},\forall y\in {ℝ}^{n}$

${v}^{\prime }\left({x}^{k};y\right)={{m}^{\prime }}_{k}\left(0;y\right),{{P}^{\prime }}_{\alpha }\left({x}^{k};y\right)={\left({Q}_{k}^{\alpha }\right)}^{\prime }\left(0;y\right),\forall y\in {ℝ}^{n}.$ (2.1)

${v}^{\prime }\left({x}^{k};y\right)=‖Dh\left({x}^{k}\right)y‖+{\left[{\lambda }_{1}{\left(\cdot \right)}_{+}\right]}^{\prime }\left(G\left({x}^{k}\right);DG\left({x}^{k}\right)y\right).$ (2.2)

$\begin{array}{c}{{m}^{\prime }}_{k}\left(\stackrel{˜}{d};y\right)=‖{\left(h\left({x}^{k}\right)+Dh\left({x}^{k}\right)d\right)}^{\prime }\left(\stackrel{˜}{d};y\right)‖+{\left[{\lambda }_{1}{\left(G\left({x}^{k}\right)+DG\left({x}^{k}\right)d\right)}_{+}\right]}^{\prime }\left(\stackrel{˜}{d};y\right)\\ =‖Dh\left({x}^{k}\right)y‖+{\left[{\lambda }_{1}{\left(\cdot \right)}_{+}\right]}^{\prime }\left(G\left({x}^{k}\right)+DG\left({x}^{k}\right)\stackrel{˜}{d};DG\left({x}^{k}\right)y\right),\end{array}$

$\stackrel{˜}{d}=0$ ，可得

${{m}^{\prime }}_{k}\left(0;y\right)=‖Dh\left({x}^{k}\right)y‖+{\left[{\lambda }_{1}{\left(\cdot \right)}_{+}\right]}^{\prime }\left(G\left({x}^{k}\right);DG\left({x}^{k}\right)y\right).$ (2.3)

(1) ${x}^{k}$${P}_{\alpha }\left(x\right)$ 的稳定点当且仅当子问题 $\text{QM}\left({x}^{k},\alpha \right)\left(1.5\right)$ 的最优解 ${d}^{k}\left(\alpha \right)=0$

(2) 若 ${x}^{k}$${P}_{\alpha }\left(x\right)$ 的稳定点且 $v\left({x}^{k}\right)=0$ ，则 ${x}^{k}$ 是NLSDP (0.1)的一个KKT点。

(3) ${x}^{k}$$v\left(x\right)$ 的稳定点当且仅当对于任意给定的信赖域半径 $\Delta >0$ ，子问题 $\text{LM}\left({x}^{k},{\Delta }_{k}\right)\left(1.7\right)$ 的最优解 ${d}_{LM}^{k}$ 满足如下等式：

${m}_{k}\left({d}_{LM}^{k}\right)=v\left({x}^{k}\right).$ (2.4)

(2) 若 ${x}^{k}$${P}_{\alpha }\left(x\right)$ 的稳定点，则由结论(1)知子问题 $\text{QM}\left({x}^{k},\alpha \right)\left(1.5\right)$ 的最优解 ${d}^{k}\left(\alpha \right)=0$ 。由子问题(1.6)的KKT条件可得

$\nabla f\left({x}^{k}\right)+{B}_{k}{d}^{k}\left(\alpha \right)+Dh{\left({x}^{k}\right)}^{\text{T}}{\lambda }_{k}+DG{\left({x}^{k}\right)}^{\ast }{Y}_{k}=0,$ (2.5a)

$h\left({x}^{k}\right)+Dh\left({x}^{k}\right){d}^{k}\left(\alpha \right)={z}_{1}^{k},$ (2.5b)

$G\left({x}^{k}\right)+DG\left({x}^{k}\right){d}^{k}\left(\alpha \right)\preccurlyeq {z}_{2}^{k}{I}_{m},$ (2.5c)

${Y}_{k}\succcurlyeq 0,$ (2.5d)

$\text{Tr}\left({Y}_{k}\left(G\left({x}^{k}\right)+DG\left({x}^{k}\right){d}^{k}\left(\alpha \right)-{z}_{2}^{k}{I}_{m}\right)\right)=0.$ (2.5e)

${d}^{k}\left(\alpha \right)=0$ 代入，即有

$\nabla f\left({x}^{k}\right)+Dh{\left({x}^{k}\right)}^{\text{T}}{\lambda }_{k}+DG{\left({x}^{k}\right)}^{\ast }{Y}_{k}=0,$ (2.6a)

$h\left({x}^{k}\right)={z}_{1}^{k},$ (2.6b)

$G\left({x}^{k}\right)\preccurlyeq {z}_{2}^{k}{I}_{m},$ (2.6c)

${Y}_{k}\succcurlyeq 0,$ (2.6d)

$\text{Tr}\left({Y}_{k}\left(G\left({x}^{k}\right)-{z}_{2}^{k}{I}_{m}\right)\right)=0.$ (2.6e)

$v\left({x}^{k}\right)=0$${x}^{k}$ 为NLSDP (0.1)的可行点，故结合(2.6b)，(2.6c)和 ${z}_{2}^{k}\ge 0$$\left({z}_{1}^{k},{z}_{2}^{k}\right)=\left(0,0\right)$ 。再结合(2.6a)，(2.6d)，(2.6e)即知 ${x}^{k}$ 是NLSDP (0.1)的KKT点。

(3) 由引理2.1知 ${x}^{k}$$v\left(x\right)$ 的稳定点当且仅当0是 ${m}_{k}\left(d\right)$ 的稳定点，结合 ${m}_{k}\left(d\right)$ 是凸函数知0是 $\text{LM}\left({x}^{k},{\Delta }_{k}\right)\left(1.7\right)$ 的一个最优解，因此， ${m}_{k}\left({d}_{LM}^{k}\right)={m}_{k}\left(0\right)$ ，结合 ${m}_{k}\left(0\right)=v\left({x}^{k}\right)$ 即得 ${m}_{k}\left({d}_{LM}^{k}\right)=v\left({x}^{k}\right)$ 。反之，若 ${m}_{k}\left({d}_{LM}^{k}\right)=m\left(0\right)$ ，即0是子问题 $\text{LM}\left({x}^{k},{\Delta }_{k}\right)\left(1.7\right)$ 的一个最优解，由此知0是 ${m}_{k}\left(d\right)$ 的稳定点，于是对任意方向 $y\in {ℝ}^{n}$ ，有 ${{m}^{\prime }}_{k}\left(0;y\right)\ge 0$ 。由引理2.1即知 ${x}^{k}$$v\left(x\right)$ 的稳定点。

${q}_{k}^{f}\left(d\right):=f\left({x}^{k}\right)+\nabla f{\left({x}^{k}\right)}^{\text{T}}d+\frac{1}{2}{d}^{\text{T}}{B}_{k}d,$ (2.7)

(1) 若算法A执行到步骤4，则当 ${m}_{k}\left({d}_{LM}^{k}\right)=0$ 时，存在 ${\stackrel{¯}{\alpha }}_{k}>0$ ，使得(1.10)式成立；当 ${m}_{k}\left({d}_{LM}^{k}\right)>0$ 时，存在 ${\stackrel{¯}{\alpha }}_{k}>0$ ，使得(1.11)式成立。另外，若(1.12)不成立，则通过(1.13)式产生的 ${\alpha }_{k}$ 满足如下不等式：

${Q}_{k}^{{\alpha }_{k}}\left(0\right)-{Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\alpha }_{k}\right)\right)\ge {ϵ}_{2}{\alpha }_{k}\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\right],$ (2.8)

(2) 若算法A执行到步骤5，则 ${d}^{k}\left({\alpha }_{k}\right)$ 是罚函数 ${P}_{{\alpha }_{k}}\left(x\right)$${x}^{k}$ 处的下降方向，并且总存在步长 ${t}_{k}>0$ ，使得(1.14)式成立。

${m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)\le {m}_{k}\left({d}_{LM}^{k}\right).$ (2.9)

${m}_{k}\left({d}_{LM}^{k}\right)=0$ ，则由上式知(1.10)成立。若 ${m}_{k}\left({d}_{LM}^{k}\right)>0$ ，注意到 ${ϵ}_{1}\in \left(0,1\right]$ 。由于0是子问题(1.7)的可行解，因此有 ${m}_{k}\left(0\right)-{m}_{k}\left({d}_{LK}^{k}\right)\ge 0$ 。于是由(2.9)有

${m}_{k}\left(0\right)-{m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)\ge {m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\ge {ϵ}_{1}\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\right],$

${m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)=0$ ，注意到 ${d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)$ 是子问题 $\text{QM}\left({x}^{k},{\alpha }_{k}\right)\left(1.5\right)$ 的最优解，则有 ${Q}_{k}^{{\alpha }_{k}}\left(0\right)\ge {Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\alpha }_{k}\right)\right)$ 。因此， ${Q}_{k}^{{\alpha }_{k}}\left(0\right)-{Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\alpha }_{k}\right)\right)-{ϵ}_{2}{\alpha }_{k}\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\right]\ge 0$ ，即(2.8)成立。

${m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)>0$ ，则 ${m}_{k}\left(0\right)>{m}_{k}\left({d}_{LM}^{k}\right)\ge 0$ ，故 ${m}_{k}\left(0\right)>0$

$\Gamma :={m}_{k}\left(0\right)-{m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)+{ϵ}_{2}\left[{m}_{k}\left({d}_{LM}^{k}\right)-{m}_{k}\left(0\right)\right]$ ，往证 $\Gamma >0$

$\Gamma ={m}_{k}\left(0\right)+{ϵ}_{2}\left[{m}_{k}\left({d}_{LM}^{k}\right)-{m}_{k}\left(0\right)\right]=\left(1-{ϵ}_{2}\right){m}_{k}\left(0\right)+{ϵ}_{2}{m}_{k}\left({d}_{LM}^{k}\right)>0.$

$\Gamma \ge {ϵ}_{1}\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\right]+{ϵ}_{2}\left[{m}_{k}\left({d}_{LM}^{k}\right)-{m}_{k}\left(0\right)\right]=\left({ϵ}_{1}-{ϵ}_{2}\right)\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\right],$

$\begin{array}{l}{\alpha }_{k}\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)\right]+{ϵ}_{2}{\alpha }_{k}\left[{m}_{k}\left({d}_{LM}^{k}\right)-{m}_{k}\left(0\right)\right]\\ =\nabla f{\left({x}^{k}\right)}^{\text{T}}{d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)+\frac{1}{2}{\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)}^{\text{T}}{B}_{k}{d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)+\Gamma \cdot \rho ,\end{array}$

$\begin{array}{l}{ϵ}_{2}{\alpha }_{k}\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\right]\\ \le -\nabla f{\left({x}^{k}\right)}^{\text{T}}{d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)-\frac{1}{2}{\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)}^{\text{T}}{B}_{k}{d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)+{\alpha }_{k}\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)\right]\\ ={Q}_{k}^{{\alpha }_{k}}\left(0\right)-{Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)\le {Q}_{k}^{{\alpha }_{k}}\left(0\right)-{Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\alpha }_{k}\right)\right),\end{array}$

${\alpha }_{k}$ 满足(3.8)。

${q}_{k}^{f}\left({d}^{k}\left({\alpha }_{1}\right)\right)+{\alpha }_{2}{m}_{k}\left({d}^{k}\left({\alpha }_{1}\right)\right)\ge {q}_{k}^{f}\left({d}^{k}\left({\alpha }_{2}\right)\right)+{\alpha }_{2}{m}_{k}\left({d}^{k}\left({\alpha }_{2}\right)\right),$

${q}_{k}^{f}\left({d}^{k}\left({\alpha }_{2}\right)\right)+{\alpha }_{1}{m}_{k}\left({d}^{k}\left({\alpha }_{2}\right)\right)\ge {q}_{k}^{f}\left({d}^{k}\left({\alpha }_{1}\right)\right)+{\alpha }_{1}{m}_{k}\left({d}^{k}\left({\alpha }_{1}\right)\right),$

${\stackrel{¯}{\alpha }}_{k}<\frac{\nabla f{\left({x}^{k}\right)}^{\text{T}}{d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)+\frac{1}{2}{\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)}^{\text{T}}{B}_{k}{d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)}{{m}_{k}\left(0\right)-{m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)+{ϵ}_{2}\left[{m}_{k}\left({d}_{LM}^{k}\right)-{m}_{k}\left(0\right)\right]},$

${m}_{k}\left({d}^{k}\left({\alpha }_{k}\right)\right)\le {m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right).$ (3.10)

${m}_{k}\left({d}_{LM}^{k}\right)=0$ ，则由(2.10)和(2.9)得 $0\le {m}_{k}\left({d}^{k}\left({\alpha }_{k}\right)\right)\le {m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)\le {m}_{k}\left({d}_{LM}^{k}\right)=0$ ，故 ${m}_{k}\left({d}^{k}\left({\alpha }_{k}\right)\right)=0$ ，即 ${\alpha }_{k}$ 满足(1.10)式。

${m}_{k}\left({d}_{LM}^{k}\right)>0$ ，则由(2.10)和(2.11)得

${m}_{k}\left(0\right)-{m}_{k}\left({d}^{k}\left({\alpha }_{k}\right)\right)\ge {m}_{k}\left(0\right)-{m}_{k}\left({d}^{k}\left({\stackrel{¯}{\alpha }}_{k}\right)\right)\ge {ϵ}_{1}\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\right],$

${\alpha }_{k}$ 满足(1.11)式。

(2) 若 ${x}^{k}$ 不是罚函数 ${P}_{{\alpha }_{k}}\left(x\right)$ 的稳定点，则由引理2.2 (1)知 ${d}^{k}\left({\alpha }_{k}\right)\ne 0$ 。由于 ${Q}_{k}^{{\alpha }_{k}}\left(d\right)$ 是凸的且 ${d}^{k}\left({\alpha }_{k}\right)$$\text{QM}\left({x}^{k},{\alpha }_{k}\right)\left(1.5\right)$ 的最优解，故有 ${Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\alpha }_{k}\right)\right)<{Q}_{k}^{{\alpha }_{k}}\left(0\right)$ 。由方向导数的定义和 ${Q}_{k}^{{\alpha }_{k}}\left(d\right)$ 的凸性得

$\begin{array}{c}{\left({Q}_{k}^{{\alpha }_{k}}\right)}^{\prime }\left(0;{d}^{k}\left({\alpha }_{k}\right)\right)=\underset{t\to {0}^{+}}{\mathrm{lim}}\frac{{Q}_{k}^{{\alpha }_{k}}\left(t{d}^{k}\left({\alpha }_{k}\right)\right)-{Q}_{k}^{{\alpha }_{k}}\left(0\right)}{t}\\ =\underset{t\to {0}^{+}}{\mathrm{lim}}\frac{{Q}_{k}^{{\alpha }_{k}}\left(\left(1-t\right)0+t{d}^{k}\left({\alpha }_{k}\right)\right)-{Q}_{k}^{{\alpha }_{k}}\left(0\right)}{t}\\ \le \underset{t\to {0}^{+}}{\mathrm{lim}}\frac{\left(1-t\right){Q}_{k}^{{\alpha }_{k}}\left(0\right)+t{Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\alpha }_{k}\right)\right)-{Q}_{k}^{{\alpha }_{k}}\left(0\right)}{t}\\ ={Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\alpha }_{k}\right)\right)-{Q}_{k}^{{\alpha }_{k}}\left(0\right)<0,\end{array}$

${{P}^{\prime }}_{{\alpha }_{k}}\left({x}^{k};{d}^{k}\left({\alpha }_{k}\right)\right)={\left({Q}_{k}^{{\alpha }_{k}}\right)}^{\prime }\left(0;{d}^{k}\left({\alpha }_{k}\right)\right)<0$

${P}_{{\alpha }_{k}}\left({x}^{k}+t{d}^{k}\left({\alpha }_{k}\right)\right)<{P}_{{\alpha }_{k}}\left({x}^{k}\right)+t\eta {{P}^{\prime }}_{{\alpha }_{k}}\left({x}^{k};{d}^{k}\left({\alpha }_{k}\right)\right).$ (2.11)

${Q}_{k}^{{\alpha }_{k}}\left(d\right)$ 的凸性可得 ${Q}_{k}^{{\alpha }_{k}}\left(0+t{d}^{k}\left({\alpha }_{k}\right)\right)\ge {Q}_{k}^{{\alpha }_{k}}\left(0\right)+t{\left({Q}_{k}^{{\alpha }_{k}}\right)}^{\prime }\left(0;{d}^{k}\left({\alpha }_{k}\right)\right)$ ，故有

$\begin{array}{c}-t{\left({Q}_{k}^{{\alpha }_{k}}\right)}^{\prime }\left(0;{d}^{k}\left({\alpha }_{k}\right)\right)\ge {Q}_{k}^{{\alpha }_{k}}\left(0\right)-{Q}_{k}^{{\alpha }_{k}}\left(0+t{d}^{k}\left({\alpha }_{k}\right)\right)\\ ={Q}_{k}^{{\alpha }_{k}}\left(0\right)-{Q}_{k}^{{\alpha }_{k}}\left(\left(1-t\right)0+t{d}^{k}\left({\alpha }_{k}\right)\right)\\ \ge {Q}_{k}^{{\alpha }_{k}}\left(0\right)-\left(1-t\right){Q}_{k}^{{\alpha }_{k}}\left(0\right)-t{Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\alpha }_{k}\right)\right)\\ =t\left[{Q}_{k}^{{\alpha }_{k}}\left(0\right)-{Q}_{k}^{{\alpha }_{k}}\left({d}^{k}\left({\alpha }_{k}\right)\right)\right],\end{array}$

${\mathcal{B}}_{k}:=\left\{d|‖d‖\le {r}^{k}\right\},$

(1) 若 $v\left({x}^{*}\right)=0$ ，则 ${x}^{*}$ 为NLSDP (0.1)的一个KKT点；

(2) 若 $v\left({x}^{*}\right)>0$ ，则 ${x}^{*}$ 为NLSDP (0.1)的一个不可行稳定点。

(反证)假设 ${d}^{*}\ne 0$ ，则 ${Q}_{*}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{*}^{\stackrel{¯}{\alpha }}\left({d}^{*}\right)>0$ 。于是有

${Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{*}\right)\stackrel{K}{\to }{Q}_{*}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{*}^{\stackrel{¯}{\alpha }}\left({d}^{*}\right)>0.$

${Q}_{*}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{*}^{\stackrel{¯}{\alpha }}\left({d}^{*}\right)=2\epsilon$ ，其中 $\epsilon >0$ 。因此存在指标 ${k}_{0}$ ，当 $k\left(\in \mathcal{K}\right)>{k}_{0}$ 时，由上式和 ${Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{*}\right)\ge {Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)$

${Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\ge {Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{*}\right)>\epsilon .$ (2.12)

$t>0$ 足够小时，由引理2.4，(1.1)，(1.3)，假设A1和Taylor展开式得

$\begin{array}{l}v\left({x}^{k}+t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)-{m}_{k}\left(t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\\ =‖h\left({x}^{k}\right)+tDh\left({x}^{k}\right){d}^{k}\left(\stackrel{¯}{\alpha }\right)+O\left({‖t{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}\right)‖-‖h\left({x}^{k}\right)+tDh\left({x}^{k}\right){d}^{k}\left(\stackrel{¯}{\alpha }\right)‖\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+{\lambda }_{1}{\left(G\left({x}^{k}\right)+tDG\left({x}^{k}\right){d}^{k}\left(\stackrel{¯}{\alpha }\right)+O\left({‖t{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}\right)\right)}_{+}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}-{\lambda }_{1}{\left(G\left({x}^{k}\right)+tDG\left({x}^{k}\right){d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)}_{+}\\ =O\left({‖t{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}\right)\end{array}$ (2.13)

$\begin{array}{l}f\left({x}^{k}+t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)-{q}_{k}^{f}\left(t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\\ =f\left({x}^{k}\right)+t\nabla f{\left({x}^{k}\right)}^{\text{T}}{d}^{k}\left(\stackrel{¯}{\alpha }\right)+\frac{1}{2}{t}^{2}{\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)}^{\text{T}}{\nabla }^{2}f\left(\xi \right){d}^{k}\left(\stackrel{¯}{\alpha }\right)-{q}_{k}^{f}\left(t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\\ =\frac{1}{2}{t}^{2}{\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)}^{\text{T}}\left({\nabla }^{2}f\left(\xi \right)-{B}_{k}\right){d}^{k}\left(\stackrel{¯}{\alpha }\right)=O\left({‖t{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}\right),\end{array}$ (2.14)

${P}_{\stackrel{¯}{\alpha }}\left({x}^{k}+t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left(t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)=O\left({‖t{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}\right),$

$|{P}_{\stackrel{¯}{\alpha }}\left({x}^{k}+t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left(t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)|\le {b}_{1}{‖t{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}.$ (2.15)

${Q}_{k}^{\stackrel{¯}{\alpha }}\left(d\right)$ 的凸性可得

$\begin{array}{c}{Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left(t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\ge {Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-\left(1-t\right){Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-t{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\\ =t\left({Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\right).\end{array}$ (2.16)

${P}_{\stackrel{¯}{\alpha }}\left({x}^{k}\right),{Q}_{k}^{\stackrel{¯}{\alpha }}\left(d\right)$ 的定义知 ${P}_{\stackrel{¯}{\alpha }}\left({x}^{k}\right)={Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)$ ，结合(2.12)，(2.15)和(2.16)，可得

$\begin{array}{l}{P}_{\stackrel{¯}{\alpha }}\left({x}^{k}\right)-{P}_{\stackrel{¯}{\alpha }}\left({x}^{k}+t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\\ =\left({Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left(t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\right)+{Q}_{k}^{\stackrel{¯}{\alpha }}\left(t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)-{P}_{\stackrel{¯}{\alpha }}\left({x}^{k}+t{d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\\ \ge t\left({Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\right)-{b}_{1}{‖t{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}\\ =\eta t\left({Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\right)+\left(1-\eta \right)t\left({Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\right)-{b}_{1}{‖t{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}\\ \ge \eta t\left({Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\right)+\left(1-\eta \right)t\epsilon -{b}_{1}{‖t{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}.\end{array}$

$t\le \frac{\left(1-\eta \right)\epsilon }{{b}_{1}{‖{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}}$ ，结合上式，则知(1.14)成立。由步长 ${t}_{k}$ 的选择可知，

${t}_{k}\ge \mathrm{min}\left\{1,\frac{\tau \left(1-\eta \right)\epsilon }{{b}_{1}{‖{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}}\right\}.$ (2.17)

$‖{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖\le \mathrm{max}\left\{\frac{2}{a}\left(‖\nabla f\left({x}^{k}\right)‖+\stackrel{¯}{\alpha }{m}_{k}\left(0\right)\right),1\right\}.$ (2.18)

(反证)假设上式不成立，则 $‖{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖>1,‖{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖>\frac{2}{a}\left(‖\nabla f\left({x}^{k}\right)‖+\stackrel{¯}{\alpha }{m}_{k}\left(0\right)\right)$ 。由(1.4)，假设A2以及上式可得

$\begin{array}{l}{Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\\ =-\nabla f{\left({x}^{k}\right)}^{\text{T}}{d}^{k}\left(\stackrel{¯}{\alpha }\right)-\frac{1}{2}{\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)}^{\text{T}}{B}_{k}{d}^{k}\left(\stackrel{¯}{\alpha }\right)-\stackrel{¯}{\alpha }{m}_{k}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)+\stackrel{¯}{\alpha }{m}_{k}\left(0\right)\\ \le ‖\nabla f\left({x}^{k}\right)‖‖{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖-\frac{1}{2}a{‖{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖}^{2}+\stackrel{¯}{\alpha }{m}_{k}\left(0\right)\\ <‖\nabla f\left({x}^{k}\right)‖‖{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖-\frac{1}{2}a‖{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖\cdot \frac{2}{a}\left(‖\nabla f\left({x}^{k}\right)‖+\stackrel{¯}{\alpha }{m}_{k}\left(0\right)\right)+\stackrel{¯}{\alpha }{m}_{k}\left(0\right)\\ =\stackrel{¯}{\alpha }{m}_{k}\left(0\right)\left(1-‖{d}^{k}\left(\stackrel{¯}{\alpha }\right)‖\right)<0,\end{array}$

$v\left({x}^{*}\right)>0$ ，往下证明 ${x}^{*}$ 为NLSDP (0.1)的不可行稳定点。

${Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\to 0,$ (2.19)

${Q}_{k}^{\stackrel{¯}{\alpha }}\left(0\right)-{Q}_{k}^{\stackrel{¯}{\alpha }}\left({d}^{k}\left(\stackrel{¯}{\alpha }\right)\right)\ge {ϵ}_{2}\stackrel{¯}{\alpha }\left[{m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\right],$ (2.20)

${m}_{k}\left(0\right)-{m}_{k}\left({d}_{LM}^{k}\right)\to {m}_{*}\left(0\right)-{m}_{*}\left({d}_{LM}^{*}\right)=0$

4. 数值试验

$\begin{array}{ll}\mathrm{min}\hfill & \text{Tr}\left(L{Q}_{F}\right)\hfill \\ \text{s}\text{.t}\text{.}\hfill & {A}_{F}L+L{A}_{F}^{\text{T}}+I=0,\hfill \\ \hfill & {A}_{F}L+L{A}_{F}^{\text{T}}\preccurlyeq 0,L\succ 0,\hfill \end{array}$

${\alpha }_{0}=80,\rho =100,\eta 1=0.5,\eta 2=0.3,\tau =0.5,\eta =0.001.$

n：自变量维数；

m：半定约束矩阵的阶数；

p：等式约束个数；

f*：最优函数值；

Iter：算法迭代次数；

P*：最优解的约束违反度函数值；

Time：计算机运行时间(秒)。

Table 1. Numerical result

5. 结束语

 [1] Ben-Tal, A., Jarre, F., Kocvara, M., Nemirovski, A. and Zowe, J. (2000) Optimal Design of Trusses under a Nonconvex Global Buckling Constraint. Optimization and Engineering, 1, 189-213. https://doi.org/10.1023/A:1010091831812 [2] Fares, B., Noll, D. and Apkarian, P. (2002) Robust Control via Sequential Semidefinite Programming. SIAM Journal on Control and Optimization, 40, 1791-1820. https://doi.org/10.1137/S0363012900373483 [3] Kocvara, M. and Stingl, M. (2004) Solving Nonconvex SDP Problems of Structural Optimization with Stability Control. Optimization Methods and Software, 19, 595-609. https://doi.org/10.1080/10556780410001682844 [4] Correa, R. and Ramirez, H.C. (2004) A Global Algorithm for Nonlinear Semidefinite Programming. SIAM Journal on Optimization, 15, 303-318. https://doi.org/10.1137/S1052623402417298 [5] Zhao, Q. and Chen, Z.W. (2018) An SQP-Type Method with Superlinear Convergence for Nonlinear Semidefinite Programming. Asia-Pacific Journal of Operational Research, 35, Article ID: 1850009. https://doi.org/10.1142/S0217595918500094 [6] Li, J.L., Yang, Z.P. and Jian, J.B. (2017) A Globally Conver-gent QP-Free Algorithm for Nonlinear Semidefinite Programming. Journal of Inequalities and Application. [7] 张辉. 非线性半定规划的两个SSDP算法[D]: [硕士学位论文]. 南宁: 广西大学, 2018. [8] Byrd, R.H., Lopez-Calva, G. and Nocedal, J. (2009) A Line Search Exact Penalty Method Using Steering Rules. Mathematical Programming, 133, 1-35. [9] Byrd, R.H., Nocedal, J. and Waltz, R.A. (2008) Steering Exact Penalty Methods for Nonlinear Programming. Optimization Methods and Software, 23, 197-213. https://doi.org/10.1080/10556780701394169 [10] Leibfritz, F. (2004) COMPlib-Constrained Matrix-Optimization Problem Library. Technical Report. [11] Gomez, W. and Ramirez, H. (2010) A Filter Algorithm for Nonlinear Semidefinite Programming. Computational and Applied Mathematics, 29, 297-328. [12] Zhao, Q. and Chen, Z.W. (2016) On the Superlinear Local Convergence of a Penalty-Free Method for Nonlinear Semidefinite Programming. Journal of Computational and Applied Mathematics, 308, 1-19. https://doi.org/10.1016/j.cam.2016.05.007