1
$\begingroup$

Denote $\mathcal F$ as the function class consisting of gradients of all real-valued convex functions in $\mathbb R^d$, that is, $\mathcal F = \{ \nabla \phi ~|~ \phi: \mathbb R^d \to \mathbb R \text{ and $\phi$ is convex}\}$. Note that every element of $\mathcal F$ is a function from $\mathbb R^d$ to $\mathbb R^d$. Then is $\mathcal F$ closed under composition operation? That is, suppose $f \in \mathcal F$ and $ g\in \mathcal F$, do we have $f\circ g \in \mathcal F$ where $\circ$ denotes function composition?

Note: the statement should be true for $d = 1$ since:

  1. Gradient of a univariate real-valued convex function is non-decreasing;
  2. Composition of two non-decreasing functions is still non-decreasing;
  3. Non-decreasing gradient corresponds to a convex function.
$\endgroup$
5
  • $\begingroup$ So, the question boils down to whether $f \circ g$ can be written as $\nabla \phi$ for some real-valued, convex, (probably want $C^1$ too) function $\phi: \mathbb{R}^d \rightarrow \mathbb{R}$. $\endgroup$
    – Selrach Dunbar
    Commented May 19, 2022 at 4:19
  • $\begingroup$ So $\mathcal{F}$ is a subset of the set of conservative vector fields on $\mathbb{R}^d$ (to use some lingo from multivariable calculus). (Most of the time folks talk about these the discussion immediately goes to line integrals.) Not to take over this post, but can anyone quickly just confirm that if we (temporarily) ignore the convexity requirement, the set of conservative vector fields is closed under composition? $\endgroup$
    – Selrach Dunbar
    Commented May 19, 2022 at 4:45
  • $\begingroup$ So, just FYI, your question prompted me to ask the related question (in the preceding comment) concerning what happens if we drop the convexity requirement. Here's a link to that question. The short answer is no, the set $\mathcal{F}'$ (your $\mathcal{F}$ with the convexity requirement dropped) is not closed under composition. That said, perhaps the convexity requirement saves it? (Restricts it enough that the restricted set is closed under composition?) $\endgroup$
    – Selrach Dunbar
    Commented May 23, 2022 at 18:24
  • $\begingroup$ Although his description is a bit sparse, @max_zorn has offered a valid counterexample to show $\mathcal{F}$ is not closed under composition. In max_zorn 's answer below he identifies: - $f(x,y)= x^2+xy+\frac{1}{2}y^2=\frac{1}{2}[x,y]\begin{bmatrix} 2 & 1\\ 1 & 1\end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$ and - $g(x,y) = \frac{5}{2}x^2+2xy+\frac{1}{2}y^2=\frac{1}{2}[x,y]\begin{bmatrix} 5 & 2\\ 2 & 1\end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$. $\endgroup$
    – Selrach Dunbar
    Commented May 24, 2022 at 3:31
  • $\begingroup$ Hence, $F := \nabla f = \left<2x+y,x+y \right> =\begin{bmatrix} 2 & 1\\ 1 & 1\end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$ and $G := \nabla g = \left<5x+2y,2x+y \right> = \begin{bmatrix} 5 & 2\\ 2 & 1\end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$. Thus, $F \circ G: \langle x,y \rangle\mapsto \left<12x+5y,7x+3y\right>=\begin{bmatrix} 2 & 1\\ 1 & 1\end{bmatrix} \begin{bmatrix} 5 & 2\\ 2 & 1\end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}=\begin{bmatrix} 12 & 5\\ 7 & 3\end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$ which is not the gradient of any scalar function $\phi$. $\endgroup$
    – Selrach Dunbar
    Commented May 24, 2022 at 3:32

1 Answer 1

Reset to default
1
$\begingroup$

Set
$$A = \begin{pmatrix} 2 & 1\\ 1 & 1\end{pmatrix} \quad\text{and}\quad B = \begin{pmatrix} 5 & 2\\ 2 & 1\end{pmatrix}.$$ Both matrices are positive definite because their diagonal entries are positive as are their determinants. Hence, they are gradients of convex functions, namely $\tfrac{1}{2}\langle x,Ax\rangle$ and $\tfrac{1}{2}\langle x,Bx\rangle$, respectively.

However, $$AB = \begin{pmatrix} 12 & 5 \\ 7 & 3\end{pmatrix}$$ is not even symmetric, so it cannot be a gradient of a convex function.

Note: The matrices were already used in a sister question: Product of any two arbitrary positive definite matrices is positive definite or NOT?

$\endgroup$
10
  • $\begingroup$ This is NOT a counter example (the function class $\mathcal F$ consists of GRADIENTS of all real-valued convex functions). $\nabla g = 2x$ and $\nabla f = -1$, so $\nabla g \circ \nabla f = -2$ which corresponds to a convex function $x \mapsto -2x + const.$. Also, $\nabla f \circ \nabla g = -1$ corresponding to convex function $x \mapsto -x + const.$ $\endgroup$
    – Ethan
    Commented May 20, 2022 at 15:11
  • $\begingroup$ @TrueRealEason I misread. Working on a better example. $\endgroup$
    – max_zorn
    Commented May 21, 2022 at 1:53
  • $\begingroup$ Unfortunately, I don't think this second example is going to scratch the itch either. The questions asks about gradients of real-valued functions. These appear to be Jacobians of vector-valued functions. That is, $A = D \overrightarrow{ F \;}= \left<\nabla f_1, \nabla f_2\right>$ where $\overrightarrow{ F \;}(x,y) = \left<f_1 (x,y), f_2(x,y)\right> = \left<2x+y, x+y\right>$. $\endgroup$
    – Selrach Dunbar
    Commented May 21, 2022 at 16:24
  • 1
    $\begingroup$ Please read the “Hence” sentence where I give the functions. $\endgroup$
    – max_zorn
    Commented May 23, 2022 at 1:26
  • $\begingroup$ Nice! I see it now. Didn't understand what you were saying at first. $\endgroup$
    – Selrach Dunbar
    Commented May 24, 2022 at 3:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .