钢框架结构离散优化问题的理论下界

王兴锋 张氢 秦仙蓉 孙远韬

摘要：针对两种典型的钢框架结构离散优化问题，即柔度约束的最小体积问题和体积约束的最小柔度问题，提出了基于凸组合的线性松弛方法，将关联离散变量进行线性松弛，进而将非线性、非凸的离散优化问题转化为松弛的凸规划问题.其中，体积约束的最小柔度问题可松弛为二阶锥规划问题，柔度约束的最小体积问题可松弛为半定规划问题.采用成熟的优化求解器，就可以得到两类凸规划问题的全局最优解，也就是原离散优化问题的理论下界.以一跨四层钢框架的离散优化问题为例，用所提出方法进行求解，并用枚举法和遗传算法对优化结果进行验证.数值结果证明，所提出方法可以快速得到离散优化问题的理论下界.

关键词：钢框架结构;离散优化;线性松弛;凸规划;理论下界

中图分类号：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离散变量的定义方法

在钢框架结构的离散优化设计中，杆件截面从标准型钢库中选取：

式中：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]中选取（见表1），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.