橢圓方程最優(yōu)控制問題的數值算法研究

高 新，袁健華

?

橢圓方程最優(yōu)控制問題的數值算法研究

高 新，袁健華

（北京郵電大學校理學院，北京 100876）

本論文引入原對偶方法（P-D）以及交替方向乘子法（ADMM）兩種算法求解橢圓方程約束的最優(yōu)控制問題，要討論的橢圓方程是一種對流擴散方程。論文解決了在無狀態(tài)約束和盒子約束的情況下對流擴散方程控制的問題。本文首先分析了最優(yōu)控制模型解的存在唯一性以及一階最優(yōu)性條件，隨后利用有限元方法將原始優(yōu)化模型轉換成優(yōu)化離散系統(tǒng)。此后，利用P-D以及ADMM分別求解離散優(yōu)化系統(tǒng)。ADMM是具有對偶上升法的可分解性以及乘子法的全局收斂性兩大優(yōu)勢的一階收斂算法，另外P-D也是具有全局收斂的一階收斂算法。本論文目的在于將P-D和ADMM兩種算法在收斂速率維度上進行比較。最后從數值實驗中得出ADMM的收斂速率快于P-D，證實了ADMM是一個高效的優(yōu)化算法。

最優(yōu)控制；橢圓方程約束；交替方向乘子法；原對偶方法；有限元

0 引言

偏微分方程（PDE）約束的最優(yōu)控制問題，起初是在80年代的法國數學家J.L.Lions的著作《Optimal control of systems governed by partial differential equations》中提出的[1]，現已成為非常受關注的交叉學科。偏微分方程約束的最優(yōu)控制問題有十分廣泛的應用，涵蓋了物理，化學，甚至工程設計領域，比如水庫管理，醫(yī)療器械的形狀優(yōu)化，天氣預報，熱現象，流體問題等。

為解決PDE最優(yōu)控制問題，很多學者已經提出了多種有效的算法，其中牛頓型迭代解法較為常見[2]。牛頓迭代解法具有局部二階收斂的性質，但是很多種牛頓迭代求解的方法對迭代初始點的選取非常嚴格[3]。所以如何選取具有全局收斂且收斂速度快的算法非常重要。

另外，無論用什么方法求解，約束條件中的偏微分方程需要借用適當的離散方法轉換成離散系統(tǒng)，在已有的大部分數值算法中控制變量和狀態(tài)變量是耦合在一起的，這樣就會消耗大量的計算資源去完成求解。

為了解決上述兩個問題，本文引入了交替方向乘子法(ADMM)。ADMM具有全局收斂性且在迭代求解過程中控制變量和狀態(tài)變量為交替迭代，從而大大減少了計算復雜度。在瀏覽文獻過程中，發(fā)現很少學者將ADMM算法用到解決PDE約束的最優(yōu)控制問題上。同時本文也引入了原對偶方法(P-D),它也是具有全局收斂性的有效算法,并且受到不少學者的青睞[4]。

本論文討論的偏微分方程是一種對流擴散方程[5]，對流擴散方程在環(huán)境科學，電子科學和流體力學等方面有著廣泛的應用。關于對流擴散方程的求解，目前已經取得了一系列的成果[6]。本文首次嘗試用上述兩種算法通過有限元離散求解由對流擴散方程約束的最優(yōu)控制問題。對兩種算法進行收斂速率的比較，經數值實驗證實了ADMM的高效性。

1 模型問題

1.1 模型問題

本文研究以下形式的最優(yōu)控制問題：

1.2 模型解的存在及唯一性

引理1.1的證明在文獻[9]中已經提到，這里就不予證明。

定理1.2 問題（1.2）在有、無控制約束條件下均存在全局最優(yōu)解。

成立。

1.3 一階最優(yōu)性條件

為了推導出最優(yōu)性條件，構造問題（1.1）的Lagrange函數：

一階最優(yōu)性條件滿足下列方程組：

故得到問題(1.1)的一階最優(yōu)性條件：

原方程：

伴隨方程（對偶方程）：

變分不等式：

2 變分和有限元離散

為了進行有限元離散，我們先要給出問題（1.1）的變分形式，再利用有限元離散，最終獲得離散優(yōu)化系統(tǒng)。

2.1 變分問題

2.2 有限元離散

接下來利用有限元離散，有限元離散的具體步驟如下[10]:

3. 有限元空間。令：

4. 有限元離散形式。

5. 基函數的選取。

同理一階最優(yōu)性條件的離散形式如下：

原約束條件的離散形式：

伴隨方程（對偶方程）的離散形式：

變分不等式的離散形式：

3 原對偶方法和交替方向乘子法

3.1 原對偶方法

算法一：無狀態(tài)約束條件的P-D算法

算法二：盒子約束條件的P-D算法

3.2 交替方向乘子法

交替方向乘子法（ADMM）算法是先離散后優(yōu)化的算法，它是基于很多優(yōu)化算法不斷優(yōu)化得來的，包括對偶上升法，對偶分解以及增廣拉格朗日乘子法，且ADMM具有全局收斂性[12]。

接下來解決下列的鞍點問題：

算法三：無狀態(tài)約束條件的ADMM算法

（2）交替迭代計算：

可知看出上述優(yōu)化系統(tǒng)與問題（2.4）是等價的。故對這個優(yōu)化系統(tǒng)進行ADMM求解。同樣，寫出增廣拉格朗日函數：

那么問題（1.1）在盒子約束條件下的ADMM算法步驟如下：

