# Discplined Convex Programming

Disciplined convex programming (DCP) is a system for constructing
mathematical expressions with known curvature from a given library of
base functions. `CVXR`

uses DCP to ensure that the specified
optimization problems are convex.

This section of the tutorial explains the rules of DCP and how they
are applied by `CVXR`

.

Visit dcp.stanford.edu for a more interactive introduction to DCP.

## Expressions

Expressions in `CVXR`

are formed from variables, numerical
constants such as R vectors and matrices, the standard
arithmetic operators `+, -, *, %*%, /`

, and a library
of functions. Here are some examples of
`CVXR`

expressions:

```
suppressWarnings(suppressMessages(library(CVXR)))
## Create variables.
x <- Variable()
y <- Variable()
## Examples of cvxr expressions.
3.69 + x / 3
```

`## AddExpression(c("Expression(AFFINE, UNKNOWN, 1)", "Expression(AFFINE, UNKNOWN, 1)"), Constant(CONSTANT, POSITIVE, (1,1)))`

`x - 4 * y`

`## AddExpression(Variable(1, 1), c("Expression(AFFINE, UNKNOWN, 1)", "Expression(AFFINE, UNKNOWN, 1)"))`

`sqrt(x) - min_elemwise(y, x - 2.5)`

`## AddExpression(c("Expression(CONCAVE, POSITIVE, 1)", "Expression(CONCAVE, POSITIVE, 1)"), c("Expression(CONVEX, UNKNOWN, 1)", "Expression(CONVEX, UNKNOWN, 1)"))`

`max_elemwise(2.66 - sqrt(y), abs(x + 2 * y))`

`## MaxElemwise(c("Expression(CONVEX, UNKNOWN, 1)", "Expression(CONVEX, UNKNOWN, 1)"), c("Expression(CONVEX, POSITIVE, 1)", "Expression(CONVEX, POSITIVE, 1)"))`

Expressions can be scalars, vectors, or matrices. The dimensions of an
expression can be obtained using the function `size`

. `CVXR`

will
raise an exception if an expression is used in a way that doesn’t make
sense given its dimensions, e.g. adding matrices of different
sizes.

```
Z <- Variable(5, 4)
A <- matrix(1, nrow = 2, ncol = 5)
## Use size to get the dimensions.
cat("dimensions of Z:", size(Z), "\n")
```

`## dimensions of Z: 5 4`

`cat("dimensions of sum_entries(Z):", size(sum_entries(Z)), "\n")`

`## dimensions of sum_entries(Z): 1 1`

`cat("dimensions of A %*% Z:", size(A %*% Z), "\n")`

`## dimensions of A %*% Z: 2 4`

Error raised for invalid dimensions.

`tryCatch(A + Z, error = function(e) geterrmessage())`

`## [1] "Incompatible dimensions"`

`CVXR`

uses DCP analysis to determine the sign and curvature of each
expression.

## Sign

Each (sub)expression is flagged as *positive* (non-negative), *negative*
(non-positive), *zero*, 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

- Zero if either expression has sign zero.
- 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. However, 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.

`CVXR`

determines the sign of constants by looking at their value. For
scalar constants, this is straightforward. Vector and matrix constants
with all positive (negative) entries are marked as positive
(negative). Vector and matrix constants with both positive and
negative entries are marked as unknown sign.

The sign of an expression is obtained via the `sign`

function:

```
x <- Variable()
a <- Constant(-1)
c <- matrix(c(1, -1), ncol = 1)
cat("sign of x:", sign(x), "\n")
```

`## sign of x: UNKNOWN`

`cat("sign of a:", sign(a), "\n")`

`## sign of a: NEGATIVE`

`cat("sign of abs(x):", sign(abs(x)), "\n")`

`## sign of abs(x): POSITIVE`

`cat("sign of c*a:", sign(c * a), "\n")`

`## sign of c*a: UNKNOWN`

## Curvature

Each (sub)expression is flagged as one of the following curvatures (with respect to its variables)

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.

## Curvature rules

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

\(f(e_1, e_2, \ldots, e_n)\) is convex if \(f\) is a convex function and for each \(e_{i}\), one of the following conditions holds:

- \(f\) is increasing in argument \(i\) and \(e_i\) is convex.
- \(f\) is decreasing in argument \(i\) and \(e_i\) is concave.
- \(e_i\) is affine or constant.

\(f(e_1, e_2,\ldots, e_n)\) is concave if \(f\) is a concave function and for each \(e_i\) one of the following conditions holds:

- \(f\) is increasing in argument \(i\) and \(e_i\) is concave.
- \(f\) is decreasing in argument \(i\) and \(e_i\) is convex.
- \(e_i\) is affine or constant.

\(f(e_1, e_2, \ldots, e_n)\) is affine if \(f\) is an affine function and each \(e_i\) is affine.

