0
$\begingroup$

I'm reading Section 3.2.4 of the Boyd-Vandenberghe book on convex optimization, in the part about vector composition. It considers a function $$ f(x) = h(g(x)) = h(g_1(x),\dotsc,g_k(x))$$ with $h~:~\mathbb{R}^k\to\mathbb{R}$ and $g_i~:~\mathbb{R}^n\to\mathbb{R}$. W.l.o.g. it assumes $n=1$ because we can analyze the behavior of a function on each possible line. It first shows how to derive rules for $h$ and the $g_i$'s so that $f$ is convex, under the condition that $h$ and the $g_i$'s are twice differentiable and their domain is respectively the whole $\mathbb{R}^k$ and $\mathbb{R}$. These rules involve the monotonicity of $h$.

Then, it says that general results hold with "no assumption on differentiability of $h$ or $g$, and general domains", but "the monotonicity condition on $h$ must hold for the extended-value extension of $\tilde{h}$". This restriction seems very strong, and I'm trying to understand whether I can relax it in some cases.

Specifically, I'm thinking of the following case: Let $z$ be a convex function from $\mathbb{R}$ to $\mathbb{R}$, with domain being the whole $\mathbb{R}$.

Consider now the prespective of $z$, i.e., the function $h : \mathbb{R}^2 \to \mathbb{R}$ defined as $$ h(x,t) = t z\left(\frac{x}{t}\right)$$ This function has domain $$ \mathbf{dom}h = \{(x,t) ~:~ x/t \in \mathbb{R}, t > 0\}, $$ and is convex on this domain. Clearly this domain is not the whole $\mathbb{R}^2$. Assume we show that $h$ is non-decreasing on its domain wrt both $x$ and $t$. We would like to compose $h$ with functions $g_1$ and $g_2$ that are convex and getting that the resulting composition $f(x)=h(g_1(x),g_2(x))$ is convex, but according to the book we cannot just do it because the domain of $h$ is not the whole $\mathbb{R}^2$.

Thus, we look at the extended-value extension $\tilde{h}$ of $h$, which is defined as $h(x,t)$ for $(x,t)\in\mathbf{dom} h$, and as $\infty$ everywhere else. Clearly $\tilde{h}$ cannot be non-decreasing: as we move from a point $(x,t_1)$ with $t_1\le 0$, to a point $(x,t_2)$ with $t_2>0$, the function goes from $\infty$ to something less than $\infty$.

Thus it seems that the composition rule "$f$ is convex if $h$ is convex and non-decreasing in each argument, and $g_i$ are convex" cannot be applied to the non-decreasing perspective of a convex function, because its extended-value extension will never be non-decreasing. Is that really true?

Are there rules or special cases in which I can apply a composition rule to such a perspective?

For example, what if $h$ and $g_i$ were twice differentiable on their domains?

In other words, is the monotonicity of the extended-value extension $\tilde{h}$ required only if the functions are not twice differentiable?

$\endgroup$
2
  • $\begingroup$ As for your final question, have you read Remark 3.3 in the book? $\endgroup$
    – LinAlg
    Commented Apr 19, 2018 at 14:26
  • $\begingroup$ @LinAlg: I find that counterexample a bit disappointing: what if we restrict $g$ to $\mathbb{R}_{+}$? At this point, the domain of $f$ would be convex. I'm wondering whether, if we restrict the domain of the $h$ and of the $g_i$ so that the domain of the composition is convex, do we still care that $\tilde{h}$ is not non-decreasing? $\endgroup$
    – Matteo
    Commented Apr 19, 2018 at 14:33

1 Answer 1

1
$\begingroup$

The function $h(g(x))$ is convex if $h(g(x)) = \min_t\{h(t) : t \geq g(x) \}$ and $g$ and $h$ are convex. This requires $h$ to be nondecreasing on the range of $g$.

$\endgroup$
14
  • $\begingroup$ Thank you. Do you have a reference for the first part of your answer? I'll check and then I'll accept the answer, because I believe it solves my question. $\endgroup$
    – Matteo
    Commented Apr 19, 2018 at 15:12
  • 1
    $\begingroup$ Let $f(x,t)= t$ if $t \geq g(x)$, $\infty$ otherwise. Then $f$ is jointly convex in $(t,x)$ (easily checked via the definition of convexity with $\lambda$ and $1-\lambda$ and dealing with all finite/$\infty$ cases). The partial minimization of a jointly convex function is convex. $\endgroup$
    – LinAlg
    Commented Apr 19, 2018 at 15:14
  • 2
    $\begingroup$ Another way to do this. Suppose $h$ is nondecreasing on the range of $g$; and let $y_\min=\inf_x g(x)$. Then define $\tilde{h}(y)=h(\max\{y,y_\min\}).$ This new function coincides with $h$ on the range of $g$, and is monotonic, so $\tilde{h}(g(\cdot))$ is convex; therefore, so is $h(g(\cdot))$. $\endgroup$ Commented Apr 19, 2018 at 15:20
  • $\begingroup$ Thank you both. I need some time to understand and internalize these suggestions, then I'll accept the answer and upvote the comments. $\endgroup$
    – Matteo
    Commented Apr 19, 2018 at 16:53
  • 1
    $\begingroup$ @Matteo the answer would be the same, except that $t \in \mathbb{R}^k$. $\endgroup$
    – LinAlg
    Commented Apr 25, 2018 at 14:00

You must log in to answer this question.

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