约束非线性离散变量规划的最优性问题

D0I:10.13374/.issn1001-053x.1987.03.030 北京钢铁学院学报 J.Beijing Univ.of Iron Steel Technol, Vol.9No.31987 约束非线性离散变量规划的最优性问题° 陈立周路鹏 (机械设计教研室) 摘 要 本文讨论了含有离散变量的约束非线性规划问题，介绍了若干基本概念和定 义，并给出了该问题的最优性条件和收敛条件。最后文中给出了理论研究的应用 成果。 关键词：离散变量，离散最优化，适时约束，单位邻域查点。 Optimable Condition of Constraint Nonlinear Programmin g with Mixed Discrete Variable Chen Lijhou Lu Peng .Abstract· This paper describes an problem of optimality for constraint nonlinear programming with mixed discrete variable.Some of concept and definition is formulated and optimable conditions and convergence is presented,La- stly,application for study of theory is introduced here. Key words:discrete variable,discrete optimization,active constraint,neighborhood finding point. 引 言 近十几年来，关于混合离散变量优化理论与方法的研究无论在数学规划中还是在 ●本项目得到国家自然科学基金资助 1986-10-18收稿 65

北 京 钢 铁 学 院 学 报 约束非线性离散变量规划的最优性问题 ’ 陈立周 路 鹏 机械设计教研室 摘 要 本文讨论了含有离散变量 的约束非线性规划 问题 。 介绍 了若干基本概念和定 义 ， 并给出了该问题的最优性条件和 收敛 条件 。 最后文中给 出了理论研究的 应用 成果 。 关键词 离散变量 ， 离散最优化 ， 适时约束 ， 单位邻域查点 扭 眼 日路 “ 乙“ 尸 爪 。 ， ， 乡 一 ， 双 。 引 言 近 十几 年 来 ， 关 于混 合 离散变量 优化理论与方 法的研究 无论在 数学规划 中 还 是 在 本项目得到 国家 自然科学基金资助 一 一 收稿 DOI ：10．13374／j ．issn1001－053x．1987．03．030

工程优化设计中，都受到了极大的重视。文献1)中指出“离散最优化是数学规划和运筹学 中最有意义，但也是最困难的领域之一”；在文献12)中也认为，“离散变量优化设计方 法是当前工程优化设计发展的主要方向之一”。这是由于现实世界中的问题都普遍包含 着整型、离散型和连续型的变量，尤其是在工程设计、计算机科学、运筹学、可靠性工 程以及自动控制等领域中，参数的离散化更具有重要的意义。 目前文献中所见到的，几种典型的约束非线性混合离散变量优化方法有：拟离散 法(2-)、离散变量的惩罚函数法(4-5)、离散随机搜索法(6)、离散搜索法7-8)、探试组合型 法9)和离散分技定界法10)等。这些算法虽各有特点，但它们的通用性和对问题的适应 性都较差，因而求解问题的可靠性和效率都不高。为此，如何结合离散变量最优化问题的 特点，利用数学规划中的最优搜索策略思想和组合数学中的查点思想来发展混合离散变 量的最优化理论，以促进有效算法和程序的发展是非常必要的。近年来，我们所研制的 几种通用性强的软件，如MDOD(15)、MDCP·已在国内得到了较大规模的推广，取得 了较好的社会效果和经济效益。 1混合离散变量最优化问题 考虑如下一般形式的约束非线性混合离散变量的最优化问题来研究这一理论 min f(x) 5·tg:(x)≤0i=1,2,…,m (1) x=(x,x)∈RDXRS=Rn 其中f是R"上定义的纯量值函数，g是从R到R的函数；xP是p元离散（包括均匀和非 均匀)和整型变量，x是n-p元连续型变量。显然，当x”=中时，即为全连续问题；当 x=中时，即为全离散问题。如果连续变量规定有x≤x:≤x”（i=p+1,P+ 2,…,·)，则可以对它作拟离散化处理，其拟增量为 e:=(x9-x1)/(1:-1) i=p+1,p+2,…,n (2) 其中1：为拟离散值域内离散值的最大个数。实际上，ε：值的大小可根据生产实际要求（如 制造、安装、度量精度等)来定。这样，就可将问题(1)都按全离散问题来讨论。 在离散空间内，定义有效离散集 x=(xii,Vii (8) 其中下标i=1,2…,n为离散变量维数，j=1,2,“,1:为离散值所取的个 数，高散变量x:沿其坐标轴方向的相邻离散值的差称为增量，即 正增量：△=X:j+1-xii 负增量：△：=xi1-1-xii (4) 一般|△|≠|△；|，但对拟离散变量|△1I=|△i「=ei。 定义2.1设x∈RD,集合 帝待发表· 66

