師瑩瑩, 周光明

向量多項(xiàng)式優(yōu)化問題的混合算法

師瑩瑩, 周光明

(湘潭大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院, 湖南 湘潭, 411105)

用混合方法將向量多項(xiàng)式優(yōu)化問題轉(zhuǎn)化為單目標(biāo)多項(xiàng)式優(yōu)化問題, 利用Lasserre半正定松弛方法求解, 提出了計(jì)算帶約束的向量多項(xiàng)式優(yōu)化問題有效解的混合算法。并分析原問題的有效解和轉(zhuǎn)化問題最優(yōu)解之間的關(guān)系, 進(jìn)行收斂性證明, 數(shù)值結(jié)果表明所提算法是可行的。

向量多項(xiàng)式優(yōu)化; 混合算法; 半正定松弛方法; 有效解

多目標(biāo)優(yōu)化問題的理論研究和應(yīng)用已有幾十年的歷史, 其數(shù)值計(jì)算方法也有多種。Schaffer[1]提出了矢量評(píng)價(jià)算法, 第一次實(shí)現(xiàn)了遺傳算法與多目標(biāo)優(yōu)化問題的結(jié)合。Goldberg[2]提出了將經(jīng)濟(jì)學(xué)中的Pareto理論與進(jìn)化算法結(jié)合求解多目標(biāo)優(yōu)化問題的新思路。林銼云等[3]對(duì)多目標(biāo)規(guī)劃中的經(jīng)典優(yōu)化算法(如: 線性加權(quán)法, 約束法, 理想點(diǎn)法等)進(jìn)行了總結(jié)。Mu Shengjing等[4]提出一個(gè)在一定程度上類似于模擬退火技術(shù)的遺傳算法求解約束優(yōu)化問題。唐泳等[5]用改進(jìn)螞蟻算法求解多目標(biāo)優(yōu)化問題。李飛等[6]提出基于分解和差分進(jìn)化的多目標(biāo)粒子群優(yōu)化算法。劉建昌等[7]立足于一種全新的性能評(píng)價(jià)指標(biāo)—R2指標(biāo), 介紹基于R2指標(biāo)的高維多目標(biāo)優(yōu)化算法。湯可宗等[8]為了改善解集分布性和提高算法收斂性, 提出一種基于極大極小關(guān)聯(lián)密度的多目標(biāo)微分進(jìn)化算法。蘭麗爾等[9]針對(duì)大規(guī)模多目標(biāo)優(yōu)化問題, 提出了一種基于分解的改進(jìn)粒子群算法。鄭夏等[10]提出了一種多目標(biāo)非線性優(yōu)化的NSGA-Ⅱ改進(jìn)算法。

多項(xiàng)式優(yōu)化是指目標(biāo)函數(shù)和約束函數(shù)均為多項(xiàng)式的一類非線性規(guī)劃。Lasserre已提出了求解該問題的經(jīng)典數(shù)值方法, 通稱為Lasserre半正定松弛方法。De Klerk等[11]和Nie[12]對(duì)該問題也進(jìn)行了深入的研究。最近, 汪琴等[13]針對(duì)帶復(fù)合結(jié)構(gòu)可化為多項(xiàng)式優(yōu)化的非線性規(guī)劃的全局優(yōu)化問題, 提出了基于Lasserre松弛方法的算法。

本文主要討論一般向量多項(xiàng)式優(yōu)化問題的混合方法, 其中目標(biāo)函數(shù)和約束函數(shù)不限定為凸多項(xiàng)式, 可行集也不限定為凸集。論文首先利用混合方法將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題, 然后利用Lasserre半正定松弛方法進(jìn)行求解, 分析收斂性, 最后設(shè)計(jì)數(shù)值實(shí)驗(yàn)驗(yàn)證算法的有效性。

1 預(yù)備知識(shí)

為了討論的方便, 首先介紹關(guān)于多項(xiàng)式、矩、矩矩陣等的相關(guān)知識(shí)[14]。

記基本半代數(shù)集

2 混合算法

設(shè)向量多項(xiàng)式優(yōu)化問題為

上述問題(2)的可行集記為

本文設(shè)集合是非空緊集。

一般來說, 同時(shí)最小化所有的目標(biāo)函數(shù)是不可能的。因此對(duì)向量多項(xiàng)式優(yōu)化問題, 通常是去尋找“最合適的解”, 即所謂的“有效解”。

使用混合方法將問題轉(zhuǎn)化為

上述問題(4)的可行集記為

根據(jù)Lasserre半正定松弛方法[14], 將問題(4)轉(zhuǎn)化為半正定規(guī)劃問題。

采用Lasserre半正定松弛方法[14]求解半正定規(guī)劃問題(6), 算法如下:

3 收斂性分析

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

本節(jié)通過在惠普電腦上的MATLAB 2016b計(jì)算一些數(shù)值實(shí)驗(yàn)來測(cè)試前面的數(shù)值算法在求解向量優(yōu)化問題時(shí)的可行性。電腦配置如下: 雙核3.20GHz CPU, 運(yùn)行內(nèi)存為4GB。MATLAB通過調(diào)用GloptiPoly[16–17]來求解轉(zhuǎn)化后的單目標(biāo)多項(xiàng)式優(yōu)化問題。

