标准准凸规划
标准准凸规划(DQCP)是凸规划(DCP)的一般化,用于准凸函数。准凸性是凸性的一般化:一个函数 \(f\) 是准凸的,当且仅当它的定义域是一个凸集,且它的子水平集 \(\{x : f(x) \leq t\}\) 对于所有 \(t\) 都是凸的。对于准凸性的详细介绍,请参阅论文 Disciplined quasiconvex programming 。
虽然DCP是用于构造凸规划的规则集,但DQCP是用于准凸规划(QCP)的规则集,其中目标是在凸集上最小化准凸函数。凸集可以使用仿射函数的等式以及凸和凹函数的不等式来指定,就像在DCP中一样;此外,DQCP允许形式为 \(f(x) \leq t\) 的不等式,其中 f(x) 是准凸表达式,\(t\) 是常数,以及形式为 \(f(x) \geq t\) 的不等式,其中 f(x) 是准凹的,\(t\) 是常数。每个标准凸规划都是一个标准准凸规划,但反过来则不成立。
CVXPY允许您构建和求解DQCP问题,就像对DCP问题一样。例如,以下代码解决了一个简单的QCP问题,
import cvxpy as cp
x = cp.Variable()
y = cp.Variable(pos=True)
objective_fn = -cp.sqrt(x) / y
problem = cp.Problem(cp.Minimize(objective_fn), [cp.exp(x) <= y])
problem.solve(qcp=True)
assert problem.is_dqcp()
print("Optimal value: ", problem.value)
print("x: ", x.value)
print("y: ", y.value)
并且它输出以下结果。
Optimal value: -0.4288821220397949
x: 0.49999737143004713
y: 1.648717724845007
要解决DQCP问题,您必须在 solve()
方法中传递选项 qcp=True
。
本节将解释DQCP是什么,并展示如何使用CVXPY构建和解决DQCP问题。本节的最后是列出可以在DQCP问题中使用的所有原子的表格,类似于在 DCP原子 一节中介绍的表格。
有关DQCP的详细参考,请参阅我们的 附带论文 。要获取交互式代码示例,请查看我们的 notebooks 。
注意:DQCP是CVXPY的最新添加功能。如果您有反馈,请在 Github 上提交问题或发起拉取请求。
曲率
DQCP为CVXPY添加了两种新的曲率类型:凸性和凹性。如果函数 \(f\) 的定义域是一个凸集,并且对于所有 \(t\),其子水平集 \(\{x : f(x) \leq t\}\) 都是凸集,则 \(f\) 是凸函数;如果 \(-f\) 是凸函数,则 \(f\) 是凹函数。每个凸函数也是凸函数,每个凹函数也是凹函数;这些陈述的逆命题是不成立的。一个既是凸函数又是凹函数的表达式称为准线性函数。
CVXPY的曲率分析可以标记表达式为未知,即使它们是凸函数或凹函数,但它永远不会错误地标记表达式为凸函数或凹函数。
表达式的曲率存储在其 .curvature
属性中。例如,运行以下脚本:
import cvxpy as cp
x = cp.Variable(3)
y = cp.length(x)
z = -y
print(y.curvature)
print(z.curvature)
w = cp.ceil(x)
print(w.curvature)
输出如下结果
QUASICONVEX
QUASICONCAVE
QUASILINEAR
你还可以通过调用 is_quasiconvex() 和 is_quasiconcave() 方法来检查表达式的曲率。例如,y.is_quasiconvex() 和 z.is_quasiconcave() 返回 True 。通过调用 is_quasilinear() 方法可以检查一个表达式是否是拟线性的。
组合规则
DQCP分析基于将凸分析的一般组合定理应用于每个表达式。在DQCP下,一个表达式是可验证的拟凸的,如果它满足以下条件之一:
是凸的(在DCP下);
是一个应用于变量或常数的拟凸原子;
是拟凸表达式的最大值(使用
cvxpy.maximum
函数);是拟凹表达式的递增函数,或者是拟凸表达式的递减函数;
是形如 \(f(e_1, e_2, \ldots, e_n)\) 的表达式,其中 (1) \(f\) 是一个拟凸原子,且 (2) 对于每个 \(i\) ,\(f\) 在第 \(i\) 个参数上是增函数,并且 \(e_i\) 是凸函数,或者 \(f\) 在第 \(i\) 个参数上是减函数,并且 \(e_i\) 是凹函数,或者 \(e_i\) 是线性的。
一个表达式是可验证的拟凹的,如果它满足以下条件之一:
是凹的(在DCP下);
是一个应用于变量或常数的拟凹原子;
是拟凹表达式的最小值(使用 cvxpy.minimum 函数);
是拟凸表达式的递增函数,或者是拟凹表达式的递减函数;
是形如 \(f(e_1, e_2, \ldots, e_n)\) 的表达式,其中 (1) \(f\) 是一个拟凹原子,且 (2) 对于每个 \(i\),\(f\) 在第 \(i\) 个参数上是增函数,并且 \(e_i\) 是凹函数,或者 \(f\) 在第 \(i\) 个参数上是减函数,并且 \(e_i\) 是凸函数,或者 \(e_i\) 是线性的。一个量子凸函数或量子凹函数的原子可能取决于其参数的符号。例如,当`x`和`y`要么都是非负的,要么都是非正的时,标量积 \(xy\) 是量子凹函数;当一个参数是非负的,并且另一个参数是非正的时,标量积是量子凸函数。
如果一个表达式满足上述规则,我们通常说该表达式“is DQCP.”你可以通过调用方法 is_dqcp()
来检查一个表达式是否是DQCP。例如,下面代码块中的断言将通过。
import cvxpy as cp
x = cp.Variable(pos=True)
y = cp.Variable(pos=True)
product = cp.multiply(x, y)
assert product.is_quasiconcave()
assert product.is_dqcp()
当一个表达式具有已知曲率时,它被认为是DQCP精确地意味着至少有一个方法 is_constant()
,is_affine()
, is_convex()
, is_concave()
, is_quasiconvex()
, is_quasiconcave()
将返回 True
。
DQCP问题
一个 Problem
由一个目标和一列约束构建。如果一个问题符合DQCP规则,它保证是一个DQCP问题,并且可以通过CVXPY解决(如果问题存在解)。
DQCP规则要求问题的目标具有以下两种形式之一:
最小化(quasiconvex)
最大化(quasiconcave)
符合DQCP规则的唯一有效约束条件是:
affine == affine
convex <= concave
concave >= convex
quasiconvex <= constant
quasiconcave >= constant
您可以通过调用 object.is_dqcp()
来检查问题、约束条件或目标函数是否符合DQCP规则。以下是一些DQCP和非DQCP问题的示例:
import cvxpy as cp
# 变量的符号会影响曲率分析。
x = cp.Variable(nonneg=True)
concave_fractional_fn = x * cp.sqrt(x)
constraint = [cp.ceil(x) <= 10]
problem = cp.Problem(cp.Maximize(concave_fractional_fn), constraint)
assert concave_fractional_fn.is_quasiconcave()
assert constraint[0].is_dqcp()
assert problem.is_dqcp()
w = cp.Variable()
fn = w * cp.sqrt(w)
problem = cp.Problem(cp.Maximize(fn))
assert not fn.is_dqcp()
assert not problem.is_dqcp()
如果在非DQCP问题上调用 problem.solve(qcp=True)
,CVXPY会抛出异常。
DQCP原子
可以使用凸和凹原子构建准凸和准凹表达式,使用上面给出的曲率规则。本节介绍了在DQCP下一些现有原子的新语义,并引入了准凸和准凹(但不是凸和凹)的新原子。其中许多新原子是整数值的。
比率。
运算符 /
是一个原子,表示比率。当分母已知为非负或非正时,这个原子既是准凸的又是准凹的。当 y
非负时,比率 x/y
在 x
上是增加的,在 y
上是增加的;当 x
非正时,比率 x/y
在 x
上是减小的,在 y
上是减小的。
比率原子可以与组合规则一起使用,构建有趣的准凸和准凹表达式。例如,非负凹函数和正凸函数的比率是准凹的,非负凸函数和正凹函数的比率是准凸的。类似地,当分母为正时,两个仿射函数的比率是准线性的。
标量积。
标量积 *
在其中一个参数为非负,另一个参数为非正时是准凸的,并且当它的两个参数都是非负或都是非正时,它是准凹的。因此,根据组合规则,两个非负凹函数的乘积是准凹的,非负凹函数和非正凸函数的乘积是准凸的。
距离比例函数。
原子 cvxpy.dist_ratio(x, a, b)
表示函数 \(\|x - a\|_2 / \|x - b\|_2\) ,隐式地强制约束 \(\|x - a\|_2 \leq \|x - b\|_2\) 。表达式 a
和 b
必须是常量。这个原子是准凸的。
最大广义特征值。
原子 cvxpy.gen_lambda_max(A, B)
计算 A
和 B
的最大广义特征值,定义为最大的 \(\lambda \in \mathbf{R}\) ,满足 \(Ax = \lambda Bx\) (其中 \(x\) 是某个向量)。这个原子是准凸的,并且它强制执行 A
是对称的和 B
是正定的约束。
条件数。
原子 cvxpy.condition_number(A)
计算 A
的条件数,定义为 \(\lambda_{\max}(A) / \lambda_{\min}(A)\) 。
这个原子是准凸的,并且它强制执行 A
是对称的和正定的约束。
向上取整和向下取整。
原子 cvxpy.ceil(x)
和 cvxpy.floor(x)
是准线性的,并且它们的参数是增加的。
符号。
原子 cvxpy.sign(x)
,它对于 x <= 0
返回 -1
,对于 x > 0
返回 +1
,是准线性的。
向量的长度。
cvxpy.length(x)
这个函数会返回向量 \(x \in \mathbf{R}^n\) 中最后一个非零元素的索引,它是拟凸的。
解决DQCP问题
一个DQCP问题 problem
可以通过调用 problem.solve(qcp=True)
来解决。
CVXPY使用二分法求解问题的最优值来解决QCP问题,并且它会自动找到二分法的上界和下界。
在解决QCP问题时,您可以选择自己提供上下界,这在某些情况下可能非常有用。
您可以通过关键字参数 low
和 high
来提供这些边界;例如,
problem.solve(qcp=True, low=12, high=17)
会将二分法限制在大于12且小于17的目标值范围内。
二分法涉及求解一系列的优化问题。如果您的问题病态或者运气不好,求解器可能会在其中一个子问题上失败,从而导致报错。
如果发生这种情况,您可以尝试使用其他求解器通过关键字参数 solver
来解决(例如, problem.solve(qcp=True, solver=cp.SCS)
)。
要获取描述二分法的详细输出,可以将关键字参数 verbose=True
传递给求解方法( problem.solve(qcp=True, verbose=True)
)。