简介：围绕拟凸问题转化为凸问题可行性问题，这份文档面向优化理论、机器学习与运筹学方向的学习者和研究者，帮助梳理拟凸函数与凸函数的差异，并给出借助二分算法寻找可行阈值的求解思路。压缩包仅含1个docx文件，整体约200KB，篇幅集中，便于按主题检索和离线阅读。已有560人学习，说明该主题在相关课程与研究中具有一定关注度。内容从拟凸性的定义及全局最优解性质切入，说明凸问题解集与局部—全局最优关系，再讨论通过引入变量和约束把拟凸优化转为凸可行性判断，并逐步展开二分算法的初始化、区间更新与终止条件。读者可据此理解阈值搜索的完整流程，掌握将较难处理的拟凸问题转化为可计算形式的分析框架，也可作为课堂笔记或算法复习的补充材料。

1. 拟凸问题为什么能靠二分法一点点逼近：从水平集到凸可行性

把拟凸问题直接丢进求解器，最常见的结局不是得到答案，而是被 DCP 规则弹回来。拟凸约束f(x) <= t本身不是凸约束，但它的下水平集是凸的——这就是二分算法能落地的原因。做法很朴素：先猜一个目标值 t，问“是否存在 x 满足 f(x) <= t”，把这个问题当作凸可行性问题求解；可行就把上界压到 t，不可行就把下界抬到 t。反复切区间，逼近原问题的最优值。适合谁？手里有拟凸目标、又不想自己推导一阶算法的人；也适合已经会用凸优化求解器、但被拟凸目标卡住的开发者。要注意，二分法逼近的是最优值，不是直接优化原函数，可行性子问题的精度会一路传染到最终结果。

2. 二分算法的骨架：上下界、可行性判定与停止准则

2.1 值域上下界怎么来得可靠：采样、先验与安全放大

二分算法的第一个动作不是写循环，而是把区间[l, u]建起来。u必须对应一个真实可行的点，l必须是一个确定不可行的下界，或者至少是一个安全下界。很多人上来就写l = -1e9、u = 1e9，然后发现迭代六十次还在跑，这不是算法慢，是区间建错了。

上界u最常见的来源是采样：在原始约束 C 内随机采一批点，或者从一个已知可行点出发做小扰动，取这些点里目标函数的最小值。采样点不需要很多，二十到五十个通常够用，目的是让u不要离最优值太远，减少二分次数。注意采样点必须满足原始约束，否则u不是可行上界，后面整个区间都会歪。

下界l分两种情况。如果目标函数有已知下界，比如非负函数，l = 0就是安全的。如果函数可能为负，或者下界未知，就不要硬猜，用指数搜索找一个不可行点：从u出发，令t = u - step，如果t可行，就把u更新为t，步长翻倍；如果t不可行，就把l设为t，搜索停止。这样得到的l是确定不可行的，u是确定可行的，区间有效。

这里有一个容易翻车的点：u对应的点必须严格满足原始约束，而不是“差不多满足”。如果初始可行点本身有约束违反，后面所有可行性判定都会带着这个误差。血泪经验是，在建立u之前，先把初始点代回原始约束检查一遍，违反量超过求解器容差就重新采样。

2.2 用 CVXPY 写一个可行性子问题：最小示例与参数说明

下面用一个具体的拟凸目标把可行性子问题写出来。目标函数取f(x) = ||x||_2 / (1 + a^T x)，原始约束取a^T x >= 0.5，其中a是单位向量。这个函数的下水平集可以写成二阶锥约束：||x||_2 <= t * (1 + a^T x)。注意t是二分传入的候选值，不是优化变量。

import numpy as np import cvxpy as cp np.random.seed(1) n = 8 a = np.random.randn(n) a = a / np.linalg.norm(a) # 归一化，避免尺度问题 x = cp.Variable(n) def solve_feasibility(t, check_tol=1e-6): # 检查是否存在 x 满足： # a^T x >= 0.5 # ||x||_2 / (1 + a^T x) <= t # 等价于 ||x||_2 <= t * (1 + a^T x) if t <= 0: return False, None constraints = [ a @ x >= 0.5, cp.norm(x, 2) <= t * (1 + a @ x) ] prob = cp.Problem(cp.Minimize(0), constraints) prob.solve() if prob.status in ("optimal", "optimal_inaccurate"): xv = x.value if xv is None: return False, None # 后校验：求解器返回 optimal 不代表严格可行 lhs = np.linalg.norm(xv) rhs = t * (1 + a @ xv) if lhs <= rhs + check_tol: return True, xv return False, None

