Expressions in the DCP analyzer and quiz are formed from the variables `x, y, z, u, v, w`

, the parameters `a, b, c, d, e, f`

, numerical constants such as `3`

and `-2.44`

, the standard arithmetic operators `+, -, *, /`

, and a library of functions. For simplicity, all expressions are scalar. Some examples are

```
3.69 + b/3
x - 4*u
sqrt(x) - min(u, v - a)
max(2.66 - sqrt(u), square(x + 2*y))
```

Each (sub)expression is flagged as *positive* (non-negative), *negative* (non-positive), or *unknown*.

The signs of larger expressions are determined from the signs of their subexpressions. For example, the sign of the expression `expr1*expr2`

is

- Positive if
`expr1`

and`expr2`

have the same (known) sign. - Negative if
`expr1`

and`expr2`

have opposite (known) signs. - Unknown if either expression has unknown sign.

The sign given to an expression is always correct. But DCP sign analysis may flag an expression as unknown sign when the sign could be figured out through more complex analysis. For instance, `x*x`

is positive but has unknown sign by the rules above.

Each (sub)expression is flagged as one of the following curvatures

Curvature | Meaning |
---|---|

constant | $ f(x) $ independent of $ x $ |

affine | $ f(\theta x + (1-\theta)y) = \theta f(x) + (1-\theta)f(y), \; \forall x, \; y,\; \theta \in [0,1] $ |

convex | $ f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y), \; \forall x, \; y,\; \theta \in [0,1] $ |

concave | $ f(\theta x + (1-\theta)y) \geq \theta f(x) + (1-\theta)f(y), \; \forall x, \; y,\; \theta \in [0,1] $ |

unknown | DCP analysis cannot determine the curvature |

using the curvature rules given below. As with sign analysis, the conclusion is always correct, but the simple analysis can flag expressions as unknown even when they are convex or concave. Note that any constant expression is also affine, and any affine expression is convex and concave.

DCP analysis is based on applying a general composition theorem from convex analysis to each (sub)expression.

$f(expr_1, expr_2, ..., expr_n)$ is convex if $\text{ } f$ is a convex function and for each $expr_{i}$ one of the following conditions holds:

- $f$ is increasing in argument $i$ and $expr_{i}$ is convex.
- $f$ is decreasing in argument $i$ and $expr_{i}$ is concave.
- $expr_{i}$ is affine.

$f(expr_1, expr_2, ..., expr_n)$ is concave if $\text{ } f$ is a concave function and for each $expr_{i}$ one of the following conditions holds:

- $f$ is increasing in argument $i$ and $expr_{i}$ is concave.
- $f$ is decreasing in argument $i$ and $expr_{i}$ is convex.
- $expr_{i}$ is affine.

$f(expr_1, expr_2, ..., expr_n)$ is affine if $\text{ } f$ is an affine function and each $expr_{i}$ is affine.

If none of the three rules apply, the expression $\text{ } f(expr_1, expr_2, ..., expr_n)$ is marked as having unknown curvature.

Whether a function is increasing or decreasing in an argument may depend on the sign of the argument. For instance, `square`

is increasing for positive arguments and decreasing for negative arguments.

The infix operators `+, -, *, /`

are treated exactly like functions. The infix operators `+`

and `-`

are affine, so the rules above are used to flag the curvature. For example, `expr1 + expr2`

is flagged as convex if `expr1`

and `expr2`

are convex.

`expr1*expr2`

is allowed only when one of the expressions is constant. `expr1/expr2`

is allowed only when `expr2`

is constant. The curvature rules above apply. For example, `expr1/expr2`

is convex when `expr1`

is concave and `expr2`

is negative and constant.

DCP analysis breaks expressions down into subexpressions. The tree visualization below shows how this works for the expression `2*square(x) + 3`

. Each subexpression is shown in a blue box. We mark its curvature on the left and its sign on the right.

We'll walk through the application of the DCP rules to the expression `sqrt(1 + square(x))`

.

The variable `x`

has affine curvature and unknown sign. The `square`

function is convex and non-monotone for arguments of unknown sign. It can take the affine expression `x`

as an argument; the result `square(x)`

is convex.

The arithmetic operator `+`

is affine and increasing, so the composition `1 + square(x)`

is convex by the curvature rule for convex functions. The `sqrt`

function is concave and increasing, which means it can only take a concave argument. Since `1 + square(x)`

is convex, `sqrt(1 + square(x))`

violates the DCP rules and cannot be verified as convex.

In fact, `sqrt(1 + square(x))`

is a convex function of `x`

, but the DCP rules are not able to verify convexity. If the expression is written as `norm2(1, x)`

, the L2 norm of the vector $[1,x]$, which has the same value as `sqrt(1 + square(x))`

, then it will be certified as convex using the DCP rules.