一、非线性约束概述
1.1 什么是非线性约束
先问个问题：你平时写约束条件时，是不是都是线性的？比如 x + y ≤ 10，或者 2x - 3y = 5。这些是线性约束，好处理。但现实世界没这么乖。
非线性约束，说白了就是约束条件里出现了非线性项。比如 x² + y² ≤ 1，或者 sin(x) + e^y ≥ 0.5，再或者 x·y ≤ 10。这些都不是直线或平面，而是曲线、曲面，甚至更复杂的形状。
我个人的习惯是，把非线性约束分成三类：
- 多项式约束：比如 x² + y² ≤ R²，或者 x³ - 2xy + y² ≥ 0
- 超越函数约束：涉及 sin、cos、exp、log 等
- 乘积约束：两个变量相乘，比如 x·y ≤ 10，这在组合优化里特别常见
举个例子。你在做物流路径规划时，有个约束是「车辆载重不能超过 10 吨」。这看起来是线性的，对吧？但如果考虑油耗和载重的关系——油耗 = 0.1 × 载重² + 5，那约束就变成非线性的了。我在项目中遇到过类似情况，当时差点用线性近似糊弄过去，结果算出来的方案根本跑不通。
1.2 为什么非线性约束难处理
这个问题我琢磨了很久。非线性约束难，难在三个地方：
- 可行域不再是凸集。线性约束的可行域是凸多边形，好找最优解。非线性约束一进来，可行域可能变成月牙形、环形，甚至碎成好几块。你想想看，搜索空间都裂开了，算法怎么找？
- 局部最优陷阱。线性规划里，局部最优就是全局最优。非线性约束下，这个结论不成立了。我踩过这个坑——有一次跑了一个通宵的算法，结果发现收敛到了一个局部最优，离全局最优差了 30% 的性能。
- 计算复杂度飙升。线性约束的检查是 O(n) 的，非线性约束往往需要数值计算，甚至迭代求解。一个约束检查就要算好几步，组合优化里约束成千上万，这谁顶得住？
核心难点总结：非线性约束让组合优化问题从「难」变成了「非常难」。NP-hard 问题加上非线性，基本就是算法工程师的噩梦。
嗯，这里要注意一点。并不是所有非线性约束都难。有些特殊结构，比如凸二次约束，其实有高效的求解方法。但大部分情况下，非线性约束意味着你要放弃「精确求解」的幻想，转而寻找近似解或启发式方法。
1.3 典型应用场景
非线性约束在组合优化里其实遍地都是。我挑三个最常见的场景说说：
场景一：资源分配中的规模效应
假设你要分配服务器资源给多个任务。每个任务的响应时间 T 和分配的资源 R 之间，往往满足 T = a / R + b。这是个非线性关系。约束条件「响应时间 ≤ 100ms」就变成了 a/R + b ≤ 100，也就是 R ≥ a/(100-b)。
看起来还能解？但如果你有 1000 个任务，每个任务还要考虑资源总量限制，问题就复杂了。我记得有一次做云资源调度，就是因为忽略了这种非线性关系，导致线上服务频繁超时。
场景二：网络设计中的信号衰减
通信网络里，信号强度随距离呈指数衰减：P_received = P_sent × e^(-αd)。约束条件「接收信号强度 ≥ 阈值」就变成了 e^(-αd) ≥ 阈值/P_sent。这玩意儿在基站选址问题里特别常见。
你想想看，既要选基站位置（离散变量），又要满足信号覆盖（非线性约束），这问题有多酸爽。我见过一个团队用线性近似处理这个约束，结果建出来的基站有一半覆盖不到目标区域。
场景三：生产调度中的能耗约束
机器能耗和加工速度之间，通常不是线性关系。比如能耗 = 0.5 × 速度² + 10。约束「总能耗 ≤ 1000 kWh」就变成了 Σ(0.5 × v_i² + 10) ≤ 1000。
这看起来是个二次约束，但组合优化里还要同时考虑机器的启停顺序、任务分配。我在一个工厂排产项目里遇到过，当时用混合整数二次规划（MIQP）求解，跑了 3 个小时才找到可行解。
我的建议：遇到非线性约束时，先别急着上复杂算法。试试能不能通过变量替换或分段线性化，把问题转化成线性约束。实在不行，再考虑用非线性求解器或启发式方法。
1.4 知识体系框架
下面这张图是我自己整理的，把非线性约束在组合优化中的位置和关系画清楚了。你可以把它当作本章的导航图。
避坑指南：我曾经在一个项目里，把非线性约束直接当成线性约束处理，结果算出来的「最优解」根本不可行。后来花了整整两周重新建模。所以我的建议是——遇到约束条件，先判断它是不是线性的。如果不是，老老实实按非线性处理，别偷懒。
好了，这一章我们聊了非线性约束是什么、为什么难、以及在哪里会遇到。下一章我会深入讲具体的建模技巧，包括怎么把实际问题转化成非线性约束，以及常见的「坑」在哪里。
公众号:蓝海资料掘金营，微信deep3321