修正共轭投影梯度滤子法

王祥玲; 左双勇; 朱志斌

doi:10.13718/j.cnki.xdzk.2018.11.012

修正共轭投影梯度滤子法

1.
宜春幼儿师范高等专科学校初等教育学院, 江西宜春 330814

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

基金项目: 国家自然科学基金项目（11361018）；广西自然科学基金资助项目（2014GXNSFFA118001）；宜春市社科研究“十三五”规划项目（YCSK2018-106，YCSK2018-115）

详细信息

作者简介:
王祥玲(1986-), 女, 讲师, 主要从事最优化理论研究 .

中图分类号: O221.2

A Modified Conjugate Projection Gradient Filter Method

1.
Primary Education College, Yichun Early Childhood Teachers College, Yichun Jiangxi 330814, China

2.
Department of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China

摘要: 利用共轭投影梯度技术，结合滤子算法的思想，通过修正搜索方向，建立了一个新的共轭投影梯度滤子算法.该算法不需要求解二次规划子问题，而且能有效避免常规滤子算法中的恢复算法.在适当的条件下，证明了算法的全局收敛性.
- 共轭投影梯度 /
- 滤子 /
- 非线性规划 /
- 全局收敛性
Abstract: A new conjugate projection gradient filter algorithm is established by modifying the search direction. In this algorithm, conjugate projection gradient technology and filter method are combined. By the introduction of the filter, this algorithm does not need to solve a QP sub-problem. With the idea of the conjugate projection gradient, this method is effective to avoid the restoration algorithm in general filter algorithms. Under some conditions, its global convergence is obtained.
- conjugate projection gradient /
- filter /
- nonlinear programming /
- global convergence .

本文考虑如下非线性规划问题：

$\begin{array}{*{20}{c}} {\mathop {\min }\limits_{\mathit{\boldsymbol{x}} \in {\mathbb{R}^n}} f\left( \mathit{\boldsymbol{x}} \right)} \\ {{\text{s}}.\;{\text{t}}.\;\;{\mathit{\boldsymbol{c}}_j}\left( \mathit{\boldsymbol{x}} \right) \leqslant 0,j \in I = \left\{ {1,2, \cdots ,m} \right\}} \end{array}$

$(1)$

其中：x∈ ${\mathbb{R}}$ ⁿ，f： ${\mathbb{R}}$ ⁿ $\longrightarrow$ ${\mathbb{R}}$ ，c_j(j∈I)： ${\mathbb{R}}$ ⁿ $\longrightarrow$ ${\mathbb{R}}$ 是二次连续可微的.可行集X={x∈ ${\mathbb{R}}$ ⁿ|c_j(x)≤0，j∈I}，有效集I(x)={j∈I|c_j(x)=0}.

非线性规划问题广泛应用于工程和社会生活的各个领域，并在其中起着举足轻重的作用.非线性规划问题的求解主要是最优性和可行性.为了使这两个规则都能满足，算法需要在迭代过程中每一步都保持这两种规则的平衡.目前关于非线性规划问题的求解方法多种多样^[1-12].近年来，滤子法引起很多学者的密切关注.滤子法最早由Fletecher和Leyffer提出^[1]，它能有效避免选择罚函数的困难且具有良好的数值结果，从而近年来被广泛应用于各种优化问题的求解中^[2-6].共轭投影梯度算法是解决非线性规划问题的另外一种有效算法^[7].文献[8]将SQP方法和广义投影技巧结合，提出一个具有显式主搜索方向的共轭投影梯度算法，有效地简化了算法结构及计算工作量.为此，在文献[8]的基础上，本文提出一个修正的共轭投影梯度算法.该方法保证了每个试探点都不会远离可行域，同时在合适的条件下证明了算法的收敛性.

1. 相关理论知识

1.1 相关符号

对于问题(1)的近似解x^k∈X，σ_k＞0，正定矩阵B_k=B(x^k)，集合L_k⊆I，为了便于讨论给出以下记号：

