企业官网建设流程全解析

简介：一份关于拟凸问题转化为凸可行性问题二分算法的DOCX格式文档，面向机器学习、数据分析、运筹学等领域的优化理论学习者与研究者，用于梳理拟凸与凸问题的差异及转化求解思路。文档以凸优化理论为基础，依次讲解拟凸函数与凸函数的判定条件、凸问题解集与全局最优性、通过引入变量与约束将拟凸问题转化为凸可行性问题的方法，并重点阐述二分算法的阈值搜索原理与具体迭代步骤；同时给出清晰的算法流程和收敛逻辑，便于读者对照推导。全文共1个DOCX文件，压缩包约200KB，便于快速下载与阅读。资源目前已有558人学习下载，适合需要系统理解拟凸优化求解技巧的初学者，也可作为相关课程与项目研究中的快速参考资料。

1. 拟凸问题为什么值得绕一圈：不是凸，但可以「假装」凸

把min max_i (a_i^T x + b_i) / (c_i^T x + d_i)这个目标直接丢给 CVXPY，大概率会收到 "does not follow DCP rules" 的报错，然后你开始怀疑是不是自己用错了工具。问题的关键在于：目标函数不是凸的，但它满足拟凸性——所有下水平集{x | f(x) ≤ t}都是凸集。这个性质允许我们绕过非凸优化的所有麻烦：把「求最小目标」替换成「判断某个 t 下有没有可行解」的凸可行性问题，再用二分法在 t 轴上逼近最优值。这样做的收益是全局收敛保证、清晰的误差上界，以及一段能直接跑通的最小实现。本文面向想真正动手求解拟凸问题的人，比如处理定位、分数规划、比率最小化的读者，会给出完整代码、参数设计逻辑和五条踩坑记录，最后说明怎么验证你求出来的确实是最优值。

2. 从拟凸到凸可行性：下水平集、二分框架与收敛保证

2.1 拟凸函数：怎么定义、怎么一眼认出来

拟凸函数（quasiconvex function）的定义比凸函数宽松：定义域是凸集，并且对任意实数 t，下水平集S_t = {x | f(x) ≤ t}都是凸集。凸函数天然满足这个条件，所以凸函数一定是拟凸函数，反过来则不一定成立。

判断一个函数是不是拟凸，不需要背性质，直接看下水平集即可。比如线性分式f(x) = (a^T x + b) / (c^T x + d)，在区域{x | c^T x + d > 0}内，f(x) ≤ t等价于a^T x + b ≤ t(c^T x + d)。因为分母为正，不等式两边乘分母不改变方向，得到一个线性不等式，下水平集是半空间，显然是凸集。所以线性分式在这个区域内是拟凸函数，严格说它还是拟线性函数，因为上水平集{x | f(x) ≥ t}同样可以写成线性不等式。

更常见的场景是一组线性分式的逐点最大：f(x) = max_i (a_i^T x + b_i) / (c_i^T x + d_i)。f(x) ≤ t等价于每一个分式都小于等于 t，也就是一组线性不等式取交集，凸集性质依然成立。逐点最大保拟凸性，这是很多定位与资源分配问题可以走二分路线的原因。识别拟凸问题的实用方法也很简单：把目标函数写成f(x) ≤ t之后，如果所有条件都能变形成凸约束，那这个目标大概率是拟凸的。

需要提醒的是，拟凸问题的 KKT 条件只是全局最优的必要条件，不充分。也就是说，按 KKT 解出来的驻点不见得是全局最优，你不能像凸优化那样放心地把问题交给求解器。二分法的价值正在于此：它把「找最优」拆成一串凸可行性判断，每一步的结论都有严格的数学依据，最终给出的不是某个可疑的驻点，而是一个包含最优值的闭区间。

2.2 可行性问题的构造：把目标函数变成一条约束

拟凸优化的标准形式是：

minimize f0(x) subject to fi(x) ≤ 0, i = 1, ..., m Ax = b

其中f0是拟凸函数，约束fi是凸函数。对任意给定的 t，定义所谓的 t-可行性问题：

find x subject to f0(x) ≤ t fi(x) ≤ 0, i = 1, ..., m Ax = b

