序列凸规划

序列凸规划（sequential convex programming，SCP）在当前点附近建立凸近似，求解后更新近似点，以处理原来非凸的目标或约束。它描述的是一类策略；不同的上界构造、信赖域与接受规则产生不同算法。每个子问题为凸，并不把原问题变成了全局凸问题。

非凸可行集上的保守近似

考虑教学问题 $$\underset{x}{min}(x+1/4{)}^2,1-x^2\le 0.$$ 可行集是两段 $x\le -1$ 与 $x\ge 1$。目标本身凸，困难来自两段互不连通的约束。记 $g(x)=1-x^2$。它是凹函数，在当前点 $a\ne 0$ 的切线为 $$\hat{g}(x;a)=1-a^2-2a(x-a)=1+a^2-2ax.$$ 两者的差可精确写为 $\hat{g}(x;a)-g(x)=(x-a{)}^2\ge 0$。所以要求切线 $\hat{g}\le 0$ 比原约束更严格：切线是上界，它的非正区域必然原始可行。

切线上界的非正区域从 5/4 开始，是原始正分支的子集。

从 $a=2$ 出发，凸子问题要求 $x\ge 5/4$，故其最小点为 $1.25$。再以该点建立新切线，得到 $x\ge 1.025$，接着得到约 $1.000304878$。每一步都在正分支上保持可行，目标从 $5.0625$ 降至 $2.25$、$1.625625$，趋近 $1.5625$。

可行性与下降各需要什么

设一般不等式为 $g_i(x)\le 0$。若凸近似满足对所用区域的每个 $x$ 有 ${\hat{g}}_i(x;a)\ge g_i(x)$，则近似可行点一定原始可行；若还满足 ${\hat{g}}_i(a;a)=g_i(a)$，原始可行的当前点仍是子问题的可行候选。再设目标近似满足 $\hat{f}(x;a)\ge f(x)$ 且在当前点相等，子问题精确最小点 $x^{+}$ 就满足 $$f(x^{+})\le \hat{f}(x^{+};a)\le \hat{f}(a;a)=f(a).$$ 第一步用目标上界，第二步用子问题最小化，第三步用接触条件。这证明的是这一保守近似方案的可行性和下降不变量，不是任意泰勒近似都拥有的性质。

若近似只在一个邻域可靠，就需限制信赖域并用原问题评价接受候选；一般非线性等式的仿射近似也不会保留精确可行性。SCP 的原始目标、约束违反量和局部模型误差须分别检查。

金色轴段表示可行范围；保守近似可能停在较差的正分支。

同一个算例中的收敛与全局差距

主例在正分支上的更新为 $a^{+}=(a+1/a)/2$。当 $a\ge 1$ 时，$a^{+}\ge 1$，因为 $a+1/a\ge 2$；同时 $a^{+}\le a$，因为 $1/a\le a$。序列因此有极限，取极限解 $\ell =(\ell +1/\ell )/2$ 得 $\ell =1$。更精细地，$a^{+}-1=(a-1{)}^2/(2a)$，说明接近一时误差二次缩小。

然而原问题负分支的边界 $x=-1$ 给出目标 $9/16=0.5625$，优于正分支极限 $25/16=1.5625$。正分支的保守近似一直排除负分支，所以即使每个子问题都被全局求解，整体仍可能只得到局部最优点。这个差距不是子问题求解精度造成的。

作为变式，从 $a=-2$ 出发，切线约束变为 $x\le (a+1/a)/2=-1.25$，子问题最小点为该边界；后续为 $-1.025$、约 $-1.000304878$，收敛到负分支的较好最优点。若从零开始，切线约束为 $1\le 0$，子问题不可行，尽管原问题有解。初值和近似构造会改变可获得的结果。

一维凸子问题的直接实现

下面函数仅为此模型服务：输入满足 $|a|\ge 1$ 的可行初值和非负轮数；返回迭代点、原目标和原始约束值，不改写输入。每个凸子问题已解析求解，每轮时间和工作空间为常数，保存历史需 $O(K)$。一般 SCP 的成本由凸子问题决定，不能只按外层轮数衡量。

Python 3

def conservative_scp(initial=2.0, count=3):
    a = float(initial)
    if abs(a) < 1 or count < 0:
        raise ValueError("feasible initial point required")
    trace = [(a,(a+.25)**2,1-a*a)]
    for _ in range(count):
        bound = (a+1/a)/2
        a = max(-.25,bound) if a > 0 else min(-.25,bound)
        trace.append((a,(a+.25)**2,1-a*a))
    return trace

for start in (2.0,-2.0):
    print("start",start)
    for row in conservative_scp(start):
        print(tuple(round(v,9) for v in row))
assert all(row[-1] <= 1e-12 for row in conservative_scp())

代码同时运行两种初值，展示两条分支各自的下降过程。小的步长或目标变化只是停止信号；在一般非凸问题中，它们不提供全局最优差距。