Skip to main content
 首页 » 编程设计

python之我的问题是否适合凸优化,如果适合,如何用 cvxpy 表达

2024年11月24日6tintown

我有一个 m 行和 n 列的标量数组。我有一个 Variable(m) 和一个 Variable(n),我想为其找到解决方案。

这两个变量分别表示需要在列和行上广播的值。

我天真地想把变量写成 Variable((m, 1)) 和 Variable((1, n)),然后把它们加在一起就好像他们是ndarrays。但是,这不起作用,因为不允许广播。

import cvxpy as cp 
import numpy as np 
 
# Problem data. 
m = 3 
n = 4 
np.random.seed(1) 
data = np.random.randn(m, n) 
 
# Construct the problem. 
x = cp.Variable((m, 1)) 
y = cp.Variable((1, n)) 
 
objective = cp.Minimize(cp.sum(cp.abs(x + y + data))) 
# or: 
#objective = cp.Minimize(cp.sum_squares(x + y + data)) 
 
prob = cp.Problem(objective) 
 
result = prob.solve() 
print(x.value) 
print(y.value) 

这在 x + y 表达式上失败:ValueError: Cannot broadcast dimensions (3, 1) (1, 4)。

现在我想知道两件事:

  • 我的问题确实可以使用凸优化来解决吗?
  • 如果是,我如何用 cvxpy 理解的方式表达它?

我对凸优化和 cvxpy 的概念还很陌生,我希望我对我的问题的描述足够好。

请您参考如下方法:

我提议向您展示如何将其表示为线性程序,所以就这样吧。我正在使用 Pyomo,因为我对此比较熟悉,但您可以在 PuLP 中做类似的事情。

要运行它,您需要先安装 Pyomo 和线性程序求解器(如 glpk)。 glpk 应该适用于合理大小的问题,但如果您发现它的求解时间太长,您可以尝试(更快的)商业求解器,如 CPLEX 或 Gurobi。

您可以通过 pip install pyomo 或 conda install -c conda-forge pyomo 安装 Pyomo。您可以从 https://www.gnu.org/software/glpk/ 安装 glpk或者通过 conda install glpk。 (我认为 PuLP 附带了一个内置的 glpk 版本,因此这可能会为您节省一步。)

这是脚本。请注意,这通过为误差的正分量定义一个变量而为负分量定义另一个变量来将绝对误差计算为线性表达式。然后它寻求最小化两者的总和。在这种情况下,求解器将始终将 1 设置为零,因为这是减少误差的一种简单方法,然后另一个将等于绝对误差。

import random 
import pyomo.environ as po 
 
random.seed(1) 
 
# ~50% sparse data set, big enough to populate every row and column 
m = 10   # number of rows 
n = 10   # number of cols 
data = { 
    (r, c): random.random() 
    for r in range(m) 
    for c in range(n) 
    if random.random() >= 0.5 
} 
 
# define a linear program to find vectors 
# x in R^m, y in R^n, such that x[r] + y[c] is close to data[r, c] 
 
# create an optimization model object 
model = po.ConcreteModel() 
 
# create indexes for the rows and columns 
model.ROWS = po.Set(initialize=range(m)) 
model.COLS = po.Set(initialize=range(n)) 
 
# create indexes for the dataset 
model.DATAPOINTS = po.Set(dimen=2, initialize=data.keys()) 
 
# data values 
model.data = po.Param(model.DATAPOINTS, initialize=data) 
 
# create the x and y vectors 
model.X = po.Var(model.ROWS, within=po.NonNegativeReals) 
model.Y = po.Var(model.COLS, within=po.NonNegativeReals) 
 
# create dummy variables to represent errors 
model.ErrUp = po.Var(model.DATAPOINTS, within=po.NonNegativeReals) 
model.ErrDown = po.Var(model.DATAPOINTS, within=po.NonNegativeReals) 
 
# Force the error variables to match the error 
def Calculate_Error_rule(model, r, c): 
    pred = model.X[r] + model.Y[c] 
    err = model.ErrUp[r, c] - model.ErrDown[r, c] 
    return (model.data[r, c] + err == pred) 
model.Calculate_Error = po.Constraint( 
    model.DATAPOINTS, rule=Calculate_Error_rule 
) 
 
# Minimize the total error 
def ClosestMatch_rule(model): 
    return sum( 
        model.ErrUp[r, c] + model.ErrDown[r, c] 
        for (r, c) in model.DATAPOINTS 
    ) 
model.ClosestMatch = po.Objective( 
    rule=ClosestMatch_rule, sense=po.minimize 
) 
 
# Solve the model 
 
# get a solver object 
opt = po.SolverFactory("glpk") 
# solve the model 
# turn off "tee" if you want less verbose output 
results = opt.solve(model, tee=True) 
 
# show solution status 
print(results) 
 
# show verbose description of the model 
model.pprint() 
 
# show X and Y values in the solution 
for r in model.ROWS: 
    print('X[{}]: {}'.format(r, po.value(model.X[r]))) 
for c in model.COLS: 
    print('Y[{}]: {}'.format(c, po.value(model.Y[c]))) 

为了完成这个故事,这里有一个更接近您的原始示例的解决方案。它使用 cvxpy,但使用我的解决方案中的稀疏数据方法。

我不知道用 cvxpy 进行逐元素计算的“官方”方法,但是使用标准的 Python sum 函数和很多单独的 cp 似乎工作正常.abs(...) 计算。

这给出的解决方案比线性程序稍微差一点,但您可以通过调整解决方案容差来解决这个问题。

import cvxpy as cp 
import random 
 
random.seed(1) 
 
# Problem data. 
# ~50% sparse data set 
m = 10   # number of rows 
n = 10   # number of cols 
data = { 
    (i, j): random.random() 
    for i in range(m) 
    for j in range(n) 
    if random.random() >= 0.5 
} 
 
# Construct the problem. 
x = cp.Variable(m) 
y = cp.Variable(n) 
 
objective = cp.Minimize( 
    sum( 
        cp.abs(x[i] + y[j] + data[i, j]) 
        for (i, j) in data.keys() 
    ) 
) 
 
prob = cp.Problem(objective) 
 
result = prob.solve() 
print(x.value) 
print(y.value)