这段代码里，t是二分传进来的候选目标值，check_tol是后校验容差。a @ x >= 0.5是原始凸约束，cp.norm(x, 2) <= t * (1 + a @ x)是下水平集的等价形式。左边是范数，属于凸表达式；右边是t乘以仿射表达式，t是常数，所以右边是仿射的。这个写法满足 DCP 规则，求解器能识别为二阶锥问题。

prob.status不能只看是不是optimal。optimal_inaccurate也要接住，但必须做后校验。后校验里的lhs <= rhs + check_tol是最后一道闸门，防止求解器容差把边界点误判成可行。check_tol不要设得太大，一般取求解器容差的十倍左右；设得太大，会把不可行点放进来，导致上界被压到错误位置。

2.3 停止准则不是“区间够小”就完了：绝对容差与相对容差

二分循环最容易写错的地方是停止准则。只写u - l <= 1e-6在函数值量级为 1 的时候没问题，但函数值量级到 1e6 时，这个准则可能一开始就满足，直接返回一个很粗的结果；函数值量级到 1e-4 时，这个准则又可能永远达不到，白跑几十轮。

更稳的写法是相对容差：(u - l) <= eps_rel * max(1.0, abs(u), abs(l))。eps_rel取 1e-5 到 1e-4 是常见起点。如果目标函数值可能非常小，max(1.0, ...)里的 1.0 起的是保底作用，避免相对容差退化成绝对容差。如果目标函数值量级已知且稳定，绝对容差也可以叠加使用，两者取更严格的那个。

迭代次数可以用公式估：ceil(log2((u0 - l0) / eps))。比如初始区间宽度是 10，目标精度是 1e-5，大约需要 20 轮；初始区间宽度是 1e6，同样精度需要 37 轮左右。如果实际迭代次数远超这个估计，通常不是精度设得太高，而是可行性判定在边界上反复抖动，或者区间更新逻辑写错了。

def bisection(feasible, l, u, x_init, eps_rel=1e-5, max_iter=80): x_best = x_init history = [] for k in range(max_iter): mid = 0.5 * (l + u) ok, x_val = feasible(mid) history.append((k, l, u, mid, ok)) if ok: u = mid x_best = x_val else: l = mid if (u - l) <= eps_rel * max(1.0, abs(u), abs(l)): break return u, x_best, history

feasible返回(ok, x_val)，x_best保存最后一次可行解。max_iter是保险丝，防止可行性判定一直返回不确定导致死循环。history记录每轮区间和判定结果，出问题时可以回看是哪一轮开始不对劲。注意，这里把False直接当成不可行；如果求解器会返回“不确定”，需要把状态拆成三类，下一章会展开。

3. 把可行性子问题交给凸优化求解器：建模细节与数值尺度

3.1 下水平集的等价写法：显式约束、辅助变量与锥形式

二分算法的可行性子问题能不能交给求解器，取决于你能不能把f(x) <= t写成凸约束。拟凸函数的下水平集是凸集，但“集合是凸的”不等于“表达式直接满足 DCP”。求解器不认识拟凸性，它只认规则。

常见的等价写法有几类。线性分式(a^T x + b) / (c^T x + d) <= t，在分母为正的前提下，等价于a^T x + b <= t(c^T x + d)，这是一个线性约束。范数比||x||_2 / (c^T x + d) <= t，等价于||x||_2 <= t(c^T x + d)，这是一个二阶锥约束。凸函数除以正凹函数p(x) / q(x) <= t，等价于p(x) - t q(x) <= 0，左边是凸函数，可以直接写。最大特征值比、矩阵分式这类目标，往往能写成线性矩阵不等式。

