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

高 新，袁健華

?

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

高 新，袁健華

（北京郵電大學(xué)校理學(xué)院，北京 100876）

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

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

0 引言

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

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

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

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

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

1 模型問題

1.1 模型問題

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

1.2 模型解的存在及唯一性

引理1.1的證明在文獻(xiàn)[9]中已經(jīng)提到，這里就不予證明。

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

成立。

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

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

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

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

原方程：

伴隨方程（對(duì)偶方程）：

變分不等式：

2 變分和有限元離散

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

2.1 變分問題

2.2 有限元離散

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

3. 有限元空間。令：

4. 有限元離散形式。

5. 基函數(shù)的選取。

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

原約束條件的離散形式：

伴隨方程（對(duì)偶方程）的離散形式：

變分不等式的離散形式：

3 原對(duì)偶方法和交替方向乘子法

3.1 原對(duì)偶方法

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

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

3.2 交替方向乘子法

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

接下來解決下列的鞍點(diǎn)問題：

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

（2）交替迭代計(jì)算：

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

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

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

（2）交替迭代計(jì)算：

4 數(shù)值實(shí)驗(yàn)

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

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

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

圖1 算法一的的數(shù)值解圖像

圖2 算法一的的誤差圖像

圖3 算法一和算法三的收斂速率對(duì)數(shù)圖像

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

圖4 算法二的的數(shù)值解圖像

圖5 算法二的的誤差圖像

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

5 結(jié)論

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

圖6 算法二和算法四的收斂速率對(duì)數(shù)圖像

[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] 陳小翠, 張小峰. 求解一維對(duì)流擴(kuò)散方程的一種新方法[J]. 武漢大學(xué)學(xué)報(bào), 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] 王烈衡, 許學(xué)軍. 有限元方法的數(shù)學(xué)基礎(chǔ)[M]. 科學(xué)出版社, 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]. 清華大學(xué)出版社, 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

國家自然科學(xué)基金項(xiàng)目(11671052, 11471052)；國家自然科學(xué)基金重大研究計(jì)劃(91630202)

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

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

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