向量多项式优化问题的混合算法

师莹莹, 周光明

向量多项式优化问题的混合算法

师莹莹, 周光明

(湘潭大学 数学与计算科学学院, 湖南 湘潭, 411105)

用混合方法将向量多项式优化问题转化为单目标多项式优化问题, 利用Lasserre半正定松弛方法求解, 提出了计算带约束的向量多项式优化问题有效解的混合算法。并分析原问题的有效解和转化问题最优解之间的关系, 进行收敛性证明, 数值结果表明所提算法是可行的。

向量多项式优化; 混合算法; 半正定松弛方法; 有效解

多目标优化问题的理论研究和应用已有几十年的历史, 其数值计算方法也有多种。Schaffer[1]提出了矢量评价算法, 第一次实现了遗传算法与多目标优化问题的结合。Goldberg[2]提出了将经济学中的Pareto理论与进化算法结合求解多目标优化问题的新思路。林锉云等[3]对多目标规划中的经典优化算法(如: 线性加权法, 约束法, 理想点法等)进行了总结。Mu Shengjing等[4]提出一个在一定程度上类似于模拟退火技术的遗传算法求解约束优化问题。唐泳等[5]用改进蚂蚁算法求解多目标优化问题。李飞等[6]提出基于分解和差分进化的多目标粒子群优化算法。刘建昌等[7]立足于一种全新的性能评价指标—R2指标, 介绍基于R2指标的高维多目标优化算法。汤可宗等[8]为了改善解集分布性和提高算法收敛性, 提出一种基于极大极小关联密度的多目标微分进化算法。兰丽尔等[9]针对大规模多目标优化问题, 提出了一种基于分解的改进粒子群算法。郑夏等[10]提出了一种多目标非线性优化的NSGA-Ⅱ改进算法。

多项式优化是指目标函数和约束函数均为多项式的一类非线性规划。Lasserre已提出了求解该问题的经典数值方法, 通称为Lasserre半正定松弛方法。De Klerk等[11]和Nie[12]对该问题也进行了深入的研究。最近, 汪琴等[13]针对带复合结构可化为多项式优化的非线性规划的全局优化问题, 提出了基于Lasserre松弛方法的算法。

本文主要讨论一般向量多项式优化问题的混合方法, 其中目标函数和约束函数不限定为凸多项式, 可行集也不限定为凸集。论文首先利用混合方法将多目标优化问题转化为单目标优化问题, 然后利用Lasserre半正定松弛方法进行求解, 分析收敛性, 最后设计数值实验验证算法的有效性。

1 预备知识

为了讨论的方便, 首先介绍关于多项式、矩、矩矩阵等的相关知识[14]。

记基本半代数集

2 混合算法

设向量多项式优化问题为

上述问题(2)的可行集记为

本文设集合是非空紧集。

一般来说, 同时最小化所有的目标函数是不可能的。因此对向量多项式优化问题, 通常是去寻找“最合适的解”, 即所谓的“有效解”。

使用混合方法将问题转化为

上述问题(4)的可行集记为

根据Lasserre半正定松弛方法[14], 将问题(4)转化为半正定规划问题。

采用Lasserre半正定松弛方法[14]求解半正定规划问题(6), 算法如下:

3 收敛性分析

4 数值实验

本节通过在惠普电脑上的MATLAB 2016b计算一些数值实验来测试前面的数值算法在求解向量优化问题时的可行性。电脑配置如下: 双核3.20GHz CPU, 运行内存为4GB。MATLAB通过调用GloptiPoly[16–17]来求解转化后的单目标多项式优化问题。

取不同的值, 利用本文算法解得算例1的数值结果见表1。

表1 算例1的数值结果

取不同的值, 利用本文算法解得算例2的数值结果见表2。由表可知, 当= (-1/2, 1)时, 可解得最优解有2个, 表明新算法不同于MATLAB中的优化函数, 它可以同时解得原问题的多个全局最优点。

表2 算例2的数值结果

取不同的值, 利用本文算法解得算例3的数值结果见表3。

表3 算例3的数值结果

取不同的值, 利用前面算法解得算例4的数值结果见表4。

表4 算例4的数值结果

取不同的值, 利用本文算法解得算例5的数值结果见表5。

表5 算例5的数值结果

取不同的值, 利用本文算法解得算例6的数值结果见表6。

表6 算例6的数值结果

取不同的值, 利用本文算法解得算例7的数值结果见表7。

表7 算例7的数值结果

取不同的值, 利用本文算法解得算例8的数值结果见表8。由表8可知, 当= (1, 1, 2)时, 可解得最优解有2个, 表明新算法不同于MATLAB中的优化函数, 它可以同时解得原问题的多个全局最优点。

表8 算例8的数值结果

取不同的值, 利用本文算法解得算例9的数值结果见表9。

表9 算例9的数值结果

取不同的值, 利用本文算法解得算例10的数值结果见表10。

