本项目为 2023 年PKU秋季学期【最优化方法】课程的编程作业
相关的课程信息链接如下：课程页面、作业描述、提交要求，后两个文件在项目 /doc 路径下有pdf版本。
本项目实现的算法面向以下问题：
其中
其中
使用以下命令测试所有算法脚本，打印求解情况并绘制目标函数下降曲线：
python Test_group_lasso.py -S all -P结果为
exact_fval=f_u: 0.652304376262884
sparsity_u: 0.099609375
Solver Objective Obj_ABS_Error x_u_Error Time(s) Iter Sparsity
-------------- ----------- --------------- ----------- --------- ------ ----------
cvx_mosek 0.652291 1.36211e-05 3.9124e-05 0.453096 13 0.102539
cvx_gurobi 0.652291 1.33551e-05 3.75525e-05 0.860177 12 0.102539
mosek 0.652301 3.33869e-06 9.84223e-06 0.33137 11 0.0996094
gurobi 0.652291 1.33727e-05 3.97062e-05 0.60077 13 0.103516
SGD_primal 0.652294 1.02855e-05 5.52482e-05 0.63127 1473 0.121094
ProxGD_primal 0.652291 1.36421e-05 3.89562e-05 0.187898 190 0.102539
FProxGD_primal 0.652291 1.36421e-05 3.8964e-05 0.249066 486 0.102539
ALM_dual 0.652308 3.97276e-06 6.83455e-05 0.303512 70 0.0996094
ADMM_dual 0.652309 4.80892e-06 6.84793e-05 0.0626595 86 0.0996094
ADMM_primal 0.652291 1.34764e-05 3.8987e-05 0.46301 2694 0.102539
不知道如何使用测试脚本？可以使用 python Test_group_lasso.py -h 查看帮助信息：
usage: Test_group_lasso [-h] [--solvers SOLVERS [SOLVERS ...]] [--seed SEED] [--plot] [--log {DEBUG,INFO,WARNING,ERROR,CRITICAL}] [--opts OPTS [OPTS ...]] [--compare] [--version] [--printDefaultOpts]
测试不同的求解器进行group-lasso求解 https://github.com/AkexStar/Algorithms-group-LASSO-problem
optional arguments:
-h, --help show this help message and exit
--version, -V show program's version number and exit
--solvers SOLVERS [SOLVERS ...], -S SOLVERS [SOLVERS ...]
指定求解器名称, 输入`all` 可以测试本项目中所有的求解器函数。默认填充为 `['gl_cvx_gurobi', 'gl_cvx_mosek']` 这两个求解器。
--seed SEED, -RS SEED
指定测试数据的随机数种子。默认为97108120，为 `alx` 的ASCII码依次排列。
--plot, -P 表明是否绘制迭代曲线，如果增加此参数，则绘制。
--log {DEBUG,INFO,WARNING,ERROR,CRITICAL}, -L {DEBUG,INFO,WARNING,ERROR,CRITICAL}
指定日志等级。默认为INFO。
--opts OPTS [OPTS ...], -O OPTS [OPTS ...]
指定测试数据的参数，格式为`key=value`，可以有多个。例如 `-O gl_ALM_dual={'maxit':60, 'maxit_inn':100} testData={'m'=256, 'n':512}` 。没有指定的参数将使用默认值。
--compare, -C 表明是否将计算得到的最优解与mosek和gurobi的结果比较，如果增加此参数，则比较。
--printDefaultOpts, -PDO
展示所有默认opts参数。不知道测试脚本的 --opts 如何使用？可指定的参数有哪些？默认参数值是多少？可以使用 python Test_group_lasso.py -PDO 打印所有可设定参数和其默认值：
testData: {'seed': 97108120, 'mu': 0.01, 'n': 512, 'm': 256, 'l': 2, 'r': 0.1}
gl_SGD_primal: {'maxit': 50, 'maxit_inn': 250, 'ftol': 1e-09, 'ftol_init_ratio': 1000000.0, 'etaf': 0.1, 'gtol': 1e-06, 'gtol_init_ratio': 1000000.0, 'etag': 0.1, 'factor': 0.1, 'mu1': 10.0, 'is_only_print_outer': False, 'method': None, 'gamma': 0.9, 'rhols': 1e-06, 'eta': 0.2, 'Q': 1.0}
gl_ProxGD_primal: {'maxit': 50, 'maxit_inn': 250, 'ftol': 1e-09, 'ftol_init_ratio': 1000000.0, 'etaf': 0.1, 'gtol': 1e-06, 'gtol_init_ratio': 1000000.0, 'etag': 0.1, 'factor': 0.1, 'mu1': 10.0, 'is_only_print_outer': False, 'method': None, 'gamma': 0.85, 'rhols': 1e-06, 'eta': 0.2, 'Q': 1.0}
gl_FProxGD_primal: {'maxit': 50, 'maxit_inn': 250, 'ftol': 1e-09, 'ftol_init_ratio': 1000000.0, 'etaf': 0.1, 'gtol': 1e-06, 'gtol_init_ratio': 1000000.0, 'etag': 0.1, 'factor': 0.1, 'mu1': 10.0, 'is_only_print_outer': False, 'method': None, 'gamma': 0.85, 'rhols': 1e-06, 'eta': 0.2, 'Q': 1.0}
gl_ALM_dual: {'sigma': 10, 'maxit': 100, 'maxit_inn': 300, 'thre': 1e-06, 'thre_inn': 0.001}
gl_ADMM_dual: {'sigma': 10, 'maxit': 1000, 'thre': 1e-06}
gl_ADMM_primal: {'sigma': 10, 'maxit': 3000, 'thre': 1e-06}如果要进行调试，在使用vs code时建议使用以下配置 launch.json：
{
"configurations": [
{
"name": "Python: Current File",
"type": "python",
"request": "launch",
"stopOnEntry": false,
"python": "${command:python.interpreterPath}",
"program": "${file}",
"cwd": "${workspaceRoot}",
"env": {
"PYTHONPATH": "${workspaceRoot}"
},
}
]
}在本项目中，每个求解器的脚本名与函数名相同，脚本名称均为 gl_*.py 格式，函数名称均为 gl_*() 格式。一个样例函数接口形式如下：
[x, iter, out] = gl_solver_name(x0, A, b, mu, opts)输入分别为给定的初始解 x0 ，而 A 、 b 、 mu 是给定的数据。
opts 是用来指定求解器内部参数的字典变量。其根据不同的求解器可填入不同的指定参数。参数种类和默认参数值可见文件utils.py中各个 solver_name_optsInit() 函数。
输出 x 为算法求解出的解，iter 为输出为 x 时所对应的算法迭代次数。 out 为算法输出的其他信息，是一个字典结构，包含以下内容：
out['fval']为算法求解出的目标函数值。out['iters']为算法每一步迭代的目标函数值与迭代号的zip组合列表。- 上述两项为调用mosek和gurobi的输出信息，主要从求解器的日志输出中用正则表达式爬取。而自行编写的求解器则除上述两项外具有更多记录信息。
如果想只测试某个算法函数，可参考以下代码：
import src.utils as utils
dataOpts = {} # 指定生成测试数据的参数 正则化系数mu 随机数种子seed 矩阵大小m n l 非零元素占比r
# dataOpts = {'mu':0.01, 'seed':2333, 'm':256, 'n':512, 'l':2, 'r':0.1}
x0, A, b, mu, u, f_u = utils.testData(dataOpts) # 得到测试数据
solver_opts = {} # 求解算法参数
solver_opts['solver_name'] = 'gl_ALM_dual' # 指定使用哪个求解算法
x, iters_N, out = utils.testSolver(x0, A, b, mu, solver_opts)或直接调用某个算法函数：
import src.utils as utils
from src.gl_ALM_dual import *
x0, A, b, mu, u, f_u = utils.testData({})
x, iter, out = gl_ALM_dual(x0, A, b, mu, {})ALGORITHMS-GROUP-LASSO-PROBLEM
│ .gitignore
│ README.md
│ report.ipynb
│ requirements.txt
│ Test_group_lasso.py
│
├─doc
│ homework-description.pdf
│ homework-requirement.pdf
│
└─src
gl_ADMM_dual.py
gl_ADMM_primal.py
gl_ALM_dual.py
gl_cvx_gurobi.py
gl_cvx_mosek.py
gl_FGD_primal.py
gl_FProxGD_primal.py
gl_GD_primal.py
gl_gurobi.py
gl_mosek.py
gl_ProxGD_primal.py
gl_SGD_primal.py
utils.py
__init__.py| Name | Version |
|---|---|
| Windows | 11+.0(22631.2) |
| python | 3.9.18 |
| pip | 23.3.1 |
| cvxpy | 1.4.1 |
| gurobipy | 11.0.0 |
| Mosek | 10.1.21 |
| matplotlib | 3.8.2 |
| numpy | 1.26.2 |
| tabulate | 0.9.0 |
本项目使用 conda 管理环境，使用 conda create -n glp python=3.9 创建环境，使用 conda activate glp 激活环境，使用 conda deactivate 退出环境。
项目可以使用 conda 或者 pip 安装各项依赖包，但是其中 mosek 和 gurobipy 需要配置许可证书，具体方法参考官方文档【Mosek installation】和【gurobipy installation】。
- [1] repo: group-lasso-optimization
- [2] 课程提供的 Matlab 代码样例
- [3] CVXPY 说明文档
- [4] python logging 说明文档
- [5] CVXPY stdout 输出重定向方法
- [6] python 正则表达式说明文档
- [7] matplotlib 说明文档
- 感谢 @wenzw 老师提供的课程资料，本项目的部分函数实现参考了其内容。
- 感谢 @gzz2000 公开的代码样例，本项目部分函数的实现参考了其内容。
- 感谢 @zhangzhao2022 提供的支持，本项目的部分函数实现受到其指导帮助。
- 感谢 @cvxgrp 提供的 CVXPY 优化库，本项目使用了其提供的接口。