鋼框架結構離散優化問題的理論下界

王興鋒 張氫 秦仙蓉 孫遠韜

摘要：針對兩種典型的鋼框架結構離散優化問題，即柔度約束的最小體積問題和體積約束的最小柔度問題，提出了基于凸組合的線性松弛方法，將關聯離散變量進行線性松弛，進而將非線性、非凸的離散優化問題轉化為松弛的凸規劃問題.其中，體積約束的最小柔度問題可松弛為二階錐規劃問題，柔度約束的最小體積問題可松弛為半定規劃問題.采用成熟的優化求解器，就可以得到兩類凸規劃問題的全局最優解，也就是原離散優化問題的理論下界.以一跨四層鋼框架的離散優化問題為例，用所提出方法進行求解，并用枚舉法和遺傳算法對優化結果進行驗證.數值結果證明，所提出方法可以快速得到離散優化問題的理論下界.

關鍵詞：鋼框架結構;離散優化;線性松弛;凸規劃;理論下界

中圖分類號：TU391? 文獻標志碼：A

Theoretical Lower Bound on DiscreteOptimization Problem of Steel Frame

WANG Xingfeng，ZHANG Qing?，QIN Xianrong，SUN Yuantao

（College of Mechanical Engineering，Tongji University，Shanghai 201804，China）

Abstract：Aiming at two typical discrete optimization problems of steel frame，namely， the volume minimization with compliance constraint and the compliance minimization with volume constraint，a linear relaxation approach based on convex combination is proposed. Meanwhile， the linked discreteness of design variables is also relaxed lin ? early， and the original nonlinear and nonconvex problems are recast as relaxed convex programming problems. Spe? cifically， the compliance minimization with volume constraint is reestablished as a second-order cone programming， and the volume minimization with compliance constraint is reformulated as a semidefinite programming. The global optimum solutions of two types of convex programming problems can be readily derived using existing mature optimi ? zation solvers. These global optimum solutions are also the theoretical lower bound for the discrete optimization prob ? lems. An example of a one-bay four-story frame is presented， and the results by the proposed approach are compared with the solutions by complete enumeration and genetic algorithm. The comparison demonstrates that the proposed approach is capable of achieving the theoretical lower bound in an efficient manner.

Key words：steel frames;discrete optimization;linear relaxation;convex programming;theoretical lower bound

在鋼框架結構的設計中，結構的桿件一般從標準型鋼庫中選取，通過組合得到滿足性能要求的最佳設計方案，因此，鋼框架結構的優化設計是一個典型的離散優化問題.

當前對鋼框架結構離散優化問題的研究，幾乎都側重于提出新的優化方法，以期獲得滿足工程精度要求的近似最優解.這些優化方法覆蓋了元啟發式算法[1-5]、優化準則法[6-7]、基于梯度的數學規劃方法[8-9]，但幾乎沒有研究能夠針對特定類型的鋼框架結構離散優化問題，明確指出優化方法的求解結果與全局最優解的距離.為確定優化算法的求解精度，一般做法是通過與多種優化方法的結果進行對比.這種論證方法只能粗略地說明優化算法的求解精度，而且需要廣泛地、有代表性地選取作為對比的優化算法.為證明某種優化算法的求解精度，一種更直接的方法是，獲取優化問題的全局最優解，或者優化問題的理論下限（假設優化問題為最小化問題）.盡管在工程實際問題中，由于約束的復雜性，幾乎不可能得到優化問題的全局最優解，但針對特定類型的鋼框架結構離散優化問題，還是有可能獲得全局最優解或理論下界.

在這方面，已經有少數學者展開了研究.針對含應力和位移約束、以體積最小為目標的鋼框架結構離散優化問題，Van等[10]提出了一種優化方法，通過將原優化問題建模為混合整數優化問題，從而得到離散優化問題的全局最優解.針對含體積約束、以柔度最小為目標的鋼框架結構離散拓撲-尺寸優化問題，Kanno[11]提出了一種混合整數二階錐規劃的建模方法，將原優化問題轉化為一個凸規劃問題，從而也得到了原問題的全局最優. kureta等[12]針對負泊松比的周期性框架結構的離散優化問題，提出了一種混合整數的線性規劃方法.Hirota等[13]將混合整數的線性規劃建模方法，進一步推廣到具有負熱膨脹能力的周期性框架結構的離散拓撲優化中.

