在 cvxpy 中指定约束时违反了 DCP 要求，可能需要重新考虑问题的整个表述 [英] DCP requirement violated when specifying constraing in cvxpy, perhaps need to rethink entire formulation of problem

问题描述

这是对早期

我已将其表述为整数线性优化问题，并在其中扩展了所有变量.有两个主要问题:

1. 约束 8 违反了 DCP 规则.约束 8 旨在使集群中包含的值保持在特定阈值以上.我通过取非零变量的平均值来检查这一点.
2. 实际问题需要指定数千个变量和约束(有 100 个类别和 >10K 家公司).这让我怀疑这是否是正确的方法.

将 numpy 导入为 np将 cvxpy 导入为 cp导入cvxoptutil = np.array([0.7, 0.95, 0.3, 2, 1.05, 2.2, 4, 1, 3])# 我们正在求解的变量dec_vars = cp.Variable(len(util), boolean = True)tot_util = util @ dec_varsis_zero_bucket1= cp.Variable(1, boolean = True)is_zero_bucket2= cp.Variable(1, boolean = True)is_zero_bucket3= cp.Variable(1, boolean = True)is_zero_cat1 = cp.Variable(1, boolean=True)is_zero_cat2 = cp.Variable(1, boolean=True)is_zero_cat3 = cp.Variable(1, boolean=True)# 给定公司至少应包含 2 个类别constr1 = sum(dec_vars[0:3]) >= 2 * is_zero_bucket1constr2 = sum(dec_vars[3:6]) >= 2 * is_zero_bucket2constr3 = sum(dec_vars[6:9]) >= 2 * is_zero_bucket3# 对于选定的给定类别，至少有 2 列(公司)constr4 = dec_vars[0] + dec_vars[3] + dec_vars[6] >= 2 * is_zero_cat1constr5 = dec_vars[1] + dec_vars[4] + dec_vars[7] >= 2 * is_zero_cat2constr6 = dec_vars[2] + dec_vars[5] + dec_vars[8] >= 2 * is_zero_cat3constr7 = np.ones(len(util)) @dec_vars >= 2constr8 = (tot_util/cp.sum(dec_vars)) >= 1.3cluster_problem = cp.Problem(cp.Maximize(tot_util)，[constr1，constr2，constr3，constr4，constr5，constr6，constr8])cluster_problem.solve()

更新

我按照建议进行了修改.现在的问题是决策变量矩阵本身没有包含相邻公司/类别的规则.为此，我可以使目标函数成为最终决策 vars 矩阵与 zero_comp_vars 和 zero_cat_vars 向量的乘积.但是，当我这样做时，遇到问题不遵循 DCP 规则 错误.一定是因为两个矩阵乘以两个向量.另外，我想知道是否有办法让程序在决策矩阵中适当位置的变量不满足至少 2 家公司和 3 个类别为非零的标准时将其归零，以便被包括在内.就目前而言，决策变量矩阵对于实际上由 zero_comp_vars 和 zero_cat_vars 变量清零的行/列将具有 1

util = np.array([[0.7, 0.95, 0.3], [2, 1.05, 2.2], [4, 1, 3]])# 我们正在求解的变量dec_vars = cp.Variable(util.shape, boolean = True)zero_comp_vars = cp.Variable(util.shape[0], boolean = True)zero_cat_vars = cp.Variable(util.shape[1], boolean = True)# 定义约束zero_comp_constr = cp.sum(dec_vars,axis=1) >= 2 * zero_comp_varszero_cat_constr = cp.sum(dec_vars,axis=0) >= 3 * zero_cat_vars# 需要以下两个约束，否则 zero_comp_constr 和 zero_cat_constr 向量中的所有值都可以为 0above_one_non_zero_comp = cp.sum(zero_comp_vars) >= 1above_one_non_zero_cat = cp.sum(zero_cat_vars) >= 1# 最小锡阵列min_comp_array=np.empty(dec_vars.shape[0])min_comp_array.fill(2)min_comp_constr = cp.sum(dec_vars,axis=1) >= min_comp_arraytot_avg_constr = tot_util >= 2.0 * cp.sum(dec_vars)# 这是出错的部分temp = cp.multiply(util, dec_vars)temp2 = cp.multiply(temp, cp.reshape(zero_comp_vars, (3,1)))temp3 = cp.multiply(temp2, cp.reshape(zero_cat_vars, (3,1)))tot_util = cp.sum(temp3)#tot_util = cp.sum(cp.multiply(util, dec_vars))cluster_problem = cp.Problem(cp.Maximize(tot_util), [zero_comp_constr, zero_cat_constr,above_one_non_zero_comp、above_one_non_zero_cat、min_comp_constr, tot_avg_constr])cluster_problem.solve()

解决方案

只需转换一下:

constr8 = (tot_util/cp.sum(dec_vars)) >= 1.3->constr8 = tot_util >= 1.3 * cp.sum(dec_vars)

您可能需要强制 cp.sum(dec_vars) 为正数，否则:0 >= 0 是一个有效的解决方案.

另见:lpsolve 文档:比率

旁注

是的，您的目标是使用通用优化工具处理机器学习规模数据，这些工具会很快达到极限，即使是纯连续的情况也是如此.在您的情况下，使用离散优化，您可能会遇到可扩展性问题(听起来像 100 万个二进制变量)，尤其是在仅限于开源求解器的情况下.

This is a follow-up to an earlier specific question, but as I add more complexity to the problem formulation, I realize that I need to take a step back and consider whether cvxpy is the best tool for my problem.

