２０１７年６月
Ｊｕｎｅ．２０１７ 运筹学学报
Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ Ｔｒａｎｓａｃｔｉｏｎｓ 第２１卷第２期
Ｖｏｌ＿２１ ＮＯ．２
ＤＯＩ：１０．１５９６０／ｊ．ｃｎｋｉ．ｉｓｓｎ．１００７—６０９３．２０１７．０２．００５
离散优化与连续优化的复杂性概念冰
邢文训 ，
摘要问题的复杂性概念起源于离散的图灵计算机理论的研究，在离散优化问题的研究中 被广泛的接受．近期连续优化领域的很多文章中提及ＮＰ难这个概念．从而来对比介绍离散 优化和连续优化研究中这两个概念的差异． 关键词复杂性概念，离散优化，连续优化 中图分类号Ｏ２２１，ＴＰ３０１．５ ２０１０数学分类号９０Ｃ６０，６８Ｑ２５
Ｃｏｍｐｌｅｘｉｔｙ ｃｏｎｃｅｐｔｓ ｆｏｒ ｃｏｍｂｉｎａｔｏｒｉａｌ ａｎｄ ｃｏｎｔｉｎｕｏｕｓ
ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ
ＸＩＮＧ ＷｅｎｘｕｎＩ，ｔ
Ａｂｓｔｒａｃｔ Ｃｏｍｐｌｅｘｉｔｙ ｃｏｎｃｅｐｔｓ ｏｒｉｅｎｔｅｄ ｆｒｏｍ ｔｈｅ ｔｈｅｏｒｅｔｉｃａｌ Ｔｕｒｉｎｇ ｍａｃｈｉｎｅ ａｒｅ ｗｉｄｅｌｙ ａｃｃｅｐｔｅｄ ｉｎ ｓｔｕｄｙ ｏｆ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ．Ｔｈｅ ｐｏｌｙｎｏｍｉａｌｌｙ ｃｏｍｐｕｔａｂｌｅ ａｎｄ ＮＰ・ｈａｒｄ ｃｏｎｃｅｐｔｓ ａｒｅ ｆｒｅｑｕｅｎｔｌｙ ｕｓｅｄ ｉｎ ｒｅｃｅｎｔ ｐａｐｅｒｓ ｏｎ ｃｏｎｔｉｎｕｏｕｓ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａ ｖｅｒｙ ｂｒｉｅｆ ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｓｈｏｗ ｔｈｅｉｒ ｒｅｌａ－ ｔｉｏｎｓｈｉｐ ａｎｄ ｄｉｆｆｅｒｅｎｃｅ ｕｓｅｄ ｉｎ ｔｈｅ ｔｗｏ ｆｉｅｌｄｓ． Ｋｅｙｗｏｒｄｓ ｃｏｍｐｌｅｘｉｔｙ ｃｏｎｃｅｐｔｓ，ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ，ｃｏｎｔｉｎｕｏｕｓ ｏｐｔｉｍｉｚａ－ ｔｉｏｎ Ｃｈｉｎｅｓｅ Ｌｉｂｒａｒｙ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ０２２１．ＴＰ３０１．５ ２０１０ Ｍａｔｈｅｍａｔｉｃｓ Ｓｕｂｊｅｃｔ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ９０Ｃ６０，６８Ｑ２５
０ 引言
计算复杂性理论成熟于２０世纪７０年代初 ］，是理论计算机划时代的一个成果．计
算复杂性概念和理论非常基础，一直吸引研究者的关注．美国Ｃｌａｙ数学所２０００年公布
了２１世纪的百万美金待解７个问题的第一个就是计算复杂性理论问题：Ｐ＝ＮＰ？
优化问题的研究和算法设计总离不开复杂性的概念，因此离散优化和连续优化领域
都会用到多项式时间问题ｆ可解）或ＮＰ难等概念．近期很多连续优化领域的研究学者愿
意用ＮＰ难来说明其研究问题的难度，但在连续优化模型的数据中或可行解区域中可能会
出现无理数或求解算法中会出现开方或指数运算等，如何处理这些的不同？
收稿日期：２０１７－０４—０４ 基金项目：国家自然科学基金（Ｎｏ．１１５７１０２９） １．清华大学数学科学系，北京１０００８４；Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃａｌ Ｓｃｉｅｎｃｅｓ，Ｔｓｉｎｇｈｕａ Ｕｎｉｖｅｒｓｉｔｙ Ｂｅｉｊｉｎｇ １０００８４，Ｃｈｉｎａ 十通信作者Ｅ—ｍａｉｌ：ｗｘｉｎｇ＠ｍａｔｈ．ｔｓｉｎｇｈｕａ．ｅｄｕ．
ａｎ ４０ 邢文 ２１卷
本文基于读者有图灵机复杂性理论的基本概念，对于计算复杂性理论中一些基本概
念，如判定问题、实例、算法、多项式时间算法与问题、ＮＰ问题类、ＮＰ完全和ＮＰ难，只
有在需要的时候才给出定义．
我们仅以离散最优化和连续优化问题，以对比的方式给出各自领域的复杂性概念，通
过一些简单例子来理解复杂性在这两个领域的差异．特别针对离散优化问题中的多项式
时间问题和连续优化问题中的多项式时间可计算性问题进行比对解释．
１ 实例规模、基本运算和可解概念
复杂性理论起源于计算机理论的研究，在优化问题研究中是一个非常基础的理论，早 期的工作可以追溯到２０世纪７０年代初Ｃｏｏｋ的一篇会议论文［１］．他基于图灵机的模型假
设，给出了多项式时间规约和ＮＰ完全的概念．由此我们知道有一类问题迄今为止还没有
多项式时间算法解决该问题．在图灵机的假设前提下，我们假设计算机只能存储有限位二
进制数据和进行有限位计算，所有实例的数据都是整数或有理数，无理数在计算机是没法
精确表示的．对于离散最优化问题，我们不但假设其所有系数是整数或有理数，还要假设
它的最优解在计算机中可以精确的表示，且在计算机中占据的规模符合要求．
对于离散优化问题，已形成了非常系统化的计算复杂性理论，详细的内容可以参考
文『３１．人们已经熟悉了ＮＰ完全和ＮＰ难这些概念，并对具有ＮＰ完全和ＮＰ难问题的难解
性予以广泛接受． 内点算法首先成功地解决了线性规划的复杂性分类［２】’将其归为多项式时间可解问
题，这是优化领域的划时代的成果．内点算法的复杂性结论采用图灵机的理论体系．随内
点算法在更为广泛问题中使用，它对解决连续优化问题的优势就越发显得突出 但针对离
散问题的图灵机复杂性理论就无法完全适应连续优化问题，于是产生了针对连续问题的
复杂性概念［４－６］．
连续问题的复杂性概念或多或少地模仿了离散问题的复杂性逻辑方法，由此引发了
离散优化问题研究学者和连续优化问题研究学者各自的理解和描述．
一般优化问题可写为 ｍｉｎ ｆ（ｘ）
ｓ．ｔ．９（ｘ）≤０， （１．１）
Ｘ∈Ｄ Ｃ ”
其中 称为定义域，ｆ：５０ 为目标函数，ｇ： ＿÷瓞 为约束函数．当 为离散点集
时，优化问题（１．１）称为离散优化问题或组合最优化问题，当Ｄ为连续点集时，该问题称为
连续优化问题． ＝｛ ∈７９ ｌ ９（ｘ）≤０）称为问题的可行解集合．
１．１ 离散模型
针对离散问题，计算复杂性的理论基于图灵机模型，或称为２进制模型．对于给定的
问题，当问题中的变量个数，系数等给定后，称为问题的一个实例．问题是实例的统称，实
例是问题的一个具体表现．图灵机模型要求实例中的所有系数是整数或有理数，目前的
计算机就是这样限定和设置的，也就有了３２位和６４位机的区别．给定一个实例后，计算机
以２进制的方式存贮实例的系数，它们在计算机中占据的空间大小称为实例的字长或规
模．算法针对问题而设计，但以每一个实例为实现对象．算法对计算机中存储的系数进行 ２期 离散优化与连续优化的复杂性概念 ４１
加、减、乘、除、比较、读、写等基本运算，最后得到问题实例的解答．这些基本运算的总
和称为算法对实例的计算量．
因为ＮＰ难问题的存在，算法设计分为启发式算法和精确算法．启发式算法是指那些
在可接受的计算复杂性要求内，给出问题实例的一个解的算法，这个解不一定是问题的最
优解，甚至连可行解也不是．精确算法必须给出问题的最优解．
记问题为Ｑ，实例为 ，字长为ｓ（ ），一个算法Ａ的计算量为ＣＡ（Ｉ）．若存在一个多项
式函数ｐ（．）满足：
ＣＡ（Ｉ）＝０（ｐ（ｓ（ ））），ＶＩ∈Ｑ，
则称Ａ是问题Ｑ的一个多项式时间算法，简称多项式算法，其中“０”表示被控制的含义，
即存在一个与任何实例无关的正常数Ｏｌ满足
ＣＡ（Ｉ）≤ ｐ（ｓ（ ）），ＶＩ∈Ｑ
上述的算法分类，具有离散优化研究的两个分析功能．第一是对算法的计算复杂性进
行分类．目前普遍接受的一个结论是：多项式时间的算法是一类好的算法．
离散优化问题复杂性理论中一个关键假设是其最优解可通过有理数可精确表示 而
一个求解离散优化问题的算法一定精确地求解到最优解．
复杂性分析的第二个功能是对问题的分类．若Ｑ存在多项式时间的精确算法，则称
为多项式时间问题．ＮＰ完全和ＮＰ难问题的定义还需要更多的概念，我们不在此赘述，所
具有的一个共同点是：到目前为止，还没有找到多项式时间的算法求解这类问题的精确最
优解．
１．２连续模型
当模型（１．１）中决策变量在定义域 ｎ连续取值时，称其为连续优化问题．由于
连续优化问题的定义域有连续性要求，可行解可以为定义域中任何一个实数，故不再限
定模型中的系数一定为有理数或整数．无理数在目前的有限位计算机中只能近似存储 而还有～大类的计算问题无法通过离散系统的有限基本运算计量其计算复杂性，如 上 的ｃｏｓ（ｘ）， 和 ｄｆ（ ｘ）等．连续系统的复杂性理论应运而生．在连续模型中，我们将一些
运算看成一个黑箱，不关心其核心的具体算法，如计算 上的ｃｏｓ（ｘ）， 和 等看成
一次运算，两个实数的加法看成一次运算，不再像离散的２进制模型中还要计算储存的位
数与对应位数之间的加法运算．因此实例的输入需要考虑：变量的个数，系数的个数和给
定的计算精度 ．
如对二次约束二次规划问题（ｑｕａｄｒａｔｉｃａｌｌｙ ｃｏｎｓｔｒａｉｎｅｄ ｑｕａｄｒａｔｉｃ ｐｒｏｇｒａｍｍｉｎｇ，简记
为ＱＣＱＰ１ ｍｉｎ三 ＴＱｏｘ＋ ＋ｃ。
】 一 一 ｓ．ｔ． ｔ ＋口 ＋Ｃｉ≤０，ｉ＝１，２，…，ｍ
ｘ∈ ．
其中 为决策变量，Ｑｔ∈ ，ｑｉ∈ ，Ｃｉ∈ ，ｉ：０，１，…，仇为给定常数．
它的输入：几个变量，（佗 ＋礼＋１）（ｍ＋１）个系数和一个给定的计算精度￡．它的实例系数
的规模仅考虑维数：ｏ（
ｎ ｍ），而系数的大小等因素一并放在Ｅ作为输入系数单独考虑．同 邢文｛：ｊ ２１卷
样的问题，当以离散模型讨论时，输入的字长需要考虑系数Ｑｉ，ｑｉ，ｃ ，ｉ＝０，１，…，ｍ的２进
制字符所占长度，变量个数等，所以在离散复杂性理论中，实例的输入规模为Ｏ（（ｎ２＋ｒｔ＋
１）（ｍ＋１）＋ｌｏｇ２『Ｐｆ），其中Ｐ为Ｑ ，ｑ ，ｃ。，ｉ＝０，１，…，ｍ中非零系数的乘积．
在连续模型复杂性理论中，实例的输入包含两部分：一是输入计算精度Ｅ＞０：另一个
是输入问题实例的维数，包括变量的个数和系数的个数．
连续模型的基本运算的计量方法为：两个实数间的加、减、乘、除、比较、读或写分别
看成一次运算；一些特殊函数的运算以黑箱的形式看成一次运算，如ＣＯＳ（Ｘ）， 和 等
看成一次运算．
对问题的最优解的理解也发生变化，这一点同离散优化问题差异较大．连续优化问题
的最优解可能是无理数，这时不能按离散模型区分到一个精确的离散问题的解，而只能按
给定的精度求出满足精度要求的一个解．同离散优化问题的想法一样，连续优化问题算法
设计中，我们首先关心多项式时间可计算问题，简称可计算问题．所谓连续优化问题Ｑ可
计算是指：存在一个算法Ａ和一个二元多项式函数９（．，．），对任意给定的￡＞０，算法Ａ计
算求解到ＸＡ（ ）并记目标值为ＶＡ（ ），问题（１．１）的理论最优值为Ｖｏｐｔ（ ），满足
ＶＡ（ｔ）一ｑＪｏｐｔ（／）Ｉ≤￡，ＶＩ∈Ｑ， （１．２）
且计算求解到ＸＡ（ ）和验证ＸＡ（ ）落在可行解区域或距可行解区域边沿距离不超过ｅ的区
域内的计算量为
ＣＡＵ）＝ｏ（Ｉ９（ｄ（ ）， ）），ＶＩ∈Ｑ，
其中ｄ（ ）是实例 的维数，Ｙ＝ｌｏｇ２（ ）．
上述可计算概念中，Ｙ＝ｌｏｇ２（ ）的要求非常之重要．由于将 ＞０看成输入，其在计算
机中的存储字长为ｓ（￡）＝ｌｏｇ。（ ），于是ＣＡ（Ｉ）：０（ （ｄ（ ），ｓ（￡）））是一个多项式时间算法．
连续优化问题的多项式时间可计算主要有两部分计算复杂性的考虑：第一部分是求
出一个解ＸＡ（ ）的计算复杂性．这一步得到的解因其用有限位字符表示，可能为原问题最
优解的一个近似表示 可能不是一个可行解．第二部分则需要计算判别是否落在可行解
区域内或可行解区域的周边．如对ＱＣＱＰ问题第二部分的验证过程就非常简单，只需验 证ｍ个约束 １ 一 一 言 Ａ（，） ＱｉＸＡ（Ｉ）＋鸟 ＸＡ（Ｉ）＋Ｃｉ≤
是否成立．这个验证算法的复杂性为Ｏ（ｎ２ｍ１，是一个多项式时间的验证算法．
对于非线性优化问题，有时判断一个解是否落在一个集合内或周边也是一个ＮＰ完全 的问题．一个经典的例子就是判断Ｕ∈ｃ，是一个ＮＰ完全问题［２］．其中ｃ称为协正锥，定
义为
ｃ：｛ｕ∈ｓ ｌ Ｔｕ ≥０，Ｖ ∈酞 ），
其中 ｎ表示ｎ阶实对称矩阵集合， 表示ｎ维欧氏空间的第一卦限．
２ 连续优化问题的复杂性结论是如何得到的？
２０世纪７０年代末８０年代初，数学规划中一个具有划时代意义的结论：内点算法［ 】是
求解线性规划问题的多项式时间精确算法，以此证明线性规划问题的多项式时间问题．原