简介围绕拟凸问题如何转化为凸问题可行性问题这份docx文档面向学习优化理论、机器学习与运筹学的读者重点讲清拟凸函数与凸函数的差异、凸问题解集特性以及借助二分搜索确定阈值来求解原问题的完整思路。压缩包内仅有1个docx文件约200KB篇幅紧凑适合作为课程复习、算法推导查阅或研究入门时的案头笔记。文中从拟凸函数的定义与全局最优性切入说明为何需要将原问题改写为带新变量和约束的凸可行性问题再给出二分算法的初始化、区间收缩与边界更新步骤并讨论函数值与中间阈值比较时的两种分支处理。已有559人学习读者可据此理解转化建模的关键环节掌握阈值搜索的终止条件与实现细节并对照自身问题检查可行性判定是否严密。1. 拟凸问题到底“凸”在哪一片不会被切成两半的低地想象你手里有一张地形图规则很简单把海拔不超过某条水位线的地方涂成蓝色。有的地形蓝区是一整块盆地有的地形蓝区东一块西一块碎成好几片。拟凸问题Quasiconvex Problem研究的正是前一种地形——不管水位线定在哪一米被淹的区域永远连成一片不会被切开。这条“低处始终连成一块”的性质就是拟凸最朴素的画面。抓住这片连通的低地后面的推导才有支点正因为低处连成一块“函数值不超过某个阈值”这个条件才能当成一个规整的约束来用也正因为如此人们才有底气把求最小值的问题改造成一连串“能不能不超过这个阈值”的是非题再用二分算法一次次砍半逼近答案。2. 凸问题凭什么好解一条线段不越界带来的连锁好处凸优化在机器学习、数据分析、运筹学里几乎是标准件很多求解工具默认你递过去的问题就是凸的。这种偏爱不是因为凸函数长得规整好看而是因为它附赠了几条别的函数给不了的保证。这几条保证恰好是理解拟凸为什么麻烦的参照系——先知道“好”长什么样才知道“差一档”差在哪里。2.1 凸集与凸函数一条线段不越界的世界先说集合。一个集合是凸的意思是里面随便挑两个点连成线段线段上每一个点都还在集合里。实心圆、正方形、半空间、整条直线都满足这个条件月牙、甜甜圈、五角星则不满足。判断方法很土但很好用拿一把尺子架在集合上尺子不出去就是凸的。再说函数。函数 f 是凸的意思是图像上任意取两点连一条直线这条线叫弦弦永远不低于函数图像本身。碗的内壁是典型形象碗底最低往两边走越走越高弦架在碗口上方自然压不到碗里。写成式子是f(λx (1−λ)y) ≤ λf(x) (1−λ)f(y)其中 0 ≤ λ ≤ 1。这个“加权平均”的形式是关键。它允许你按任意比例混合两个方案并保证混合后的效果不差于两个方案效果的同样比例混合。工程上这意味着折中方案不会突然崩掉两个参数各取一半结果至少不比各取一半的预期差。二次函数、指数函数、各种范数、线性函数都满足这条而像 x⁴ − 3x² 这种有两个坑的函数就不满足两个坑中间那段凸起来的部分把弦顶穿了。2.2 局部最优就是全局最优这条保证值多少钱局部最优是指存在一个小范围在这个范围里没有比它更好的点。全局最优是指在所有可行点里它最好。对一般函数这两件事可以差得很远。梯度下降只保证走到一个“四周都比自己高”的点那个点完全可能只是个小坑翻过旁边一道坎就有更低的谷底。凸函数上这两者重合。于是“下坡走到走不动”就等于“找到了全局最好”。这条保证省掉的麻烦做过非凸优化的人都懂要多起点重启要随机初始化要模拟退火、遗传算法轮着上跑十次出十个结果还得挑一个看起来最像样的。模型稍微改一行昨天能跑出结果的参数今天全废这种玄学体验的根源就是丢了“局部即全局”这条保证。所以在工程实践里能建模成凸问题的几乎没人愿意建模成非凸的。凸性不是审美偏好是省下来的算力和少掉的后悔药。2.3 解集是凸集两个好答案之间的折中也是好答案凸问题还有一条常被忽略的性质最优解的集合本身是凸集。也就是说如果 x 和 y 都是最优解那么它们连线上的任意一点也是最优解而且目标值完全相同。推导只有一行设最优值为 p则 f(λx (1−λ)y) ≤ λf(x) (1−λ)f(y) p而 p 已经是最小值不等号只能取等。这条性质在工程上的价值很直接你算出两个方案可以放心取中间值。两个调度方案各取一半时间比例两个模型参数做加权平均结果不会突然变差。而非凸问题里两个各自优秀的解中间那一点可能是灾难现场——这正是很多“模型融合”翻车的原因。2.4 求解器为什么偏爱凸问题梯度下降、投影梯度、内点法、切平面法在凸问题上都有一整套收敛速度的保证迭代多少步、误差降到什么量级大致能预期。而一般情形下的非凸问题在最坏情况下难度会陡增没有哪套算法敢承诺一个可接受的步数。于是工程上形成了一条朴素的策略能写成凸的就写成凸的写不成凸的就找一个凸的替身——松弛、近似、外包都是这个思路。拟凸问题转化为凸问题可行性问题本质上就是“找替身”的一种原问题的目标函数不凸不好直接优化但它的某个侧面是凸的那就绕到那个侧面上去做文章。3. 拟凸比凸宽在哪一步从“加权平均”退到“取较大的那个”拟凸函数是凸函数的一次放宽放宽的幅度很微妙只把定义里的加权平均换成了“取两端中较大的那个”。这一步退让看起来不大却让函数家族一下子宽了很多代价是凸优化那套成熟工具不再能直接套用。3.1 定义只要求“不超过两端里较大的那个”一个函数 f 称为拟凸的如果对定义域内任意两点 x、y 和任意 0 ≤ λ ≤ 1都有f(λx (1−λ)y) ≤ max{f(x), f(y)}。和凸函数的式子对照着看凸要求中点的函数值不超过两端的加权平均拟凸只要求不超过两端里较大的那个。因为加权平均永远不超过最大值所以凸函数一定是拟凸的反过来不成立拟凸的家族严格更大。例子能说明这个差距。f(x) x³ 在实数轴上是单调递增的任取两点中间的函数值必然夹在两端之间自然不超过较大的那个所以它拟凸但它的二阶导是 6x在负数区间为负曲线在那儿是向下弯的不满足凸性。再比如 f(x) √|x|图像在原点是个尖角两侧向下弯明显不是碗形但它的下水平集是一段区间仍然拟凸。反过来f(x) sin x 在 [0, 2π] 上就不是拟凸的。取阈值 −0.5满足 sin x ≤ −0.5 的点分布在两段互不相连的区间里低处被切成了两半——这正是第 1 章那片“碎成好几块”的地形。3.2 下水平集把函数比较翻译成集合判断拟凸有一个等价的集合版定义用起来比公式方便得多。给定阈值 t把满足 f(x) ≤ t 的所有点收集起来记作 S(t) {x | f(x) ≤ t}这叫下水平集。函数是拟凸的当且仅当对每一个 tS(t) 都是凸集。道理不难若 f 拟凸取 x、y 都在 S(t) 里那么 f(x) ≤ t 且 f(y) ≤ t于是 max{f(x), f(y)} ≤ t再由拟凸的定义连线上的点函数值也不超过 t整条线段都在 S(t) 里。反方向同样成立。这个翻译的价值在于它把“函数值够不够小”这种数值比较变成了“集合是不是连成一块”的形状判断。回到水位线的比喻水淹到哪一米露出来的低地都必须是一整块这就是拟凸在几何上的全部要求。而“一整块”正是凸集最好辨认的特征。3.3 麻烦在哪目标不凸工具就不好使拟凸函数依然保留了那条最诱人的性质在凸定义域上局部最小值就是全局最小值。听起来好像问题解决了其实麻烦出在算法这一侧。函数性质上的保证不等于算法行为的保证。最典型的例子还是 f(x) x³它在 x 0 处的导数为零梯度法走到这里会停住可这个点根本不是最小值函数在整条轴上都没有下界。也就是说梯度为零只是“坡变平了”不保证脚下是谷底。凸函数上这个推理成立拟凸函数上不成立。更麻烦的是工具箱里的一大半东西都失效了投影梯度要靠可行域的凸性这条还在但拉格朗日对偶的强对偶性质、KKT 条件的充分性、解集的凸性这些在拟凸问题上一般都不再成立。你没法像处理凸问题那样解一个对偶问题再回头验证。算法能走但走到哪、停得对不对说不清楚。3.4 比值型目标拟凸最常出现的地方拟凸不是数学家的玩具它在实际问题里出现得相当频繁最常见的形状是比值型目标。比如最小化(aᵀx b) / (cᵀx d)分母代表收益、产量或者耗时这类恒为正的量。单位成本最小化、性价比最大化、效率指标优化都是这个形状。这类函数一般不凸但它是拟凸的甚至是拟线性的既拟凸又拟凹。关键在于判定“f(x) ≤ t”可以两边同乘分母分母恒正不等号方向不变化成 aᵀx b ≤ t(cᵀx d)这是一个线性不等式。线性不等式定义的是半空间是凸集。于是给定 t 之后“有没有解”变成了一件事先很好处理的问题。特征凸函数拟凸函数定义中点值 ≤ 两端的加权平均中点值 ≤ 两端中较大的那个下水平集凸集凸集且这是等价刻画局部最小是否等于全局最小是是凸定义域上梯度为零是否即全局最小是可微时不一定强对偶与 KKT 充分性通常成立一般不成立常见求解思路梯度法、内点法二分加可行性判定这张表里最值得盯住的是第三行和第四行的分裂局部即全局这条性质还在但算法没法可靠地找到那个全局点。正是这个裂缝把思路推向了“不直接优化改去判定”。4. 把求最小值换成求可行二分算法在阈值上做的那点事原问题是找一个让 f 尽量小的点但 f 不凸直接优化没把握。换个问法给定一个阈值 t能不能找到一个点让 f 的值不超过 t这个问题只问“有没有”不问“多好”听起来像是退让实则是把问题搬到了一个更结实的地基上。4.1 阈值判定从“最小是多少”变成“能不能不超过 t”把原问题写成 min f(x)约束是 x 属于可行域 C。现在引入一个阈值 t改问存在 x ∈ C 使得 f(x) ≤ t 吗这个问题的答案只有两种。如果“有”说明最优值不会超过 tt 是一个偏保守的估计如果“没有”说明最优值一定大于 tt 定得太严了。两种回答都在告诉我们最优值落在哪一边这就是二分能工作的全部信息基础。更关键的是这个判定为什么可做。条件 f(x) ≤ t 等价于 x ∈ S(t)而拟凸性保证了 S(t) 是凸集。于是“存在一个同时属于 C 和 S(t) 的点”变成了两个凸集是否相交的问题。凸集求交非空是一件有成熟手段的事情可以写成一族凸约束交给内点法也可以用投影方法迭代。原本那个凹凸不明的目标函数被换成了一个纯粹的几何问题。这就是“拟凸问题转化为凸问题可行性问题”的全部秘密拟凸性不保证函数凸但保证每个下水平集凸于是函数值约束可以当一个凸约束用。二分算法则负责在外面一层一层地试探阈值。4.2 单调性二分能成立的那根支柱二分搜索能用的前提只有一个待搜索的判定必须是单调的。这里恰好满足。阈值 t 越大条件越松S(t) 越大越容易找到可行点。所以存在一个临界值 t*当 t ≥ t* 时判定为“有”当 t t* 时判定为“没有”。t* 就是原问题的最优值。二分就是在一条单调的是非序列上做猜测每次猜中间根据回答砍掉一半。它不要求函数可微不要求函数是凸的甚至不怎么关心函数长什么样只要求那个“是/否”的回答稳定可靠。这是它比梯度下降更皮实的地方也是它的软肋所在一旦回答不稳定整套推理就塌了。4.3 算法流程与代码骨架把判定函数当成一个黑匣子二分的骨架短得可以背下来。下面这段代码只表达结构具体判定交给外部实现def bisect_on_threshold(feasible, lb, ub, tol1e-6, max_iter200): feasible(t) - bool : 判断阈值 t 是否可行, 必须关于 t 单调不减 lb : 下界, 应当是一个已知不可行的阈值 ub : 上界, 应当是一个已知可行的阈值 tol: 终止精度, 区间窄于它就停 if not feasible(ub): raise ValueError(上界不可行, 初始区间没有框住最优值) for _ in range(max_iter): mid (lb ub) / 2.0 # 取中点作为试探阈值 if feasible(mid): ub mid # 中点可行, 最优值不高于它, 收紧上界 else: lb mid # 中点不可行, 最优值高于它, 抬高下界 if ub - lb tol: # 区间足够窄, 认为已经夹住最优值 break return ub # 返回可行的那一端, 保证结果可用代码里能读出三件事。第一lb 和 ub 不是随便给的它们的含义是“已知不可行”和“已知可行”如果 ub 本身不可行二分会在一个错误的区间里收敛出一个假答案所以开头直接抛错比后面悄悄出错好。第二每次迭代只调用一次判定代价就是一次凸可行性问题的求解开销。第三返回的是 ub 而不是中点因为 ub 一定是可行的那一端结果至少能满足阈值约束不至于给出一个连约束都不满足的数。参数怎么定可以照着这张表来参数含义怎么定lb下界必须不可行用松弛后的解或者问题先验给一个偏小的值ub上界必须可行先构造一个已知可行方案取它的目标值tol终止精度按目标值的相对误差要求定别小于判定本身的精度max_iter迭代上限防止浮点误差导致死循环正常情况远用不到4.4 收敛速度与几个常见翻车点二分的迭代次数很好估区间长度每迭代一次减半从 (ub − lb) 收到 tol需要的次数约是 log₂((ub − lb) / tol)。区间长度为 1、精度要求 1e-4 时大约 14 次区间长度为 100、精度 1e-6 时大约 27 次。这个增长速度慢得可爱精度每提高十倍只多三四次判定。但翻车点也集中在这几处。第一是初始区间没框住ub 不可行或者 lb 可行二分的结果就失去意义所以上界最好由一个构造出来的可行方案给出而不是拍脑袋估。第二是判定函数不单调内部用迭代法近似求解可行性时容差会让边界附近出现抖动同一个 t 问两次答案不一样二分会当成真的分界点最后收敛到一个假位置。第三是精度定得比判定精度还细区间收到判定分辨不出来的程度还在继续纯属白跑。第四是量纲问题目标值从几万跨到零点几的时候绝对精度不好使改成相对精度或者先做对数变换更稳。第五是判定本身很贵一次判定要解一个规模不小的凸问题二十几次叠起来就是二十几倍成本这时候得先算清楚这笔账值不值。5. 拟凸、单峰、可行性几个最容易混掉的概念区别这几个词经常在同一段话里出现含义却各有各的边界。混着用的时候感觉都对一旦要据此选算法差别就暴露出来了。5.1 拟凸与凸条件弱一档结论丢一片易混点两个词都带“凸”而且都保证局部最优即全局最优于是很容易当成可以互换的说法。为什么混这条相同的结论太显眼遮住了别处的差异。实际上拟凸只是在定义里把加权平均换成了取最大值弱了这么一档凸优化那套工具就掉了大半。怎么区分看定义里的组合方式是加权平均还是取较大者这是最直接的判别。再看能不能用对偶、KKT 充分性、解集凸性这些工具拟凸一般都不行。最实用的一条凸性保证“梯度为零即最优”拟凸不保证x³ 在原点就是现成的反例。所以拟凸问题不能直接丢给梯度法了事得走阈值判定这条路。5.2 拟凸与单峰一维的通俗说法高维会误导易混点很多资料把拟凸解释成“单峰”于是有人以为只要函数图像只有一个峰就是拟凸。为什么混在一维上下水平集是区间这件事直观上确实就是“只有一个谷”两者对得上所以这个说法流传很广。怎么区分单峰这个词太依赖图像直觉遇到平台、常数段、不可微的尖点就说不清了。一个恒等于 5 的函数算不算单峰它是拟凸的但没有“峰”可言。更稳妥的判断方式是回到集合把每个下水平集画出来看是不是都连成一块。这个判据在高维也成立单峰这个说法在高维容易让人误以为“沿每个方向看一遍就行”。5.3 可行性问题与优化问题答案从“多少”变成“有没有”易混点两者都叫“解问题”都返回一个解看起来只是问法不同。为什么混阈值判定那一步确实也返回了一个 x看起来和优化问题的解没什么两样。怎么区分优化问题要的是最优值和最优解可行性问题只要一个满足约束的点或者干脆只回答是或否。这个区别带来的宽松很实在可行性判定一旦找到一个点就可以立刻收工不必继续找更好的而优化必须把“还有没有更好的”这个问题回答完。二分正是把一次优化拆成了一系列可行性判定每一次都只回答一个是非题攒起来才逼近最优值。5.4 二分与梯度下降一个在阈值上查一个在变量里爬易混点两者都是迭代算法都在缩小范围容易以为可以互相替代。为什么混最终都能给出一个解表面上都是“一步步逼近”。怎么区分二分搜索的是一维的阈值空间每一步砍掉一半区间靠的是判定的单调性梯度下降搜索的是变量空间每一步沿负梯度方向挪一点靠的是目标函数的可微性和近似凸性。二分对 f 可微不可微无所谓只要判定能做梯度下降对单调性无所谓但对函数形状很挑。二者其实可以嵌套二分的每一次判定内部可能就在跑一个投影梯度或者内点法。5.5 局部最优与全局最优拟凸也有这条保证但它不是护身符易混点既然拟凸函数的局部最小就是全局最小那算法停下来的点不就是答案吗为什么混把函数性质上的保证误当成了算法行为上的保证。这两件事之间隔着一整个算法的距离。怎么区分局部即全局说的是“如果这个点真是局部最小那它就是全局最小”可算法停下时你怎么知道它是局部最小x³ 在原点梯度为零四周看看两边都有更小值它连局部最小都不是。拟凸性给的是函数层面的好消息算法层面还得靠二分加可行性判定这种不依赖梯度的方法来兜底。6. 什么时候该上二分加可行性什么时候别硬扛这套方法的适用边界其实很清楚判断起来看三条目标是不是拟凸的、判定是不是便宜又稳定、精度要求是不是有限。适合的情况目标是比值型或者单峰型的拟凸函数本身不可微、梯度法容易卡住把阈值约束展开之后能写成一组规整的凸约束判定一次不算太贵对最优值只需要有限精度比如定到小数点后三四位就够用。这类场景里二分加可行性判定几乎是现成的最优解迭代二十来次就能收工而且每次迭代的结果都可解释。不适合的情况也得说清楚。判定本身很贵的时候要谨慎一次判定要解一个大规模凸问题二十几次叠起来的成本可能远超直接上一个启发式算法。目标值域完全未知、上下界只能靠猜的时候二分会把初始区间的错误原样带进结果。判定函数带噪声、边界附近答案来回跳的时候单调性这个前提就没了二分只是在放大噪声。需要极高精度或者需要完整最优解集的时候二分只能给一个夹逼区间也不合适。场景建议目标拟凸、不可微、梯度法反复卡住用二分加可行性判定判定一次就要解大规模凸问题先估成本或换更粗的搜索上下界没有可靠来源先构造可行解定上界别拍脑袋判定结果在边界附近抖动先修判定的精度再谈二分需要最优解集而非单个值不适合二分只给一个阈值有个教训我记了很久早些年做一个小规模的参数调节实验图省事把上界直接设成了理论最大值没验证它到底可不可行跑出来的曲线光滑得很收敛也漂亮结果和人工核算差了将近一倍。排查了半天才发现二分的区间从一开始就框错了那个“最优值”只是在自己划的错误范围里收敛出来的假象。从那以后我每次用二分之前都强制走一遍先构造一个真正可行的方案把上界定死再确认下界确实不可行两步都过了才允许开跑。这套习惯多花不了十分钟但省下的返工时间不止十倍。希望帮到你。本文还有配套的精品资源点击获取