5. 凸优化工具包

# CVX

CVX 是由 Michael Grant 和 Stephen Boyd 开发的基于 disciplined convex programming 的建模系统。

基本信息
- CVX 基于 disciplined convex programming 的思想
- 建立在早期工作基础上：Löfberg 的 YALMIP、Dahl 和 Vandenberghe 的 CVXOPT
- 在给定规则集下，提供凸原子的正确组合，确保优化问题是可证明的凸问题
- 可以求解标准问题：线性规划（LP）、二次规划（QP）、二阶锥规划（SOCP）、半正定规划（SDP）
CVX 的局限性
- CVX 不是用于检查问题是否为凸的工具，但如果 CVX 接受你的问题，可以确定它是凸的
- CVX 不适合求解非常大的问题，它是用于实验和原型设计的工具
- 可以使用 CVX 求解缩小规模或简化版本的问题
CVX 的工作原理
- CVX 本身不求解优化问题，只将问题重新表述为可以输入数值凸优化包的形式（SDP 和 SOCP）
- 底层求解器包括：
  - SDPT3: http://www.math.nus.edu.sg/~mattohkc/sdpt5.html
  - SeDuMi: http://sedumi.ie.lehigh.edu/
- 这些求解器随 CVX 一起分发
- CVX 消除了使用这些包的障碍
求解器选择
- 可以选择数值求解器，例如 SeDuMi：
```
cvx_solver sedumi
cvx_save_prefs
```
- 第二个命令使 CVX 工具箱记住你的偏好选择
- 自 2012 年起，CVX 支持一些商业软件，如 Gurobi、MOSEK
- 详细信息：http://cvxr.com/cvx/doc/solver.html
安装
- CVX 可从 http://cvxr.com/cvx/download 下载
- 安装步骤：
  1. 解压 .zip 文件到任意位置（不要安装到 MATLAB 自己的工具箱目录）
  2. 在 MATLAB 命令提示符下，输入 cd <cvxroot>
  3. 运行命令 cvx_setup 配置软件
- 安装成功后，MATLAB 路径已更新指向 CVX 分发目录
使用方法
- 为了将 CVX 规范与周围的 MATLAB 代码分离，CVX 代码以 cvx_begin 开始，以 cvx_end 结束
- 规范可以包括任何普通的 MATLAB 语句，以及特殊的 CVX 特定命令：
  - 声明原始和对偶优化变量
  - 指定约束和目标函数
- CVX 选项和控制语句：
  - cvx_quiet：打开和关闭求解器输出
  - cvx_precision：控制求解器精度
无约束例子：最小二乘问题

在最小二乘问题中，我们寻求 $x \in \mathbb{R}^n$ 使得 $\|Ax - b\|_2$ 最小，其中 $A \in \mathbb{R}^{m \times n}$ 是瘦且满秩的。

MATLAB 版本：
```
% 输入数据
m = 16; n = 8;
A = randn(m, n);
b = randn(m, 1);

% 最小二乘解
x_ls = A \ b;  % MATLAB 版本
```
CVX 版本：
```
% CVX 版本
cvx_begin
    variable x(n);
    minimize( norm(A*x - b) );
cvx_end
```
说明：
- variable x(n) 指定 $x$ 是优化变量（长度为 $n$ 的向量形式）
- minimize( norm(A*x - b) ) 给出目标函数并指定我们希望最小化它
- 在 cvx_end 之后， $x$ 被最优点覆盖，不再是符号变量
约束例子
- CVX 可以处理各种约束，包括线性约束、二次约束、半正定约束等
- 约束的写法遵循 MATLAB 语法，但使用 CVX 特定的运算符（如 <=, >=, ==）
其他情况
- CVX 支持多种凸优化问题类型
- 可以处理复杂的目标函数和约束组合
- 提供了丰富的示例和文档

# CVXOPT

CVXOPT 是用于凸优化的 Python 软件包。

基本信息
- CVXOPT 是 Python 中的凸优化工具包
- 提供了求解线性规划、二次规划、二阶锥规划、半正定规划等问题的接口
- 基于内点法实现
特点
- Python 接口，易于使用
- 支持多种凸优化问题类型
- 可以与 NumPy 和 SciPy 等 Python 科学计算库集成

# CVXPY & CVXGEN

CVXPY
- CVXPY 是 Python 中的凸优化建模语言
- 类似于 CVX，但使用 Python 语法
- 提供了简洁的语法来表述凸优化问题
- 支持自动微分和问题变换
CVXGEN
- CVXGEN 是用于嵌入式凸优化的代码生成器
- 由 J. Mattingley 和 S. Boyd 开发
- 可以为特定的凸优化问题生成快速、定制的求解器代码
- 适用于需要实时求解的应用场景
相关工具
- YALMIP：Yet Another LMI Parser，MATLAB 中的建模语言
- JuMP：Julia 中的数学优化建模语言

# Cplex, Gurobi and Their Competitors

CPLEX

历史背景

CPLEX 最初由 Robert E. Bixby 开发，1988 年起由 CPLEX Optimization Inc. 商业销售
1997 年被 ILOG 收购，2009 年 1 月 ILOG 被 IBM 收购
目前可在 IBM 官网下载，学术版免费且变量数量无限制，需要用学校邮箱申请

功能特点