$\begin{array}{*{20}{c}} {\mathit{\boldsymbol{g}}_j^k = {\mathit{\boldsymbol{g}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right) = \nabla {\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right),\mathit{\boldsymbol{H}}_j^k = {\mathit{\boldsymbol{H}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right) = {\nabla ^2}{\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right)}\\ {\mathit{\boldsymbol{F}}\left( {{\mathit{\boldsymbol{x}}^k}} \right) = \left( {{\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right),j \in {L_k}} \right),{\mathit{\boldsymbol{A}}_k} = \mathit{\boldsymbol{A}}\left( {{\mathit{\boldsymbol{x}}^k}} \right) = \left( {{\mathit{\boldsymbol{g}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right),j \in {L_k}} \right)\;\;\;\;\;\;\;\;j = 1, \cdots ,m} \end{array}$

$(2)$

本文算法引用了文献[7]提出的共轭投影梯度技术，并采用文献[7]中定义的以下各量：

${\mathit{\boldsymbol{Q}}_k} = \mathit{\boldsymbol{Q}}\left( {{\mathit{\boldsymbol{x}}^k}} \right) = {\left( {\mathit{\boldsymbol{A}}_k^{\rm{T}}\mathit{\boldsymbol{B}}_k^{ - 1}{\mathit{\boldsymbol{A}}_k}} \right)^{ - 1}}\mathit{\boldsymbol{A}}_k^{\rm{T}}\mathit{\boldsymbol{B}}_k^{ - 1},{\mathit{\boldsymbol{P}}_k} = \mathit{\boldsymbol{P}}\left( {{\mathit{\boldsymbol{x}}^k}} \right) = \mathit{\boldsymbol{B}}_k^{ - 1}\left( {{\mathit{\boldsymbol{E}}_n} - {\mathit{\boldsymbol{A}}_k}{\mathit{\boldsymbol{Q}}_k}} \right)$

$(3)$

${\mathit{\boldsymbol{\pi }}^k} = \mathit{\boldsymbol{\pi }}\left( {{\mathit{\boldsymbol{x}}^k}} \right) = - {\mathit{\boldsymbol{Q}}_k}\nabla f\left( {{\mathit{\boldsymbol{x}}^k}} \right),\mathit{\boldsymbol{d}}_0^k = {\mathit{\boldsymbol{d}}_0}\left( {{\mathit{\boldsymbol{x}}^k}} \right) = - {\mathit{\boldsymbol{P}}_k}\nabla f\left( {{\mathit{\boldsymbol{x}}^k}} \right) + \mathit{\boldsymbol{Q}}_k^{\rm{T}}{\mathit{\boldsymbol{V}}^k}$

$(4)$

${\mathit{\boldsymbol{V}}^k} = \mathit{\boldsymbol{V}}\left( {{\mathit{\boldsymbol{x}}^k}} \right) = \left( {\mathit{\boldsymbol{V}}_j^k,j \in {L_k}} \right),\mathit{\boldsymbol{V}}_j^k = \left\{ {\begin{array}{*{20}{c}} { - {f_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right)}&{\mathit{\boldsymbol{\pi }}_j^k \gt 0}\\ {\mathit{\boldsymbol{\pi }}_j^k}&{\mathit{\boldsymbol{\pi }}_j^k \le 0} \end{array}} \right.$

$(5)$

$\mathit{\boldsymbol{d}}_1^k = - \mathit{\boldsymbol{Q}}_k^{\rm{T}}\left( {{{\left\| {\mathit{\boldsymbol{d}}_0^k} \right\|}^\tau }\mathit{\boldsymbol{e}} + \mathit{\boldsymbol{F}}\left( {{\mathit{\boldsymbol{x}}^k} + \mathit{\boldsymbol{d}}_0^k} \right)} \right),\mathit{\boldsymbol{e}} = \left( {1, \cdots ,1} \right),{\mathit{\boldsymbol{d}}^k} = \mathit{\boldsymbol{d}}_0^k + \mathit{\boldsymbol{d}}_1^k$

$(6)$

${\mathit{\boldsymbol{\rho }}_k} = - \nabla f{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}\mathit{\boldsymbol{d}}_0^k,\mathit{\boldsymbol{d}}_2^k = \frac{{ - {\mathit{\boldsymbol{\rho }}_k}}}{{1 + 2\left\| {{\mathit{\boldsymbol{e}}^{\rm{T}}}{\mathit{\boldsymbol{\pi }}^k}} \right\|}}\mathit{\boldsymbol{Q}}_k^{\rm{T}}\mathit{\boldsymbol{e}},{\mathit{\boldsymbol{q}}^k} = {\mathit{\boldsymbol{\rho }}_k}\left( {\mathit{\boldsymbol{d}}_0^k + \mathit{\boldsymbol{d}}_2^k} \right)$

$(7)$

定义1^[7] 如果函数μ(x)： ${\mathbb{R}}$ ⁿ $\longrightarrow$ ${\mathbb{R}}$ ^m满足以下条件：

1) μ(x)连续.

2) 当x^*是问题(1)的K-T点时，μ(x^*)为相应的K-T乘子.则称μ(x)为乘子函数.

1.2 滤子技术

滤子技术能很好地平衡目标函数和约束条件，对于每次迭代，试探点被接受当且仅当约束违反度函数值或目标函数值相对于当前的滤子集中的点有充分的下降.

本文定义约束违反度函数为

$h\left( \mathit{\boldsymbol{x}} \right) = {\left\| {\mathit{\boldsymbol{c}}{{\left( \mathit{\boldsymbol{x}} \right)}^ + }} \right\|_\infty }$

$(8)$

其中

$\mathit{\boldsymbol{c}}{\left( \mathit{\boldsymbol{x}} \right)^ + } = \max \left\{ {0,{\mathit{\boldsymbol{c}}_j}\left( \mathit{\boldsymbol{x}} \right):j \in I} \right\}$

易知h(x)=0的充要条件是保证迭代点x是可行点，所以试探点应该使得约束违反度函数值降低或目标函数值减小.为了保证这两项至少有一项满足，参照文献[1]引入滤子的相关定义.

定义2 称点x¹支配点x²当且仅当

$h\left( {{\mathit{\boldsymbol{x}}^1}} \right) \le h\left( {{\mathit{\boldsymbol{x}}^2}} \right)\;且\;f\left( {{\mathit{\boldsymbol{x}}^1}} \right) \le f\left( {{\mathit{\boldsymbol{x}}^2}} \right)$

$(9)$

定义3 滤子为具有形式为(h_i，f_i)的点集Z，使得任意点不能被其他点支配，即h(xⁱ)≤h(x^j)或f(xⁱ)≤f(x^j)对所有的i≠j成立.

在实际计算中，为了获得全局收敛性，需要添加一些条件，如文献[1]中定义了一个“包络”来阻止点任意接近滤子.从而有以下滤子准则：

定义4 一个点被滤子接受当且仅当对任意的(h_j，f_j)∈Z有

$h\left( \mathit{\boldsymbol{x}} \right) \le \beta {h_j}\;或\;f\left( \mathit{\boldsymbol{x}} \right) \le {f_j} - \gamma {h_j}$

$(10)$

其中：h_j=h(x^j)；f_j=f(x^j)；0＜γ＜β＜1且γ→0，β→1.

在算法的进程中需要将(h_j，f_j)对添加到滤子中，如果一个点x^k被滤子集Z接受，则令x^k+1=x^k+t_kd^k且滤子按如下的规则更新

${Z_{k + 1}} = {Z_k} \cup \left\{ {\left( {{h_{k + 1}},{f_{k + 1}}} \right)} \right\}\backslash {D_{k + 1}}$

$(11)$

其中

${D_{k + 1}} = \left\{ {\left( {{h_j},{f_j}} \right)\left| {{h_j} \ge {h_k}} \right.,{f_j} - \gamma {h_j} \ge {f_k} - \gamma {h_k},\forall \left( {{h_j},{f_j}} \right) \in {Z_k}} \right\}$

事实上，这里“点x被滤子集Z接受”严格上说是将(h_j，f_j)对添加到滤子集中.如果点x^k被滤子集接受或者已在滤子集中，那么满足

$h\left( \mathit{\boldsymbol{x}} \right) \le \left( {1 - \gamma } \right){h_k}\;且\;f\left( \mathit{\boldsymbol{x}} \right) \le {f_k} - \gamma {h_k}$

$(12)$

的点x也是被滤子接受的.

2. 算法模型

算法1

步0 (初始化) 给定x⁰∈ ${\mathbb{R}}$ ⁿ，μ(x⁰)∈ ${\mathbb{R}}$ ^m，B₀是对称正定矩阵，选择σ₀，ξ，ε，v∈(0，1)，τ∈(2，3)，δ＞2且α₁，α₂，η∈(0，1)，t₀=1，初始化滤子集Z₀，并令k=0.

步1 (有效集L_k)

(a) 令i=0，σ_k，i=σ₀；

(b) 若det(A_k^TA_k)＞σ_k，i，令L_k=L_k，i，i_k=i，转步2，否则转步1(c)，其中：

${L_{k,i}} = \left\{ {j \in I\left| { - {\sigma _{k,i}}\left| {{\mathit{\boldsymbol{\mu }}_j}\left( {{x^k}} \right)} \right|} \right. \le {f_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right) \le 0} \right\},{\mathit{\boldsymbol{A}}_{k,i}} = \left( {{\mathit{\boldsymbol{g}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right),j \in {L_{k,i}}} \right)$

步2 (搜索方向) 通过式(2)-(5)获得d₀^k.若d₀^k=0，则获得一个K-T点，停止.否则，通过式(6)计算d^k.

若

$\nabla f{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}\mathit{\boldsymbol{d}}_0^k \le \min \left\{ { - \xi {{\left\| {\mathit{\boldsymbol{d}}_0^k} \right\|}^\delta }, - \xi {{\left\| {{\mathit{\boldsymbol{d}}^k}} \right\|}^\delta }} \right\}$

$(13)$

则转步3.否则，转步4.

步3 (滤子准则) 若x^k+t_kd^k不被滤子接受，则令x^k+1=x^k，t_k+1=0.5t_k，k=k+1，转步4.若x^k+t_kd^k被滤子接受，则令x^k+1=x^k+d^k，f_k+1=f(x^k+d^k)，h_k+1=h(x^k+d^k)，并去除那些被x^k+1支配的点，更新滤子集Z_k+1，转步5.

步4 (线搜索) 通过式(7)获得q^k，取 $\left\{ {1, \frac{1}{2}, \frac{1}{4}, \cdots } \right\}$ 的最大值为λ_k，使其满足

$f\left( {{\mathit{\boldsymbol{x}}^k} + {\lambda _k}{\mathit{\boldsymbol{q}}^k}} \right) \le f\left( {{\mathit{\boldsymbol{x}}^k}} \right) + v{\lambda _k}\nabla f{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^k}$

$(14)$

${\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k} + {\lambda _k}{\mathit{\boldsymbol{q}}^k}} \right) \le 0,j \in I$

$(15)$

令d^k=q^k，t_k=λ_k.

步5 (迭代更新) 令x^k+1=x^k+t_kd^k，更新正定对称矩阵B_k+1，k=k+1.返回步1.

3. 算法的可行性和收敛性分析

算法A需要以下理论的支持.

假设A

(A1) 迭代序列{x^k}⊆X非空且位于 ${\mathbb{R}}$ ⁿ中的有界闭凸子集内；

(A2) 对任意的x∈ ${\mathbb{R}}$ ⁿ，向量组{▽c_j(x)，j∈I(x)}是线性无关的；

(A3) ∀k，B_k∈ ${\mathbb{R}}$ ⁿ是一个n阶对称正定矩阵且{B_k}一致有界；

(A4) 目标函数f(x)和约束违反度函数h(x)都是二次连续可微的.

(A5) 存在两个常数0＜a≤b，使得a‖d‖²≤d^TB_kd≤b‖d‖²，∀k，∀d∈ ${\mathbb{R}}$ ⁿ.

由于集合L_k⊆I的有限性，不妨设存在无穷子列K，使得

${\mathit{\boldsymbol{x}}^k} \to {\mathit{\boldsymbol{x}}^ * },{\mathit{\boldsymbol{B}}_k} \to {\mathit{\boldsymbol{B}}_ * },{L_k} \equiv L,k \in K$

其中L为一个固定指标集.记A_*，Q_*，P_*，π^*，V^*，d₀^*，d^*，q^*分别为式(3)-(7)中各式在x^*处以B_*代替B(x^*)的相应各量，则A_k→A_*，Q_k→Q_*，P_k→P_*，d₀^k→d₀^*，q^k→q^*，k∈K，k→∞.

引理1 对任意的迭代指标k，算法1步1(b)和步1(c)之间的循环有限步终止.

证利用反证法.

假设算法在步1(b)和步1(c)之间无限循环，则由算法结构知，

$\begin{array}{*{20}{c}} {\det \left( {\mathit{\boldsymbol{A}}_k^{\rm{T}}{\mathit{\boldsymbol{A}}_k}} \right) \le \frac{1}{{{2^i}}}{\sigma _0}}&{i = 1,2, \cdots } \end{array}$

由L_k，i的定义有

${L_{k,i}} \supseteq {L_{k,i + 1}}$

又集合I是个有限集，从而对充分大的i有

${L_{k,i}} = {L_{k,i + 1}}$

并定义为L_k^*.令i→∞，则

$\begin{array}{*{20}{c}} {\det \left( {\mathit{\boldsymbol{A}}_k^{\rm{T}}{\mathit{\boldsymbol{A}}_k}} \right) = 0}&{J_k^ * = I\left( {{\mathit{\boldsymbol{x}}^k}} \right)} \end{array}$

这与假设(A2)矛盾.

引理2 若假设A满足且迭代点x^k∈X，则有下列结论成立

1) x^k是问题(1)的K-T点当且仅当d₀^k=0.