在鋼框架結構中，桿件的截面參數包括截面寬度、高度、板厚，以及截面面積、強弱軸慣性矩等.對于標準型鋼截面，這些截面參數是相互關聯的，選定某一個截面參數則意味著同一截面的其他參數也被選中，故稱為關聯離散變量[14-15].在以上研究中[10-13]，關聯離散變量是通過0-1變量進行定義，以此來表征是否選擇了某個標準截面，對應的優化問題都是含0-1變量的凸規劃問題.對于此類優化問題，一般采用隱枚舉法（如分支定界法）進行求解，計算效率非常低，若結構中的桿件數量或可選的標準截面增多，計算效率會大幅下降.

有鑒于此，本文提出了一種新的離散變量處理方法，即基于凸組合的線性松弛方法.該方法將關聯離散變量進行線性松弛，從而將結構的剛度矩陣轉化為設計變量的線性函數，根據這一優勢，可以將鋼框架結構離散優化中的多種非線性優化問題進一步建模為凸規劃問題.本文重點分析了兩類非線性優化問題：柔度約束的最小體積問題和體積約束的最小柔度問題.根據剛度矩陣與設計變量的線性關系，將柔度約束的最小體積問題轉化為半定規劃問題，將體積約束的最小柔度問題轉化為二階錐規劃問題.采用現成的優化求解器，直接求解這兩類凸規劃問題，快速得到松弛問題的全局最優解，也就是離散優化問題的理論下界.

1離散變量的定義方法

在鋼框架結構的離散優化設計中，桿件截面從標準型鋼庫中選?。?/p>

式中：S 為標準截面構成的集合;ii =1，…，p為標準型鋼的截面參數;p 為標準型鋼的個數.

對于關聯離散變量，一種常見的處理方法為采用0-1變量：

式中：ti為0-1變量，用于表征某一標準截面是否被選中.這種定義方法的本質，是在p 維的0-1離散空間與標準截面集 S 之間定義了一種映射關系.

若優化數學模型中包含0-1變量，則求解特別耗時，為此，本文提出了一種新的離散變量定義方法，即基于凸組合的線性松弛方法.

對于平面鋼框架結構的優化問題，若只考慮結構的軸向變形和彎曲變形，則結構的剛度矩陣僅僅與桿件的截面面積和慣性矩有關.因此，在作者前期的研究[16]中，提出了以截面面積和慣性矩為設計變量的定義方法：

式中：A、I 分別為桿件的截面面積和慣性矩.考慮到標準型鋼的 A 和 I 是關聯離散變量，優化過程中需要同時選取某一標準截面的 A 和 I，故在每一次優化迭代后將設計變量圓整到標準截面.根據式（5），標準型鋼可視為二維空間中的一個離散點（見圖1）.

對于空間中的任意多個點，總是存在一個包含所有點的最小凸多邊形（即凸包），使得凸多邊形內的任意一點，都可以用凸多邊形頂點的凸組合進行描述.因此，提出一種基于凸組合的線性松弛方法，將式（5）表示的變量定義方法推廣到連續空間：

式中： i、Iˉi分別對應于凸多邊形頂點的截面面積和慣性矩;ci 為凸組合的系數;q 為凸多邊形頂點的個數.由此，離散優化問題的設計空間從一個離散點集變為為一個凸多邊形，凸多邊形內的任意一點都可以用于結構設計.

在式（6）～（9）中，將基于凸多邊形的線性松弛方法應用于二維空間，若將這一方法應用于一維空間時，就退化為一種常見的松弛方法.以桁架結構的離散優化問題為例，假設桿件的可選截面集為：

式中： i i =1，…，r按從小到大排列.對于這一離散點集，最常用的松弛方法就是將桿件的截面面積 At 限制在最小面積值和最大面積值之間：

從幾何角度看，桿件的截面面積限定在一維凸多邊形1， r 內，其中1、 r 為一維凸多邊形的兩個頂點：

式中：c 1、c2為凸組合系數.顯然，式（12）～（14）就是式（6）～（9）的一維形式.

