Operations Research and Fuzziolgy 运筹与模糊学, 2013, 3, 1-6 http://dx.doi.org/10.12677/orf.2013.31001 Published Online February 2013 (http://www.hanspub.org/journal/orf.html) Subgradient Algorithm for a Form of Mixed Variational Inequalities Chao Zheng, Hongyou Yin, Yuanping Wang College of Sciences, Nanjing University of Aeronautics and Astronautics, Nanjing Email: xuzhouzhengchao@sina.com, zhengchao_math@163.com Received: Dec. 9th, 2012; revised: Jan. 7th, 2013; accepted: Jan. 18th, 2013 Abstract: This paper studies a form of mixed variational inequalities problem. When disturbance function is nonsmooth, the optimal condition of these mixed variational inequalities is proposed. Then subgradient is of- fered and its convergence is proved. Keywords: Mixed Variational Inequalities; Nonsmooth; Optimal Condition; Subgradient 一类混合变分不等式的次梯度法 郑 超,殷洪友,王园萍 南京航空航天大学理学院,南京 Email: xuzhouzhengchao@sina.com, zhengchao_math@163.com 收稿日期:2012 年12 月9日;修回日期:2013年1月7日;录用日期:2013年1月18日 摘 要:本文研究了一类混合变分不等式问题.在扰动泛函非光滑的情况下,给出了这类混合变分不等 式的最优性条件,设计了次梯度算法,并证明了该算法的收敛性。 关键词:混合变分不等式;非光滑;最优性条件;次梯度法 1. 引言 “变分不等式”是计算数学与运筹学的一个交叉研究领域,与非线性规划、互补问题、最优化理论、广 义方程、对策论、不动点理论等分支有密切的联系。它作为一类数学模型应用在如力学、工程学、经济学和 运筹学等诸多领域。对于经典的Hartman-Stampacchia 变分不等式的理论与算法方面的研究可见文献[1]和文献 [2]。设 是一个实线性空间, n R,, n x xxx R, K 是中的一个闭凸锥,映射 n R:n f KR,: F KR 是中的凸泛函,本文考虑广泛应用在弹性塑料学领域的混合变分不等式问题[3]:求 n R x K ,使得 ,0, x xfxFx FxxK (1) 显然,若F是零泛函,则(1)就是经典 Hartman变分不等式:求 x K ,使得 ,0, x xfx xK 混合变分不等式问题比一般的变分不等式问题更加具有代表性,从而研究混合变分不等式问题具有更广 泛的适用范围。对于混合变分不等式问题的研究一般分为理论与算法,前者主要研究解的存在性、唯一性; 后者则主要建立在有效的算法及收敛性分析。文献[4]给出了在 Banach 空间混合变分不等式与 F-互补问题的 等价性,文献[5]提供了混合变分不等式的投影算法,文献[6]假设扰动泛函F非光滑的情况下,给出了投影梯 度算法。 Copyright © 2013 Hanspub 1 郑超 带有非自治项的非线性 Schrödinger 方程的基态解的存在性 本文在扰动泛函非光滑的情况下,第二章给出了所需的定义和引理,第三章证明了这类混合变分不等式问 题的最优性条件,第四章设计了次梯度算法并对算法的收敛性进行了理论证明。 本文记凸规划问题:求 x K ,使得 min xK PxFxPx Fx (2) 2. 预备知识 定义 2.1 设 是非空凸集,若 n R ,0 ,则称 是锥。若还有 ,则称 是凸锥。 定义 2.2 设n K R是非空开凸集, f 是 K 上的凸函数, x K ,称集合 ,, n f xvRfyfxvyxyK 是 f 在 x 处的次微分,称 是 vfx f 在 x 处的次梯度。 定义 2.3 设n K R是非空开凸集且 0 x K ,记 00 0, x vxx xK ,则称 00 x x 是 在点 K0 x 处的可行方向锥。 定义 2.4 设 是锥,则集合 n R ,0, n yR xyx 称为 的共轭锥。 引理 2.1 设 f 是 K 上的凸函数,则 f 在 K 的每一点都上半连续。 引理 2.2[7] 假设 ,若Pf x 是(1)的解,且 P 是凸函数,则 x 是(2)的解;反之,若 x 是(2)的解,则 x 也 是(1)的解。 3. 最优性条件 为方便叙述,本节记凸规划问题: min ,min xK xK x f xFxPxFx (3) 定理 3.1 x K 是(3)的最优解当且仅当 ,1 min;; 0 gxg Pxg Fxg (4) 证:设 x 是(3)的最优解,若(4)不成立,则存在单位向量 0 g x ,使得 00 00 00 ;;lim lim PxgPxFxgFx Pxg Fxg 0 由极限的保号性,存在 00 ,使得 00 0 0, 0, PxgPxFxgFx 即 00 ,0,Px gFx gPxFx0 由于 0 g x ,因此 0,0, g xx xK 于是当 充分小时有 01 x gxxxx xK 这与 x 是(3)的最优解矛盾。 反之,设(3)成立, , x Kx x ,有 Copyright © 2013 Hanspub 2 郑超 带有非自治项的非线性 Schrödinger 方程的基态解的存在性 max ,max, max ,max, vPx uFx vPx uFx Px Fx Pxvx xFxux x xx xx Pxx xvFxx xu xx xx (5) 记0 x x g x x ,则 01g,且 0 g x ,有(4)和(5)得 00 00 00 00 00 00 ,1 ,1 00 ,1 max ,max, ;; min ;min; min ;; vPx uFx gxg gxg gxg Px Fx Px xxvgFx xxug PxxxPxgFxxxFxg PxxxP x gFxxxFx g PxFxxxP x gFx g Px Fx 即 x 是(3)的最优解。 引理 3.1 设 是闭凸集,且,令 n CRfr C 1 min sup,,min,min fr gvC vC vg dvv vC 则a)当 时,有 0dd ;b)当 时,有 0d 。 证:a) 当时,有0d0C ,从而存在 0 vC ,使 0 min vC dv v, 即 是在 上的投影,于是 0 v0xC2 00 ,,vvvv C。 令0 0 0 v gv ,即 00 ,,vgvvC , 从而 00 1 minsup ,sup , gvC vC vgvgv d . 另一方面, , n gRg 1,有 00 0 sup ,, vC vgv gvgvd 。 从而 0.vd 综上所述,有 0 vd 。 b) 当 ,有,从而 0d0C1 min sup,0 gvC vg 。 如果 0 f r C,则 0 ,由边界点的凸集分离定理,存在单位向量 0 n g R,使得 0 ,0,vgv C,从而 0 0sup,vg 0 ,因此 0 C 。 vC 如果 ,则,于是0intC 0S , n gRg1,有 0 max ,supvg , vS vC vg , 从而 1 min sup, gvC vg 。 以下证明 。 如果 ,则 ,则存在向量,使 0SS 00 v 00vS ,但 0 vC ,根据凸集分离定理,存在单位 Copyright © 2013 Hanspub 3 郑超 带有非自治项的非线性 Schrödinger 方程的基态解的存在性 向量 0 n g R和数 0 ,使得 00 ,,vvg vC 。 于是 000 0 1 minsup ,sup ,, gvC vC vgvgv gv ,即 0 v ,这与 相矛盾,因此 00vS 。 推论 3.1 在引理 1的条件下,如果 0 00 0 min 0, vC v vvdg v ,则 00 sup , vC vgv d 。 推论 3.2 在引理 1的条件下, 000dC 。 引理 3.2 设是紧凸集,是闭凸锥, n BRn R 是 的共轭锥,令 ,1 1 ,minmax,,min sup, gg g vB vC C Bvgvg 则 。 证:已知 是紧凸集,则B 12 12 sup ,max,max, vB v vC vgvgvg 。 当 时,有g 2,vg0,从而 2 2 max ,0 v vg 。 当 时,则存在,使g 2 v 2,0vg , 从而 2 22 2 sup ,,,, v vg vgvg ,于是 1 1 max, , sup , , vB vC vgg vg g , 因此 1,1 min sup,minmax, ggg vB vC vg vg 。 推论 3.3 在引理 3.2 的条件下,如果sup , vC vg ,则 g 且sup ,max , vB vC vg vg 。 定理 3.2 设 x K 是凸规划(3)的最优解当且仅当 0 f xFx x 。 证:在引理3.2 中取 ,,BPxFxxCB ,注意到 ,Pxxf x 以及 的光滑性, 则 ,1 1 ,1 min;;minmax,min sup, gg g gxg fx vBfx vC Pxg Fxgfxvgfxvg 。 是凸规划(3)的最优解的充要条件是 ,1 min;; 0 gxg Pxg Fxg , 根据定理3.1, x 即0 。根据推论 3.2,有000dC 。于是 x 是凸规划问题(3)的最优解 0 f xFx x 。 推论 3.4 设int x K ,则 x 是(3)的最优解当且仅当 0fx Fx 。 设0 x 不是(3)的最优解,根据定理 3.2,有 00 0fx Fxx 0 0 ,于是存在向量 , 00 vFx 0 wx ,使得 00 0000 , min 0 vFx wx dxfxv wfxvw 0 。 定义 3.1 设0 x K不是(3)的最优解,若存在单位向量 00 g x ,使得 0 00 0000 ,1 ;;min; gxg PxgFxgPxg Fxg ; 则称 0 g 是(3)在0 x 处的最速下降方向。 定理 3.3 设0 x K不是(3)的最优解,向量 000 ,vFxw x 0 满足条件 00 0000 , min 0 vFx wx dxfxv wfxvw 0 Copyright © 2013 Hanspub 4 郑超 带有非自治项的非线性 Schrödinger 方程的基态解的存在性 则 000 0 000 f xvw g f xvw 是(3)在0 x 处的最速下降方向,且 0000 ,;dxfxgFxg 0 证:设 00 0 ,,Bfx FxxCB ,根据引理 3.2,有 00 00 0 ,1 ,1 min,;min max, gxgg gfx vB fx gFxgfxvg 由于 0 x 不是最优解,则 00ddx。 根据推论3.1 有 0 00 sup , fx vC fx vgd 。 根据推论3.3 有 00 g x ,且 0 0 0 000000000 0 sup,max,,max ,,; fxvBv Fx fx vC 0 f xvgfxvg fxgvg fxgFxg 。 因此 0 0 00000 000 ,1 ,;sup ,min, gxg fx vC ; f xgFxgfxvgfxgFxg ,即 0 g 是(3)的最速下 降方向。 4. 算法及收敛性 算法 Step1 取初始点 ,选取数列 0,xKk0 k 满足 ; 0 0, 0,, kk k k k Step2 若 0kk k f xFx x ,则停止;否则,转 Step3; Step3 计算向量 , kkk vFxw x k ,满足 , min 0 kk kkkk vFx wx dxfx vwfx vw k 并且计算 kkk k kkk f xvw g f xvw ; Step4 令1kkkk x xg ,,转 Step2。 1kk 引理 4.1 是单调映射。 F 定理 4.1 设 f 是单调映射, k x 是由算法4.1 产生的点列,若 k x 不是凸规划问题的解,则对任意(3)的解 x , 且 kkk k g fxxx F,必存在常数 ,使得0 k T 1,0, kk k xxx T x ;且若凸规划问题有 最优解,则 k x 的任一极限点都是凸规划问题的解;若还有扰动泛函 F 是严格凸函数,则混合变分不等式有唯 一的最优解。 证:注意到 ,0 kkk k g fx Fxxfx Fxx ,且由 F 的单调性可知 ,0 kk k gfx fxxx 即 ,, kkk k gx xfxfxx x 0 直接计算 222 2 12, kkkkkkkkk x xxgxxx gxx 。 Copyright © 2013 Hanspub 5 郑超 带有非自治项的非线性 Schrödinger 方程的基态解的存在性 Copyright © 2013 Hanspub 6 若取 2, kkk g xx ,则有 1kk x xxx 。 令2, kkk Tgxx ,则 ,且0 k T1kk x xxx , 从而序列 k x 有界,则必存在聚点,下证 k x 的任一聚点都是凸规划问题(3)的解。 设 i k x 是 k x 的任一收敛子列,且 limi k i x x ,从而有 0ii kk i k f xFx x 于是 0 f xFx x 。 即 x 是凸规划问题(3)的最优解。当扰动 泛函 F 为严格凸函数时,凸规划问题有唯一解,从而混合变分不等 式只有唯一解。 5. 结论 本文通过将混合变分不等式问题转化为凸规划问题,在扰动泛函 F非光滑的情况下,给出了混合变分不等 式的最优性条件,设计了次梯度算法并证明了该算法的收敛性。从算法步骤可以看出,次梯度算法迭代简单, 比较容易实现,在每一迭代点处只要能够计算到目标函数次微分中一个元素就可以。另一方面,次梯度法不需 要线搜索,步长 k 事先给出,只要满足条件 0 0, 0,, kkk k k 即可。在这里,条件 是要使点列 0 k k k x 全局收敛所必须的。但是作为最早提出的非光滑优化算法,次 梯度法有许多不足之处,一是收敛速度慢;二是次梯度法甚至不是下降方向。所以是否可以在迭代过程中通过 预测–校正的思想进行调整,从而加快迭代速度也有待深入探索。最后,作者对审稿人提出的修改意见表示感 谢。 参考文献 (References) [1] P. T. Harker, J. S. Pang. Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications. Mathematica Programming, 1900, 48(2): 161-220. [2] F. Facchinei, J. S. Pang. Finite-dimensional variational inequalities and complementarity problems. New York: Springer-Verlag, 2003. [3] W. Han, B. Reddy. On the finite element method for mixed variational inequalities arising in elastoplasticity. SIAM Journal on Numerical Analysis, 1995, 32(6): 1778-1807. [4] 殷洪友, 徐成贤, 张忠秀. F-互补问题及其与极小元问题的等价性[J]. 数学学报, 2001, 4: 679-686. [5] 何诣然. 一个关于混合变分不等式问题的投影算法[J]. 数学物理学报, 2007, 27A(2): 215-220. [6] 唐国吉, 黄南京. 非Lipschitz 集值混合变分不等式的一个投影次梯度法法[J]. 应用数学和力学, 2011, 32(10): 1254-1263. [7] 李娟. F-互补问题的算法设计[D]. 南京航空航天大学, 2010. [8] 韩继业, 修乃华, 戚厚铎. 非线性互补理论与算法[M]. 上海: 上海科学技术出版社, 2006. [9] 高岩. 非光滑优化[M]. 北京: 科学出版社, 2008. |