Norm Z. Shor 1992 → NP-hardness by Amir Ali Ahmadi .al https://doi.org/10.1007/s10107-011-0499-2
Stanford | Michael Grant. 2005
<aside>
问题 → 优化模型 → 程序语言描述 → 优化求解器 → 结果反馈
诸多应用场景问题可抽象为最优化 Optimization
凸优化 Convex Optimization 可有效求解，整数优化等存在商用（综合）优化求解器 MOSEK ，更复杂的组合优化问题常用 分支限域法 搜索，或遗传算法 随机优化。
CVXPY 能够程序化判定优化问题凸性。它能够帮助 coder 用自然语言表述优化问题并向 solver 完成转译（reduction）。
当前各类成熟求解器正在尝试功能融合。
比如一阶投影法的代表 SCS SCS 支持 warm-start 热更新（迭代），并行（CPU/GPU）投影，处理大规模问题，同时给出原始对偶问题对的可行性分析HSDE ，二次优化目标（Clarabel ），优化DSL CVXPY 支持，底层数学库（Intel OneAPI cuDSS MPICH2 ）对接，特例（锥投影 ）接入这些功能；
一些设计者尝试在 IPM 中加入这些功能，甚至将 ADMM 算法本身作为 IPM 的子程序。
生成模型生成 warm-start 以加速收敛
另一方面，优化问题的逐领域求解贡献着新的最优化 应用场景
CvxpyLayers 允许用户在 神经网络 / 机器学习 中用最优化建模目标函数 或 物理控制层，进而缓解 NN 的黑箱状态，简化训练。 vgon
JAXopt 充分利用 机器学习框架的微分系统对 投影算子（对应求解投影问题）自动微分，方便研究者数值实验并对比新的专用算法，推动优化控制（如 机器人学）程序实现演进。 Automatic Differentiation
</aside>
<aside>
GPU
Cholesky Factorization $O(\log_2N\cdot n^3)$ N is the number of bloks n is block size - ‣ | cuDSS ←https://github.com/giaf/blasfeo(BLAS For Embedded Optimization / CPU)←‣
https://github.com/NVIDIA/warp?tab=readme-ov-file#warpexamplesoptim → 可微的CUDA包装器，支持PyTorch JAX
</aside>
<aside>
convex
booksConvex Optimization | definitions Convexity | applications Convex Optimization
quasi-convex 拟凸：函数曲线在任意两函数点的矩形内
$$ f(\lambda x+(1-\lambda)y)\le\min\{f(x),f(y)\} $$
strong-convex 强凸：函数在叠加变量的度量后保持凸性的函数
$$ g(x)=f(x)-\frac m2\|x\|^2_2 $$
范数/度量常用欧几里得距离/2-范数。不同度量性质不保证一致。
$$ g(tx+(1-t)y)\le tg(x)+(1-t)g(x)\\ f(tx+(1-t)y)\le tf(x)+(1-t)f(x)+\frac m2\left( \|tx+(1-t)y\|_2^2- \|x\|^2_2-\|y\|^2_2 \right)\\ $$
余项中可以提取公因子$t(1-t)=(1-t)\left(1-(1+t)\right)$
这与 https://en.wikipedia.org/wiki/Convex_function#Strongly_convex_functions third def 等价
$$ f(tx+(1-t)y)\le tf(x)+(1-t)f(y)-\frac 12mt(1-t)\|x-y\| _2^2 $$
如果凸函数$f$ 一阶可微，凸函数等价于
$$ (x-y)^T(\nabla f(x)-\nabla f(y))\ge 0 $$
（考虑关于t单调性，带入 $x,x+t(y-x)$）
一阶支撑函数$f(y)\ge f(x)+(y-x)^Tf(x)$能够推出凸性，$f(y)\ge f(x)+(y-x)^Tf(x)+\frac m2 \|x-y\|^2_2$
强凸定义为
$$ (x-y)^T(\nabla f(x)-\nabla f(y))\ge m\|x-y\|^2_2 $$
如果凸函数$f$二阶连续可微，其二阶导数不小于$m$，或者说
$$ \nabla ^2f(\vec x)\succeq mI \iff
\nabla ^2f(\vec x)\succeq mI $$
则称函数$f$为强凸函数。写成二次型
$$ h^THh^T\ge mh^TIh $$
对于2-范数$h^T\nabla ^2f(\vec x)h\ge m\|h\|^2_2$
通常用 Lipschitz 连续再限制
$$ \nabla ^2f(\vec x)\preceq LI $$
$$ (x-y)^T(\nabla f(x)-\nabla f(y))\le L\|x-y\|^2_2 $$
(one-sided Lipschitz)
$$ f(y)\le f(x)+(y-x)^Tf(x)+\frac L2 \|x-y\|^2_2 $$
$$ \|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|_2 $$
(Lipschitz continuous)
这四条基本上等价。https://zhuanlan.zhihu.com/p/210252556 https://zhuanlan.zhihu.com/p/181718998 https://en.wikipedia.org/wiki/Lipschitz_continuity
强凸函数（ ）能够在经典牛顿法下收敛 Disciplined Convex Programming 牛顿方法
</aside>
Norm Z. Shor 1992 → NP-hardness by Amir Ali Ahmadi .al https://doi.org/10.1007/s10107-011-0499-2
Stanford | Michael Grant. 2005
<aside>
</aside>
reduction
<aside>
</aside>
<aside>
</aside>
http://faculty.bicmr.pku.edu.cn/~wenzw/optbook/lect/07-lect-theory.pdf