算法四：盒子約束條件的ADMM算法

（2）交替迭代計算：

4 數值實驗

數值實驗分為兩種情況，一種是問題（1.1）在無狀態(tài)約束條件下的情況，另一種是盒子約束的情況，每種情況又包括兩部分，分別是：

算例一:無狀態(tài)約束情況

從圖3易知算法三的收斂速率快于算法一的收斂速率，即ADMM的收斂速率快于P-D算法的收斂速率。

圖1 算法一的的數值解圖像

圖2 算法一的的誤差圖像

圖3 算法一和算法三的收斂速率對數圖像

算例二：有狀態(tài)約束條件（盒子約束）的情況

圖4 算法二的的數值解圖像

圖5 算法二的的誤差圖像

從圖6易看出算法四的收斂速率快于算法二的收斂速率，即ADMM的收斂速率要比P-D的收斂速率快。

5 結論

本論文首次嘗試用P-D以及ADMM兩種算法解決了由一種對流擴散方程約束的在有、無狀態(tài)約束條件情況下的最優(yōu)控制問題。雖然P-D和ADMM都是具有全局收斂的一階收斂算法，但是通過數值實驗可得出ADMM要比P-D算法的收斂速率快，因而證實了ADMM是一個高效的算法。

圖6 算法二和算法四的收斂速率對數圖像

[1] Lions J L. Optimal Control of Systems Governed by Partial Differential Equations[M].Springer-Verlag, New York-Berlin, 1971, 79.

[2] GUNZBURGER M D. Perspectives in Flow Control and Optimization[J]. Applied Mechanics Reviews, 2003, 56(6): B82-B83.

[3] KUNISCH K, WACHSMUTH D. Sufficient optimality conditions and semi-smooth Newton methods for optimal control of stationary variational inequalities[J]. ESAIM: Control, Optimisation and Calculus of Variations, 2012, 18(02): 520-547.

[4] BERGOUNIOUX M. Optimal Control of Problems Governed by Abstract Elliptic Variational Inequalities with State Constraints[J]. Siam Journal on Control & Optimization, 1998, 36(1): 273-289.

[5] 陳小翠, 張小峰. 求解一維對流擴散方程的一種新方法[J]. 武漢大學學報, 2014, 43(1): 10-13.

[6] IVANON M.Exact solutions of diffusion-convection equations[J].Dynamics of PDE,2008,5(2):139-171.

[7] REES T, DOLLAR H S,WATHEN A J. Optimal solvers for PDE-Constrained Optimization[J]. Siam Journal on Scientific Computing, 2010, 32(1): 271-298.

[8] EVANS L C. Partial Differential Equations[M]. Providence: Amer Math Soc, 2008.

[9] REYES J C D L. Numerical PDE-Constrained Optimization[M]. Springer International Publishing, 2001, 19(7): 121-163.

[10] 王烈衡, 許學軍. 有限元方法的數學基礎[M]. 科學出版社, 2007, 60-65.

[11] HEINKENSCHLOSS M. Numerical solution of implicitly constrained optimization problems[R]. Technical Report TR08-08, USA: Rise University, 1892, 1-22.

[12] ZHANG K, LI J S, SONG Y C, et al. An alternating direction method of multipliers for elliptic equation constrained optimization problem[J]. Science China Mathematics, 2017, 60(2): 1-18.

[13] 陳寶林. 最優(yōu)化理論與算法[M]. 清華大學出版社, 2005, 33-40.

[14] HE B S, YUAN X M. On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers[J]. Numerische Mathematik, 2015, 130(3): 567-577

[15] BOYD S, PARIKH N, CHU E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning.

Numerical Research on Constrained Optimization Problems Governed By Elliptic Equations

GAO Xin, YUAN Jian-hua

(Beijing University of Posts and Telecommunications, Beijing 100876, China)

In this paper, the primal-dual (P-D) methods and the alternating direction method of multipliers (ADMM) for solving the state constrained optimization problems, which is governed by elliptic equations, are investigated. The governing equations discussed is a kind of diffusion-convection equations. The unconstrained as well as box-constrained cases of the diffusion-convection equation control problems are solved in this work. The existence and uniqueness of the solution of the optimal control model is given, and the first-order optimality conditions is also mentioned firstly. Then the original optimal control problem can be converted into an optimized discrete system by using finite element methods. We solve the discrete optimization system by using P-D method and ADMM. The ADMM is a first order algorithm that has both the decomposability of the dual rise method and the global convergence of the multiplier method, while the P-D method is a first order algorithm with global convergence also. The purpose of this paper is to compare the primal-dual method with ADMM about the convergence rate. The numerical experiments in this paper are shown that the convergence rate of the ADMM is faster than P-D method, which means ADMM is an efficient optimization algorithm for the elliptic PDE-constrained optimization problems.

Optimal control problems; Elliptic equation constrained; Alternating direction method of multipliers; Primal-dual algorithm; Finite element method

O232

A

10.3969/j.issn.1003-6970.2018.07.012

國家自然科學基金項目(11671052, 11471052)；國家自然科學基金重大研究計劃(91630202)

高新(1993-)，女，研究生，PDE最優(yōu)控制。

袁健華(1979-)，教授，主要研究方向：有限元方法，微分方程數值解，最優(yōu)化算法。

本文著錄格式：高新，袁健華. 橢圓方程最優(yōu)控制問題的數值算法研究[J]. 軟件，2018，39（7）：57-62