2) 若x^k不是问题(1)的K-T点，则d^k仍是问题(1)在点x^k处的一个可行下降方向，即有

$\nabla f{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}\mathit{\boldsymbol{d}}_0^k \lt 0,\nabla f{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^k} \le - \frac{1}{2}\mathit{\boldsymbol{\rho }}_k^2 \lt 0,{\left( {\mathit{\boldsymbol{g}}_j^k} \right)^{\rm{T}}}\mathit{\boldsymbol{d}}_0^k \le 0,{\left( {\mathit{\boldsymbol{g}}_j^k} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^k} \lt 0,j \in I\left( {{\mathit{\boldsymbol{x}}^k}} \right)$

证参考文献[7]中定理1的证明.

引理3^[7] 对于算法1产生的序列{x^k}，设x^*是它的任意一个聚点.若x^k+1=x^k+t_kd^k均由步4和步5产生，且x^*不是问题(1)的K-T点，则有

$\begin{array}{*{20}{c}} {\nabla f{{\left( {{\mathit{\boldsymbol{x}}^ * }} \right)}^{\rm{T}}}{\mathit{\boldsymbol{q}}^ * } \lt 0,{\mathit{\boldsymbol{g}}_j}{{\left( {{\mathit{\boldsymbol{x}}^ * }} \right)}^{\rm{T}}}{\mathit{\boldsymbol{q}}^ * } \lt 0,j \in I\left( {{\mathit{\boldsymbol{x}}^ * }} \right)}\\ {{\lambda _k} \ge {\lambda _ * } = \inf \left\{ {{\lambda _k}} \right\} \gt 0,k \in K} \end{array}$

引理4 算法是可执行的.

证只需证明在假设A成立的前提下，当k充分大时，算法不再执行步4.由算法知，只需证明由步4产生的迭代点也一定能被滤子接受.假设算法不能有限步终止，则有t_k→0，k→∞，且新的迭代点x^k+1=x^k+t_kq^k不能被滤子接受.下面分两种情况讨论.

1) 若h_k=0.由h(x)的定义可得，

${h_{k + 1}} = \max \left\{ {0,{\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right)} \right\} = \max \left\{ {0,{\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right) + {t_k}{{\left( {\mathit{\boldsymbol{g}}_j^k} \right)}^{\rm{T}}}{\mathit{\boldsymbol{q}}^k} + O{{\left\| {{t_k}{\mathit{\boldsymbol{q}}^k}} \right\|}^2}} \right\}$

由引理1知，

${\left( {\mathit{\boldsymbol{g}}_j^k} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^k} \lt 0$

结合t_k→0，k→∞，则存在一个常数β，使得

${h_{k + 1}} \le \max \left\{ {0,\beta {\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right)} \right\} \le \beta {h_k}$

$(16)$

再由式(14)和引理2知

$f\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right) \le f\left( {{\mathit{\boldsymbol{x}}^k}} \right) + v{\lambda _k}\nabla f{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^k} \le f\left( {{\mathit{\boldsymbol{x}}^k}} \right) - v{\lambda _k}\frac{1}{2}\mathit{\boldsymbol{\rho }}_k^2 \le f\left( {{\mathit{\boldsymbol{x}}^k}} \right) - c\mathit{\boldsymbol{\rho }}_k^2,0 \lt \mathit{\boldsymbol{c}} \lt 1$

