PDF《数学杂志》

Vol.

38 (

2018 ) No.

3 数学杂志J. of Math. (PRC) 多目标优化问题近似解的非线性标量化刻画 李小燕, 李美术, 高英(重庆师范大学数学科学学院, 重庆 401331) 摘要: 本文主要研究非线性标量化问题近似解与多目标优化问题近似解的关系. 利用两种范数 建立非线性标量化问题, 得到了多目标优化问题近似有效解和近似真有效解的非线性标量化结果, 并给 出例子对主要结果进行了说明. 关键词: 多目标优化;

近似解;

范数;

非线性标量化 MR(2010) 主题分类号: 90C29;

90C30 中图分类号: O221.6 文献标识码: A 文章编号: 0255-7797(2018)03-0563-08

1 引言 多目标优化问题中, 如何定义最优解是首要问题. 目前研究的解的概念主要有: 有效解, 弱有效解和各种真有效解的概念. 关于这些解的存在性, 最优性条件和对偶等理论是多目标 优化理论研究的主要内容. 但这些解存在性条件较强, 通常需要对可行集增加某种意义下的 凸性或紧性条件. 大量研究表明, 在非紧条件下, 近似解有可能存在. 因此, 在非紧条件下研究 近似解成为了多目标优化问题研究的又一重要方向. 近几十年来, 一些学者提出了各种不同 的近似解的概念, 并进行了进一步的研究.

1979 年, Kutateladze [1] 首先提出了近似解的概念.

1984 年, Loridan [2] 引进了多目标优化问题 ε - 有效解的概念. 随后, 一些学者又提出了几 种近似解的概念 (如White [3] , Helbig [4] ).

2006 年, Guti? errez 等人 [5,6] 利用 co-radiant 集定 义了多目标优化问题的一种新的近似解, 该近似解推广并统一了先前给出的诸多近似解的概 念 (如 Kutateladze [1] , White [3] , Helbig [4] ). 受文献 [5, 6] 中研究工作的启发, 高英等人 [7,8] 在Benson 真有效解的基础上, 利用 co-radiant 集提出了一种近似真有效解的概念. 求解多目标优化问题一个重要途径是将多目标优化问题转化为数值优化问题, 这种转化 方法称为标量化方法. 标量化主要分为线性标量化和非线性标量化. 线性标量化主要是在凸 性和一些广义凸性条件下利用凸集分离定理或择一定理进行刻画. 非线性标量化主要是通过 一些特殊的非线性函数, 在非凸分离定理的基础上进行研究. 近年来, 对有效解, 弱有效解和 各种真有效解的标量化研究可参见文献 [9C15], 关于多目标优化问题各种近似解的标量化研 究可参见文献 [16C20]. 但利用范数研究多目标优化问题各种近似解的非线性标量化的成果并 不多见. 因此本文受文献 [7C9, 17] 的启发, 利用范数考虑多目标优化问题近似有效解和近似 真有效解的非线性标量化刻画, 并举例说明主要结果. ? 收稿日期: 2016-11-28 接收日期: 2017-04-01 基金项目: 国家自然科学基金 (11201511;

11771064);

重庆市科委项目 (cstc2015jcyjA00005);

重庆市教 委项目 (KJ1500309). 作者简介: 李小燕 (1990C), 女, 重庆, 硕士, 主要研究方向: 最优化理论与方法. 通讯作者: 高英.

564 数学杂志Vol.

38 2 预备知识 令Rn 为n维欧氏空间, Rn + 为其非负卦限. 设C?Rn , intC 表示 C 的内部, clC 表示 C 的闭包. 若C∩(?C) ? {0}, 则称 C 为点集. 任取 x, y ∈ Rn , 记x 0, αk →

0 且αk ・ sk → ? s}. 考虑如下的多目标优化问题 (MOP) min f(x) = (f1(x)fp(x))T , s.t. x ∈ X, 其中 X ? Rn 非空, fi : X → R, i = 1,p. 令Y=f(X) := x∈X f(x). 定义 2.2 [5] 称C?Rp 为co-radiant 集, 若对所有的 d ∈ C 和α>