根據式（6）～（9），離散優化問題的設計變量變成連續松弛變量（即凸組合系數），而標準截面的截面面積和慣性矩成為設計變量的線性函數.由此，鋼框架結構的剛度矩陣成為凸組合系數的線性函數.根據這一特性，可以將兩類典型的鋼框架結構離散優化問題，即柔度約束的最小體積問題、體積約束的最小柔度問題，分別轉化為松弛的凸規劃問題.

2凸規劃建模

2.1柔度約束的最小體積問題

在鋼框架結構的離散優化中，柔度約束的最小體積問題可表達如下：

式中：Li、Ai 分別為第i個桿件的長度和截面面積;n 為桿件的總數;K 為結構的剛度矩陣;U 為節點位移列陣;F 為載荷列陣;為柔度上限.

根據桁架結構的研究[17-18]，桁架結構的柔度約束和力平衡約束可等效于矩陣的半正定約束：

式中：Kt 為桁架結構的剛度矩陣.

式（18）成立的一個重要前提條件，就是 Kt 為桿件截面面積的線性函數.根據本文提出的線性松弛方法，鋼框架結構的剛度矩陣也成為設計變量的線性函數，故同樣可以將鋼框架結構的柔度約束最小體積問題轉化為半定規劃問題：

式中：K C為鋼框架結構的剛度矩陣;C 為凸組合系數矩陣.

針對半定規劃問題，當前已經有多個成熟的優化求解器，如 MOSEK[19]、SeDuMi[20].應用這些求解器，可以快速得到半定規劃問題的全局最優解，也就是離散優化問題的理論下界.

2.2體積約束的最小柔度問題

在鋼框架結構的離散優化中，體積約束的最小柔度問題可表達如下：

式中：為體積上限.

根據Kanno[11]，體積約束的最小柔度問題可轉化為混合整數的二階錐規劃問題：

式中：will =1，2，3是桿件i的應變余能;sill =1，2，3是桿件i的內力;bill =1，2，3為桿件i的方向列陣，具體計算方法可參照文獻[11]的附錄 A.

其中，Ai、Ii屬于關聯離散變量，Kanno[11]采用0-1變量的定義方法進行處理.為提高問題的求解效率，快速得到離散優化問題的理論下界，本文采用基于凸組合的線性松弛方法來重新定義離散變量：

式（33）～（36）僅包含線性約束，不改變優化問題的數學特性，故所得到的優化問題仍然屬于二階錐規劃問題.二階錐規劃問題可以用成熟的優化求解器（如 MOSEK、CPLEX[21]、Gurobi[22]或SeDuMi）進行快速求解，進而得到原離散優化問題的理論下界.

3數值算例

通過求解一跨四層鋼框架結構的離散優化問題，對所提出的方法進行驗證.鋼框架結構的尺寸、桿件分組和加載情況如圖2所示.桿件的彈性模量為2.1×105 MPa，體積上限為0.18 m3，柔度上限為25.結構中的桿件從標準規格中的 H 型鋼[23]中選?。ㄒ姳?），H型鋼在二維空間中的分布如圖1所示.

采用枚舉法計算離散優化問題的全局最優解，并驗證所提出方法求解優化問題的理論下界的能力.為判斷所提出方法的計算效率，再用遺傳算法（Genetic Algorithm，GA）求解當前優化問題. GA是一種經典的智能優化算法，可依概率收斂到優化問題的全局最優解，因此采用 GA 與所提出方法進行對比.采用 MATLAB 平臺自帶的 ga 求解器作為 GA 的實現，其中：種群大小為30，最大迭代次數為500，其余參數都采用默認值.將 GA 獨立運行30次，得到最佳的優化結果.

為了對關聯離散變量進行線性松弛，需要定義包含離散點集的凸包.對于平面內的離散點集，可采用經典的 Graham 掃描算法[24]獲得對應的凸包.

所有的優化計算都在 MATLAB 平臺中編碼，并在一臺工作站中執行.該工作站含雙核2.2.GHz Xeon 處理器，運行內存為32 GB.

3.1 柔度約束的最小體積問題

采用 MOSEK 求解松弛的半定規劃問題，得到松弛最優解.采用枚舉法求解該離散優化問題，得到離散的全局最優解，并采用 GA 得到近似最優解.松弛最優解對應的結構體積為0.1378 m3，結構柔度為25.00;離散全局最優解對應的結構體積為0.1414 m3，結構柔度為24.96;GA 得到的近似最優解對應的結構體積為0.1420 m3，結構柔度為24.75.顯然，松弛最優解比離散全局最優解略小，松弛最優解成為了離散優化問題的理論下界.同時，根據松弛最優解進行鄰域搜索，可以快速得到高質量的離散可行解，甚至是離散的全局最優解.

