二阶锥规划

二阶锥规划（second-order cone programming，SOCP）在仿射目标、仿射等式以及“欧氏范数不超过仿射量”的约束下优化。范数约束同时描述方向和大小，右侧还隐含非负要求。它可表达最小包围圆、某些鲁棒约束和凸二次上图。

三个点的最小包围圆

给定平面点 $a_1=(-1,0),a_2=(1,0),a_3=(0,2)$，选择圆心z及半径r，要求三点都在圆内。模型为 $$\underset{z\in {ℝ}^2,r\in ℝ}{min}r,\Vert z-a_j{\Vert }_2\le r(j=1,2,3).$$ 范数约束本身已迫使r非负。若圆心为 $(x,y)$，左右两点的较大距离平方为 $x^2+y^2+1+2|x|\ge 1+y^2$；到上方点的距离至少为 $|2-y|$。当 $y<3/4$，后一个下界大于5/4；当 $y>3/4$，$\sqrt{1+y^2}>5/4$。所以半径不可能小于5/4。

取 $z=(0,3/4),r=5/4$，三个距离都恰为5/4，达到下界，证明全局最优。若r达到这个值，上述不等式还迫使 $y=3/4,x=0$，故圆心唯一。

三个距离均为 5/4；圆心 (0,3/4) 是唯一最优点。

二阶锥及凸性证明

维数k的Lorentz锥写为 ${𝒦}_{k+1}=\{(t,u)\in ℝ\times {ℝ}^k:\Vert u{\Vert }_2\le t\}$。若两个点在锥内、$0\le \theta \le 1$，由三角不等式 $$\Vert \theta u+(1-\theta )v\Vert \le \theta \Vert u\Vert +(1-\theta )\Vert v\Vert \le \theta t+(1-\theta )s,$$ 所以凸组合仍在锥内。一般SOCP可写为 $min{c}^{𝖳}x$，约束 $$\Vert A_{i}x+b_i{\Vert }_2\le c_i^{𝖳}x+d_i(i=1,\dots ,m),Fx=g.$$ 各矩阵维数须使范数内向量和对应标量有定义；x为共同决策向量。仿射映射的凸锥原像仍凸，故整个模型凸。

范数边界是 t 等于 u 的绝对值；固定 t=1 的截面是一段区间。

二次变换中的符号条件

直接平方 $\Vert u\Vert \le t$ 时必须同时保留 $t\ge 0$，否则平方式 $\Vert u{\Vert }^2\le t^2$ 也会接受负t。例如u为零、t为负一满足平方式，却不在二阶锥中。

对 $s,t\ge 0$，旋转锥约束 $\Vert u{\Vert }^2\le st$ 等价于 $${\Vert (\genfrac{}{}{0ex}{}{2u}{s-t})\Vert }_2\le s+t.$$ 证明平方两边并消去 $(s-t{)}^2$，得到 $4\Vert u{\Vert }^2\le 4st$；非负条件保证右侧s+t允许从平方式开方。若没有非负条件，s=t=−1、u=0会满足乘积式却违反范数式。

因此当 $Q=R^{𝖳}R⪰0$ 时，$x^{𝖳}Qx\le s$ 可用u=Rx、t=1的上述约束表示；不定二次型不能未经处理就写成某个范数平方。

端点变式与直接实现

把上方点改为 $(0,1/2)$。左右两点距离二，任意包围圆的直径至少二，所以r至少一；圆心原点、半径一包含全部三点，故最优。此时较矮的第三点不在圆周，不能仍强求三点等距。一般上方高度h为非负时，圆心高度为 $max\{0,(h^2-1)/(2h)\}$（h=0时取零），半径据此求最大距离。

下例只用标准库，解析求解这组三点并返回各点距离，不改写输入。固定规模的成本为常数；一般SOCP需要锥优化算法，不能由这一个对称模型的闭式解估计通用求解成本。数值运行应检查范数残差和终止状态，而不是仅检查平方后的残差。

Python 3

import math

def symmetric_enclosing_circle(height=2.0):
    h = float(height)
    if h < 0:
        raise ValueError("nonnegative apex height required")
    y = max(0.0,(h*h-1)/(2*h)) if h > 0 else 0.0
    distances = [math.hypot(1,y),math.hypot(1,y),abs(h-y)]
    radius = max(distances)
    return (0.0,y),radius,distances

print("main",symmetric_enclosing_circle())
print("variant",symmetric_enclosing_circle(.5))
assert symmetric_enclosing_circle()[1] == 1.25
assert symmetric_enclosing_circle(.5)[1] == 1.0