用对角二次近似方法解凸分离问题*

士明军，黎 蕾

（重庆师范大学数学学院，重庆 400047）

1 引言与基础知识

对于一个函数f（x），最优解往往不容易得到，而且有时是无法得到.然而可以找一个和最优解近似的数来代替最优解，这就是近似最优解.序列近似最优化是解非线性规划问题的主要策略之一，它是构造一个序列x（k）去逼近最优解x*.

此处主要考虑下面一个非线性优化问题G，变量x=（x1，…，xn）T∈Rn，y=（y1，…，ya）T∈Ra.

下面给出问题G的子问题Gr［k］在x（k）的连续近似:

2 对角二次近似

文献［2］和［3］中给出一种对角二次近似［2，3］，借助这种方法，可以给出如下的形式

3 对偶问题

问题（2）中，如果所有的h2jp＞0且d2rq≥0或者h2jp≥0且d2rq＞0，则所有的子问题Gr［k］都是严格凸的.于是可以构造它的Falk对偶函数［5，6］，原问题的近似对偶子问题可以由式（4）给出

这样，把式（2）的带有等式和不等式约束的问题转化为式（4）中只需要确定m个λp和m个μq的非负约束的问题.定理1 当问题Gr［k］严凸时，满足如下的条件的λ和μ是稳定点

证明 当问题Gr［k］严凸时，解式（4）就等价于解问题Gr［k］.将式（4）右边进行一阶近似展开，其中只取 对x（λ）j的偏导数 对y（μ）r的偏导数，于是得到

由于gk（x）=0，所以将式（7）整理得

对式（8）两边分别对x（λ）j和y（μ）r求导，常数部分求导为0，于是得到

证毕.

下面通过对偶问题考虑原问题.由式（2）给出问题的解x（λ）和y（μ）的表示形式.

定理2 问题Gr［k］有如下形式的解，

证明 与定理1证明类似，将目标函数

二阶近似展开，化简、求导就得到了bj（λ）和cr（μ）.

4 算法

根据上面的推导，给定初始点（x0，y0），给出了一个求解问题G的算法，具体步骤如下:

3）构造（x（l），y（l））处的局部近似子问题Gr［l］，就解这一子问题得到（x（l*），λ（l*），y（l*），μ（l*））.

［1］GROENWOLD A A，ETMAN L F P，KOK S，et al.An augmented Lagrangian Approach to non-convex SAO using diagonal quadratic approximations［J］.Struct Multidiscipl Optim，2009（38）:415-421

［2］GROENWOLD A A，ETMAN L F P，SNYMAN J A，et al.Incomplete series expansion for function approximation［J］.Struct Multidisc Optim 2007（34）:21-40

［3］GROENWOLD A A，ETMAN L F P，SNYMAN J A，et al.Incomplete series expansion for function approximation［A］.In:Proc.sixth world congress on structural and multidisciplinary optimization［C］.Rio de Janeiro，Brazil，May，2005

［4］ JIANG T，PAPALAMBROS P Y.A first order method of moving asymptotes for structrural optimization［J］.Structrural Optimization，1999（10）:75-83

［5］FALK J E.Lagrangemultipliers and nonlinear programming［J］.JMAA，1967（19）:141-159

［6］GROENWOLD A A，ETMAN L F P.Sequential approximate optimization using dual subproblems based on incomplete series expansions［J］.Struct Multidisc Optim，2008（36）:547-570

［7］ GROENWOLD A A，ETMAN L F P，WOOD D W.Approximated approximations for SAO［J］.Struct Multidiscipl Optim，2010（41）:39-56