If none of the three rules apply, the expression \(f(e_1, e_2,\ldots, e_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, `abs`

is increasing for
positive arguments and decreasing for negative arguments.

The curvature of an expression is determined using the `curvature`

function:

```
x <- Variable()
a <- Constant(5)
cat("curvature of x:", curvature(x), "\n")
```

`## curvature of x: AFFINE`

`cat("curvature of a:", curvature(a), "\n")`

`## curvature of a: CONSTANT`

`cat("curvature of abs(x):", curvature(abs(x)), "\n")`

`## curvature of abs(x): CONVEX`

`cat("curvature of sqrt(x):", curvature(sqrt(x)), "\n")`

`## curvature of sqrt(x): CONCAVE`

## Infix operators

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`

and `expr1 %*% expr2`

are allowed only when one of the expressions is constant.
If both expressions are non-constant, `CVXR`

will raise an exception.
`expr1/expr2`

is allowed only when `expr2`

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

is convex when
`expr1`

is concave and `expr2`

is negative and constant.

### Example 1

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

. Here `square`

is synonymous with squaring each element of the input `x`

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

### Example 2

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 function `sqrt`

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 `p_norm(vstack(1, x), 2)`

, 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.

`cat("sqrt(1 + square(x)) curvature:", curvature(sqrt(1 + square(x))), "\n")`

`## sqrt(1 + square(x)) curvature: UNKNOWN`

`cat("p_norm(vstack(1, x), 2) curvature:", curvature(p_norm(vstack(1, x), 2)), "\n")`

`## p_norm(vstack(1, x), 2) curvature: CONVEX`

## DCP problems

A problem is constructed from an objective and a list of constraints. If
a problem follows the DCP rules, it is guaranteed to be convex and
solvable by `CVXR`

. The DCP rules require that the problem objective have
one of two forms:

- Minimize(convex)
- Maximize(concave)

The only valid constraints under the DCP rules are

- affine == affine
- convex <= concave
- concave >= convex

You can check that a problem, constraint, or objective satisfies the DCP
rules by calling `is_dcp(object)`

. Here are some examples of DCP and
non-DCP problems:

```
x <- Variable()
y <- Variable()
## DCP problems.
prob1 <- Problem(Minimize((x - y)^2), list(x + y >= 0))
prob2 <- Problem(Maximize(sqrt(x - y)),
list(2 * x - 3 == y,
x^2 <= 2))
cat("prob1 is DCP:", is_dcp(prob1), "\n")
```

`## prob1 is DCP: TRUE`

`cat("prob2 is DCP:", is_dcp(prob2), "\n")`

`## prob2 is DCP: TRUE`

```
## Non-DCP problems.
## A non-DCP objective.
prob3 <- Problem(Maximize(x^2))
cat("prob3 is DCP:", is_dcp(prob3), "\n")
```

`## prob3 is DCP: FALSE`

`cat("Maximize(x^2) is DCP:", is_dcp(Maximize(x^2)), "\n")`

`## Maximize(x^2) is DCP: FALSE`

```
## A non-DCP constraint.
prob4 <- Problem(Minimize(x^2), list(sqrt(x) <= 2))
cat("prob4 is DCP:", is_dcp(prob4), "\n")
```

`## prob4 is DCP: FALSE`

`cat("sqrt(x) <= 2 is DCP:", is_dcp(sqrt(x) <= 2), "\n")`

`## sqrt(x) <= 2 is DCP: FALSE`

`CVXR`

will raise an exception if you call `solve()`

on a non-DCP
problem.

```
## A non-DCP problem.
prob <- Problem(Minimize(sqrt(x)))
tryCatch(solve(prob), error = function(e) geterrmessage())
```

`## [1] "Problem does not follow DCP rules."`

## Session Info

`sessionInfo()`

```
## R version 3.6.0 (2019-04-26)
## Platform: x86_64-apple-darwin18.5.0 (64-bit)
## Running under: macOS Mojave 10.14.5
##
## Matrix products: default
## BLAS/LAPACK: /usr/local/Cellar/openblas/0.3.6_1/lib/libopenblasp-r0.3.6.dylib
##
## locale:
## [1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8
##
## attached base packages:
## [1] stats graphics grDevices datasets utils methods base
##
## other attached packages:
## [1] kableExtra_1.1.0 CVXR_0.99-6
##
## loaded via a namespace (and not attached):
## [1] gmp_0.5-13.5 Rcpp_1.0.1 highr_0.8
## [4] compiler_3.6.0 pillar_1.4.1 R.methodsS3_1.7.1
## [7] R.utils_2.8.0 tools_3.6.0 digest_0.6.19
## [10] bit_1.1-14 viridisLite_0.3.0 evaluate_0.14
## [13] tibble_2.1.2 lattice_0.20-38 pkgconfig_2.0.2
## [16] rlang_0.3.4 Matrix_1.2-17 rstudioapi_0.10
## [19] yaml_2.2.0 blogdown_0.12.1 xfun_0.7
## [22] xml2_1.2.0 httr_1.4.0 Rmpfr_0.7-2
## [25] ECOSolveR_0.5.2 stringr_1.4.0 knitr_1.23
## [28] hms_0.4.2 webshot_0.5.1 bit64_0.9-7
## [31] grid_3.6.0 glue_1.3.1 R6_2.4.0
## [34] rmarkdown_1.13 bookdown_0.11 readr_1.3.1
## [37] magrittr_1.5 scales_1.0.0 htmltools_0.3.6
## [40] scs_1.2-3 rvest_0.3.4 colorspace_1.4-1
## [43] stringi_1.4.3 munsell_0.5.0 crayon_1.3.4
## [46] R.oo_1.22.0
```