由于f0的下水平集是凸集，约束f0(x) ≤ t是凸约束，整个可行性问题对任意 t 都是凸可行性问题。这是整个算法的基石。

构造可行性问题时的关键习惯是：把目标函数从 objective 移到约束里，并且把 objective 写成 0。很多初学者会写成「最小化 f0(x)，同时 f0(x) ≤ t」，这等于把原问题又解了一遍，二分完全没有意义。正确做法是让求解器只回答一个问题：在加了f0(x) ≤ t之后的约束系统里，能不能找到一个点？能找到，说明对某个可行解来说f0不超过 t，因此最优值p*不大于 t；找不到，说明所有可行解都满足f0(x) > t，因此p*大于 t。

有一个细节值得提前说：可行性问题虽然没有目标函数，但求解器内部的 Phase-I 算法仍然会把原约束和对偶约束一起求解，数值表现通常比带目标函数的优化问题稳定，因为不存在目标函数梯度和约束梯度相互拉扯的情况。这也是二分法在实际项目中比直接硬解原问题更受欢迎的原因之一。

2.3 二分主循环：为什么可行缩上界、不可行升下界

二分搜索的前提是：手头有一个可行上界 U（p* ≤ U）和一个不可行下界 L（p* > L）。每次循环取中点t = (L + U) / 2，求解可行性问题。如果可行，说明最优值不超过 t，把上界收缩到 t；如果不可行，说明最优值大于 t，把下界抬升到 t。区间长度每轮减半，经过 N 轮后误差上界是(U - L) / 2^N。

这个循环的代码骨架非常短：

def bisection(L, U, N, check_feasible): for _ in range(N): t = 0.5 * (L + U) if check_feasible(t): U = t else: L = t return 0.5 * (L + U), L, U

check_feasible(t)返回布尔值，表示给定 t 下可行性问题是否有解。返回值一般用中点0.5 * (L + U)，但更可靠的工程习惯是同时把L和U一起返回，因为L不可行、U可行这件事本身就是对算法正确性的证明。

注意这里没有把「t 的变化量小于阈值」作为终止条件。在最优值附近比较平坦的时候，连续几轮的t变化很小，但实际上区间还可能很大，过早停止会得到一个虚高的上界。固定迭代次数 N，或者按区间长度U - L判断终止，比按 t 的变化量可靠得多。

理论上二分法对任何拟凸目标都收敛，前提是初始区间必须满足「L 不可行、U 可行」。这个前提在实际代码里经常被忽略，我在第 4 章会展开讲怎么验证初始区间，以及忽略它之后会翻什么样的车。

3. 用线性分式规划跑通二分算法：CVXPY 全流程与参数解读

3.1 测试问题的建模：一组能复现的随机数据

我用一个经典的最大分式比值问题作为贯穿全文的例子：

minimize max_i (a_i^T x + b_i) / (c_i^T x + d_i) subject to c_i^T x + d_i ≥ δ, i = 1, ..., m ||x||_∞ ≤ 5

约束c_i^T x + d_i ≥ δ显式要求分母为正，这是拟凸下水平集成立的数学前提，也是数值稳定的工程保障。生成数据时我特意让x = 0成为一个可行点，这样初始上界 U 可以直接从原点出发计算。

import numpy as np np.random.seed(42) m, n = 12, 4 # 保证 x = 0 处分母为正且远离 0 C = np.random.randn(m, n) d = np.random.rand(m) + 1.0 # d_i 落在 [1, 2] # x = 0 是可行点，因此上界 U 可用 f(0) 得到 A = np.random.randn(m, n) b = np.random.randn(m) def f0(x): num = A @ x + b den = C @ x + d return np.max(num / den)

d取np.random.rand(m) + 1.0而不是标准正态，是为了让每个d_i都是正数，这样x = 0时分母天然大于 1，省去了解可行域是否为空的经验判断。如果你在自己的问题里复现，请务必先确认至少存在一个可行点，否则整个二分框架无从谈起。||x||_∞ ≤ 5的约束保证问题有下界，避免出现p* = -∞导致二分算法失效的情况。

3.2 可行性检查函数：最小可运行实现

下面是整个二分算法的核心函数。每次给定 t，构建凸可行性问题并求解：

