第２４卷第６期 大 学 数 学 Ｖｏ１．２４，ＮＱ．６ ２ＯＯ８年１２月 ＣＯＬＬＥＧＥ ＭＡＴＨＥＭＡＴＩＣＳ ＤｅＣ．２００８ 有效解适合鞍点准则的条件 闫春雷 （青岛大学数学科学学院，青岛２６６０７１） ［摘要］建立了单目标优化问题的用次微分表达的对偶问题，并用其对偶性给出多目标优化问题的有 效解适合鞍点准则的条件． ［关键词］次微分；有效解；鞍点准则；强对偶性 ［中图分类号］０２２１．６ ［文献标识码］Ａ ［文章编号］１６７２—１４５４（２００８）０６—００９５—０４ 讨论以下多目标最优化问题： （Ｐ）ｒａｉｎ｛－厂（ ）ｌｇ（３ｃ）≤Ｏ，ＬＴＥＣ｝， 其中ｃ为局部凸线性拓扑空间ｘ中的凸集， －厂（ ）：一Ｃｆ】（ ），…， （ｚ）），ｇ（ ）：（ｇ （ ），…，ｇ （ ））． 假定－厂 ，…，ｆ ｇ 一，ｇ 均为Ｘ上的连续实凸函数，沿用习惯记号： 和ｉｎｔ 分别表示 ”中的非 负向量锥和正向量锥．ｙ＞ｊＯ∞ Ｅ ，．ｙ＞０㈢ ∈ｉｎｔ ．ａ 表示向量ａ的转置． 称（Ｐ）在有效解 。适合鞍点准则，是指对于ａＥ－ｉｎｔ 存在 。Ｅ－ ，使对一切ｚＥ Ｃ， ∈虱ｍ，有 Ｌ （ ｏ， ）≤Ｌ （ 。， 。）≤Ｌ （ ， 。）， 其中Ｌ。（ ，．ｙ）：＝＝：ａ ｆ（ ）＋ ｇ（ ）． 设 。为（Ｐ）的可行解，由 。可产生一个单目标问题： ” （ｓ） ｒａｉｎ｛ （ ）ｆ （ ）≤＿厂（ 。），ｇ（ ）≤ｏ， ∈Ｃ｝． ＝ｌ 在文［１］，［２］中分别给出了（Ｐ）在有效解 。适合鞍点准则的充要条件．本文建立了问题（Ｓ）用次微 分表达的对偶问题（Ｄ），利用（ｓ）与（Ｄ）的对偶性刻画了（Ｐ）在有效解 。适合鞍点准则的条件． 对于问题（Ｓ）引入以下集合与函数： Ｂ：一｛（ ，２）∈翼 × ” ｊ ∈Ｃ，使厂（ ）一ｆ（ｘ。）≤ ，ｇ（ ）≤ ）， Ｕ（ｙ， ）：一｛ Ｅ ＣＩ厂（ｚ）一ｆ（ｘｏ）≤ ，ｇ（ｚ）≤２｝， （ ， ）Ｅ Ｂ， ：Ｂ一 ：一 Ｕ｛～Ｃｘ３），ｖ（ｙ， ）一ｉｎｆ｛ ：ｉ＝ （ｚ）｝：ｒＥＵ（ｙ，ｚ）｝． １ 易证Ｂ为凸集且 为Ｂ上凸函数． 定义 在（ 。， 。）∈Ｂ的次微分 ａｕ（ｙｏ， 。）一｛（“，叫）∈ ”× Ｉ“ （ — ｏ）＋叫 （ ～ ｏ）≤ｖ（ｙ，ｚ）一ｖ（ｙ。，‘ｚｏ），（３，， ）Ｅ Ｂ｝． 建立（Ｓ）的对偶问题（Ｄ）： ｍａｘ｛ （厂（ ）一＿厂（ 。），ｇ（ ））一“ （ （ ）一，（ ０））一叫 ｇ（工）ｌ（“，叫）∈ａ （，（ ）一ｆ（ｘ０），ｇ（ｚ）），ｚ∈Ｃ｝． 引理ｌ 设 。为（Ｐ）的可行解，则．７２。为（Ｐ）的有效解当且仅当 。为（Ｓ）的最优解． 引理２｜】 设ｚ。为（Ｐ）的有效解，则（Ｐ）在 。适合鞍点准则当且仅当（ｓ）在最优解 。适合鞍点 准则． ［收稿日期］２００６—０９—２１ ９６ 大 学 数 学 第２４卷 引理３ 设（ ， ）∈Ｂ，（“， ）∈Ｏｖ（ｙ， ），则“Ｅ一 ，ｗＥ一 半． 证 任取 ∈Ｕ（ ，／ ），对于任意ｙ Ｅ ，显然有 ｙ Ｕ（ｙ，ｚ） Ｕ（ ＋ ｌ， ）． 因而 【 Ｉｆｎ ３ｃＥＵ（ｙ，ｚ）｝＞ｊｉｎｆ｛∑ （ｚ）Ｉ：ｃＥＵ（ｙ＋ｙ ， ）｝＝ｖ（ｙ＋ｙ，， ）． ＝ｌ 于是由（ ，叫）Ｅ８ｖ（ｙ，∑ ２）得 （ ｕ＇ｙｌ＝“ （ ＋Ｙ１一 ）＋ （ 一２）≤ （ ＋ １， ）一ｖ（ｙ， ）≤Ｏ． 由．）’ Ｅ 的任意性，“Ｅ—Ｉ风 ．同理可证ｗＥ一 ． （Ｓ）与（Ｄ）之间弱对偶性，即（ｓ）可行解目标函数值不小于（Ｄ）的可行解目标函数值是无附加条件 的．但强对偶性，即双方最优值相等是有条件的．下面给出强对偶性的条件． 定理１（强对偶性） 设 。为（Ｐ）的有效解，则（Ｐ）在－ｚ。适合鞍点准则当且仅当（Ｓ）与（Ｄ）的强对偶 性成立． 证充分性． 。为（Ｐ）的有效解，由引理１， 。为（Ｓ）的最优解．由（Ｓ）与（Ｄ）的强对偶性，存在（Ｄ）的 可行解（ ， ， ），使得 ∑ｆｋ（ 。）一 （，（ ）一ｆ（ｘ。），ｇ（２ｒ））一 （ （ ）一ｆ（ｘ。））一面 ｇ（２ｃ）， ＝１ 其中（ ， ）∈ａ （＿厂（ ）一厂（ 。），ｇ（ ））．由引理３， 五∈一 ， ∈一 ． 又因 。为（ｓ）的最优解，故∑ （ 。）一 （０，０）．于是Ｖ（－ｙ， ）ＥＢ，有 】 ｖ（ｙ， ）一ｖ（Ｏ，０）一 （ ，２）一∑ｆｋ（３ｃ。） ＝ （ ，ｚ）－－ｖ（ｆ（２ｒ）一，（ｚ。），ｇ（２ｃ））＋ （厂（ ）－－ｆ（ｘ。））＋ ｇ（ ） ≥ ｔ（ －－２）（ｊ）＋，（ 。））＋ （ｚ－ｇ（２ｃ））＋ （＿厂（；）一厂（ｚ。））＋ ｇ（ ） 一 ．）’＋训 一 （ 一０）＋ （ｚ一０） 成立．所以 （ ，面）∈ （Ｏ，Ｏ）． 因Ｖ．２Ｃ∈Ｃ，（＿厂（ ）一ｆ（ｘ。），ｇ（ ））ＥＢ，从而 ∑ｆｋ（ｚ。）＝＝ （ｏ，ｏ）≤ （厂（ｚ）一ｆ（ｘ。），ｇ（ｚ））一 （厂（ ）一ｆ（３ｃ。））一 ｇ（ｊｃ） 一１ ≤∑ｆ （ ）一 （，（ｚ）一ｆ（ｘ。））一 ｇ（．一ｒ）． 上式中令 — 。，得 ｇ（ｚ。）≤Ｏ．又因 ∈一 ，ｇ（ｚ。）≤ｏ，故 ｇ（ 。）≥０．因此 讪 ｇ（ｚｎ）一０． 于是 ∑ｆ￣女＝ｌ （ｃｏ。）一Ｕｔ（＿厂（ 。）一 （ 。））一训 ｇ（ 。） ≤∑ｆ （ 。）一ｕ （厂（ｚ。）一－，’（１ｚ。））一 ｇ（ｚ。） ＝１ ≤∑＾（ ）一 （，（ ）一，（ｚ。））一 ｇ（ ），Ｖ：ｒＥ Ｃ， Ｖ一（“，叫）Ｅ × ． 因此（Ｓ）在．ｚ。适合鞍点准则．由引理２，（Ｐ）在 。适合鞍点准则． 必要性．（Ｐ）在 。适合鞍点准则，由引理２，（Ｓ）在 。适合鞍点准则．因此存在“Ｅ一 ， ∈一 ，使得 第６期 闫春雷：有效解适合鞍点准则的条件 ９７ ∑＾（ 。）一“ （厂（ 。）～ｆ（ｘ。））一Ｗ ｇ（ｚ。） ；１ ≤∑＾（ 。）一 （厂（ 。）一ｆ（ｘ。））一ｗ ｇ（ｘ。） ｋ＿－１ ≤∑＾（ ）一 （厂（ ）一ｆ（ｘ。））一７—２３ ｇ（Ｌｚ），ＶｘＥＣ， Ｖ一（“， ）∈ ｘ （１） ：ｌ 成立． 下面证（ 。， ， ）为（Ｄ）的可行解，只需证（／一ｔ， ）Ｅ ａ ７３（ｆ（ 。）一ｆ（３５。），ｇ（３７。）），即（ ，７一．Ｕ） Ｅａｖ（０，ｇ（ｘｏ））成立． 由（１）得，Ｖ叫∈一 ，～叫 ｇ（，２７。）≤一 ｇ（ 。）．令 一０，得 ｇ（３７。）≤０．又因 。为（Ｐ）的可行 解，我们有７３３ ｇ（ｚ。）≥Ｏ．于是 叫 ｇ（ ｎ）一０． 另夕 ，Ｖ（．ｙ，ｚ）∈Ｂ，Ｖ ＥＵ（ｙ，２），有 ＿厂（ ）一ｆ（ｘ。）≤ ，ｇ（ ）≤ｚ． 由（１）得 ∑ｆｋ（ ）≥∑ｆｋ（ 。）十五 （＿厂（ ）～ｆ（ｘ。））＋ ｇ（ ）≥∑＾（ 。）十 ｙ＋ ． ＾：ｌ ｋ＝１ ＝１ 又因ｖ（Ｏ，ｇ（ｘ。））一∑ｆｋ（３ｃ。），故有 ｋ＝＝１ ｖ（ｙ， ）＝ｉｎｆ｛∑ｆｋ（ ）ｆ－厂（ｔ－，）一ｆ（ｘ。）≤ ，ｇ（ ）≤ ｝≥ （０，ｇ（ｘ。））＋ ｙ＋ｗ ． —ｌ 即 ｖ（ｙ， ）一ｖ（ｏ，ｇ（ｘｏ））≥“ Ｙ＋叫 成立．所以（ ， ）Ｅ ３ｖ（Ｏ，ｇ（ｘ。）），（ 。， ， ）为（Ｄ）的可行解．此时 （厂（ 。）～－厂（ 。），ｇ（ｘ。））－ｕ （厂（ 。）一ｆ（ｘ。））一 ｇ（ｘ。）＝ （０，ｇ（ｘ。））＝∑＾（ 。）． ：１ （Ｓ）与（Ｄ）最优值相等，即强对偶性成立． 定理２（逆对偶） 设 为（Ｓ）的可行解．若存在 ， ，使得（ ， ， ）为（Ｄ）的可行解且满足 ∑ （ｋ一１ ）一 （／ （ ）一ｆ（ｘ。），ｇ（ ）），五 （厂（ ）一ｆ（ｘ。））＋ ｇ（ ）一ｏ， 则 为（Ｓ）的最优解且（Ｓ）与（Ｄ）强对偶成立． 证设 为（ｓ）的任意可行解，则－厂（ ）－－ｆ（＝。）≤Ｏ，ｇ－（ｘ）≤０．又因（ ， ， ）为（Ｄ）的可行解，由弓 理３， ∈一 ， ∈～ ．由已知条件，得 一 （－厂（ ）－－ｆ（ｘ。），ｇ（ｚ））－－ｖ（ｆ（ｘ）－－ｆ（ｘ。），ｇ（ ）） ≥ （＿厂（ ）一ｆ（ｘ。））＋ ｇ（ ）一［五 （ （ ）一厂（ 。））＋ ｇ（；）］ 一 （，（ ）－－ｆ（ｘ。））＋ ｇ（ ）≥０． 因此 为（Ｓ）的最优解．由（Ｓ）与（Ｄ）的弱对偶性及条件 ∑＾（ｊ）一 （－厂（ ）一／’（ｚ。），ｇ（ ））， （＿厂（ ）一ｆ（ｘ。））＋ ｇ（ ）一ｏ， ｋ—Ｉ 得（ ， ， ）为（Ｄ）的最优解且（Ｓ）与（Ｄ）强对偶成立． 推论设 。为（Ｐ）的可行解．若存在“。，Ｗ。使得（ 。，“。，训。）为（Ｄ）的可行解且满足 ∑ｆｋ＾一ｌ （ｘ。）一 （ｏ，ｇ（ｘ。）），ｗ￣ｇ（ｘ。）一０， 则ｚ。为（Ｐ）的有效解且（Ｐ）在 。适合鞍点准则． ９８ 证 由定理ｌ，２及引理１可得． 大 学 数 学 第２４卷 ［参 考 文 献］ Ｅｌｉ 李师正，张玉芬．多目标最优化问题有效解的鞍点准则［Ｊ］．工程数学学报，１９９６，１３（３）：８１～８６． １９９６，１６（３）：１—６． ［２］ 李师正．有效解适合鞍点准则的条件［Ｊ］．数学物理学报，ｌ Ｒ Ｅ。Ｌｅｅ Ｄ Ｎ．Ｅｆｆｉｃｉｅｎｃｙ ｉｎ ｍｕｌｔｉｐｌｅ ｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ［Ｊ］．Ｍａｔｈ．Ｐｒｏｇｒａｍｍｉｎｇ，１９７７，１２： ［３］ Ｗｅｎｄｅｌ４０６—４１４． ［４］ Ｌｉ Ｓｈｉ—ｚｈｅｎｇ．Ａ ｄｕａｌ ｐｒｏｂｌｅｍ ｆｏｒ ｃｏｎｖｅｘ ｐｒｏｇｒａｍｍｉｎｇ ｉｎ ｏｒｄｅｒｅｄ ｖｅｃｔｏｒ ｓｐａｃｅｓ［Ｊ］．Ｏｐｔｉｍｉｚａｔｉｏｎ，１９９０，２１（３）： ３４３—３４９． Ｃｏｎｄｉｔｉｏｎｓ ｆｏｒ Ｅｆｆｉｃｉｅｎｔ Ｓｏｌｕｔｉｏｎｓ Ｓａｔｉｓｆｙｉｎｇ ｔｈｅ Ｓａｄｄｌｅ Ｐｏｉｎｔ Ｃｒｉｔｅｒｉａ ｙ＿ＡＮ Ｃｈｕｎ—ｌｅ （Ｍａｔｈｅｍａｔｉｃｓ Ｄｅｐａｒｔｍｅｎｔ，Ｑｉｎｇｄａｏ Ｕｎｉｖｅｒｓｉｔｙ，Ｑｉｎｇｄａｏ ２６６０７１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｓｅｔｓ ｕｐ ａ ｄｕａｌ ｐｒｏｂｌｅｍ ｏｆ ａ ｓｉｎｇｌｅ ｏｂｊｅｃｔｉｖｅ ｐｒｏｇｒａｍｍｉｎｇ ｉｎ ｓｕｂｄｉｆｆｅｒｅｎｔｉａｌ ａｎｄ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｃｏｎｄｉｔｉｏｎｓ ｆｏｒ ｔｈｅ ｅｆｆｉｃｉｅｎｔ ｓｏｌｕｔｉｏｎ ｏｆ ａ ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ ｐｒｏｇｒａｍｍｉｎｇ ｓａｔｉｓｆｙｉｎｇ ｔｈｅ ｓａｄｄｌｅ ｐｏｉｎｔ ｃｒｉｔｅｒｉａ ｂｙ ｔｈｅ ｄｕａｌｉｔｙ． Ｋｅｙ ｗｏｒｄｓ：ｓｕｂｄｉｆｆｅｒｅｎｔｉａｌ；ｅｆｆｉｃｉｅｎｔ ｓｏｌｕｔｉｏｎ；ｓａｄｄｌｅ ｐｏｉｎｔ ｃｒｉｔｅｒｉａ；ｓｔｒｏｎｇ ｄｕａｌｉｔｙ