基于半定規劃的方法僅需要采用調用一次優化求解器、耗時0.51 s，就可以得到優化問題的理論下界，而枚舉法需要求解524（≈5.96×1016）個子問題、耗時1724.21 s，才能得到離散的全局最優解.為了得到近似最優解，GA 需要獨立運行多次，而每一次運行的計算時間都超過1 s（介于1.10 s 到2.00 s 之間），所以，GA 的計算效率也遠不如所提出的半定規劃方法.顯然，當需要判斷某種算法的優化結果是否為全局最優時，半規劃方法可以是一種高效的驗證方法，尤其是對于規模稍大一些的同類優化問題.

松弛最優解和離散最優解在空間中的分布情況如圖3所示，離散最優解如表2所示.

3.2體積約束的最小柔度問題

采用 MOSEK 求解松弛的二階錐規劃問題，同時采用枚舉法求解離散優化問題的全局最優解，并采用 GA 得到近似最優解.優化結果如下：松弛最優解的最小柔度為17.74，結構體積為0.1800 m3;離散全局最優解的最小柔度為18.09，結構體積為0.1790 m3;GA 得到的近似最優解對應的結構柔度為18.00，結構體積為0.1801 m3，略大于體積上限.因此，對于體積約束的最小柔度離散優化問題，采用二階錐規劃的方法也可以得到離散問題的理論下界.可以根據松弛最優解進行鄰域搜索，得到離散優化問題的可行解.

同樣的，基于二階錐規劃方法僅調用一次優化求解器、耗時0.67 s，就能夠得到離散優化問題的理論下界，而采用枚舉法需要計算524（≈5.96×1016）個子問題、耗時1605.13 s，才能得到離散的全局最優解.為了得到近似最優解，GA 需要運行多次，而每一次運行的計算時間都超過0.70 s（介于0.70 s 到1.50 s 之間），所以，二階錐規劃方法的計算效率遠高于枚舉法和 GA.

松弛最優解和離散全局最優解在空間中的分布情況如圖4所示，離散最優解如表3所示.

4結論

針對兩類典型的鋼框架結構離散優化問題，即柔度約束的最小體積問題、體積約束的最小柔度問題，進行了研究并得到如下結論：

1）基于凸組合的線性松弛方法，可以實現離散設計變量的線性松弛，使結構的剛度矩陣成為設計變量的線性函數，從而可將柔度約束的最小體積問題轉化為松弛的半定規劃問題，將體積約束的最小柔度問題轉化為松弛的二階錐規劃問題.對這兩類松弛的凸規劃問題，可以快速得到全局最優解，即離散優化問題的理論下界.

2）基于松弛的半定規劃方法和二階錐規劃方法，可以高效求解柔度約束的最小體積問題、體積約束的最小柔度問題，且求解效率遠高于枚舉法.因此，采用松弛的半定規劃方法和二階錐規劃方法，可以快速驗證某種優化方法是否得到全局最優解.

需要說明的是，基于凸組合的線性松弛方法實現了桿件的截面面積和慣性矩的線性化描述，但未能對其他截面屬性進行線性化描述.因此，本文的優化方法適用于僅考慮桿件的拉壓變形和彎曲變形的平面鋼框架結構.

參考文獻

[1]? GHOLIZADEH S，EBADIJALAL M. Performance based discretetopology optimization of steel braced frames by a new metaheuris ? tic [J]. Advances in Engineering Software，2018，123：77-92.

[2]? MANSOURI I，SOORI S，AMRAIE H，et al. Performance based design optimum of CBFs using bee colony algorithm [J]. Steel and Composite Structures.2018，27（5）：613-622.

[3]? KAVEH A，HAMEDANI K B，HOSSEINI S M，et al. Optimal design of planar steel frame structures utilizing meta-heuristic opti ? mization algorithms[J]. Structures，2020，25：335-346.

[4]? TALATAHARI S，AZIZI M. Optimal design of real-size buildingstructures using quantum-behaved developed swarm optimizer[J]. Structural Design of Tall and Special Buildings，2020，29（11）： e1747.

