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$
  • $\begingroup$ As for your final question, have you read Remark 3.3 in the book? $\endgroup$ – LinAlg Apr 19 '18 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 Apr 19 '18 at 14:33
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$
  • $\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 Apr 19 '18 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 Apr 19 '18 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$ – Michael Grant Apr 19 '18 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 Apr 19 '18 at 16:53
  • 1
    $\begingroup$ @Matteo the answer would be the same, except that $t \in \mathbb{R}^k$. $\endgroup$ – LinAlg Apr 25 '18 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.