故

$f\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right) \le f\left( {{\mathit{\boldsymbol{x}}^k}} \right)$

$(17)$

由式(16)-(17)可知新的迭代点x^k+1=x^k+t_kq^k能被滤子和x^k接受.矛盾.

2) 若h_k≠0.类似于情况(1)，可得h_k+1≤βh_k.由于x^k被滤子接受，所以有

${h_k} \le \beta {h_j}\;或\;{f_k} \le {f_j} - \gamma {h_j},\forall \left( {{h_j},{f_j}} \right) \in Z$

由假设迭代点x^k+1=x^k+t_kq^k不能被滤子接受，则有

${h_j} \ge {h_k}$

$(18)$

和

${f_j} - \gamma {h_j} \ge {f_k} - \gamma {h_k}$

$(19)$

对于点x^k，若h_k≤βh_i成立，则由引理1知，

${\left( {\mathit{\boldsymbol{g}}_j^k} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^k} \lt 0$

结合t_k→0，k→∞，则存在一个常数β，使得

${h_{k + 1}} = \max \left\{ {0,{\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right)} \right\} \le \max \left\{ {0,{\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right)} \right\} \le {h_k} \le \beta {h_j}$

这与式(18)矛盾.

对于点x^k，若f_k≤f_j-βh_j成立，则由引理1知，

${\left( {\mathit{\boldsymbol{g}}_j^k} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^k} \lt 0$

结合t_k→0，k→∞，则存在一个常数β，使得

$f\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right) = f\left( {{\mathit{\boldsymbol{x}}^k}} \right) + {t_k}\nabla f{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^k} + O\left( {{{\left\| {{t_k}{\mathit{\boldsymbol{q}}^k}} \right\|}^2}} \right) \le {f_j} - \beta {h_j}$

这与式(19)矛盾.

综上分析，当k充分大时，算法不再执行步4，即算法是有效的.

引理5^[9] 考虑{x^k}是进入滤子集的无穷序列，与其对应的h(x^k)＞0且{f(x^k)}有下界，则

$\mathop {\lim }\limits_{k \to \infty } h\left( {{\mathit{\boldsymbol{x}}^k}} \right) = 0$

引理6^[9] 1)如果有无限多个点被添加到滤子集中，则

$\mathop {\lim }\limits_{k \to \infty } h\left( {{\mathit{\boldsymbol{x}}^k}} \right) = 0$

2) 如果有有限多个点被添加到滤子集中，则存在一个k₁，使得当k＞k₁时，有

$\mathop {\lim }\limits_{k \to \infty } h\left( {{\mathit{\boldsymbol{x}}^k}} \right) = 0$

引理7 按式(6)计算的主方向d^k满足‖d^k‖~‖d₀^k‖，‖d₁^k‖=O(‖d₀^k‖²).

证由算法1步4中λ_k的取法易知，当k充分大时，有λ_k≡1，此时x^k+1=x^k+d^k.当j∈I_*时有

$\begin{array}{l} {\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right) = {\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k} + {\mathit{\boldsymbol{d}}^k}} \right) = {\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k} + \mathit{\boldsymbol{d}}_0^k + \mathit{\boldsymbol{d}}_1^k} \right) = \\ {\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k} + \mathit{\boldsymbol{d}}_0^k} \right) + {\left( {\mathit{\boldsymbol{g}}_j^k} \right)^{\rm{T}}}\mathit{\boldsymbol{d}}_1^k + O\left( {{{\left\| {\mathit{\boldsymbol{d}}_1^k} \right\|}^2}} \right) = {\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k} + \mathit{\boldsymbol{d}}_0^k} \right) + {\left( {\mathit{\boldsymbol{g}}_j^k} \right)^{\rm{T}}}\mathit{\boldsymbol{d}}_1^k + O\left( {{{\left\| {\mathit{\boldsymbol{d}}_0^k} \right\|}^3}} \right) \end{array}$

而

$\mathit{\boldsymbol{A}}_k^{\rm{T}}\mathit{\boldsymbol{d}}_1^k = - {\left\| {\mathit{\boldsymbol{d}}_0^k} \right\|^\tau }\mathit{\boldsymbol{e}} - \mathit{\boldsymbol{F}}\left( {{\mathit{\boldsymbol{x}}^k} + \mathit{\boldsymbol{d}}_0^k} \right),故\;{\mathit{\boldsymbol{g}}_j}{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}\mathit{\boldsymbol{d}}_1^k = - {\left\| {\mathit{\boldsymbol{d}}_0^k} \right\|^\tau } - {\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k} + \mathit{\boldsymbol{d}}_0^k} \right)$

所以，

${\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right) = {\mathit{\boldsymbol{c}}_j}\left( {{\mathit{\boldsymbol{x}}^k} + {\mathit{\boldsymbol{d}}^k}} \right) = - {\left\| {\mathit{\boldsymbol{d}}_0^k} \right\|^\tau } + O\left( {{{\left\| {\mathit{\boldsymbol{d}}_0^k} \right\|}^3}} \right),\tau \in \left( {2,3} \right)$

从而当k充分大时有，

$\left\| {\mathit{\boldsymbol{d}}_1^k} \right\| = O\left( {{{\left\| {\mathit{\boldsymbol{d}}_0^k} \right\|}^2}} \right),\left\| {{\mathit{\boldsymbol{d}}^k}} \right\| \sim \left\| {\mathit{\boldsymbol{d}}_0^k} \right\|$

定理1 在假设A成立的前提下，算法1或有限次迭代终止于问题(1)的一个K-T点x^k，或产生一个无穷迭代序列{x^k}，使得它的任意一个聚点x^*是问题(1)的K-T点.

证若算法1终止于点x^k，则d₀^k=0.故由引理2可知迭代点x^k是问题(1)的K-T点.即证明了定理1的前半部分.下面假设x^*为无穷迭代序列{x^k}的任意一个聚点，不妨设当k→∞时有x^k→x^*，k∈K，其中K为无穷指标集.下面分情况讨论.

1) 若存在一个无穷序列K₁⊆K，使得迭代点x^k+1=x^k+t_kd^k均由算法1步2和步3产生.结合引理5、引理6知 $\mathop {\lim }\limits_{k \to \infty }$ h(x^k)=0.若 $\mathop {\lim }\limits_{k \in {K_1}, k \to \infty }$ d^k‖=0，则易知x^*是一个K-T点.由 $\mathop {\lim }\limits_{k \to \infty } h\left( {{\mathit{\boldsymbol{x}}^k}} \right) = 0$ 和假设A中的(A5)可设存在一个k₀，使得当k＞k₀，k∈K₁，有 $h\left( {{\mathit{\boldsymbol{x}}^k}} \right) \le \frac{{a{\varepsilon ^2}}}{{2M}} \le \frac{{a{{\left\| {{\mathit{\boldsymbol{d}}^k}} \right\|}^2}}}{{2M}} \le \frac{{{{\left( {{\mathit{\boldsymbol{d}}^k}} \right)}^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{d}}^k}}}{{2M}}$ ，结合K-T条件，对所有的k＞k₀，k∈K₁有