工程优化设计中 ，都受到 了极大的重视 。 文献〔 〕 中 指 出 “ 离散最优化是数学规划和运筹学 中最 有意义 ， 但也是 最困难的领域之一” 在文献〔 “ 〕 中也认 为 ， 、 “ 离散变量优化设 计方 法是 当前工程 优化设计发展 的主要方 向之一” 。 这是 由于现实世界中的 问题都普遍包含 着整型 、 离散型 和连续型 的变量 ， 尤其是在工程设计 、 计算机科学 、 运筹学 、 可靠性工 程 以及 自动控制等领 域 中 ， 参数的离散化更具有重 要的意义 。 目前文献 中所 见到 的 ， 几 种典型的约 束非线性混 合离散变量 优化方法 有 拟 离 散 法〔 一 、 离散变量的惩罚 函数法 〔 ‘ 一 〕 、 离散随机搜索法 〔 〕 、 、 离散搜索法〔 一 〕 、 探试 组 合 型 法 〕和 离散分技定界法 〔 〕等 。 这 些算法虽各有特点 ， · 但它们 的通 用性和 对 问题的适 应 性都较差 ， 因而求 解 问题的 可 靠性和效率都不 高 。 为此 ，如何结合 离散 变量 最优化 问题的 特 点 ， 利 用数学规划 中的最 优搜索 策 略思想 和组合数学 中的查点 思想 来发展混 合离散变 量 的 最优化理论 ， 以促进 有效算法 和程 序的发展 是 非 常必要的 。 近 年 来 ， 我们所研 制 的 几 种通 用性 强 的软件 ， 如 〕 、 已在 国 内得到 了 较大规模的推广 ， 取 得 了较好 的社 会效果和经 济效益 。 混合离散变量最优化 问题 考虑如下一 般形 式的约 束非 线性混 合 离散变量的最优化问题来研究这 一 理论 火 · 劣 簇 ， ， … … ， 戈 ， ‘ 〔 ” 其 中 是 ” 上 定义 的纯量 值 函数 是 从 ” 到 的 函数， 尸是 元 离散 厂 包括 均 匀 和 非 均 匀 和 整型变量 二 ‘ 是 一 元连续型 变量 。 显然 ， 当尸 小时 ， 即为全连续 问题， 当 二 “ 小时 ， 即为全离散问题 。 如果 连 续 变 量 规 定 有 专《 、 簇 丫 二 ， ， · ” … ， ， 则 可 以对它作 拟 离散化处理 ， 其 拟增量为 。 一 专 八 、 一 ， ， ‘ 二 ’ 二 ， 其 中 为拟 离散值域内离散值的最大个数 。 实际 上 ， 。 值的大小 可根据生 产实际要求 如 制 造 、 安装 、 度量精度等 来定 。 这 样 ， 就 可将问题 都按全 离散 问题 来讨论 。 在 离散空 间内 ， 定义 有效离散集 二 ， 其 中下标 ， ，’ … ， 为 离散变量 维数 ， 二 ， ， “ 一 ， 为 离散值所 取 的 个 数 ， 公高散 变量 沿其坐标轴方 向的相 邻 离散值的 差称 为增量 ， 即 正增量 △士 十 一 负增量 △ 卜 ， 一 一般 △士 子 △下 ， 但对拟离散 变量 △士 定义 设劣 任 。 ， 集 合 待发表 △万 。