1都有 αd ∈ C. ?ε >

0, 令C(ε) = εC, C(0) = ε>

0 C(ε). 定义 2.3 [5,7] 设ε∈R, 且ε0, x ∈ X, C ? Rp 为co-radiant 点集. (i) 称?x为(MOP) 问题关于 C 的ε-有效解, 若(f(? x) ? C(ε)) ∩ f(X) ? {f(? x)}. (ii) 称?x为(MOP) 问题关于 C 的ε-真有效解, 若clcone(f(X) + C(ε) ? f(? x)) ∩ (?C(ε)) ? {0}. 记(MOP) 问题 关于 C 的ε-有效解和 ε - 真有效解之集分别为 E(f, C, ε) 和P(f, C, ε). Rp 中的 l∞ - 范数和 lα - 范数分别定义为 ||y||∞ = max{|yi| :

1 i p} 和||y||α = [ p i=1 |yi|α ]

1 α , 其中 y = (y1,yp)T ∈ Rp , α ∈ [1, ∞). 令?y=(? y1, yp), 其中 ? yi = inf{yi : yi为y∈Y的第 i 个分量}, i = 1,p. 若?y∈Rp , 满足 ? y ? y, 则称 ? y 为Y的理想点. 设|| ・ || 为Rp 中的某种范数, ? y 为Y=f(X) 的理想点. 考虑如下的非线性标量化问题: (SP) min ||f(x) ? ? y||, s.t. x ∈ X. 定义 2.4 设ε0, ? x ∈ X, α ∈ [1, ∞). (i) 称?x为(SP) 问题关于 ||・||∞ 的ε-最优解, 若||f(? x)?? y||∞ ||f(x)?? y||∞+ε, ? x ∈ X. No.

3 李小燕等: 多目标优化问题近似解的非线性标量化刻画

565 (ii) 称?x为(SP) 问题关于 ||・||α 的ε-最优解, 若||f(? x)?? y||α ||f(x)?? y||α +ε, ? x ∈ X. 记(SP) 问题关于 和|| ・ ||α 的ε-最优解之集分别为 A∞(f, ε) 和Aα(f, ε).

3 主要结果 本节利用 || ・ ||1 范数和 范数得到多目标优化问题近似有效解和近似真有效解的标 量化结果. 若无特别说明, 本节总假设 C ? Rp + 为co-radiant 点集且

0 / ∈ clC. 为了证明的方便, 假设 y1 = (y1 1,y1 p)T ∈ Rp , y2 = (y2 1,y2 p)T ∈ Rp , 由||・||1 范数的 定义, ||y1 +y2 ||1 ||y1 ||1+||y2 ||1. 若y1 , y2 ∈ Rp +, 则满足等式关系 ||y1 +y2 ||1 = ||y1 ||1+||y2 ||1, 这是因为 ||y1 + y2 ||1 = p i=1 |y1 i + y2 i | = p i=1 (|y1 i | + |y2 i |) = p i=1 (|y1 i |) + p i=1 (|y2 i |) = ||y1 ||1 + ||y2 ||1. 本文在很多地方用到这一结论. 定理 3.1 设ε0,

0 <

β <

d||・||1 (0, C), 则(i) A1(f, εβ) ? E(f, C, ε);

(ii) 若Y+C(ε) 为闭集, 则A1(f, εβ) ? P(f, C, ε), 其中 d||・||1 (0, C) 为0到C的距离, 即d||・||1 (0, C) = inf{||c||1 : c ∈ C}. 证设?x∈A1(f, εβ), 令f(? x) = ? y, 则由定义 2.4 有||? y ? ? y||1 ||y ? ? y||1 + εβ, ? y ∈ Y. (3.1) (i) 当ε>

