标准准凸规划

标准准凸规划(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/yx 上是增加的,在 y 上是增加的;当 x 非正时,比率 x/yx 上是减小的,在 y 上是减小的。

比率原子可以与组合规则一起使用,构建有趣的准凸和准凹表达式。例如,非负凹函数和正凸函数的比率是准凹的,非负凸函数和正凹函数的比率是准凸的。类似地,当分母为正时,两个仿射函数的比率是准线性的。

标量积。 标量积 * 在其中一个参数为非负,另一个参数为非正时是准凸的,并且当它的两个参数都是非负或都是非正时,它是准凹的。因此,根据组合规则,两个非负凹函数的乘积是准凹的,非负凹函数和非正凸函数的乘积是准凸的。

距离比例函数。 原子 cvxpy.dist_ratio(x, a, b) 表示函数 \(\|x - a\|_2 / \|x - b\|_2\) ,隐式地强制约束 \(\|x - a\|_2 \leq \|x - b\|_2\) 。表达式 ab 必须是常量。这个原子是准凸的。

最大广义特征值。 原子 cvxpy.gen_lambda_max(A, B) 计算 AB 的最大广义特征值,定义为最大的 \(\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问题时,您可以选择自己提供上下界,这在某些情况下可能非常有用。 您可以通过关键字参数 lowhigh 来提供这些边界;例如, 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) )。