标准准凸规划

标准准凸规划（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) ）。