0时, 若?x/∈E(f, C, ε), 则存在 y1 ∈ Y, y1 = ? y, 使得 y1 ? ? y ∈ ?C(ε). 从而存在 c1 ∈ C ? Rp +, 使得 ? y = y1 + εc1 . 因此 ||? y ? ? y||1 = ||y1 + εc1 ? ? y||1. 由?y为Y的理想点, 则?yy1 , 即y1 ? ? y ∈ Rp +. 因此, 由|| ・ ||1 范数的性质可得 ||y1 + εc1 ? ? y||1 = ||y1 ? ? y||1 + ||εc1 ||1 >

||y1 ? ? y||1 + εβ. 这与 (3.1) 式矛盾. 因此 ? x ∈ E(f, C, ε). 当ε=0时, 若?x/∈E(f, C, 0), 则存在 y2 ∈ Y, y2 = ? y, 使得 y2 ? ? y ∈ ?C(0). 从而存在 ? ε >

0, c2 ∈ C ? Rp +, 使得 ? y = y2 + ? εc2 . 因此 ||? y ? ? y||1 = ||y2 + ? εc2 ? ? y||1 = ||y2 ? ? y||1 + ||? εc2 ||1 >

||y2 ? ? y||1. 这与 (3.1) 式矛盾. 因此 ? x ∈ E(f, C, 0). 综上, (i) 成立. (ii) 当ε>

0时, 若?x/∈P(f, C, ε), 则存在非零向量 ?c ∈ clcone(f(X) + C(ε) ? ? y) ∩ (?C(ε)). 从而存在 {βk} ? R+ {0},{yk } ? f(X) = Y, {ck } ? C(ε), 使得 βk(yk + ck ? ? y) → ?c. 若{βk} 有界. 不失一般性, 假设 βk → β0, 则β0 0. 若β0 = 0, 由C?Rp + 有ck ∈ C(ε) ? Rp +, 因此 yk +ck ? y, 则yk +ck ? ? y ∈ ? y? ? y+Rp +, 从而 ?c ∈ (? y? ? y+Rp +)+ = Rp +, 这与 c ∈ C(ε) 矛盾. 若β0 >

0, 则yk + ck ? ? y → ? c β0 . 由Y+C(ε) 为闭集有 yk + ck → ? y ? c β0 ∈ Y + C(ε).

566 数学杂志Vol.

38 从而存在 y0 ∈ Y, d0 ∈ C 使得 ? y = y0 + c β0 + εd0 , 则由 || ・ ||1 范数的性质可得 ||? y ? ? y||1 = ||y0 + c β0 + εd0 ? ? y||1 >

||y0 + εd0 ? ? y||1 = ||y0 ? ? y||1 + ||εd0 ||1 >

||y0 ? ? y||1 + εβ. 这与 (3.1) 式矛盾. 若{βk} 无界, 不失一般性, 假设当 k → ∞ 时, βk → +∞, 则yk +ck ?? y = yk +εdk ?? y → 0, 其中,dk ∈ C ? Rp +, ?k. 即?γ >

0, 存在自然数 Kγ, 当k>

Kγ 时, 有||yk + εdk ? ? y||1 <

γ, 则||yk + εdk ? ? y||1 ? ||? y ? ? y||1 <

||yk + εdk ? ? y||1 <

γ. 从而 ||yk + εdk ? ? y||1 ? γ <

||? y ? ? y||1. 因此存在 k? 使得 ||yk? + εdk? ? ? y||1 ||? y ? ? y||1. 事实 上, 若对任意的 k, ||yk + εdk ? ? y||1 >

||? y ? ? y||1, 则存在 ? γ >

0, 使得 ||yk + εdk ? ? y||1 ? ? γ >

||? y ? ? y||1, ? k. (3.2) 令γ=?γ, 则对 ? γ 存在自然数 K? γ, 使得当 k >

K? γ 时, ||yk + εdk ? ? y||1 ? ? γ <

||? y ? ? y||1, 这与 (3.2) 式矛盾. 因此, 结合 || ・ ||1 范数的定义可得 ||? y ? ? y||1 ||yk? + εdk? ? ? y||1 = ||yk? ? ? y||1 + ||εdk? ||1. 从而 ||? y ? ? y||1 >

