A Cheatsheet on Convex Conjugates
Table of Contents
Convex conjugates play a prominent role in convex optimization. This page gathers several facts regarding conjugate calculus and related formulas.
Notation. Throughout this page, we will denote \( \overline{\mathbb R} = \mathbb R \cup \{ -\infty, +\infty \} \) the extended real number line. For a given function \( f:\mathbb R^n \rightarrow \overline{\mathbb R} \), we let \( \textrm{dom}(f) = \{ \mathbf x\in\mathbb R^n : f(\mathbf x) < +\infty \} \) be the domain of \(f\).
Definition and Basic Properties
Let \( f: \mathbb R^n \rightarrow \overline{\mathbb R} \) be a given function.
(Definition)
The convex conjugate of \( f \) is noted \( f^* \) and is defined as
$$ f^*(\mathbf y) = \sup_{ \mathbf x\in \textrm{dom}(f) } \{ \mathbf y^\top\mathbf x - f(\mathbf x) \} $$
The concave conjugate of \( f \) is noted \( f_* \) and is defined as
$$ f_*(\mathbf y) = \inf_{ \mathbf x\in\textrm{dom}(f) } \{ \mathbf y^\top\mathbf x - f(\mathbf x) \} $$
\textcite[page 104]{Rockafellar_1970}.
(Fenchel inequality)
Let \( f \) be a proper convex function. Then, for any \( \mathbf
x\in\mathbb R^n \) and any \( \mathbf y\in\mathbb R^n \), we have $$
\mathbf y^\top\mathbf x \le f(\mathbf x) + f^*(\mathbf y). $$
\textcite[page 105]{Rockafellar_1970}.
(Convexity)
Let \( f \) be a convex function. Then, \( f^* \) is a closed proper convex
function if and only if \( f \) is proper. Moreover, \( (\text{cl}f)^* = f^* \) and
\( f^{**} = \text{cl} f \).
We recall that a closed convex function is lower semicontinuous.
We recall that a closed convex function is lower semicontinuous.
\textcite[Theorem~12.2]{Rockafellar_1970}.
(Order Reversing)
$$ f \le g \Rightarrow f^* \ge g^* $$
(Double conjugate)
$$ \text{cl}(\text{vex}(f)) = f^{**} \le f $$
Moreover, if \( f = f^{**} \) if and only if it is convex and lower semi-continuous.
(Subgradients)
Asume \( f \) is closed and convex, then $$ \mathbf y \in \partial f(\mathbf x) \Leftrightarrow \mathbf x \in \partial f^*(\mathbf y) \Leftrightarrow \mathbf x^\top\mathbf y = f(\mathbf x) + f^*(\mathbf y). $$
(Strongly convex)
Asume \( f \) is closed and strongly convex with parameter \( \mu > 0 \) for the norm \( ||.|| \), then \( \textrm{dom}(f^*) = \mathbb R^n \). Moreover, \( f^* \) is differentiable everywhere with
$$ \nabla f^*(\mathbf y) = \textrm{argmax} \{ \mathbf y^\top\mathbf x - f(\mathbf x) : \mathbf x \in\mathbb R^n \} $$
and \( \nabla f^*(\mathbf y) \) is \( \frac 1\mu \)-Lipschitz continuous with respect to the dual norm \( ||.||_* \), i.e.,
$$ || \nabla f^*(\mathbf y) - \nabla f^*(\mathbf y') || \le \frac 1\mu || \mathbf y - \mathbf y' ||_*. $$
(Fenchel duality)
Asume \( f \) is proper and convex and let \(g : \mathbb R^n \rightarrow \overline{\mathbb R} \) be a given proper concave function. If the following Slater's conditions hold,
$$ \exists \hat{\mathbf x} \in \textrm{int}(\textrm{dom}(f))\cap\textrm{int}(\textrm{dom}(-g)), $$
then the following equality holds.
$$ \inf_{ \mathbf x\in\textrm{dom}(f)\cap\textrm{dom}(-g) } \{ f(\mathbf x) - g(\mathbf x) \} = \sup_{ \mathbf y\in\textrm{dom}(f^*)\cap\textrm{dom}(-g_*) } \{ g_*(\mathbf y) - f^*(\mathbf y) \} $$
(Maximizing a concave function over a convex set)
Let \( X\subseteq\mathbb R^n \) be a convex set with non-empty interior and let \( g:\mathbb R^n\rightarrow \mathbb R \) be a proper concave function over \( X \), then the following holds.
$$
\sup_{\mathbf x\in X} g(\mathbf x)
=
\inf_{\mathbf y\in\textrm{dom}({-g})}\{ \delta^*(\mathbf y | X) - g_*(\mathbf y) \}
$$
Examples
(Affine functions)
Assume \( f(\mathbf x) = \mathbf a^\top\mathbf x + \mathbf b \), then,
$$
f^*(\mathbf y) = \begin{cases}
-\mathbf b & \textrm{if } \mathbf y = \mathbf a \\
+\infty & \textrm{otherwise}
\end{cases}
$$
(Convex Quadratic Functions)
Assume \( f(\mathbf x) = \frac 12\mathbf x^\top\mathbf A\mathbf x + \mathbf b^\top\mathbf x + c \) with \( \mathbf A \) a psd matrix, then,
$$
f^*(\mathbf y) = \begin{cases}
\frac 12(\mathbf y - \mathbf b)^\top\mathbf A^\dagger(\mathbf y - \mathbf b) - c & \textrm{if } \mathbf y \in \textrm{span}(\mathbf A) + \mathbf b \\
+\infty & \textrm{otherwise}
\end{cases}
$$
where \(\mathbf A^\dagger\) is the Moore-Penrose pseudo inverse of \( \mathbf A \).
If \( f \) is strictly convex (i.e., \( \mathbf A \) is positive definite), then \( \mathbf A^\dagger = \mathbf A^{-1} \) and the column span of \( \mathbf A \) is \( \mathbb R^n \).
If \( f \) is strictly convex (i.e., \( \mathbf A \) is positive definite), then \( \mathbf A^\dagger = \mathbf A^{-1} \) and the column span of \( \mathbf A \) is \( \mathbb R^n \).
(Finite Maximum)
Assume \( f(\mathbf x) = \max_{i=1,...,n} x_i \), then,
$$
f^*(\mathbf y) = \begin{cases}
0 & \textrm{if } \displaystyle \sum_{i=1}^n y_i = 1, \mathbf y \ge \mathbf 0 \\
+\infty & \textrm{otherwise}
\end{cases}
$$
(Soft max)
Assume \( \displaystyle f(\mathbf x) = \log\left(\sum_{i=1}^n e^{x_i}\right) \), then,
$$
f^*(\mathbf y) = \begin{cases}
\displaystyle \sum_{i=1}^n y_i\log(y_i) & \textrm{if } \displaystyle \sum_{i=1}^n y_i = 1, \mathbf y \ge \mathbf 0 \\
+\infty & \textrm{otherwise}
\end{cases}
$$
(Norms)
Assume \( f(\mathbf x) = ||\mathbf x|| \), then,
$$
f^*(\mathbf y) = \begin{cases}
0 & \textrm{if } ||\mathbf y||_* \le 1 \\
+\infty & \textrm{otherwise}
\end{cases}
$$ where \( ||\cdot||_* \) is the dual norm of \( ||\cdot|| \).
(Negative Entropy)
Assume \( f(\mathbf x) = \displaystyle \sum_{i=1}^n x_i\log{x_i} \) with \( \textrm{dom}(f) = \mathbb R_{++}^n \), then,
$$
f^*(\mathbf y) = \sum_{i=1}^n e^{y_i-1}
$$
https://piazza.com/class_profile/get_resource/is58gs5cfya7ft/ivubdhmws163zc
(Negative logarithm)
Assume \( \displaystyle f(\mathbf x) = -\sum_{i=1}^n \log{x_i} \) with \( \textrm{dom}(f) = \mathbb R_{++}^n \), then,
$$
f^*(\mathbf y) = \begin{cases}
\displaystyle -\sum_{i=1}^n \log{-y_i} - n & \textrm{if } \mathbf y \le \mathbf 0 \\
+\infty & \textrm{otherwise}
\end{cases}
$$
(Indicator of a convex set/cone)
Let \( X \) be a given convex set, then, by definition,
$$
\delta^*(\mathbf y | X) = \sup_{\mathbf x\in X} \mathbf y^\top\mathbf x.
$$
Moreover, assume that \( X \) is a convex cone, then the following holds.
$$
\delta^*(\mathbf y | X) = \delta^*(\mathbf y | -X^*) = \delta^*(-\mathbf y | X^*) =
\begin{cases}
0 & \textrm{if } \mathbf y^\top\mathbf x \le 0 \quad \forall\mathbf x\in X \\
+\infty & \textrm{otherwise}
\end{cases}
$$
where \( X^* \) denotes the dual cone of \( X \).
Calculus Rules
(Addition with an Affine Mapping)
Assume \( f(\mathbf x) = \tilde f(\mathbf x) + \mathbf a^\top\mathbf x + b \), then,
$$
f^*(\mathbf y) = \tilde f^*\left( \mathbf y - \mathbf a \right) - b
$$
\textcite[Theorem~12.3]{Rockafellar_1970}.
(Composition with an Affine Mapping)
Assume \( f(\mathbf x) = \tilde f(\mathbf A\mathbf x + \mathbf b) \).
If \( A \) is invertible, then, $$ f^*(\mathbf y) = \tilde f^*\left( \mathbf A^{-\top}\mathbf y \right) - \mathbf b^\top\mathbf A^{-T}\mathbf y $$
Otherwise, $$ f^*(\mathbf y) = \begin{array}[t]{rl} \displaystyle \inf_{\mathbf \lambda} \ & \tilde f^*(\mathbf \lambda) - \mathbf \lambda^\top \mathbf b \\ \text{s.t.} \ & \mathbf A^\top\mathbf \lambda = \mathbf y. \end{array} $$
If \( A \) is invertible, then, $$ f^*(\mathbf y) = \tilde f^*\left( \mathbf A^{-\top}\mathbf y \right) - \mathbf b^\top\mathbf A^{-T}\mathbf y $$
Otherwise, $$ f^*(\mathbf y) = \begin{array}[t]{rl} \displaystyle \inf_{\mathbf \lambda} \ & \tilde f^*(\mathbf \lambda) - \mathbf \lambda^\top \mathbf b \\ \text{s.t.} \ & \mathbf A^\top\mathbf \lambda = \mathbf y. \end{array} $$
\textcite[Theorem~12.3]{Rockafellar_1970}.
(Separable sum)
Assume \( f(\mathbf x_1, \mathbf x_2) = f_1(\mathbf x_i) + f_2(\mathbf x_2) \), then,
$$
f^*(\mathbf y_1, \mathbf y_2) = f_1^*(\mathbf y_1) + f_2^*(\mathbf y_2)
$$
(Non-separable sum)
Assume \( \displaystyle f(\mathbf x) = \sum_{i=1}^p f_i(\mathbf x) \), then,
$$
f^*(\mathbf y) = \begin{array}[t]{ll}
\displaystyle \inf_{\mathbf v^{(1)}, \dots, \mathbf v^{(p)}} & \displaystyle \sum_{i=1}^p f_i^*(\mathbf v^{(i)}) \\
\textrm{s.t. } & \displaystyle \sum_{i=1}^p \mathbf v^{(i)} = \mathbf y \\
& \mathbf v^{(1)}, \dots, \mathbf v^{(p)} \in\mathbb R^{n}
\end{array}
$$
(Scalar multiplication)
Assume \( f(\mathbf x) = \alpha \tilde f(\mathbf x) \) with \( \alpha > 0 \), then,
$$
f^*(\mathbf y) = \alpha \tilde f^*\left(\frac{\mathbf y}\alpha\right)
$$
(Convex/Concave conjugate)
Let \( f \) be a given function, then $$ (-f)_*(\mathbf y) = -f^*(-\mathbf y). $$
Proof.
$$
(-f)_*(\mathbf y) = \inf_{\mathbf x}\{ \mathbf y^\top\mathbf x - (-f)(\mathbf x) \}
= - \sup_{\mathbf x} \{ -\mathbf y^\top\mathbf x - f(\mathbf x) \}
= -f^*(-\mathbf y)
$$
References
@book{Rockafellar_1970,
title = {Convex Analysis},
isbn = {9781400873173},
doi = {10.1515/9781400873173},
publisher = {Princeton University Press},
author = {Rockafellar, Ralph Tyrell},
year = {1970}
}