拟凸优化转凸可行性：二分算法、下水平集与可行性Oracle实践

简介：面向优化理论与机器学习方向的初学者及工程实践者，这份文档聚焦「拟凸问题转化为凸问题可行性问题」这一主题，系统梳理拟凸函数与凸函数的定义差异、凸问题解集与「局部最优即全局最优」的特性，并讲解如何通过引入新变量与约束，把拟凸优化目标改写为带阈值的凸可行性问题。内容重点落在二分算法的完整流程上：初始化左右边界、取中点迭代、依据函数值与中点的大小关系收缩区间，直至收敛得到满足条件的阈值，并配有步骤化说明便于对照实现。压缩包内仅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 ∈ C，f(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_tol=1e-5, max_iter=80): """ 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_tol=1e-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_iters=120, step0=1.0, feas_tol=1e-9): """拟凸 f 的启发式可行性 oracle：只保证下降方向，不保证找到""" def feasible(t): x = np.array(x0, dtype=float) 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/(k+1) 改成带回溯线搜索的版本（走一步之后必须让 f 严格下降，否则减半步长）；内层迭代次数随外层进行逐步提高，前几轮宽松、后几轮严格。这些在代码上都是几行的事，效果比调 step0 明显。

4.4 参数与收敛判据对照

收敛判据建议同时看三个：外层区间宽度是否达标、返回点代回后的函数值是否真的不超过 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]^n，n 取 2 或 3。用 4.2 节的结构化 oracle 配 4.1 节的主循环跑一遍，记录 value 和 gap；再用 200×200 的网格暴力枚举，取满足约束的最小 f 值做对照。正常情况下两者差值应该落在 gap 之内。这个实验十分钟能跑完，但它把容差对齐、尺度归一、代回验证三个环节全串了一遍，出问题的地方一目了然。

从那以后我每次写这类求解器，都会在二分外面先跑一个“自检模式”：构造一个已知最优值的小实例，走完整流程，看返回值和 gap 是否把真值夹住，不通过就不许进入正式数据。这个习惯是从一次线上事故里换来的——那次返回的“最优值”比真实值低了两个数量级，原因只是可行性容差和二分精度差了一个数量级。希望帮到你。

本文还有配套的精品资源，点击获取