||yk? ? ? y||1 + εβ. 这与 (3.1) 式矛盾. 综上, 当ε>

0时, ? x ∈ P(f, C, ε). 当ε=0时, 利用 ε >

0 的证明思路, 结合 (i) 中ε=0的情况, 可得结论. 从而 (ii) 成立. 注3.1 (i) 定理中的

0 <

β <

d||・||1 (0, C) 必不可少. 若β=d||・||1 (0, C), 则A1(f, εβ) ? E(f, C, ε) 不一定成立. 见例 3.1. (ii) 定理中的两种反包含关系不一定成立. 事实上, 对任意的

0 <

β <

d||・||1 (0, C), E(f, C, ε) ? clA1(f, εβ), P(f, C, ε) ? clA1(f, εβ) 都不一定成立. 见例 3.1. (iii) 文献 [9] 利用 || ・ ||α( α ∈ [1, ∞)) 给出了精确的有效解和真有效解的非线性标量化结 果. 但对近似解来说, 定理中的结果对其它范数不一定成立. 如 范数 和|| ・ ||2 范数. 见例3.2. 例3.1 令X=R2 +, C = {(x1, x2)T : x1 0, x2 0, x1 +x2 1}, f : X → R2 , f(x) = x, 则Y=f(X) = R2 + 的理想点之集为 R2 ? 且d||・||1 (0, C) = 1. 令ε=1, 则E(f, C, 1) = {(x1, x2)T : x1 0, x2 0, x1 + x2 <

1}, P(f, C, 1) = {(x1, x2)T : x1 0, x2 0, x1 + x2 1}. E(f, C, 1) 的图象如图

1 所示. 若β=d||・||1 (0, C) = 1, 则A1(f, β) = A1(f, 1) = {(x1, x2)T : x1 0, x2 0, x1 + x2 1}. 显然, A1(f, εβ) E(f, C, ε), ? β ∈ (0, 1), A1(f, β) = {(x1, x2)T : x1 0, x2 0, x1 + x2 β}. No.

3 李小燕等: 多目标优化问题近似解的非线性标量化刻画

567 图1图2特别取 β = 0.9 时, A1(f, 0.9) 的图象如图

2 所示. 显然, E(f, C, 1) clA1(f, β),P(f, C, 1) clA1(f, β), ?

0 <

β <

1. 这说明定理 3.1 中的两种反包含关系不一定成立. 例3.2 令X={(x1, x2)T : x1 0, x2 ?1}, C = {(x1, x2)T : x1 0, x2 0, x1 + x2 1}, f : X → R2 , f(x) = x, 则d||・||∞ (0, C) =

1 2 , d||・||2 (0, C) = √

2 2 . 令ε=1, 容易验证 (0, 0) / ∈ E(f, C, 1), (0, 0) / ∈ P(f, C, 1). 取?y=(?1, ?1), β =

1 3 , 则(0, 0) ∈ A∞(f,

1 3 ). 取?y=(?1, ?1), β =

1 2 , 则(0, 0) ∈ A2(f,

1 2 ). 这说明定理 3.1 的结果对 范数 和|| ・ ||2 范数不一定成立. 令Λ++ 1,p)T : p i=1 ?i =

1 且?i >

0, i = 1,p}, ?? ∈ Λ++ , α ∈ [1, ∞), y = (y1,yp)T ∈ Rp +, y 的(?, α) 范数定义为 ||y||? α = ||? y||α, y 的(?, ∞) 范数定义为 ||y||? α = ||? y||∞, 其中 ? y = (?1y1,pyp)T . 记A?

1 (f, ε) = {? x ∈ X : ||f(? x) ? ? y||?

1 inf{||f(x) ? ? y||?

1 : x ∈ X} + ε}, A? ∞(f, ε) = {? x ∈ X : ||f(? x) ? ? y||? ∞ inf{||f(x) ? ?........