有时候直接写等价形式会让表达式很长，可以引入辅助变量。比如把分母记成s = c^T x + d，约束s > 0，再把||x||_2 <= t s写进去。辅助变量本身不改变凸性，但能让求解器看到更清晰的结构。注意辅助变量只能用等式或凸不等式引入，不能引入非凸等式，否则 DCP 检查会失败。

如果目标函数是黑箱，没有显式凸表示，二分法就不能直接落地。这时需要先找下水平集的凸表示，或者改用序列凸近似、Dinkelbach 之类的路线。不要硬把黑箱函数塞进cp.Problem，求解器不会因为你是拟凸的就放行。

3.2 尺度归一化：函数值量级、变量量级与约束容差

求解器对尺度很敏感。变量x的分量如果从 1e-6 到 1e6 混在一起，约束矩阵的条件数会很差，可行性判定在边界上容易抖。目标函数值如果跨好几个数量级，二分区间的绝对宽度也不能统一。

变量归一化是最有效的一步。令x = D z，D是对角缩放矩阵，让z的每个分量大致落在[-1, 1]。原始约束变成A D z <= b，目标函数也跟着变。缩放矩阵可以从变量的物理范围、采样点的标准差、或者约束矩阵的列范数估计。缩放之后，求解器的容差才有可比性。

函数值归一化是第二步。如果f的量级很大，可以令g(x) = f(x) / scale，其中scale是一个正估计，比如初始可行点的函数值。二分在g上进行，得到结果后再乘回scale。这样停止准则的相对容差更容易设。注意，缩放只改变数值，不改变最优解。

约束容差不要设得太紧。求解器的feastol、abstol、reltol常见起点是 1e-8 到 1e-6。如果问题本身有测量噪声，或者变量尺度很大，设到 1e-10 反而会让求解器返回infeasible_inaccurate。一个实用做法是先用默认容差跑一遍，看可行性判定的稳定性，再决定要不要收紧。

3.3 可行性结论的三种状态：可行、不可行、求解器不确定

二分算法最怕把“不确定”当成“不可行”。求解器返回optimal时，候选解可能只是近似可行；返回infeasible时，可能是真不可行，也可能是数值困难；返回infeasible_inaccurate或solver_error时，结论根本不能直接用。

稳妥的做法是把状态分成三类：feasible、infeasible、unknown。optimal和optimal_inaccurate先归到候选可行，做后校验，通过才叫feasible；infeasible归到候选不可行，但如果是infeasible_inaccurate，归到unknown。unbounded在可行性问题里通常意味着约束写错了，因为目标函数是常数 0，不应该无界。

def classify_status(prob, x_var, t, a, check_tol=1e-6): status = prob.status if status in ("optimal", "optimal_inaccurate"): xv = x_var.value if xv is None: return "unknown", None lhs = np.linalg.norm(xv) rhs = t * (1 + a @ xv) if lhs <= rhs + check_tol: return "feasible", xv return "unknown", None if status == "infeasible": return "infeasible", None return "unknown", None

classify_status里的check_tol是后校验容差。unknown不能用来更新二分区间，否则可能把上界压到不可行点，或者把下界抬到可行点。处理unknown的常见策略是：先收紧求解器容差重跑一次；如果还是不确定，对问题做缩放；连续多次不确定就停止二分，返回当前x_best，同时报告区间宽度。不要无限重试，二分循环里需要一个unknown_count计数器。

4. 不可行性不是“无解”两个字：证书、分离超平面与二分区间维护

4.1 对偶变量能告诉你什么：近似分离与不可行证据

可行性子问题返回不可行时，二分算法只关心“不能把上界压到 mid”。但如果你想知道这个不可行结论有多可信，可以看对偶信息。凸可行性问题不可行时，强对偶条件下存在分离超平面，把可行域和原点分开。部分求解器会返回对偶变量，这些变量可以用来构造近似分离证据。

不是所有求解器都直接给不可行证书。拿不到证书时，可以用最小违反量问题替代：把f(x) <= t放宽成f(x) <= t + s，最小化s。如果最优s明显大于零，说明原可行性问题不可行，s是最小违反量；如果s只在 1e-8 量级，可能是数值不可行，不是真正不可行。这个信息对二分很有用：当s很小时，不要把 `l

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