取不同的值, 利用本文算法解得算例1的數(shù)值結(jié)果見表1。

表1 算例1的數(shù)值結(jié)果

取不同的值, 利用本文算法解得算例2的數(shù)值結(jié)果見表2。由表可知, 當(dāng)= (-1/2, 1)時(shí), 可解得最優(yōu)解有2個(gè), 表明新算法不同于MATLAB中的優(yōu)化函數(shù), 它可以同時(shí)解得原問題的多個(gè)全局最優(yōu)點(diǎn)。

表2 算例2的數(shù)值結(jié)果

取不同的值, 利用本文算法解得算例3的數(shù)值結(jié)果見表3。

表3 算例3的數(shù)值結(jié)果

取不同的值, 利用前面算法解得算例4的數(shù)值結(jié)果見表4。

表4 算例4的數(shù)值結(jié)果

取不同的值, 利用本文算法解得算例5的數(shù)值結(jié)果見表5。

表5 算例5的數(shù)值結(jié)果

取不同的值, 利用本文算法解得算例6的數(shù)值結(jié)果見表6。

表6 算例6的數(shù)值結(jié)果

取不同的值, 利用本文算法解得算例7的數(shù)值結(jié)果見表7。

表7 算例7的數(shù)值結(jié)果

取不同的值, 利用本文算法解得算例8的數(shù)值結(jié)果見表8。由表8可知, 當(dāng)= (1, 1, 2)時(shí), 可解得最優(yōu)解有2個(gè), 表明新算法不同于MATLAB中的優(yōu)化函數(shù), 它可以同時(shí)解得原問題的多個(gè)全局最優(yōu)點(diǎn)。

表8 算例8的數(shù)值結(jié)果

取不同的值, 利用本文算法解得算例9的數(shù)值結(jié)果見表9。

表9 算例9的數(shù)值結(jié)果

取不同的值, 利用本文算法解得算例10的數(shù)值結(jié)果見表10。

表10 算例10的數(shù)值結(jié)果

以上10個(gè)算例考慮了目標(biāo)函數(shù)個(gè)數(shù)、自變量個(gè)數(shù)、函數(shù)次數(shù)、及可行域的變化等多種情況, 從數(shù)值結(jié)果知, 本文提出的向量多項(xiàng)式優(yōu)化問題的混合算法是可行的。

本文提出的算法可以求解一般的向量多項(xiàng)式優(yōu)化問題, 其中目標(biāo)函數(shù)和約束函數(shù)不限定為凸多項(xiàng)式, 可行集也不限定為凸集。例如算例2和算例3的目標(biāo)函數(shù)為非凸多項(xiàng)式, 算例1和算例3的約束函數(shù)為非凸多項(xiàng)式, 算例4和算例5的可行集不是凸集。本文的算法僅適用于可行集是緊集的情況, 對(duì)于可行集不是緊集的情況有待進(jìn)一步討論。

6 總結(jié)

本文針對(duì)一般的向量多項(xiàng)式優(yōu)化問題, 提出了求其有效解的混合算法, 證明了該算法的收斂性, 并通過大量數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的有效性。

[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] 林銼云, 董加禮. 多目標(biāo)優(yōu)化的方法和理論[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ìn)螞蟻算法求解多目標(biāo)優(yōu)化問題[J]. 電子科技大學(xué)學(xué)報(bào), 2005, 34(2): 281–284.

[6] 李飛, 劉建昌, 石懷濤, 等. 基于分解和差分進(jìn)化的多目標(biāo)粒子群優(yōu)化算法[J]. 控制與決策, 2017, 32(3):403–410.

[7] 劉建昌, 李飛, 王洪海, 等. 進(jìn)化高維多目標(biāo)優(yōu)化算法研究綜述[J]. 控制與決策, 2018, 033(005): 879–887.

[8] 湯可宗, 柳炳祥, 詹棠森, 等. 基于極大極小關(guān)聯(lián)密度的多目標(biāo)微分進(jìn)化算法[J]. 南京理工大學(xué)學(xué)報(bào)(自然科學(xué)版), 2019, 43(6): 693–696.

[9] 蘭麗爾, 孫超利, 何小娟, 等. 求解大規(guī)模多目標(biāo)問題的改進(jìn)粒子群算法[J]. 太原科技大學(xué)學(xué)報(bào), 2020, 41(4): 249– 256.

[10] 鄭夏, 馬良. 一種多目標(biāo)非線性優(yōu)化的NSGA-Ⅱ改進(jìn)算法[J]. 微電子學(xué)與計(jì)算機(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] 汪琴, 周光明, 趙文杰. 一類帶復(fù)合結(jié)構(gòu)的非線性規(guī)劃的數(shù)值算法[J]. 湖南文理學(xué)院學(xué)報(bào)(自然科學(xué)版), 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

國家自然科學(xué)基金資助項(xiàng)目(11671342)。

(責(zé)任編校: 張紅)