Advances in Applied Mathematics
Vol.
11
No.
11
(
2022
), Article ID:
58068
,
10
pages
10.12677/AAM.2022.1111840
椭圆最优控制问题的修改交替方向乘子 计算方法
林继桐
广东工业大学数学与统计学院,广东 广州
收稿日期:2022年10月16日;录用日期:2022年11月10日;发布日期:2022年11月21日
摘要
本文研究了具有混合控制–状态约束的椭圆最优控制问题。我们采用有限元法离散化连续型最优化问题,并使用由正定矩阵诱导的范数作为非精项,近似计算经典交替方向乘子算法中的子问题,由此提出了修改的交替方向乘子(mADMM)算法。此外我们证明了mADMM算法的全局收敛性和收敛速率。最后,利用数值例子来验证提出的理论结果。
关键词
最优控制问题,交替方向乘子算法,收敛性分析
A Modified Alternating Direction Method of Multipliers Algorithm for Elliptic Optimal Control Problem
Jitong Lin
School of Mathematics and Statistics, Guangdong University of Technology, Guangzhou Guangdong
Received: Oct. 16th, 2022; accepted: Nov. 10th, 2022; published: Nov. 21st, 2022
ABSTRACT
In this paper, an elliptic optimal control problem with mixed control-state constraint is considered. The finite element method is used to discretize the continuous optimization problem. And the norm induced by a positive definite matrix is used as the inexact term to approximate the subproblem in the classical alternating direction method of the multipliers algorithm. And a modified alternating direction method of multipliers (mADMM) algorithm is proposed. In addition, the global convergence and convergence rate of mADMM algorithm are proven. Finally, a numerical example demonstrates the theoretical results.
Keywords:Optimal Control Problem, Alternating Direction Method of Multipliers, Convergence Analysis
Copyright © 2022 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
早在60年代初,最优控制理论出现了众多的研究方法。其中极大值原理,动态规划和变分法奠定了最优控制理论基础。近年偏微分方程最优控制问题成为了国内外研究热点之一,它在癌症检查 [1],捕鱼模型 [2] 和致动器设计 [3] 等领域起着重要的作用。随着研究不断深入,具有混合约束的偏微分方程最优控制问题也逐渐引起研究员关注。一般的,这类最优控制问题的解析解都难以获得,即使可以求出解析解,但在工业设计上也难以实现,从而,如何获得既接近解析解又方便计算的数值解变得尤其重要。
离散–优化是处理偏微分方程最优控制问题的有效思路。有限元法作为一种成熟的偏微分方程数值方法,在离散化连续型最优控制问题中也发挥着重要作用,并且有大量文献 [4] [5] [6] 讨论了有限元法在离散化椭圆最优控制问题时的收敛性。对于离散的最优控制问题,文献 [7] 使用交替方向乘子算法进行计算数值解,并对多种偏微分约束情况进行讨论,最后给出了该算法全局收敛性证明。文献 [8] 考虑带控制 范数代价的椭圆最优控制问题,提出具有非精确结构的交替方向乘子算法,并证明该算法的全局收敛性及其收敛速率。文献 [9] 采用了原对偶主动集方法作交替方向乘子算法的后处理器来提高计算精度。文献 [10] 研究了一类具有点态约束的椭圆最优控制问题,采用Lavrentiev正则化处理状态约束后,使用有限元法离散该问题,并在有限维线性空间上使用非精确的交替方向乘子算法进行计算。文献 [11] 采用“优化–离散–优化”策略,提出了一种叫多级交替方向乘子算法,并给出该算法的收敛性及其收敛速率证明。
基于以上研究,本文采用有限元法离散化具有混合控制–状态约束的椭圆最优控制问题,在有限维空间上提出mADMM算法计算离散最优控制问题的解。
2. 主要问题和预备知识
在下文的讨论中我们设 为 空间上的范数, 为 或 上的范数,由正定矩阵 诱导范数为 ,。
本文主要关注使用mADMM算法解决以下椭圆最优控制问题:
(1)
其中 为Laplace算子, , 和 是一个开、凸区域,有着多边形边界 。函数 已给定, 和 为给定参数。由文献 [7] [10] 可知最优控制问题(1)存在唯一解 。根据偏微分方程知识我们可知,存在连续线性单射 ,使得 。从而,我们把最优控制问题(1)转化成以下最优化问题:
(2)
其中 ,I为恒等算子。
我们使用有限元法对最优化问题(2)进行离散。对区域 进行均匀三角分割,并获得节点集合 和有限元空间 ,其中 为分片线性函数。我们选用插值算子 为
.
由此我们得到离散的最优化问题:
(3)
其中 ,, 为离散化的S算子。我们不妨设最优化问题(3)的解为 ,由文献 [4] [10] 可知当网格测度 时,我们有 。
令 ,则在有限元空间 中的任意元素 可以表示为 ,其中 。根据有限元法的知识我们得到刚度矩阵K和质量矩阵M分别为
和 ,
其中 为梯度算子。因为,刚度矩阵K是对称半正定矩阵,质量矩阵M是对称正定矩阵,从而 是可逆矩阵。利用刚度矩阵K和质量矩阵M我们得到最优化问题(3)的矩阵–向量形式:
(4)
其中 ,,,,,E为单位矩阵。由于 是强凸函数,X为有界闭紧凸集,从而最优化问题(4)的解必定存在且唯一,记作 。
3. 正定误差近似交替方向乘子算法
本节提出mADMM算法来计算凸优化问题(4),并讨论了该算法的全局收敛性和收敛速率。
首先,我们把凸优化问题(4)转化成线性约束优化问题。令集合 和定义指
示函数
,
为了方便,我们设
和 ,
则凸优化问题(4)等价于以下线性约束优化问题:
. (5)
根据线性束优化问题(5),易得其增广Lagrange函数为
,
其中 是Lagrange乘子。在增广Lagrange函数的基础上,我们提出mADMM算法如下:
输入初始数值 ,惩罚参数 ,停机误差 和任意对称正定矩阵W。令迭代次数 。
输出 。
步骤1计算 如下式所示:
. (6)
步骤2计算 如下式所示:
. (7)
步骤3计算 如下式所示:
. (8)
步骤4计算误差
若 时停止计算,并输出 ,否则,令 回到步骤1继续计算。
3.1. mADMM算法的收敛性
为了证明mADMM算法的收敛性,我们需要以下符号:
, 和 ,
序列 由(6)~(8)计算所得。由于最优化问题(4)的解是存在且唯一的,同样地线性约束优化问题(5)的解也是唯一的,由此我们可以得到线性约束优化问题(5)的一阶最优条件:
定理3.1设 为线性约束优化问题(5)的解,当且仅当存在Lagrange乘数 ,使得下面的条件
, ,
, ,
,
成立。
根据定理3.1,我们可以把线性约束优化问题(5)转化为变分不等式问题:找 使得
, , (9)
其中
, 和 。
根据文献 [12],我们可以推导得到以下不等式:
, , (10)
, , (11)
由不等式(10)和(11),我们可以证明mADMM算是全局收敛的,并有以下定理。
定理3.2 设序列 中的每个元素由(6)~(8)计算所得,则
.
证明由(10)我们可得
.
利用三角不等式可得
.
从而, 为有界序列,则在 上必存在收敛子列 。假设任意收敛子列收敛到 ,即 ,根据(11)我们易得 。选择 ,当 时,根据等式(6)~(8)的连续性我们有
, (12)
, (13)
. (14)
由(12)和(14),利用变分法我们可得
, .
同理根据(13)和(14),我们有
, .
把上述两不等式相加,并根据等式(14),我们有
, .
上述不等式意味着 是变分不等式问题(9)的解。我们已知变分不等式问题(9)等价于线性约束优化问题(5),从而 。由于序列 为有界序列且任意收敛子列都收敛到 ,则定理得证。
3.2. mADMM算法的收敛速率
基于定理3.1我们定义函数 ,
,
其中 表示函数 在点z上的次微分, 。由 ,可以推导得 。由此,我们用 的快慢来估计mADMM算法的收敛速率。
定理3.3 设序列 中的每个元素由(6)~(8)计算所得,则
.
证明由函数 的定义,易得
.
根据(6)和(7),我们有
,
.
把上述两式代入 ,并利用(8)可得
.
由于在有限维空间上任意范数都是等价的,则存在 ,使得
.
根据(10)和定理3.2可推导得
.
上述不等式意味着正项级数 收敛,根据文献 [13] 的Lemma 6.1,定理3.3得证。
4. 数值例子
我们使用文献 [10] 中的Example 2来验证本文的结论。在这个例子中我们设 , 和 。在网格测度 时,我们在图1到图4中展示了用mADMM算法计算的结果与真实解的对比。在网格测度 时,我们在图5中给出误差 随迭代次数增加的收敛性结果。
Figure 1. Numerical control
图1. 数值控制
Figure 2. Exact control
图2. 真实控制
Figure 3. Numerical state
图3. 数值状态
Figure 4. Exact state
图4. 真实状态
从图1到图4中我们很难比较得出数值解与真实解的差异,从而这个例子反应了我们提出的mADMM算法是收敛的。
图5表明,在本例中经过近20次迭代后,mADMM算法的收敛速率明显快于ADMM算法,在接近100次迭代后,这两种算法的误差系数 都会在10-26的量级上下浮动,并且这两种算法趋向0的速度会比序列 趋向0的速度要快,这也表明了(11)的合理性。
Figure 5. Iteration error
图5. 迭代误差
4. 结论
本文利用有限元法对具有混合控制–状态约束的椭圆最优控制问题进行离散化,并提出mADMM算法来求解 空间上的离散最优化问题。此外,验证了mADMM算法具有全局收敛性,并给出该算法的收敛速率。值得注意的是,我们可以通过选择不同的正定矩阵W来减少mADMM算法的迭代次数,这样可以提高算法的计算速度。因此,“如何选择最优的正定矩阵?”将会是我们继续研究的对象。
文章引用
林继桐. 椭圆最优控制问题的修改交替方向乘子计算方法
A Modified Alternating Direction Method of Multipliers Algorithm for Elliptic Optimal Control Problem[J]. 应用数学进展, 2022, 11(11): 7936-7945. https://doi.org/10.12677/AAM.2022.1111840
参考文献
- 1. Abdulla, U.G., Bukshtynov, V. and Seif, S. (2021) Cancer Detection through Electrical Impedance Tomography and Optimal Control Theory: Theoretical and Computational Analysis. Mathematical Biosciences and Engineering, 18, 4834-4859. https://doi.org/10.3934/mbe.2021246
- 2. Grass, D., Uecker, H. and Upmann, T. (2019) Optimal Fishery with Coastal Catch. Natural Resource Modeling, 32, e12235. https://doi.org/10.1111/nrm.12235
- 3. Ciambella, J. and Tomassetti, G. (2020) A Form-Finding Strategy for Magneto-Elastic Actuators. International Journal of Non-Linear Mechanics, 119, Article ID: 103297. https://doi.org/10.1016/j.ijnonlinmec.2019.103297
- 4. Casas, E. (1985) L^2 Estimates for the Finite Element Method for the Dirichlet Problem with Singular Data. Numerische Mathematik, 47, 627-632. https://doi.org/10.1007/BF01389461
- 5. Hinze, M. and Meyer, C. (2010) Variational Discretization of Lavrentiev-Regularized State Constrained Elliptic Optimal Control Problems. Computational Optimization and Applications, 46, 487-510. https://doi.org/10.1007/s10589-008-9198-1
- 6. Ciarlet, P.G. (1978) The Finite Element Method for Elliptic Problems. North-Holland, Amsterdam.
- 7. Zhang, K., Li, J.S., Song, Y.C. and Wang, X.S. (2017) An Alternating Direction Method of Multipliers for Elliptic Equation Constrained Optimization Problem. Science China Mathematics, 60, 361-378. https://doi.org/10.1007/s11425-015-0522-3
- 8. Song, X.L., Yu, B., Wang, Y.Y. and Zhang, X.P. (2018) An FE-Inexact Heterogeneous ADMM for Elliptic Optimal Control Problems with L^1-Control Cost. Journal of Systems Science and Complexity, 31, 1659-1697. https://doi.org/10.1007/s11424-018-7448-6
- 9. Song, X.L. and Yu, B. (2017) A Two-Phase Strategy for Control Constrained Elliptic Optimal Control Problems. Numerical Linear Algebra with Applications, 25, e2138. https://doi.org/10.1002/nla.2138
- 10. Chen, Z.X., Song, X.L., Zhang, X.P. and Yu, B. (2019) A FE-ADMM Algorithm for Lavrentiev-Regularized State-Con- strained Elliptic Control Problem. ESAIM-Control Optimisation and Calculus of Varuations, 25, Article No. 5. https://doi.org/10.1051/cocv/2018019
- 11. Chen, X.T., Song, X.L., Chen, Z.X. and Yu, B. (2020) A Multi-Level ADMM Algorithm for Elliptic PDE-Constrained Optimization Problems. Computational and Applied Mathematics, 39, Article No. 331. https://doi.org/10.1007/s40314-020-01379-1
- 12. He, B.S. and Yuan, X.M. (2015) On Non-Ergodic Convergence Rate of Douglas-Rachford Alternating Direction Method of Multipliers. Numerische Mathematik, 130,567-577. https://doi.org/10.1007/s00211-014-0673-6
- 13. Chen, L., Sun, D.F. and Toh, K.-C. (2017) An Efficient Inexact Symmetric Gauss-Seidel Based Majorized ADMM for High-Dimensional Convex Composite Conic Programming. Mathematical Programming, 161, 237-270. https://doi.org/10.1007/s10107-016-1007-5