import cvxpy as cp def check_feasible(t, A=A, b=b, C=C, d=d, delta=1e-4): m, n = A.shape x = cp.Variable(n) cons = [ x >= -5.0, x <= 5.0, C @ x + d >= delta, # 分母正，数值安全 ] for i in range(m): cons.append(A[i] @ x + b[i] <= t * (C[i] @ x + d[i])) prob = cp.Problem(cp.Minimize(0), cons) prob.solve(solver=cp.OSQP, eps_abs=1e-6, eps_rel=1e-6, max_iter=20000) return prob.status == cp.OPTIMAL

逻辑说明：cp.Minimize(0)表示纯可行性问题，不做任何优化，只找满足约束的点。目标函数f0(x) ≤ t被展开成 m 条线性不等式，与分母正的约束一起交给求解器。最后的状态判断必须写成prob.status == cp.OPTIMAL，不要用prob.status != cp.INFEASIBLE，因为optimal_inaccurate和infeasible_inaccurate这两种状态既不是严格可行也不是严格不可行，用不等号判断会把模糊状态误当成可行。

参数说明：eps_abs和eps_rel是 OSQP 的绝对与相对残差容差，控制约束违反到什么程度算「可行」。max_iter=20000是给一阶方法一个足够长的迭代上限，因为 OSQP 判定不可行问题有时要跑很多轮。如果你的问题规模达到几千条约束，把max_iter再调大一倍并不丢人。

3.3 外层二分主循环：三段代码拼起来

有了可行性检查函数，外层二分只需要一个循环。我习惯把每次迭代的中间结果打印出来，方便事后复盘：

def bisection_search(L, U, N=30): for k in range(N): t = 0.5 * (L + U) if check_feasible(t): U = t flag = "feasible" else: L = t flag = "infeasible" print(f"iter {k+1:2d}: t = {t:8.4f} [{L:8.4f}, {U:8.4f}] {flag}") return 0.5 * (L + U), L, U

打印的信息里最有价值的是每一轮[L, U]区间。如果某几轮L一直不动，说明当前中点被判定为不可行，这可能是数值问题，也可能是初始区间选错了（详见第 5 章）。如果U一直不动，说明当前中点被判定为可行，但上界没有收缩，同样值得警惕。

主循环调用方式如下，假设有了初始L和U：

p_opt, L_final, U_final = bisection_search(L=-2.0, U=2.0, N=30) print(f"最优值估计: {p_opt:.6f}") print(f"可行上界: {U_final:.6f}") print(f"不可行下界: {L_final:.6f}")

注意U_final和L_final本身也是输出结果的一部分。写进报告或结论时，说「最优值落在 [L_final, U_final] 区间内」比说「最优值是 p_opt」严谨得多，因为二分给的是区间保证，不是点估计。

3.4 初始区间的求法：先找可行点，再向下试探

初始上界最容易获得：任取一个可行点，算出目标函数值，这个值天然就是p*的一个上界。在我们的例子里x = 0可行，所以U = f0(0)。但如果你的问题里可行点不是随手就能给出来的，可以先解一个不带 t 的纯可行性问题，得到某个可行解x0，再计算U = f0(x0)。

初始下界要难一些：它必须是一个「不可行」的值。一个实用的试探策略是从上界出发向下缩，直到找到第一个不可行的 t：

def find_lower_bound(U, factor=2.0): L = U / factor while check_feasible(L): L /= factor return L

factor=2.0表示每次把 t 减半，直到某个值被判为不可行。这个函数能结束的前提是问题有下界；如果问题本身p* = -∞，check_feasible对任何 t 都返回 True，死循环。因此调用前先用||x||_∞ ≤ 5这类约束把可行域框住，是写这个函数之前的必做功课。

找完 L 和 U 之后，我强烈建议立刻做一次验证：

assert check_feasible(U), "上界必须可行" assert not check_feasible(L), "下界必须不可行"

这两个断言能在 5 秒内检查出 80% 的初始化错误。二分算法的正确性完全建立在「初始区间左不可行、右可行」之上，这个前提如果错了，后面所有结果都是错的，而且很难从迭代日志里看出来。

4. 二分算法的参数设定：区间、迭代次数、容差与求解器选择

4.1 初始区间为什么必须「左不可行、右可行」

二分算法的收敛性证明依赖一个核心前提：最优值p*存在于开区间(L, U)内。如果违反了这个前提，算法不会报错，而是静默地给你一个错误区间，这种失败方式在项目里最危险。

先看上界 U 选错的情况：如果 U 其实不可行（比如你随手取了一个 t 小于真正的p*），那么二分循环里每一次检查都返回 False，L 每一轮都跳到中点，最终 L 收敛到 U，整个循环结束后输出的区间宽度接近 0，看似收敛，实则整个区间都在最优值下方。下界 L 选错则相反：如果 L 实际上是可行的，循环每一轮都返回 True，U 收敛到 L，结果整个区间高于真实最优值。

这两种错误都表现为「区间正常缩短，但答案整体偏移」。唯一的防线就是在进入循环之前，用 3.4 的断言把两个端点各验证一次。代价只是多跑两次可行性问题，时间几乎可以忽略。

另外，初始区间的跨度直接决定迭代次数。若U - L很大，而最终精度要求很高，N 要对应加大。如果你的模型里目标函数尺度悬殊，建议先估一下数量级：f0的量级是 1e6 还是 1e-6，决定了后续容差参数是否要按比例缩放。

4.2 迭代次数 N：先定绝对误差，再套公式

二分算法每轮把区间长度减半，N 轮后的区间长度是(U - L) / 2^N。想达到绝对误差 ε，需要的迭代次数是：

N = ceil( log2( (U - L) / ε ) )

举例：初始区间长度为 100，想要最终误差不超过 1e-3，log2(100 / 1e-3) ≈ 16.6，取 N = 17；想要误差不超过 1e-6，log2(1e8) ≈ 26.6，取 N = 27。在代码里可以写成：

import math L, U = -2.0, 2.0 eps_abs = 1e-4 N = math.ceil(math.log2((U - L) / eps_abs)) print(N) # 约为 16

超过 40 轮之后继续二分意义不大，因为求解器自身的可行性容差通常在 1e-6 到 1e-8 之间，区间缩小到这个量级时，边界上的可行性判断已经受浮点舍入影响，结果不再可靠。实用的做法是：先按公式算 N，跑完看最终区间长度是否满足需求；如果最后一轮可行性和不可行性判断开始抖动，说明已经到数值极限了，再增加 N 只会浪费时间。

另一个常见误用是用「相邻两轮 t 的差值小于阈值」作为终止条件。这在最优值平坦的问题上会提前终止：t 在平坦区里变化很小，但区间宽度还很大，得到的上界可能离真实最优值很远。二分法的正确终止条件永远是区间宽度或固定轮数，不是 t 的位移。

4.3 可行性容差与求解器：内点法更干净

可行性检查的容差设置比普通人想象中更敏感。容差太松，求解器会把 t 略小于p*的问题误判为可行，导致上界收缩到真实最优值之下；容差太紧，求解器又可能因为数值噪声把可行问题判定为不可行。

容差的合理取值和模型尺度强相关。目标值量级在 1 附近的问题，eps_abs=1e-6是一个比较稳的起点；如果目标值量级是 1e6，容差也得放大到 1e-3 甚至更大，否则求解器内部在 1e-8 的容差下永远无法满足约束残差。我的习惯是先看模型初始可行点的约束残差量级，再定容差，而不是一上来就用默认值。

求解器选择方面，我的经验如下表：

一阶求解器如 OSQP 和 SCS 求解大型 LP 速度快，但判定不可行时经常出现两种模糊状态：optimal_inaccurate和infeasible_inaccurate。前者表示找了一个点但残差没达标，后者表示大概率不可行但没被严格证明。在二分循环里，模糊状态是最烦人的——你没法干脆地归入 True 或 False。内点法求解器在中小规模问题上很少出现这类模糊状态，这也是我推荐 CLARABEL 或 ECOS 作为默认选项的原因：宁可多花几毫秒，也要一个明确的状态判定。

5. 避坑：可行性判断翻车的五种常见场景与处置

5.1 solver 返回 optimal，解代入约束却发现违反

现象：prob.status == cp.OPTIMAL，但把x.value回代到约束里，残差明显超过容差，甚至f0(x)大于你传进去的 t。有时候 CVXPY 还会直接给出optimal_inaccurate，但如果你只写了status != cp.INFEASIBLE，这个状态会被当成可行处理。

原因：一阶求解器在接近约束边界时提前停止，残差停留在eps_abs附近；或者模型本身数值条件差，比如约束矩阵列尺度相差悬殊。

解决：把「求解 + 回代验证」合并成一个函数，用代验证作为最终判定，而不是 solver 的状态。我一般这样写：

def check_feasible_with_verify(t, atol=1e-4): prob, x = build_feasibility(t) prob.solve(solver=cp.OSQP, eps_abs=1e-6, eps_rel=1e-6) if prob.status not in (cp.OPTIMAL, cp.OPTIMAL_INACCURATE): return False n = x.value.size xv = np.clip(x.value, -5.0, 5.0) # 防止 solver 给出边界外的值 for i in range(A.shape[0]): lhs = A[i] @ xv + b[i] rhs = t * (C[i] @ xv + d[i]) if lhs > rhs + atol: return False if np.min(C @ xv + d) < 1e-4: return False return True

这个函数把「solver 说可行」和「数值上真可行」做了双向校验。判 False 的条件是硬性约束违反，判 True 的条件是回代后所有约束都满足，两个方向都在代码里显式表达。

5.2 二分结果永远贴在上界，L 一步都没动

现象：迭代日志显示每一轮都是 infeasible，L 不断向 U 靠拢，最终区间长度趋近于零，但算出来的「最优值」其实只是初始 U 附近的一个值，没有任何优化的意义。

原因：初始 U 本身不可行，或者你给的 U 根本不是真正的上界。比如你从某个不可行点出发计算了目标值，那个点其实不在可行域内，f0(x0)自然不是p*的上界。还有一种情况是目标值本身无下界，二分循环里所有 t 都返回 False。

解决：初始化阶段做一次显式验证，确认check_feasible(U)为真。如果 U 不可行，退回第 3.4 节，先解一个纯可行性问题找可行点，再重新计算上界。另外，在循环开始前打印一下f0(x0)和对应点的约束残差，能避免很多无效的排查。

5.3 分母接近零导致每轮可行性结果像抽签

现象：同一组数据连续跑两次二分，得到的最优值相差很大；或者相邻两轮对相近的 t 给出相反的可行性判断。检查迭代日志常能看到区间宽度还在 1e-2 量级时，可行性判断就开始抖动。

原因：线性分式的分母c_i^T x + d_i在可行域内部接近零点，f0(x) ≤ t两边同时乘分母时，分母的正负号在数值上不稳定。一旦分母的符号被浮点误差翻转，约束方向就错了，可行性检查结果自然不可信。更深层的原因是可行域包含分母过零点附近的退化区域，而下水平集凸性只在分母为正的区域内成立。

解决：把分母正约束写成显式约束，并加大安全间隙。将delta从 1e-6 提到 1e-4 或 1e-3，通常能明显稳定结果。代价是可行域被轻微压缩，最优值可能略有偏移。我落地时的习惯是做一次 delta 敏感性分析：

for delta in [1e-3, 1e-4, 1e-5, 1e-6]: p_opt, L, U = solve_with_delta(delta) print(f"delta={delta:.0e}: 最优值区间 [{L:.6f}, {U:.6f}]")

如果不同 delta 下最优值区间变化小于你设定的精度，说明结果可靠；如果变化很大，说明问题本身在退化边界附近，需要重新审视建模，而不是继续调二分参数。

5.4 最优值平坦段：区间收敛了，解却漂移

现象：二分最终给出很窄的区间，但每次运行得到的可行解x都不同，甚至差异巨大。仔细看发现目标函数在最优区域附近几乎是一条平坦段，任何落在平坦段里的点目标值都差不多。

原因：拟凸问题的最优解集可能不是单点。二分法收敛的是最优值p*，不是最优解本身。在平坦段上，t略大于p*时存在一大片可行解，求解器每次返回的可行点随机分布在这片区域里，看起来就像「算出来的解不稳定」。

解决：接受二分法的定位——它只负责给出最优值的高精度区间。如果你需要唯一解或性质更好的解，把t = U（可行上界）固定住，再求解一个带正则项的辅助问题：

x = cp.Variable(n) cons = [约束条件, f0_expr <= U_final] prob = cp.Problem(cp.Minimize(cp.sum_squares(x - x_ref)), cons)

这样在保证目标值不超过U_final的前提下，挑选离参考点最近的解，结果稳定且可复现。x_ref可以取上一轮二分过程中的某个可行点，也可以全零向量。

5.5 solver 报 infeasible 但问题其实可行

现象：check_feasible(t)返回 False，但你把 t 稍微调大 1e-3 再跑，返回 True；或者换一个求解器跑同一个 t，结果是可行。整个二分循环在这种抖动下反复震荡，最终区间收敛到噪声级别，无法确定最优值。

原因：严格说，数值求解器对「不可行」的判定本身也是一种数值结果，不是数学证明。约束矩阵病态、尺度失衡、或 t 恰好卡在最优值边界附近时，内点法可能提前报告 infeasible，尤其是边界残差在容差边缘的情况。

解决：三管齐下。第一，把求解器容差放宽 10 倍再判一次，如果变可行，说明之前是不可靠的数值误判；第二，换一个求解器交叉验证；第三，用一个带松弛变量的 Phase-I 问题做仲裁：

def check_feasible_phase1(t, slack_penalty=1e3): x = cp.Variable(n) s = cp.Variable(m + n, nonneg=True) # 松弛变量 # 原约束加上松弛，目标是最小化松弛和 ...

Phase-I 的思想是：给每条约束加一个非负松弛变量，最小化松弛变量的总和。如果松弛和为 0，问题严格可行；如果最小松弛和大于 0，问题在数值意义上确实不可行。这个仲裁方法比直接信任何一个 solver 的状态更可靠，尤其是当你怀疑某个特定求解器给出的是「数值噪音」而非「数学结论」的时候。

6. 从可用的二分到可信的最优：验证手段与更快替代

6.1 把答案写成一个闭区间，而不是一个点

二分算法最强的数学资产不是最终那个中点值，而是「最优值一定在闭区间 [L, U] 内」这个结论。写技术报告或对接下游系统时，我总是把结果输出成(p_est, L, U)三元组，并附上一行说明：估计值p_est是区间中点，真实最优值以 1 的概率落在[L, U]内。这个写法看似保守，实际上能帮你挡掉大量关于「这个数准不准」的质疑。

6.2 复用问题对象：参数化 t 能省一半时间

每轮 t 都重建 CVXPY 问题对象会带来可观的解析开销。改成用cp.Parameter预构建问题，循环里只更新 t 的值，能省下 30%~50% 的总时长：

t_param = cp.Parameter(nonneg=True) x = cp.Variable(n) cons = [x >= -5.0, x <= 5.0, C @ x + d >= 1e-4] for i in range(m): cons.append(A[i] @ x + b[i] <= t_param * (C[i] @ x + d[i])) prob = cp.Problem(cp.Minimize(0), cons) def check_feasible(t): t_param.value = t prob.solve(solver=cp.CLARABEL) return prob.status == cp.OPTIMAL

注意Parameter(nonneg=True)限定了 t 非负。如果最优值可能为负，去掉nonneg=True参数，否则求解器会直接拒绝负值。问题规模越大，复用问题对象的收益越明显。

6.3 替代方案：DQCP 自动二分与手工二分的边界

CVXPY 的 DQCP 扩展能做到类似的事，对符合拟凸规则的问题自动做二分。作为一个快速验证手段，DQCP 很方便，但它把容差、初始区间、状态判定全部封装在内部，出了问题你很难定位。手工二分保留的恰恰是问题排查能力：你可以打印每一轮的区间走向，可以换求解器，可以插入回代验证，可以给出数学上有保证的闭区间。项目进入交付阶段，或者问题数值条件比较差的时候，我会毫不犹豫选择手工二分。早年我做某个跨平台系统的定位模块时，偷懒直接用 DQCP 黑匣子，得到一个看起来正常的最优值，却怎么都解释不了为什么换一组数据结果跳变。拆开自己写二分之后，才定位到是求解器把optimal_inaccurate当成optimal，又因为我从没验证过初始上界是否真可行，整个二分从一开始就建立在错误的假设上。从那以后我的习惯是：可行性检查单独成函数，初始区间跑两次验证，最终永远输出[L, U]闭区间。希望帮到你。

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