UN (x) xi+△i,x,x:+△ (5 xi-ei,xi,xi+i 称为离散点x的单位邻域。在此邻域内共有3”个离散点。 定义2.2 集合 NC(x)=x UN(x)nei,Vi} (6) 称为坐标邻域。在坐标邻域内共有2·+1个点。 定义2.3， 设x∈R°，若Vx∈UN(x·),恒有f(x)≤f(x),则x·为无约束 局部离散最优解；若VxENC(x·),恒有f(x·)≤f(x),则x·为局部伪离散最优 解。 在现有的不少算法中，如圆整法、拟离散法等，往往以求得局部伪离散最优解为前提 2 最优性条件 设离散点的可行集D={x【g:（x)≤O,V:}∈R,在约束非线性离散变量问题 中，则其最优点x·的约束条件将隐含了这样的假设：g:(x·)+C:=0,使得问题显 著地变得更加难以求解。为此，先给出几个重要的概念。 定义3.1集合 W={△x|△x7f(x)<0 ·(7) 为向量-7f指向的闭半空间，7f为拟次梯度向量15)。 定义3.2集合 z={△x|△t,△i,0,V:} ~(8) 称为x在UN(x)内的可变动范围。 因此，集合 H=WOZ (9) 具有如下性质：若存在△x∈Z,使f(x+△x)<f(x),则△x∈H。这是由于若将 f(x+△x)作线性近似展开，必有△xVf≤0，即△x∈W,由式（9)推知，则有 △x∈H。 由集合H的性质可知：若x+△x点优于x点，则△x∈H。但其逆不一定正确，因为不 一定能保证满足x+△xED条件。这给我们一个极重要的启示：当在UN(x)内搜索最 优点时，起作用的约束必然是那些“穿”过H的约束。换言之，若某约束g:(x)=0 在R·中所形成的超曲面与H相交，则此约束面不但离x点很近，而且对H内的各离散点 都有可能起限制的作用，我们称此类约束为适时约束。 定义3.3设C:=-g:(x),若C1<C,则i∈I(x),称I(x)为适时约束的 下标集合。 C:为约束g:(x)的违反估计量，其计算如下：设△x∈Z,若x+△x不∈D,则由约 67

介 十 △士 劣 ‘ △夏 ， 一 ， ， 次 称 为离散点， 的单位邻域 。 在此 邻域 内共有 ” 个 离散点 。 ‘ 定义 集合 二 二 ， 称 为坐标邻 域 。 在坐标邻 域 内共 有 ” 十 个点 。 定义 设’ 任 “ ， 若 二 任 二 ‘ ， 恒有 扩 《 二 ， 则扩 为无约 束 局 部离散 最优解 若 任 护 ， 恒有 妙 簇 二 ， 则扩 为局 部伪离散 最 优 解 。 在现有的不 少算法 中 ， 如 圆整法 、 拟 离散法等 ， 往往 以求 得局 部伪 离散 最优解为前提 最优性条件 设 离散点的可行集 二 《 ， 、 〔 尺 ， 在约 束非 线性离散 变量 问 题 中 ， 则其最 优点扩 的约 束条件将 隐含了这 样的假设 扩 、 ， 使得 问 题 显 著地变得更加难以求解 。 为此 ， 先给 出几个重要 的概念 。 定义 一 集合 王△、 △了可 二 为 向量 一 亏了指 向的 闭半空 间 ， 前为拟次梯度向量 〔 ‘ ，。 定义 集 合 △二 △宵 ， △下 ， ， 一 称 为 在 二 内的可 变动 范围 。 因此 ， 集合 具 有如下 性质 若存在 △二 〔 ， 使 二 △二 ， 则△二 〔 。 这 是 由 于 若 将 十 △ 作 线性近似展 开 ， 必 有△尹 良 。 ， 即△二 任 ， 由式 推 知 ， 则 有 △ 任 。 由集合 的性质可知 若二 △， 点优于习氛 ， 则 △二 任 。 但其逆 不 一 定正确 ， 因为不 一 定能保证满足 二 十 △二 〔 条件 。 这 给 我们 一个极重买的启示 当在 二 内搜索最 优 点时 ， 起作 用的约 束必 然是 那 些 “ 穿” 过 的约 束 。 换言 之 若某约 束 、 、 在 ” 中所形 成的 超 曲面与 相 交 ， 则此约 束面 不 但 离二 点很近 ， 而 且对 内的各 离散点 都有可 能起 限制 的作 用 ， 我们 称此 类约 束 为适 时约 束 。 定义 设 一 、 二 ， 若 ， 则 任 二 ， 称 二 为适 时约 束 的 下标集合 。 ，为约 束 ， 二 的违反 估计量 ， 其计算如下 设 △ 〔 ， 若 十 △ 不 〔 ， 则 由约