$\begin{array}{l} \nabla f{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{d}}^k} = - {\left( {{\mathit{\boldsymbol{d}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{d}}^k} - {\left( {{\mathit{\boldsymbol{d}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{A}}_k}{\omega _k} = - {\left( {{\mathit{\boldsymbol{d}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{d}}^k} - \omega _k^{\rm{T}}\mathit{\boldsymbol{c}}\left( {{\mathit{\boldsymbol{x}}^k}} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; - {\left( {{\mathit{\boldsymbol{d}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{d}}^k} + {\left\| {{\omega _k}} \right\|_\infty }h\left( {{\mathit{\boldsymbol{x}}^k}} \right) \le Mh\left( {{\mathit{\boldsymbol{x}}^k}} \right) - {\left( {{\mathit{\boldsymbol{d}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{d}}^k} \le \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; - 0.5{\left( {{\mathit{\boldsymbol{d}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{d}}^k} \le - 0.5a{\left\| {{\mathit{\boldsymbol{d}}^k}} \right\|^2} \end{array}$

其中ω_k为拉格朗日乘子.从而，

$\begin{array}{l} 0 = \mathop {\lim }\limits_{k \in {K_1},k \to \infty } \left( {f\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right) - f\left( {{\mathit{\boldsymbol{x}}^k}} \right)} \right) = \\ \;\;\;\;\;\mathop {\lim }\limits_{k \in {K_1},k \to \infty } \left( {{t_k}\nabla f{{\left( {{\mathit{\boldsymbol{x}}^k}} \right)}^{\rm{T}}}{\mathit{\boldsymbol{d}}^k} + O\left( {{{\left\| {{t_k}{\mathit{\boldsymbol{d}}^k}} \right\|}^2}} \right)} \right. \le \\ \;\;\;\;\;\mathop {\lim }\limits_{k \in {K_1},k \to \infty } {t_k}\nabla f{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{d}}^k} \le 0 \end{array}$

因此

$\mathop {\lim }\limits_{k \in {K_1},k \to \infty } \left\| {{\mathit{\boldsymbol{d}}^k}} \right\| = 0$

再结合引理7可得

$\mathop {\lim }\limits_{k \in {K_1},k \to \infty } \left\| {\mathit{\boldsymbol{d}}_0^k} \right\| = 0$

而

$\mathop {\lim }\limits_{k \in {K_1},k \to \infty } \mathit{\boldsymbol{d}}_0^k = \mathit{\boldsymbol{d}}_0^ *$

因此，根据引理2的证明，可证x^*是问题(1)的一个K-T点.

2) 若存在一个无穷序列K₁⊆K，使得若迭代点x^k+1=x^k+t_kd^k均由算法1步4和步5产生，反设x^*不是问题(1)的一个K-T点，则由引理3知

$\nabla f{\left( {{\mathit{\boldsymbol{x}}^ * }} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^ * } \lt 0,{\mathit{\boldsymbol{g}}_j}{\left( {{\mathit{\boldsymbol{x}}^ * }} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^ * } \lt 0,j \in I\left( {{\mathit{\boldsymbol{x}}^ * }} \right),{\lambda _k} \ge {\lambda _ * } = \inf \left\{ {{\lambda _k}} \right\} \gt 0,k \in K$

再由式(14)知

$0 = \mathop {\lim }\limits_{k \in {K_1},k \to \infty } \left( {f\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right) - f\left( {{\mathit{\boldsymbol{x}}^k}} \right)} \right) \le \mathop {\lim }\limits_{k \in {K_1},k \to \infty } v{\lambda _k}\nabla f{\left( {{\mathit{\boldsymbol{x}}^k}} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^k} \le 0.5v{\lambda _ * }\nabla f{\left( {{\mathit{\boldsymbol{x}}^ * }} \right)^{\rm{T}}}{\mathit{\boldsymbol{q}}^ * } \lt 0$

这是一个矛盾.因此x^*是问题(1)的一个K-T点.

4. 数值实验

在这一部分从数值计算的角度进一步说明本文给出的算法的有效性，算法的编程使用MATLAB软件.算法中涉及的参数取值如下：

${\sigma _0} = 0.01,\xi = 0.01,\varepsilon = 0.05,v = 0.1,\tau = 2.25,\delta = 2.5,\gamma = 0.05,\beta = 0.95,{\mathit{\boldsymbol{B}}_0} = I \in {\mathbb{R}^{n \times n}}$

B_k的更新选自BFGS公式修正^[10]：

${\mathit{\boldsymbol{B}}_{k + 1}} = BFGS\left( {{\mathit{\boldsymbol{B}}_k},{\mathit{\boldsymbol{s}}^k},{\mathit{\boldsymbol{y}}^k}} \right)$

其中：

${\mathit{\boldsymbol{s}}^k} = {\mathit{\boldsymbol{x}}^{k + 1}} - {\mathit{\boldsymbol{x}}^k},{{\mathit{\boldsymbol{\hat y}}}^k} = \nabla f\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right) - \nabla f\left( {{\mathit{\boldsymbol{x}}^k}} \right) + \sum\limits_{j = 1}^m {\mathit{\boldsymbol{\mu }}_j^k\left( {{\mathit{\boldsymbol{g}}_j}\left( {{\mathit{\boldsymbol{x}}^{k + 1}}} \right) - {\mathit{\boldsymbol{g}}_j}\left( {{\mathit{\boldsymbol{x}}^k}} \right)} \right)} ,\\{\mathit{\boldsymbol{y}}^k} = \theta {{\mathit{\boldsymbol{\hat y}}}^k} + \left( {1 - \theta } \right){\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{s}}^k}$

$\theta = \left\{ {\begin{array}{*{20}{c}} 1&{如果{{\left( {{{\mathit{\boldsymbol{\hat y}}}^k}} \right)}^{\rm{T}}}{\mathit{\boldsymbol{s}}^k} \ge 0.2{{\left( {{\mathit{\boldsymbol{s}}^k}} \right)}^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{s}}^k}}\\ {\frac{{0.8{{\left( {{\mathit{\boldsymbol{s}}^k}} \right)}^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{s}}^k}}}{{{{\left( {{\mathit{\boldsymbol{s}}^k}} \right)}^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{s}}^k} - {{\left( {{{\mathit{\boldsymbol{\hat y}}}^k}} \right)}^{\rm{T}}}{\mathit{\boldsymbol{s}}^k}}}}&{否则} \end{array}} \right.$

而乘子函数μ(x)=-(N(x)^TN(x)+D(x))^-1N(x)^T▽f(x)，其中N(x)=(g_j(x)，j∈I)，D(x)=diag(c_j²(x)，j∈I).终止准则为‖d₀^k‖＜10^-6.

从文献[11]中选取了7个测试问题，对本文的算法进行测试，测试结果见表 1.

表 1 本文算法与文献[11]的数值结果

问题编号	n	m	X⁰	NF₁	NG₁	NIT₁	NF₂	NG₂	NIT₂
hs012	2	1	(0，0)^T	10	8	7	13	60	12
hs033	3	6	(0，0，3)^T	4	4	3	142	159	48
hs043	4	3	(0，0，0，0)^T	19	12	11	19	12	11
hs076	4	3	(0.5，0.5，0.5，0.5)^T	7	7	6	17	48	13
hs100	7	4	(1，2，0，4，0，1，1)^T	37	19	18	65	113	23
hs110	10	20	(9，9，9，9，9，9，9，9，9，9)^T	10	8	9	8	16	8
hs113	10	8	(2，3，5，5，1，2，7，3，6，10)^T	25	15	14	62	204	33

| Show Table

DownLoad: CSV

表 1问题编号即测试问题在文献[11]中的编号，n表示问题中变量的维数，m表示问题中约束的维数，X⁰表示问题的初始点，NF₁，NF₂分别表示本文算法和文献[11]的目标函数和约束函数的计算次数，NG₁，NG₂分别表示本文算法和文献[11]的梯度的计算次数，NIT₁，NIT₂分别表示本文算法和文献[11]的算法的迭代次数.

从上述分析可看出，本文给出的修正共轭投影梯度滤子算法是有效可行的.将共轭投影技术引入到滤子算法使得该算法不需要求解二次规划子问题，而且能有效避免常规滤子算法中的恢复算法，简化了计算.

表 1 本文算法与文献[11]的数值结果

问题编号	n	m	X⁰	NF₁	NG₁	NIT₁	NF₂	NG₂	NIT₂
hs012	2	1	(0，0)^T	10	8	7	13	60	12
hs033	3	6	(0，0，3)^T	4	4	3	142	159	48
hs043	4	3	(0，0，0，0)^T	19	12	11	19	12	11
hs076	4	3	(0.5，0.5，0.5，0.5)^T	7	7	6	17	48	13
hs100	7	4	(1，2，0，4，0，1，1)^T	37	19	18	65	113	23
hs110	10	20	(9，9，9，9，9，9，9，9，9，9)^T	10	8	9	8	16	8
hs113	10	8	(2，3，5，5，1，2，7，3，6，10)^T	25	15	14	62	204	33

下载: 导出CSV

[1]	FLETCHER R, LEYFFER S. Nonlinear Programming Without a Penalty Function[J]. Mathematica Programming, 2002, 91(2):239-269. doi: 10.1007/s101070100244
[2]	NIE P Y. Composite-Step like Filter Methods for Equality Constriant Problems[J]. Journal of Computational Mathematics, 2003, 21(5):613-624.
[3]	苏珂, 刘英.求解非线性规划的修正滤子信赖域方法[J].数学学报(中文版), 2009, 52(6):1157-1164. doi: http://d.old.wanfangdata.com.cn/Periodical/sxxb200906014
[4]	王祥玲, 朱志斌, 杨萌.一种基于步长的SQP滤子法[J].应用数学, 2010, 23(3):670-674. doi: http://d.old.wanfangdata.com.cn/Periodical/yingysx201003030
[5]	WANG X L, ZHU Z B, ZUO S Y, et al. An SQP-Filter Method for Inequality Constrained Optimization and Its Global Convergence[J]. Applied Mathematics and Computation, 2011, 217(24):10224-10230. doi: 10.1016/j.amc.2011.05.019
[6]	HUANG Q Q, ZHU Z B, WANG X L. A Predictor-Corrector Algorithm Combined Conjugate Gradient with Homotopy Interior Point for General Nonlinear Programming[J]. Applied Mathematics and Computation, 2013, 219(9):4379-4386. doi: 10.1016/j.amc.2012.10.036
[7]	朱志斌, 张可村.一个新的共轭投影梯度算法及其超线性收敛性[J].应用数学学报, 2004, 27(1):149-161. doi: 10.3321/j.issn:0254-3079.2004.01.017
[8]	王祥玲, 朱志斌, 周志轩.共轭投影梯度滤子算法及其全局收敛性[J].桂林电子科技大学学报, 2012, 32(6):496-498. doi: 10.3969/j.issn.1673-808X.2012.06.017
[9]	doi: http://d.old.wanfangdata.com.cn/NSTLQK/10.1137-S105262340038081X/ FLETCHER R, LEYFFER S, TOINT P L. On the Global Convergence of a Filter-SQP Algorithm[J]. SIAM Journal on Optimization, 2002, 13(1):44-59.
[10]	袁亚湘, 孙文瑜.最优化理论与方法[M].北京:科学出版社, 1997:232-238.
[11]	HOCK W, SCHITTKOWSKI K. Test Examples for Nonlinear Programming Codes[J]. Journal of Optimization Theory and Applications, 1980, 30(1):127-129. doi: 10.1007/BF00934594
[12]	柳馨.两个修正的DL共轭梯度法[J].重庆工商大学学报(自然科学版), 2017, 34(5):13-18. doi: http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=yzdxxb-zr201705003

表( 1)

计量

文章访问数: 2045
HTML全文浏览数: 1719
PDF下载数: 153
施引文献: 0

全文HTML

本文考虑如下非线性规划问题：

其中：x∈ ${\mathbb{R}}$ ⁿ，f： ${\mathbb{R}}$ ⁿ $\longrightarrow$ ${\mathbb{R}}$ ，c_j(j∈I)： ${\mathbb{R}}$ ⁿ $\longrightarrow$ ${\mathbb{R}}$ 是二次连续可微的.可行集X={x∈ ${\mathbb{R}}$ ⁿ|c_j(x)≤0，j∈I}，有效集I(x)={j∈I|c_j(x)=0}.

非线性规划问题广泛应用于工程和社会生活的各个领域，并在其中起着举足轻重的作用.非线性规划问题的求解主要是最优性和可行性.为了使这两个规则都能满足，算法需要在迭代过程中每一步都保持这两种规则的平衡.目前关于非线性规划问题的求解方法多种多样^[1-12].近年来，滤子法引起很多学者的密切关注.滤子法最早由Fletecher和Leyffer提出^[1]，它能有效避免选择罚函数的困难且具有良好的数值结果，从而近年来被广泛应用于各种优化问题的求解中^[2-6].共轭投影梯度算法是解决非线性规划问题的另外一种有效算法^[7].文献[8]将SQP方法和广义投影技巧结合，提出一个具有显式主搜索方向的共轭投影梯度算法，有效地简化了算法结构及计算工作量.为此，在文献[8]的基础上，本文提出一个修正的共轭投影梯度算法.该方法保证了每个试探点都不会远离可行域，同时在合适的条件下证明了算法的收敛性.

1. 相关理论知识

1.1. 相关符号

对于问题(1)的近似解x^k∈X，σ_k＞0，正定矩阵B_k=B(x^k)，集合L_k⊆I，为了便于讨论给出以下记号：

本文算法引用了文献[7]提出的共轭投影梯度技术，并采用文献[7]中定义的以下各量：

定义1^[7] 如果函数μ(x)： ${\mathbb{R}}$ ⁿ $\longrightarrow$ ${\mathbb{R}}$ ^m满足以下条件：

1) μ(x)连续.

2) 当x^*是问题(1)的K-T点时，μ(x^*)为相应的K-T乘子.则称μ(x)为乘子函数.

1.2. 滤子技术

滤子技术能很好地平衡目标函数和约束条件，对于每次迭代，试探点被接受当且仅当约束违反度函数值或目标函数值相对于当前的滤子集中的点有充分的下降.

本文定义约束违反度函数为

其中

易知h(x)=0的充要条件是保证迭代点x是可行点，所以试探点应该使得约束违反度函数值降低或目标函数值减小.为了保证这两项至少有一项满足，参照文献[1]引入滤子的相关定义.

定义2  称点x¹支配点x²当且仅当

定义3  滤子为具有形式为(h_i，f_i)的点集Z，使得任意点不能被其他点支配，即h(xⁱ)≤h(x^j)或f(xⁱ)≤f(x^j)对所有的i≠j成立.

在实际计算中，为了获得全局收敛性，需要添加一些条件，如文献[1]中定义了一个“包络”来阻止点任意接近滤子.从而有以下滤子准则：

定义4  一个点被滤子接受当且仅当对任意的(h_j，f_j)∈Z有

其中：h_j=h(x^j)；f_j=f(x^j)；0＜γ＜β＜1且γ→0，β→1.

在算法的进程中需要将(h_j，f_j)对添加到滤子中，如果一个点x^k被滤子集Z接受，则令x^k+1=x^k+t_kd^k且滤子按如下的规则更新

其中

事实上，这里“点x被滤子集Z接受”严格上说是将(h_j，f_j)对添加到滤子集中.如果点x^k被滤子集接受或者已在滤子集中，那么满足

的点x也是被滤子接受的.

2. 算法模型

算法1

步0 (初始化)  给定x⁰∈ ${\mathbb{R}}$ ⁿ，μ(x⁰)∈ ${\mathbb{R}}$ ^m，B₀是对称正定矩阵，选择σ₀，ξ，ε，v∈(0，1)，τ∈(2，3)，δ＞2且α₁，α₂，η∈(0，1)，t₀=1，初始化滤子集Z₀，并令k=0.

步1 (有效集L_k)

(a) 令i=0，σ_k，i=σ₀；

(b) 若det(A_k^TA_k)＞σ_k，i，令L_k=L_k，i，i_k=i，转步2，否则转步1(c)，其中：

(c) 令i=i+1，σ_k，i=0.5σ_k，i-1，返回步1(b).

步2 (搜索方向)  通过式(2)-(5)获得d₀^k.若d₀^k=0，则获得一个K-T点，停止.否则，通过式(6)计算d^k.

若

则转步3.否则，转步4.

步3 (滤子准则)  若x^k+t_kd^k不被滤子接受，则令x^k+1=x^k，t_k+1=0.5t_k，k=k+1，转步4.若x^k+t_kd^k被滤子接受，则令x^k+1=x^k+d^k，f_k+1=f(x^k+d^k)，h_k+1=h(x^k+d^k)，并去除那些被x^k+1支配的点，更新滤子集Z_k+1，转步5.

步4 (线搜索)  通过式(7)获得q^k，取 $\left\{ {1, \frac{1}{2}, \frac{1}{4}, \cdots } \right\}$ 的最大值为λ_k，使其满足

令d^k=q^k，t_k=λ_k.

步5 (迭代更新)  令x^k+1=x^k+t_kd^k，更新正定对称矩阵B_k+1，k=k+1.返回步1.

3. 算法的可行性和收敛性分析

算法A需要以下理论的支持.

假设A

(A1) 迭代序列{x^k}⊆X非空且位于 ${\mathbb{R}}$ ⁿ中的有界闭凸子集内；

(A2) 对任意的x∈ ${\mathbb{R}}$ ⁿ，向量组{▽c_j(x)，j∈I(x)}是线性无关的；

(A3) ∀k，B_k∈ ${\mathbb{R}}$ ⁿ是一个n阶对称正定矩阵且{B_k}一致有界；

(A4) 目标函数f(x)和约束违反度函数h(x)都是二次连续可微的.

(A5) 存在两个常数0＜a≤b，使得a‖d‖²≤d^TB_kd≤b‖d‖²，∀k，∀d∈ ${\mathbb{R}}$ ⁿ.

由于集合L_k⊆I的有限性，不妨设存在无穷子列K，使得

其中L为一个固定指标集.记A_*，Q_*，P_*，π^*，V^*，d₀^*，d^*，q^*分别为式(3)-(7)中各式在x^*处以B_*代替B(x^*)的相应各量，则A_k→A_*，Q_k→Q_*，P_k→P_*，d₀^k→d₀^*，q^k→q^*，k∈K，k→∞.

引理1  对任意的迭代指标k，算法1步1(b)和步1(c)之间的循环有限步终止.

证  利用反证法.

假设算法在步1(b)和步1(c)之间无限循环，则由算法结构知，

由L_k，i的定义有

又集合I是个有限集，从而对充分大的i有

并定义为L_k^*.令i→∞，则

这与假设(A2)矛盾.

引理2  若假设A满足且迭代点x^k∈X，则有下列结论成立

1) x^k是问题(1)的K-T点当且仅当d₀^k=0.

2) 若x^k不是问题(1)的K-T点，则d^k仍是问题(1)在点x^k处的一个可行下降方向，即有

证  参考文献[7]中定理1的证明.

引理3^[7]  对于算法1产生的序列{x^k}，设x^*是它的任意一个聚点.若x^k+1=x^k+t_kd^k均由步4和步5产生，且x^*不是问题(1)的K-T点，则有

引理4  算法是可执行的.

证  只需证明在假设A成立的前提下，当k充分大时，算法不再执行步4.由算法知，只需证明由步4产生的迭代点也一定能被滤子接受.假设算法不能有限步终止，则有t_k→0，k→∞，且新的迭代点x^k+1=x^k+t_kq^k不能被滤子接受.下面分两种情况讨论.

1) 若h_k=0.由h(x)的定义可得，

由引理1知，

结合t_k→0，k→∞，则存在一个常数β，使得

再由式(14)和引理2知

故

由式(16)-(17)可知新的迭代点x^k+1=x^k+t_kq^k能被滤子和x^k接受.矛盾.

2) 若h_k≠0.类似于情况(1)，可得h_k+1≤βh_k.由于x^k被滤子接受，所以有

由假设迭代点x^k+1=x^k+t_kq^k不能被滤子接受，则有

和

对于点x^k，若h_k≤βh_i成立，则由引理1知，

结合t_k→0，k→∞，则存在一个常数β，使得

这与式(18)矛盾.

对于点x^k，若f_k≤f_j-βh_j成立，则由引理1知，

结合t_k→0，k→∞，则存在一个常数β，使得

这与式(19)矛盾.

综上分析，当k充分大时，算法不再执行步4，即算法是有效的.

引理5^[9]  考虑{x^k}是进入滤子集的无穷序列，与其对应的h(x^k)＞0且{f(x^k)}有下界，则

引理6^[9]  1)如果有无限多个点被添加到滤子集中，则

2) 如果有有限多个点被添加到滤子集中，则存在一个k₁，使得当k＞k₁时，有

引理7  按式(6)计算的主方向d^k满足‖d^k‖~‖d₀^k‖，‖d₁^k‖=O(‖d₀^k‖²).

证  由算法1步4中λ_k的取法易知，当k充分大时，有λ_k≡1，此时x^k+1=x^k+d^k.当j∈I_*时有

而

所以，

从而当k充分大时有，

定理1  在假设A成立的前提下，算法1或有限次迭代终止于问题(1)的一个K-T点x^k，或产生一个无穷迭代序列{x^k}，使得它的任意一个聚点x^*是问题(1)的K-T点.

证  若算法1终止于点x^k，则d₀^k=0.故由引理2可知迭代点x^k是问题(1)的K-T点.即证明了定理1的前半部分.下面假设x^*为无穷迭代序列{x^k}的任意一个聚点，不妨设当k→∞时有x^k→x^*，k∈K，其中K为无穷指标集.下面分情况讨论.

1) 若存在一个无穷序列K₁⊆K，使得迭代点x^k+1=x^k+t_kd^k均由算法1步2和步3产生.结合引理5、引理6知 $\mathop {\lim }\limits_{k \to \infty }$ h(x^k)=0.若 $\mathop {\lim }\limits_{k \in {K_1}, k \to \infty }$ d^k‖=0，则易知x^*是一个K-T点.由 $\mathop {\lim }\limits_{k \to \infty } h\left( {{\mathit{\boldsymbol{x}}^k}} \right) = 0$ 和假设A中的(A5)可设存在一个k₀，使得当k＞k₀，k∈K₁，有 $h\left( {{\mathit{\boldsymbol{x}}^k}} \right) \le \frac{{a{\varepsilon ^2}}}{{2M}} \le \frac{{a{{\left\| {{\mathit{\boldsymbol{d}}^k}} \right\|}^2}}}{{2M}} \le \frac{{{{\left( {{\mathit{\boldsymbol{d}}^k}} \right)}^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{d}}^k}}}{{2M}}$ ，结合K-T条件，对所有的k＞k₀，k∈K₁有

其中ω_k为拉格朗日乘子.从而，

因此

再结合引理7可得

而

因此，根据引理2的证明，可证x^*是问题(1)的一个K-T点.

2) 若存在一个无穷序列K₁⊆K，使得若迭代点x^k+1=x^k+t_kd^k均由算法1步4和步5产生，反设x^*不是问题(1)的一个K-T点，则由引理3知

再由式(14)知

这是一个矛盾.因此x^*是问题(1)的一个K-T点.

4. 数值实验

在这一部分从数值计算的角度进一步说明本文给出的算法的有效性，算法的编程使用MATLAB软件.算法中涉及的参数取值如下：

B_k的更新选自BFGS公式修正^[10]：

其中：

而乘子函数μ(x)=-(N(x)^TN(x)+D(x))^-1N(x)^T▽f(x)，其中N(x)=(g_j(x)，j∈I)，D(x)=diag(c_j²(x)，j∈I).终止准则为‖d₀^k‖＜10^-6.

从文献[11]中选取了7个测试问题，对本文的算法进行测试，测试结果见表 1.

表 1问题编号即测试问题在文献[11]中的编号，n表示问题中变量的维数，m表示问题中约束的维数，X⁰表示问题的初始点，NF₁，NF₂分别表示本文算法和文献[11]的目标函数和约束函数的计算次数，NG₁，NG₂分别表示本文算法和文献[11]的梯度的计算次数，NIT₁，NIT₂分别表示本文算法和文献[11]的算法的迭代次数.

从上述分析可看出，本文给出的修正共轭投影梯度滤子算法是有效可行的.将共轭投影技术引入到滤子算法使得该算法不需要求解二次规划子问题，而且能有效避免常规滤子算法中的恢复算法，简化了计算.

参考文献 (12)

姓名

邮箱

手机号码

标题

留言内容

验证码
	验证码错误！

留言板

修正共轭投影梯度滤子法

1.
宜春幼儿师范高等专科学校初等教育学院, 江西宜春 330814

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

作者简介:
王祥玲(1986-), 女, 讲师, 主要从事最优化理论研究 .

A Modified Conjugate Projection Gradient Filter Method

1.
Primary Education College, Yichun Early Childhood Teachers College, Yichun Jiangxi 330814, China

2.
Department of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China

1. 相关理论知识

1.1 相关符号

1.2 滤子技术

2. 算法模型

3. 算法的可行性和收敛性分析

4. 数值实验

计量

修正共轭投影梯度滤子法

作者简介: 王祥玲(1986-), 女, 讲师, 主要从事最优化理论研究
1. 宜春幼儿师范高等专科学校初等教育学院, 江西宜春 330814

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

English Abstract

A Modified Conjugate Projection Gradient Filter Method

全文HTML

1.1. 相关符号

1.2. 滤子技术

目录

全文HTML

1.1. 相关符号

1.2. 滤子技术

留言板

修正共轭投影梯度滤子法

1. 宜春幼儿师范高等专科学校 初等教育学院, 江西 宜春 330814 2. 桂林电子科技大学 数学与计算科学学院, 广西 桂林 541004

作者简介: 王祥玲(1986-), 女, 讲师, 主要从事最优化理论研究 .

A Modified Conjugate Projection Gradient Filter Method

1. Primary Education College, Yichun Early Childhood Teachers College, Yichun Jiangxi 330814, China 2. Department of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China

1. 相关理论知识

1.1 相关符号

1.2 滤子技术

2. 算法模型

3. 算法的可行性和收敛性分析

4. 数值实验

计量

出版历程

修正共轭投影梯度滤子法

作者简介: 王祥玲(1986-), 女, 讲师, 主要从事最优化理论研究 1. 宜春幼儿师范高等专科学校 初等教育学院, 江西 宜春 330814 2. 桂林电子科技大学 数学与计算科学学院, 广西 桂林 541004

English Abstract

A Modified Conjugate Projection Gradient Filter Method

全文HTML

1.1. 相关符号

1.2. 滤子技术

目录

全文HTML

1.1. 相关符号

1.2. 滤子技术

1.
宜春幼儿师范高等专科学校初等教育学院, 江西宜春 330814

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

作者简介:
王祥玲(1986-), 女, 讲师, 主要从事最优化理论研究 .

1.
Primary Education College, Yichun Early Childhood Teachers College, Yichun Jiangxi 330814, China

2.
Department of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China

作者简介: 王祥玲(1986-), 女, 讲师, 主要从事最优化理论研究
1. 宜春幼儿师范高等专科学校初等教育学院, 江西宜春 330814

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