简介面向优化理论与机器学习方向的初学者及工程实践者这份文档聚焦「拟凸问题转化为凸问题可行性问题」这一主题系统梳理拟凸函数与凸函数的定义差异、凸问题解集与「局部最优即全局最优」的特性并讲解如何通过引入新变量与约束把拟凸优化目标改写为带阈值的凸可行性问题。内容重点落在二分算法的完整流程上初始化左右边界、取中点迭代、依据函数值与中点的大小关系收缩区间直至收敛得到满足条件的阈值并配有步骤化说明便于对照实现。压缩包内仅1个docx文件约200KB篇幅精炼结构按概念、转化、算法、步骤层层推进适合作为课程复习提纲或算法实现前的思路梳理材料。目前已有559人学习下载读者可从中获得问题转化的建模思路与二分求解的伪代码级参考为后续在数据分析、运筹优化场景中处理非凸目标提供可复用的方法框架。1. 拟凸的陷阱为什么“局部最优即全局最优”救不了你把拟凸问题直接丢进凸优化求解器多数时候连编译都过不去——不是数值不收敛而是 DCP 规则当场判死这不是凸问题。可拟凸函数的每个下水平集明明是凸集全局最优也真实存在。这个矛盾正是理解“拟凸问题转凸可行性 二分算法”这条路线最好的入口我们优化的不是一个非凸函数而是在对一个凸集族做二分查找。搞懂它你就有了一个在目标不满足凸性、却必须拿到全局最优的场景里能反复复用的框架尤其是当目标长成比值、分位数、“最大值中的最小值”这类形状的时候。2. 层集视角拟凸性到底把什么问题变简单了2.1 定义本身比你想的弱得多设约束集 C ⊆ R^n 是凸集f: C → R。如果对任意 x, y ∈ C 和任意 λ ∈ [0,1]都有 f(λx (1-λ)y) ≤ max{f(x), f(y)}那么 f 在 C 上拟凸。把这个式子念一遍线段上任意一点的高度不会超过两端中较高的那一个。等价的说法是函数沿任意直线段不会出现“中间鼓包”——它可以是单调递增的比如 x³可以是单峰的先降后升比如 ||x||²也可以有一段平顶但不允许出现“降了又升、升了又降”的双谷形状。凸性要求的是更严格的东西f(λx (1-λ)y) ≤ λf(x) (1-λ)f(y)右侧是函数值本身的线性插值。拟凸只拿 max 做上界等于把“函数曲线在线段下方”放宽成“函数曲线不高于端点之间较高的那个点”。这个放宽带来的自由度很大x³ 在整条实轴上拟凸但它显然不是凸函数二次除以线性那类比值函数也常常拟凸而 Hessian 想怎么不定就怎么不定。可微的时候有一个等价刻画值得记住若 f 拟凸且可微那么对任意 x, y ∈ Cf(y) ≤ f(x) 蕴含 ∇f(x)ᵀ(y - x) ≤ 0。这句话说的是梯度方向总指向“不低于当前水平”的那一侧因此 −∇f(x) 一定是一个能降低函数值的方向除非 x 已经是全局最小点。注意“除非”后面的条件这个一阶条件并没有说 ∇f(x) 0 就意味着最优点。这一点会在 2.3 节变成具体的翻车现场。再补一句容易忽略的前提dom f 必须凸。反例函数 1/x 在 x 0 上拟凸在整条实轴上连定义域都不连通谈线段就无从谈起。很多人写代码时把拟凸判断用在非凸定义域上后面所有结论都会失效。2.2 下水平集把函数的形状问题翻译成集合的形状问题定义下水平集 S_t {x ∈ C : f(x) ≤ t}。有一个干净得让人舒服的等价关系f 拟凸当且仅当所有非空的 S_t 都是凸集。证明只有两行。若 f 拟凸取 x, y ∈ S_t则 f(λx (1-λ)y) ≤ max{f(x), f(y)} ≤ t线段整段落在 S_t 里。反过来给定任意 x, y取 t max{f(x), f(y)}此时 x, y 都在 S_t 内S_t 的凸性直接把线段塞进集合内部于是拟凸定义成立。这个等价关系是整条算法路线的地基。它把“函数值长什么样”这种分析起来很吃力的问题换成了“集合是什么形状”这种几何上容易处理的问题。函数可以非凸、可以不可微、可以写成黑匣子但只要它的每一个下水平集是凸的我们就还有办法。代价也很清楚函数值本身失去了凸结构。凸函数的梯度是单调的(∇f(x) − ∇f(y))ᵀ(x − y) ≥ 0拟凸函数没有这个性质Hessian 不定沿某条线下降得很快、沿另一条线可能几乎不动。这些特性在数值上会变成步长难调、收敛判据不可靠后面会具体讲。顺带提醒一个几何直觉拟凸函数的下水平集可以又扁又长条件数极差也可以有尖锐的角点不可微。这两种形状恰好是数值算法的两个高发事故区因为二分法外层不在乎形状内层的可行性判定却必须在这个形状上找点。2.3 梯度下降在这里会以什么方式失败先说最朴素的反例f(x) x³ 在整条实轴上拟凸。在 x 0 处梯度为零。如果你用“‖∇f‖ ε 就收敛”这套在凸优化里非常好用的停止准则算法会兴高采烈地在 0 处停下并宣布找到了最优解——而真正的最小值在负无穷方向。凸函数里 ∇f 0 是最优性的充分条件拟凸函数里它什么都不是。这是踩坑率最高的一条因为它不报错只是安静地给出错误答案。再说实际一点的场景。f(x) ‖x − a‖² / (bᵀx c) 这类比值形状分子凸、分母仿射且为正函数本身拟凸。梯度下降不是完全跑不动但一旦迭代点靠近分母变小的区域梯度模长会陡然放大步长稍大就飞出去步长稍小就爬不动如果再叠加一个盒约束投影之后的点很可能落在约束边界上梯度在那里几乎不提供有效信息。血泪经验是这类问题的调参时间往往比换一个算法框架还长。还有一种更彻底的情况函数根本给不出梯度。分位数、最大值函数、仿真程序的输出、查表得到的响应曲面这些只能“给一个 x问一个 f(x)”。此时所有基于导数的办法全部失效剩下的只有查值。而“只能查值”恰恰是二分法最舒服的战场。所以结论不是“拟凸不能优化”而是拟凸缺两样东西一个可靠的下降方向一个可靠的停止准则。既然缺就换个问法绕开它们。2.4 换成可行性判定问题根本没变只是问法变了原问题是 min f(x) s.t. x ∈ C最优值记为 p*。现在定义一个新的谓词P(t) : 是否存在 x ∈ C使得 f(x) ≤ t。这个谓词有一个极其关键的性质P(t) 为真当且仅当 t ≥ p*。于是 p* inf{t : P(t) 为真}。换句话说求最小值这件事被完整地等价成了在阈值 t 上的一次搜索——二分法的位置就是这么来的。更值得注意的是这个谓词背后的集合形状。P(t) 要判定的可行域是 C ∩ S_t两个凸集的交仍然是凸集。这就是“拟凸问题转化为凸可行性问题”这句话的全部含义我们并没有把一个非凸函数变成凸函数那是不可能的我们只是把一个函数优化问题换成了一个集合非空判定问题而那个集合是凸的。这里有一个区分必须讲清楚否则后面写代码会一路撞墙集合凸不等于约束能写进 DCP。f(x) ≤ t 这个约束在 f 拟凸时定义的可行域是凸的但约束函数本身不是凸函数标准凸优化求解器只认“凸函数 ≤ 0”这种形式看到拟凸表达式会直接拒绝。所以“转化”能不能落地取决于你能不能给这个凸集合找到一个可计算的表示——第 4 章会给出两条具体的路。3. 二分为何成立单调谓词、嵌套层集与不变式3.1 只有一个性质被用到单调二分能在阈值上跑靠的不是连续性不是可微性甚至不是凸性本身而是一个更弱的结构单调性。看层集的定义就知道t₁ ≤ t₂ 蕴含 S_{t₁} ⊆ S_{t₂}。层集是嵌套的随着 t 增大一层层往外长。嵌套直接推出谓词的单调若 P(t) 为真即存在某点 x 满足 f(x) ≤ t那么同一个点也满足 f(x) ≤ t对任意 t ≥ t所以 P(t) 也为真。这就是全部。二分只需要一个“一旦为真就一直为真”的谓词加一个已知的区间端点。它不需要知道 f 长什么样不需要导数不需要 Lipschitz 常数也不需要求解器返回对偶变量。对于黑匣子函数这种低要求是决定性的优势。再补一个几何版本的说法二分实际上是在层集序列 S_{t} 上做“由外向内”的搜索。每次把阈值往下压就是在问“更小的那个层集还碰得到约束集 C 吗”。碰到就继续压碰不到就退回来。整个算法的语义非常干净出问题时也容易定位——要么是谓词判错了要么是不变式被破坏了。3.2 不变式与迭代次数标准写法维护一个不变式lb 是已知不可行或者至少是问题的下界的阈值ub 是一个已知可行的阈值且附带一个真实的可行点 x_ub。每轮取 mid (lb ub)/2调用一次可行性 oracle可行就把 ub 压到 mid 并保存新的可行点不可行就把 lb 抬到 mid。区间长度每轮减半所以要把精度做到 ε需要的轮数是 ⌈log₂((ub₀ − lb₀)/ε)⌉。注意几个容易想当然的地方。第一返回的是什么。算法返回的 ub 是最优值的一个上界而且这个上界是“可证”的因为手上有一个真真切切满足 f(x) ≤ ub 的点。lb 是下界。这与“求解器返回一个近似最优解”的语义不同二分的每一次输出都自带可行性凭证如果你把 oracle 返回的点存下来了这在工程上非常好用出错时能直接代回验证。第二绝对精度还是相对精度。如果目标值本身量级是 1e-8用绝对精度 1e-6 一开始就超了循环一轮都不跑。反过来量级 1e8 时用 1e-6 的绝对精度要跑四十多轮主要时间都花在无意义的精度上。实践里通常写成 ub − lb ≤ rel_tol · max(1, |ub|) 这种混合形式。第三初始上界必须可行。这不是“最好可行”是“必须可行”。如果 ub 本身不可行二分的不变式从一开始就是破的算法照样会跑完还会返回一个看起来很正常的数值只是它是错的。第 5 章会讲怎么找这个初始上界。3.3 容差耦合精度的天花板不在二分在 oracle这是整个方法里最隐蔽、也最容易吃亏的一处。可行性 oracle 一定是带容差的。假设它判定可行的规则是 f(x) ≤ t ε_f其中 ε_f 是数值容差求解器的可行性容差、浮点误差、启发式搜索的松弛量等等。那么当 t 落在 [p* − ε_f, p*] 区间内时oracle 会诚实地回答“可行”尽管真实最优值 p* 严格大于 t。二分于是把 ub 一路压到 p* − ε_f 附近最终返回一个偏小的、实际上不可行的“最优值”。反过来也成立。如果二分的 tol 设置得比 oracle 容差还小在最优值附近mid 的微小变化根本不会改变 oracle 的回答区间更新会变得极其缓慢你会在日志里看到 ub 和 lb 一格一格地挪跑满 max_iter 才停。看起来是“收敛慢”实际上是两套容差在互相打架。正确的做法是让两级容差对齐二分的目标精度应该比 oracle 容差大一个数量级以上或者反过来把 oracle 容差压到二分目标精度的十分之一以下。我一般会在外层跑完后把返回的 x 代回原函数检查 f(x) ≤ ub ε_f 是否成立不成立就把 ub 往上抬一档重跑。这个检查只要一行代码能挡住绝大多数安静的错误。注意二分返回的 ub 是“最优值的上界”但这个结论的前提是 oracle 的可行性答复可信。oracle 一旦单边出错二分的所有保证同时失效。3.4 为什么二分特别适合黑匣子场景把二分的成本结构算一遍就明白了。总代价等于轮数乘以单次 oracle 的代价轮数是 log 级别的通常二三十轮。这意味着你可以承受一个相当昂贵的 oracle哪怕单次可行性判定要解一个中等规模的凸优化问题总时间也在可接受范围内。它还有两个附带的优点。其一二分对 f 的平滑性完全无要求断层、尖点、平台都不影响外层逻辑只影响内层 oracle 好不好写。其二它天然是“可中断”的任何时候停下来你手上都有一个当前最好的可行点和一个下界能给出最优值的误差区间。这对需要长时间跑的任务非常友好。代价也说清楚二分丢掉了所有对偶信息。凸优化求解器顺手给你的拉格朗日乘子、灵敏度分析在二分框架里统统没有想要的话得在最后一次 oracle 调用里自己去捞。另外二分是纯串行的没有天然的并行度每一次 mid 都必须等上一次的结果。如果 oracle 本身很便宜而精度要求极高二分的轮数优势就不明显了这时候可以考虑割平面类的方法——它们在层集上累积切平面来加速定位本质上是二分的加强版思路一致。4. 可行性 oracle 怎么写比值结构与投影次梯度的两条路4.1 主循环二十行的骨架外层逻辑短得几乎不需要解释但每个参数都有讲究。import numpy as np def bisect_level(feasible, lb, ub, rel_tol1e-5, max_iter80): feasible(t) - (ok, x) 判断层集 {x : f(x) t} 与约束集 C 是否有交点 lb: 已知不可行或问题下界的阈值 ub: 已知可行的阈值必须预先验证 ok, x_ub feasible(ub) if not ok: raise ValueError(上界必须预先可行否则不变式从一开始就不成立) best_x, best_t x_ub, ub iters 0 for iters in range(1, max_iter 1): # 混合精度目标值量级很小时不至于一轮就跑完 if ub - lb rel_tol * max(1.0, abs(ub)): break mid 0.5 * (lb ub) ok, x_mid feasible(mid) if ok: ub, best_x mid, x_mid # 收紧上界同时留下可行点 else: lb mid # 只抬起下界可行点不动 return {value: ub, x: best_x, iters: iters, gap: ub - lb}几个参数的实际含义feasible 返回的 x 不只是布尔量它是你后面所有验证工作的凭据rel_tol 建议设在 1e-4 到 1e-6 之间再小就要看 oracle 敢不敢跟max_iter 是保险丝正常情况下 ⌈log₂((ub−lb)/tol)⌉ 就够了加二十轮余量足以发现异常返回的 gap 比 value 本身更值得看它才是你真正拿到的最优值误差。有一处写法上的细节值得单独说不可行的时候不要动 best_x。有些实现图省事每次调用都把返回向量存下来结果最后拿到的是某个不可行点代回去 f 值超标排查半天才发现是存取逻辑的问题。4.2 结构化路线把 f(x) ≤ t 写成凸约束第一条路要求函数有可利用的结构。最常见的一类是比值形式f(x) g(x)/h(x)其中 g 凸、h 凹且恒正。这类函数的拟凸性可以直接验证而它的下水平集有一个漂亮的代数表示f(x) ≤ t ⟺ g(x) − t·h(x) ≤ 0 当 h(x) 0 且 t ≥ 0右边这个表达式对 x 是凸的因为 g 凸而 −t·h 在 t ≥ 0 且 h 凹时凸。于是原本写不进求解器的拟凸约束被改写成了标准的凸约束。import cvxpy as cp import numpy as np def oracle_ratio(a, b, c, lo, hi, feas_tol1e-8): f(x) ||x - a||^2 / (b^T x c)分子凸、分母仿射正 n a.size def feasible(t): x cp.Variable(n) # 直接写 f(x) t 会违反 DCP 规则 # 两边同乘正分母后||x-a||^2 - t*(b^T x c) 0左边对 x 凸 lhs cp.sum_squares(x - a) - t * (b x c) prob cp.Problem(cp.Minimize(lhs), [x lo, x hi]) prob.solve() if prob.status in (optimal, optimal_inaccurate) and lhs.value feas_tol: return True, x.value return False, None return feasible这里的逻辑是把可行性判定改成“最小化左端表达式看最小值是否 ≤ 0”。因为可行域是凸的盒约束而目标凸这个子问题是标准凸优化求解器能处理。lhs.value feas_tol 这一句就是 3.3 节说的那个容差feas_tol 必须明显小于二分精度。另一类常见结构是“凸函数族的最大值”f(x) max{f₁(x), ..., f_m(x)}各 fᵢ 凸。这种 f 一定是拟凸的甚至更好而 f(x) ≤ t 直接拆成 m 条凸约束 fᵢ(x) ≤ t 就行比比值形式还省事。很多“最坏情况”型的目标都属于这一类值得优先识别。注意比值形式里 t 0 时−t·h 在 h 凹的情形下会变成凹函数凸性直接崩掉。所以二分下界必须从 0 附近起步或者先证明最优值非负。4.3 黑匣子路线用投影次梯度硬找一个可行点没有结构可用的时候只剩下“能查值”这一个能力。此时可行性 oracle 变成一个内层迭代从某个点出发如果 f(x) t就沿 −∇f(x) 走一步拟凸的一阶条件保证了这是个下降方向走完投影回约束集 C如果 f(x) ≤ t立刻返回成功。def oracle_projected(f, grad, project, x0, inner_iters120, step01.0, feas_tol1e-9): 拟凸 f 的启发式可行性 oracle只保证下降方向不保证找到 def feasible(t): x np.array(x0, dtypefloat) for k in range(inner_iters): if f(x) t feas_tol: return True, x.copy() g grad(x) # 拟凸只保证 -g 是下降方向步长没有理论保证只能自己衰减 step step0 / np.sqrt(k 1.0) x project(x - step * g) return f(x) t feas_tol, x.copy() return feasible必须把丑话说在前面这是一个启发式 oracle收敛性没有保证。它返回 False 只代表“这一轮没找到”不代表“真的不可行”。这个单边错误会系统性地把二分结果往高估的方向推——内层找不到点外层就以为阈值太低于是 lb 抬高最终收敛到一个比真实 p* 更大的值。反过来如果它返回 True那一定是真的可行点就在手上代回去验一下即可这个方向的错误是不存在的。实践里提高内层成功率有几个手段起点用上一次 oracle 返回的可行点做热启动而不是固定 x0步长从 1/(k1) 改成带回溯线搜索的版本走一步之后必须让 f 严格下降否则减半步长内层迭代次数随外层进行逐步提高前几轮宽松、后几轮严格。这些在代码上都是几行的事效果比调 step0 明显。4.4 参数与收敛判据对照参数位置典型取值调错的后果rel_tol二分外层1e-4 ~ 1e-6过小轮数白白增加过大误差区间失去意义max_iter二分外层80 ~ 200过小正常收敛被截断返回的 gap 偏大feas_tol可行性 oracle二分精度的 1/10过小浮点噪声导致永不判可行过大结果系统性偏小inner_iters投影次梯度100 ~ 500过小假不可行频发过大单次 oracle 变慢step0投影次梯度与定义域尺度同阶与尺度不匹配震荡或停滞收敛判据建议同时看三个外层区间宽度是否达标、返回点代回后的函数值是否真的不超过 ub、以及外层轮数是否明显超过 log₂((ub₀−lb₀)/tol)。第三个是最好用的异常信号——正常情况不该超超了基本就是容差打架或者 oracle 在高估。5. 排查二分加拟凸组合里最容易翻车的五个现场5.1 上界不可行结果照样跑完现象算法正常收敛返回一个漂亮的数值但把 x 代回原函数f(x) 比返回值大得多或者返回的点根本不满足约束。原因初始 ub 是拍脑袋给的没有真实验证过可行性二分的“ub 一定可行”这条不变式从一开始就是假的。更糟的是很多时候 oracle 在 ub 上也返回 False代码里只有一句 assert 或者干脆没写于是 ub 被当作可行值一路保留到最后。解决把“找初始可行上界”变成一个独立步骤。可以从一个宽松阈值起步逐步放大直到 oracle 返回 True 并带回一个真实点也可以用启发式搜索随机采样、粗网格、历史解先找一个可行点再把它对应的 f 值作为 ub。这个前置步骤多花的时间远小于一次错误结果带来的返工。5.2 两级容差倒挂结果不可行现象二分精度设到 1e-8返回的 ub 很小但代回去 f(x) − ub 稳定在 1e-6 量级怎么调都下不去。原因oracle 的可行性容差是 1e-6求解器默认值或者自己写的松弛量比二分目标精度还大。在最优值附近oracle 会把一堆实际上略微超标的点判为可行ub 被一路压到 p* 之下。二分精度再高也只是在错误的基础上做精细化。解决把 oracle 容差压到二分精度的十分之一以下或者反过来把二分精度放宽到 oracle 容差的十倍以上。两者必须匹配不能各调各的。跑完之后一定加一句“代回验证”这是成本最低的兜底。5.3 数值尺度失控精度设置失去意义现象某些问题上二十轮就收敛换个数据规模后跑满 max_iter 还在磨或者一开始就退出gap 是初始区间的全部。原因绝对精度用在了量级差异极大的问题上。目标值 1e7 的时候1e-6 的绝对精度意味着要跑四十多轮目标值 1e-9 的时候这个精度比整个区间还宽第一轮判定就直接通过。解决统一用相对精度ub − lb ≤ rel_tol · max(1, |ub|)并且在进入二分之前对问题做一次尺度归一化把约束集 C 平移缩放到单位盒附近把 f 除以一个量级估计值。这两步做完容差参数基本可以固定下来复用。5.4 把拟凸当凸直接扔给求解器现象模型构建阶段直接报 DCP 错误或者没有报错但结果明显不是全局最优换个初值结果就变。原因拟凸函数的约束 f(x) ≤ t 定义出的集合是凸的但约束函数本身不是凸函数DCP 规则只看函数表达式不看集合形状。有人绕开报错的方式是改用局部求解器或者加松弛结果就是回到了局部最优。解决先判断能不能做 4.2 节那种结构化改写比值形式、最大值形式、凸函数复合形式。能改写问题就真的变成凸的了放心交给求解器不能改写就走黑匣子路线老老实实用 oracle 二分不要试图用局部方法蒙混。5.5 内层启发式的单边错误被当成真结论现象二分单调地抬高下界最终收敛到一个明显偏大的值把 ub 手动调低再跑oracle 有时又能返回可行点。原因4.3 节的投影次梯度只看下降方向步长没有理论保证。它在某些几何形状细长层集、尖锐角点、平台区上会反复横跳inner_iters 用完还没进到层集内部于是返回 False外层就误判为“阈值太低”。解决三个改法叠加使用。第一热启动用上一次 oracle 的可行点作为下次的起点第二加回溯线搜索每步必须让 f 严格下降否则步长减半第三把内层的失败次数记下来如果某个阈值上连续失败多次就把这一步的结论标记为“可疑”在外层收敛后单独复核。最后一招很土但能救命。6. 设计取舍二分、次梯度与直接求解什么时候选哪条路把三条路摆在台面上比较。第一条是直接结构化改写把拟凸约束变成标准凸约束比值形式、最大值形式交给通用求解器。它的优点是拿到的是完整解附带对偶信息精度可控缺点是适用范围窄函数形状稍微复杂一点就改写不出来。第二条是次梯度法直接在原问题上迭代。它每一轮都要一个下降方向在可微的时候很自然在不可微的时候需要广义梯度而且步长策略对收敛速度影响极大。它适合函数光滑、维度不太高、只需要一个还不错的解的场景。缺点是没有可靠的停止准则——3.1 节说过拟凸函数里梯度为零不代表最优你得额外想办法给误差定界。第三条是二分加可行性 oracle。它把“优化”彻底降维成“判定”代价是每一轮都必须解一个完整的可行性问题。当 oracle 便宜比如有闭式投影、或者子问题是小规模凸优化时这条路的性价比极高迭代轮数是对数级的实现只有几十行出错时容易定位而且天然支持黑匣子函数。选哪条我看三个信号。函数能不能写出凸的等价形式能就走第一条别犹豫。函数能不能稳定地给出梯度且维度不高能次梯度法可以试。剩下所有情况——只能查值、形状奇怪、约束复杂、需要严格的最优值误差区间——走二分。二分也有它自己的取舍需要提前想清楚。它的精度上限被 oracle 容差锁死所以如果业务要求 1e-10 级别的精度而 oracle 只能做到 1e-8这条路直接堵死。它的总耗时等于轮数乘单次 oracle 的代价如果单次 oracle 本身就要解一个大规划问题二三十轮叠起来可能比一次直接求解还慢这时候应该考虑割平面类的加速变体。它还不给对偶变量需要灵敏度分析的话得自己在最后一次 oracle 里额外捞。验证方法我一般固定做三件事成本都很低。第一把返回的 x 代回原函数和全部约束逐条检查这一步能抓住 90% 的容差问题。第二在小规模实例上用网格或随机采样暴力搜索对比最优值——不需要很精确能确认二分结果没有偏出一个量级就够。第三把二分的 gap 和暴力搜索的误差区间对一下如果二分的 gap 覆盖不住暴力解说明 oracle 在某处给了错误的可行性判断回头查 5.5 节。一个具体的可复现实验形状是这样取 f(x) ‖x − a‖² / (bᵀx c)盒约束 [−1, 1]^nn 取 2 或 3。用 4.2 节的结构化 oracle 配 4.1 节的主循环跑一遍记录 value 和 gap再用 200×200 的网格暴力枚举取满足约束的最小 f 值做对照。正常情况下两者差值应该落在 gap 之内。这个实验十分钟能跑完但它把容差对齐、尺度归一、代回验证三个环节全串了一遍出问题的地方一目了然。从那以后我每次写这类求解器都会在二分外面先跑一个“自检模式”构造一个已知最优值的小实例走完整流程看返回值和 gap 是否把真值夹住不通过就不许进入正式数据。这个习惯是从一次线上事故里换来的——那次返回的“最优值”比真实值低了两个数量级原因只是可行性容差和二分精度差了一个数量级。希望帮到你。本文还有配套的精品资源点击获取