表10 算例10的数值结果

以上10个算例考虑了目标函数个数、自变量个数、函数次数、及可行域的变化等多种情况, 从数值结果知, 本文提出的向量多项式优化问题的混合算法是可行的。

本文提出的算法可以求解一般的向量多项式优化问题, 其中目标函数和约束函数不限定为凸多项式, 可行集也不限定为凸集。例如算例2和算例3的目标函数为非凸多项式, 算例1和算例3的约束函数为非凸多项式, 算例4和算例5的可行集不是凸集。本文的算法仅适用于可行集是紧集的情况, 对于可行集不是紧集的情况有待进一步讨论。

6 总结

本文针对一般的向量多项式优化问题, 提出了求其有效解的混合算法, 证明了该算法的收敛性, 并通过大量数值实验验证了算法的有效性。

[1] Schaffer J D. Multiple objective optimization with vector evaluated genetic algorithms[C]//Proceedings of the First International Conference on Genetic Algorithms. Pittsburgh: Lawrence Erlbaum IEEE Press, 1985: 93–100.

[2] Goldberg, D. E.Genetic Algorithms in Search Optimization and Machine Learning [M]. New Jersey: Addison-Wesley Professional, 1989.

[3] 林锉云, 董加礼. 多目标优化的方法和理论[M]. 吉林: 吉林教育出版社, 1992: 55–72.

[4] MU Shengjing, SU Hongye, MAO Weijie, et al. A new genetic algorithm to handle the constrained optimization problem [C]//41st IEEE Conference of Decision and Control. Las Vegas: IEEE Control Systems Society, 2002: 739–740.

[5] 唐泳, 马永开. 用改进蚂蚁算法求解多目标优化问题[J]. 电子科技大学学报, 2005, 34(2): 281–284.

[6] 李飞, 刘建昌, 石怀涛, 等. 基于分解和差分进化的多目标粒子群优化算法[J]. 控制与决策, 2017, 32(3):403–410.

[7] 刘建昌, 李飞, 王洪海, 等. 进化高维多目标优化算法研究综述[J]. 控制与决策, 2018, 033(005): 879–887.

[8] 汤可宗, 柳炳祥, 詹棠森, 等. 基于极大极小关联密度的多目标微分进化算法[J]. 南京理工大学学报(自然科学版), 2019, 43(6): 693–696.

[9] 兰丽尔, 孙超利, 何小娟, 等. 求解大规模多目标问题的改进粒子群算法[J]. 太原科技大学学报, 2020, 41(4): 249– 256.

[10] 郑夏, 马良. 一种多目标非线性优化的NSGA-Ⅱ改进算法[J]. 微电子学与计算机, 2020, 37(7): 47–53.

[11] Klerk de E, Laurent M. Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube [J]. SIAM Journal on Optimization, 2010, 20(6): 3 104–3 120.

[12] Nie J. An approximation bound analysis for lasserre relaxation in multivariate polynomial optimization [J]. Journal of the Operations Research Society of China, 2013, 1(3): 313–332.

[13] 汪琴, 周光明, 赵文杰. 一类带复合结构的非线性规划的数值算法[J]. 湖南文理学院学报(自然科学版), 2019, 31(3): 1–6.

[14] Lasserre J B. Moments, Positive Polynomials and Their Applications [M].London: Imperial College Press, 2010:3-120.

[15] Giannessi, F., Mastroeni, G., Pellegrini, L. On the theory of vector optimization and variational inequalities. Image space analysis and separation [M]. Boston: Springer, 2000: 153–215.

[16] Henrion D, Lasserre J B. GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi [J]. Acm Transactions on Mathematical Software, 2003, 29(2): 165–194.

[17] Henrion D, Lasserre J B, Lofberg J. GloptiPoly 3: moments, optimization and semidefinite programming [J]. Optimization Methods and Software, 2009, 24(4–5): 761–779.

Hybrid algorithm for vector polynomial optimization problems

Shi Yingying, Zhou Guangming

(School of Mathematics and Computational Science, Xiangtan University, Xiangtan 411105, China)

In this paper, the vector polynomial optimization problem is transformed into a single-objective polynomial optimization problem by using a hybrid method, and the Lasserre semi-definite relaxation method is applied to solve the new problem. Then the hybrid algorithm is proposed to calculate the effective solution of the constrained vector polynomial optimization problem. In addition, we discuss the relationship between the effective solution of the original problem and the optimal solution of the transformation problem. Finally the convergence is proved and numerical results show that the proposed algorithm is feasible.

vector polynomial optimization; hybrid algorithm; positive semidefinite relaxation method; efficient solution

O 221.1

A

1672–6146(2021)02–0011–06

10.3969/j.issn.1672–6146.2021.02.003

周光明, zhougm@xtu.edu.cn。

2020–9–25

国家自然科学基金资助项目(11671342)。

(责任编校: 张红)