What I'm trying to solve: create the largest cluster of a category and company where the average values are above a particular threshold. The trick is that if we include particular categories for a company in the cluster, in order to add another company, that company also should have high values for the same categories.

I've formulated this as an integer linear optimization problem, where I've expanded out all the variables. There are 2 main problems:

1. Constraint 8 violates the DCP rule. Constraint 8 is intended to keep the values included in the cluster above a particular threshold. I check this by taking the average of the non-zero variables.
2. The actual problem will require thousands of variables and constraints to be specified (there are 100 categories and >10K companies). This makes me question whether this is the correct approach at all.

import numpy as np
import cvxpy as cp
import cvxopt 

util = np.array([0.7, 0.95, 0.3, 2, 1.05, 2.2, 4, 1, 3])

# The variable we are solving for
dec_vars = cp.Variable(len(util), boolean = True)

tot_util = util @ dec_vars

is_zero_bucket1= cp.Variable(1, boolean = True)
is_zero_bucket2= cp.Variable(1, boolean = True)
is_zero_bucket3= cp.Variable(1, boolean = True)

is_zero_cat1 = cp.Variable(1, boolean=True)
is_zero_cat2 = cp.Variable(1, boolean=True)
is_zero_cat3 = cp.Variable(1, boolean=True)

# at least 2 categories should be included for a given company
constr1 = sum(dec_vars[0:3]) >= 2 * is_zero_bucket1
constr2 = sum(dec_vars[3:6]) >= 2 * is_zero_bucket2
constr3 = sum(dec_vars[6:9]) >= 2 * is_zero_bucket3

# at least 2 columns (companies) for a given category that's selected
constr4 = dec_vars[0] + dec_vars[3] + dec_vars[6] >= 2 * is_zero_cat1
constr5 = dec_vars[1] + dec_vars[4] + dec_vars[7] >= 2 * is_zero_cat2
constr6 = dec_vars[2] + dec_vars[5] + dec_vars[8] >= 2 * is_zero_cat3

constr7 = np.ones(len(util)) @ dec_vars >= 2

constr8 = (tot_util/cp.sum(dec_vars)) >= 1.3

cluster_problem = cp.Problem(cp.Maximize(tot_util), [constr1, constr2, constr3, constr4, constr5, constr6, constr8])

cluster_problem.solve()

Update

I modified as per the suggestions. The problem now is that the decision variables matrix itself doesn't incorporate the rules for adjacent companies / categories. To do that, I can make the objective function the product of the final decision vars matrix and the zero_comp_vars and zero_cat_vars vectors. However, getting an Problem does not follow DCP rules error when I do this. Must be because of multiplying the 2 matrices by the two vectors. Also, I wonder whether there is a way to get the program to zero out the variables in the appropriate places in the decision matrix when they don't meet the criteria for at least 2 companies and 3 categories to be non-zero in order to be included. As it stands, the decision variables matrix will have 1s for rows/columns that are actually zeroed out by the zero_comp_vars and zero_cat_vars variables

util = np.array([[0.7, 0.95, 0.3], [2, 1.05, 2.2], [4, 1, 3]])

# The variable we are solving for
dec_vars = cp.Variable(util.shape, boolean = True)

zero_comp_vars = cp.Variable(util.shape[0], boolean = True)
zero_cat_vars = cp.Variable(util.shape[1], boolean = True)

# define constraints
zero_comp_constr = cp.sum(dec_vars, axis=1) >= 2 * zero_comp_vars
zero_cat_constr = cp.sum(dec_vars, axis=0) >= 3 * zero_cat_vars
# need the following two constraints, otherwise all the values in the zero_comp_constr and zero_cat_constr vectors can be 0
above_one_non_zero_comp = cp.sum(zero_comp_vars) >= 1
above_one_non_zero_cat = cp.sum(zero_cat_vars) >= 1

# min tin array
min_comp_array=np.empty(dec_vars.shape[0])
min_comp_array.fill(2)

min_comp_constr = cp.sum(dec_vars, axis=1) >= min_comp_array
tot_avg_constr = tot_util >= 2.0 * cp.sum(dec_vars)

# this is the section that gives error
temp = cp.multiply(util, dec_vars)
temp2 = cp.multiply(temp, cp.reshape(zero_comp_vars, (3,1)))
temp3 = cp.multiply(temp2, cp.reshape(zero_cat_vars, (3,1)))

tot_util = cp.sum(temp3)
#tot_util = cp.sum(cp.multiply(util, dec_vars))

cluster_problem = cp.Problem(cp.Maximize(tot_util), [zero_comp_constr, zero_cat_constr, 
                                                     above_one_non_zero_comp, above_one_non_zero_cat,
                                                     min_comp_constr, tot_avg_constr])

cluster_problem.solve()

解决方案

Just transform it:

constr8 = (tot_util/cp.sum(dec_vars)) >= 1.3

->

constr8 = tot_util >= 1.3 * cp.sum(dec_vars)

You might need to enforce that cp.sum(dec_vars) is positive though or else: 0 >= 0 is a valid solution.

See also: lpsolve docs: Ratios

Side-remark

Yes, you are targeting machine-learning scale data with general-purpose optimization tools which will quickly hit a limit, even for pure continuous cases. In your case, using discrete-optimization, you probably will run into scalability issues (sounds like 1M binary-variables), especially when limited to open-source solvers.

这篇关于在 cvxpy 中指定约束时违反了 DCP 要求，可能需要重新考虑问题的整个表述的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！