束g1(×)线性展开有 △x7gi(x)>-g:(x)=C: (10) 或 Ax:(,）+ax(会；）+…+△x(会经：>c (11) 引入符号函数 1 E>0 Sga (E 0 E=0 (12) -1E<0 若使△x={△x|△t,△i,0,V:}满足 s8a(ax)=5g(-,）i=1,2,,a (13) 则必有△x∈H。将式(13)代入式(11)得 sga(-)Ax(0,)+sa()Ax(80:-）++ +Ss(A )ax.()>C (14) 为使保证不漏掉适时约束，应找出使式(14)左边为最大的项，即所有正数项之和，令 1=iIs(-)Ax(8>0,V,} (15) C-图5(-，）4x(0） (16) 代入式(14)得负数项之和为 -5(-）x(2）人-G,-e) (17) 故有 C.>C: (18) 由此得证。式(18)可作为判别适时约束的条件。 根据以上讨论，通过对适时约束g:(x)+c:=0、i∈I(x)附加非负乘子，就可以从 式(1)导出离散变量的拉格朗日函数 L (u)=min {f(x)+ui(gi (x)+ci) (19) XERD iel(x) 因为x在离散空间中是有限个点，所以L(u)对所有都是实值函数。但是由于求优时 所用的算法应具有组合数学性质，所以这是拉格朗日函数在离散最优中的第一个基本特 性，这与一般情况下的拉格朗日函数不同，不能通过求解非线性方程组7f(x)+ 68

束 二 线性展开有 △二 ，而 二 一 二 ‘ 或 △一 箫 △一 会纷 一 ‘ △二 长是士 引入符号函数 一 若使△笑 二 厦△ △ ， △万， ， 满足 。 ， ‘ 、 。 △ 、 。 叹。 少 气、 一 一 一丈二 一 口 入 则必有△二 〔 。 将式 代 入式 ， ， “ · … ， 得 · 一 橇升 △一 甲 箫 · 。 一翼一、 △ 。 衅导 、 已 盖 ， 、 。 盖 一 一 瑟 “ 瓷于 。 · … 为使保证不漏掉适 时约 束 ， 应 找 出使式 左边 为最大 的项 ， 即所 有正数项之和 ， 令 ， ‘ ，， · 一 一 奇 △一 一条十 ， ， 瓦 二 爵 · 一兴二 △一 、 ， 瓷份 代 入式 得负数项之和 为 。 △ 、 ， △ 、 、 名 《 一 一下岑一 △ ，卜 羚乙 】 一 忿 ， 厂。 一 、 △ ，一 ’ 、 △ 一 、 “ ， 夕 、 “ 一 ， 故有 由此 得证 。 式 可作 为判别适时约 束 的 条件 。 根据以上讨论 ， 通过 对适时约 束 劝 、 式 导 出离散 变量 的拉格 朗 日函数 一 〔 附加非 负乘子 ， 就可以从 “ 劣 因 为戈在离散空 间中是 有限个点 ， 所 以 “ 对所 有 都是 实值 函数 。 但是 由于求 优 时 所 用 的算法 应具 有组合 数学 性 质 ， 所 以这 是 拉格 朗 日函数在 离散最优 中的第一 个基本特 性 ， 这与一般 情 况下 的 拉格 朗 日函数不 同 ， 不 能通过 求 解 非 线 性 方 程 组

u7g(x)=0得到最优解。其次是由于式(19)中的x的离散性引起了它的不可微性， 所以使得下面讨论的对偶问题成为一个不可微的最优化问题，这样只能使拉格朗日函数 中u的选择取决于对式(1)的最优充分条件。 若对于x∈RP和u≤0，有 D L(u)=f(x)+u(g(x)+c) ②u(g(×)+c)=0 ③g(x)≤c 则称(x、“)满足离散最优化问题(1)的最优性条件。 定理3.1如果（x、)满足离散问题(1)的最优性条件，则x是问题(1)的最 优点x“,亦即x=x°。 证明：因为x·∈R°，而且由条件③有g(x°)≤c,所以x·点显然是一个可行域D中 的离散点。设在可行域中有另一点x∈D二RD,则由条件①有 L(w°)=f(x·)+u°(g(x°)+C) ≤f(x)+w(g(x)+c)≤f(x) 其中最后一不等式是由于u>0和g(x)+c≤0而得到的。但由条件②有L(u)=f(x),· 因此对所有可行的x,均有f(x°)≤f(x)。 定理3.2如果x°是满足问题(1)的最优性条件，则作为一种离散搜索算法的收敛 条件是，以x·点所生成的集合 T=WOS 必为空集。 其中 W={△x|△x又f(x*)≤0} S={△x|△T7gi(x")≤ci,i∈I(x)} 证明：设x=x°+△x,因由线性展开可得 f(x)≈f(x")+△xr7f(x") g:(x)≈g(x°)+.△xT7g:(x)i∈I(x) 若x"是原问题的局部离散最优解，而又T中中，则必存在一个△x∈Z,使△xT△f(x) ≤0和△x7g:（x°)≤c:同时成立，故x不是离散最优解，与题设矛盾，由此得证。 由定理3,2又可作出如下的一个极为重要的推论。 推论3.1T为满足目标函数下降性和约束可行性的单位领域内离散点的集合，若 x”点为非离散最优解，则在T内的任一个△x均可使x+△x满足f(x+△x)<f(x)和 x+△x∈D。因此，当需要在UN(x)内查点时。只需设法查找T内的离散点即可。 69

。 得到最优解 。 其次是 由于式 中的二 的离散性引起 了它 的不可微性 ， 所 以 使得下面讨论 的对偶 问题成 为一个不 可微的最优化 问题 ， 这 样只 能使拉格 朗 日函数 中 “ 的选 择取 决于对式 的最优充分条 件 。 若对于 〔 ” 和 ， 有 ① 。 二 一卜 名 二 ② 二 ③ 二 则称 二 、 满足 离散最优化 问题 的最优性 条件 。 定理 如果 义 、 满足 离散 问题 的最优性条件 ， 则二 是 问题 的最 优 点扩 ， 亦 即二 扩 。 证 明 因 为扩 〔 “ ， 而且由条件③有 二 ’ 簇 ， 所 以’ 点显 然是 一 个 可行 域 中 的 离散 点 。 设 在可行 域 中有另 一 点 〔 创 “ ， 则 由条件①有 二 十 ’ 一 。 劣 其中最后一不 等式是 由于。 和 劝 十 。 成 。 而得到 的 。 但 由条件② 有 沪 ， 因此 对所 有可行 的二 ， 均 有 二 ， 《 二 。 定理 如果 ’ 是 满足 问题 的最优性条件 ， 则作 为一种离散搜索 算法 的 收 敛 条件是 ， 以二 ， 点所 生 成 的集合 二 门 必为空集 。 其 中 △” △二 示 二 · 二 笼△ △ ， 二 镇 ， 任 二 证 明 设二 扩 十 △ ， 因 由线性展 开 可 得 岛 △ 劣 岛 △戈 任 义 若尹 是 原 问题的局 部 离散 最优 解 ， 而 又 笋 中 ， 则 必存在 一 个 △二 任 ， 使 △了 应 护 和 △ 扩 成 同时成立 ， 故扩 不 是 离散 最优 解 ， 与 题设 矛盾 ， 由此 得证 。 由定理 又 可 作 出如下 的一 个极 为重 要 的推论 。 推论 为满 足 目标 函数下 降性 和约 束可行 性 的单位领 域 内离散 点的集 合 ， 若 点 为非 离散 最 优解 ， 则在 内的 任一 个 △ 均 可 使二 十 △戈 满足 二 十 △二 二 ， 和 、 十 △二 任 。 因此 ， 当需要在 二 内查点时 。 只需设 法 查找 内的 离散 点 即可