专门用于求解大规模的线性规划（LP）、二次规划（QP）、带约束的二次规划（QCQP）、二阶锥规划（SOCP）等四类基本问题
支持相应的混合整数规划（MIP）问题
在运筹学（OR）学术圈，CPLEX 是事实的计算基准软件
IBM 为 CPLEX 提供了中文网页：https://www.ibm.com/cn-zh/analytics/cplex-optimizer

使用示例（C++ 风格）

#include <ilcplex/ilocplex.h>
ILOSTLBEGIN

int main(int argc, char **argv) {
    IloEnv env;
    try {
        IloModel model(env);
        IloNumVarArray vars(env);
        
        // 定义变量
        vars.add(IloNumVar(env, 0.0, 40.0));
        vars.add(IloNumVar(env));
        vars.add(IloNumVar(env));
        
        // 加入目标函数和约束
        model.add(IloMaximize(env, vars[0] + 1*vars[1] + 3*vars[2]));
        model.add(-vars[0] + vars[1] + vars[2] <= 20);
        model.add(vars[0] - 3*vars[1] + vars[2] <= 30);
        
        // 求解
        IloCplex cplex(model);
        if (!cplex.solve()) {
            env.error() << "Failed to optimize LP." << endl;
            throw(-1);
        }
        
        // 输出结果
        IloNumArray vals(env);
        env.out() << "Solution status = " << cplex.getStatus() << endl;
        env.out() << "Solution value = " << cplex.getObjValue() << endl;
        cplex.getValues(vals, vars);
        env.out() << "Values = " << vals << endl;
    }
    catch (IloException &e) {
        cerr << "Concert exception caught: " << e << endl;
    }
    env.end();
    return 0;
}

Gurobi

基本信息
- Gurobi 是另一个用起来非常方便的优化计算软件
- 可以求解大规模线性问题、二次型问题和混合整数线性和二次型问题
- 支持的问题类型不如 CPLEX 多
- 新版本在操作上有很多提升，提供了方便轻巧的接口
- 支持 C++, Java, Python, .Net, Matlab 和 R
- 内存消耗少
特点
- 增加了 Python 对于矩阵操作的接口
- 对于混合整数模型增加了多场景的实验分析，观察特定数据的敏感度
- 丰富了变量和约束的下标操作
- 支持优化过程中间输出结果到文件中
Gurobi 9.0（2019 年）的新特性
- 向非凸非线性优化迈出的重要第一步
- 对于二次规划，在增加了对双线性形式（bilinear objective function）支持之后，可求解任何形式的二次型约束和目标，不论是否是半正定
- 增加了一类新的约束表达形式，Gurobi 称之为广义函数约束
- 函数形式可以是高阶多项式、对数、指数、三角函数等非线性函数
- Gurobi 会对这些函数自动分段线性化进行近似，用户可以通过参数来平衡近似的精度和速度
- 这大大扩展了 Gurobi 求解器的适用范围
使用示例（MATLAB 风格）
```
model.obj = ones(1, 24);
model.obj = [0.6 0.8 0.2 0.4 0.8 0.6 0.4 0.2 0.6 0.4 0.8 0.2 0.4 ...
             0.6 0.2 0.8 0.25 0.25 0.3 0.2 0.25 0.25 0.25 0.25];
model.modelsense = 'Max';
model.rhs = [1 1 1 2 2 1 1 2 2 1 1];
model.sense = ['=' '=' '=' '<' '<' '<' '<' '<' '<'];
model.vtype = 'B';
result = gurobi(model);
disp(result.objval);
disp(result.x);
[row, col] = find(result.x ~= 0);
```
CPLEX 和 Gurobi 的创始人
- 1987 年共同创立了 CPLEX Optimization, Inc.
- 1997 年 CPLEX 被 ILOG Inc. 收购；2009 年 1 月 ILOG Inc. 被 IBM 公司收购
- 2008 年与 Ed Rothberg, Zonghao Gu 共同创立 Gurobi
Netlib 测试平台
- Netlib 存储库包含免费提供的软件、文档和数据库
- 由 AT&T Bell Laboratories、田纳西大学和橡树岭国家实验室维护
- 有趣的是，CVX+SDPT3 对于有些问题不能找到正确解
- 测试数据：http://www.netlib.org/lp/data/
国产求解器

杉数求解器（Cardinal Optimizer, COPT）
- 杉数科技自主研发的针对大规模优化问题的高效数学规划求解器套件
- 高效实现了单纯形法和内点法
- 支持所有主流 64 位操作系统：Windows、Linux 和 MacOS
- 提供接口：Python、PuLP、Pyomo、C、C++、C#、Java、AMPL 和 GAMS
- 也支持 ARM64 平台
- 官网：https://www.shanshu.ai/copt/
MindOpt
- 达摩院决策智能实验室自主研发的数学规划求解器套件
- 目前支持单纯形法、内点法、并发法求解线性规划
- 有 C++、Python 版本的 API
- 官网：https://solver.damo.alibaba.com/htmlpages/page#/
测试平台
- 亚利桑那州立大学的 Hans D. Mittelmann 提供了测试平台，方便各种求解软件打榜
- 测试平台：http://plato.asu.edu/
- 基准测试：http://plato.asu.edu/bench.html

# CVX

# CVXOPT

# CVXPY & CVXGEN

# Cplex, Gurobi and Their Competitors

4. 对偶理论

6. 凸优化与SVM