[5] 唐和生，范德偉，王兆亮，等.桁架尺寸優化微分演化算法[J].湖南大學學報（自然科學版），2011，38（11）：13-18.

TANG H S，FAN D W，WANG Z L，et al. Differential evolution algorithm to size the optimization of truss structures[J].Journal of Hunan University （Natural Sciences），2011，38（11）：13-18.（ In Chinese）

[6]? MOHAMMADI R K，GHASEMOF A. Performance-based designoptimization using uniform deformation theory：a comparison study [J]. Latin American Journal of Solids and Structures，2015，12（1）：18-36.

[7]? 白久林，楊樂，歐進萍.基于等損傷的鋼框架結構抗震性能優化[J].工程力學，2015，32（6）：76-83.

BAI J L，YANG L，OU J P. Aseismic performance optimization of steel frame structures based on uniform damage concept[J].En? gineering Mechanics，2015，32（6）：76-83.（In Chinese）

[8] 侯玉品，張永存，劉書田.基于梯度優化方法的鋼結構標準截面選型優化設計[J].工程力學，2013，30（1）：454-462.

HOU Y P，ZHANG Y C，LIU S T. Optimization of standard cross- section type selection in steel frame structures based on gradient methods[J]. Engineering Mechanics，2013，30（1）：454-462.（ In Chinese）

[9]? CHANGIZI N，JALALPOUR M. Stress-based topology optimization of steel-frame structures using members with standard cross sections：gradient-based approach[J]. Journal of Structural Engi? neering，2017，143（8）：04017078.

[10] VAN M R，MELA K，TIAINEN T，et al. Mixed-integer linear programming approach for global discrete sizing optimization of frame structures [J].? Structural and Multidisciplinary Optimization，2018，57（2）：579-593.

[11] KANNO Y. Mixed-integer second-order cone programming forglobal optimization of compliance of frame structure with discrete design variables[J]. Structural and Multidisciplinary Optimiza? tion，2016，54（2）：301-316.

[12] KURETA R，KANNO Y. A mixed integer programming approachto designing periodic frame structures with negative Poisson′s ratio [J]. Optimization and Engineering，2014，15（3）：773-800.

[13] HIROTA M，KANNO Y. Optimal design of periodic frame structures with negative thermal expansion via mixed integer program ? ming[J]. Optimization and Engineering，2015，16（4）：767-809.

[14] ARORA J S. Methods for discrete variable structural optimization[ C]// Recent Advances in Optimum Structural Design. Reston， VA：ASCE，2002：1-40.

[15] HUANG M W，ARORA J S. Optimal design of steel structures using standard sections[J]. Structural Optimization，1997，14（1）：24-35.

[16] WANG X F，ZHANG Q，QIN X R，et al. An efficient discrete optimization algorithm for performance-based design optimization of steel frames[J]. Advances in Structural Engineering，2020，23（3）：411-423.

[17] KO?VARA M. Truss topology design with integer variables madeeasy [ DB/OL]. http：//www.optimization-online，2010-05.

[18] ACHTZIGER W，KO?VARA M. Structural topology optimizationwith eigenvalues [J]. SIAM Journal on Optimization，2008，18（4）：1129-1164.

[19] MOSEK. The MOSEK modeling cookbook [ EB/OL]. http：//www.mosek.com/，2020.

[20] STURM J F. Using SeDuMi 1.02，A Matlab toolbox for optimization over symmetric cones [J]. Optimization Methods and Soft? ware，1999，11（1/2/3/4）：625-653.

[21] IBM ilog. User′s manual for CPLEX [ EB/OL]. http：//www. ilog.com/，2014.

[22] Gurobi optimization inc. Gurobi optimizer reference manual [ EB/OL]. http：//www.gurobi.com/，2015.

[23]熱軋 H 型鋼和部分 T 型鋼：GB/T 11263—2017[ S].北京：中國計劃出版社，2017：3-7.

Hot rolled H and cut T section steel：GB/T 11263—2017[ S]. Bei? jing：China Planning Press，2017：3-7.（In Chinese）

[24] TERESHCHENKO V，TERESHCHENKO Y，KOTSUR D. Pointtriangulation using Graham′s scan[ C]// Fifth International Confer? ence on the Innovative Computing Technology （ INTECH）.Piscat? away：IEEE Press，2015：148-151.