4
$\begingroup$

EDIT: I made some critical corrections below.

Let $\mathcal{H}\colon\mathbf{w}\cdot\mathbf{x}+c=0$ be a hypeplane in $\mathbb{R}^n$. Also, let $g\colon\mathbb{R}^n\to\mathbb{R}_+$, be a non-negative, real-valued function. I would like to decide on the convexity of the function $f\colon\mathbb{R}^n\times\mathbb{R}\to\mathbb{R}$, given by $$ f(\mathbf{a},b)=\int_{\Omega}\! (\mathbf{a}\cdot\mathbf{x}+b)g(\mathbf{x}) \,\mathrm{d}\mathbf{x}, $$ where $\mathbf{x}\in\mathbb{R}^n$, $b\in\mathbb{R}$, and $\Omega$ is the half-space defined by $\mathcal{H}$ as $\Omega=\{\mathbf{x}\in\mathbb{R}^n\rvert\mathbf{w}\cdot\mathbf{x}+c\geq0\}$.

What I have thought so far is to express the integral as a sum (if such a thing is feasible) and use the property of the affine (and consequently convex) quantity $(\mathbf{a}\cdot\mathbf{x}+b)\cdot k$, where $k\in\mathbb{R}$. Albeit, I am not sure at all this is going to work. In addition, I am not sure in what direction should I work to...

Is there any appropriate argument I could use instead?

$\endgroup$
  • $\begingroup$ There must be a typo. The integral with respect to x can't be a function of x. $\endgroup$ – p.s. Apr 14 '14 at 19:02
  • $\begingroup$ @p.s.thanks, yes there were some typos... I think it's ok now. $\endgroup$ – nullgeppetto Apr 14 '14 at 20:01
  • $\begingroup$ It's now constant with respect to x. $\endgroup$ – p.s. Apr 14 '14 at 21:34
  • $\begingroup$ Sorry, I am bit confused.. Now? $\endgroup$ – nullgeppetto Apr 14 '14 at 22:03
  • $\begingroup$ @p.s., What's the correct way to express it? I've been lost I think... $\endgroup$ – nullgeppetto Apr 14 '14 at 22:10
1
$\begingroup$

Not sure if you can use this, but a basic property of convex functions is that nonnegative combinations of them are convex. This extends to nonnegative integrals as well. If $h(x,t)$ is convex in $x$ and $g$ is nonnegative over the domain $\Omega$, and $$ f(x) = \int_\Omega h(x,t)g(t)dt $$ then $f$ is convex.

This is a consequence of the definition of convexity and some basic properties of integrals:

$$ \begin{aligned} f(\theta x + (1-\theta) y) &= \int_\Omega h(\theta x + (1-\theta) y,t)g(t)dt \\ &\le \int_\Omega (\theta h(x,t) + (1-\theta) h(y,t))g(t)dt \\ &= \theta \int_\Omega h(x,t) g(t)dt + (1-\theta) \int_\Omega h(y,t)g(t)dt \\ &= \theta f(x) + (1-\theta) f(y) \end{aligned} $$

Conversely, if you can express $f$ in this form with a nonconvex $h$, then you might be able to use it to find a example where $f$ is nonconvex.

In your specific case, it seems, the function is not only convex, but affine, which you can see by factoring: $$ f(\mathbf{a},b)=\mathbf{a} \cdot \left(\int_{\Omega}\! \mathbf{x}g(\mathbf{x}) \,\mathrm{d}\mathbf{x}\right) + b \left(\int_{\Omega}\! g(\mathbf{x}) \,\mathrm{d}\mathbf{x}\right) $$

$\endgroup$
  • $\begingroup$ I have used your idea making my formulation more clear, could you take a look at my answer below and check its correctness? $\endgroup$ – nullgeppetto Apr 15 '14 at 8:47
  • $\begingroup$ yes can be proven to be affine too! That's nice! Thanks again! $\endgroup$ – nullgeppetto Apr 15 '14 at 12:23
  • $\begingroup$ Hi, @p.s.! It's been a long time ago, but I've found some mistake here... Could you take a look at my edited answer below? I've added a counter-example. Where is the problem? $\endgroup$ – nullgeppetto Aug 5 '14 at 19:11
1
$\begingroup$

Let me make my question more general and clear, maybe giving an answer, thanks to @p.s, of course!

Let $f\colon K\subseteq\mathbb{R}^n\times\mathbb{R}\to\mathbb{R}$, given by $$ f(\mathbf{a},b)=\int_{\Omega}\! h(\mathbf{a},b,\mathbf{x})g(\mathbf{x}) \,\mathrm{d}\mathbf{x}, $$ where $\Omega=\{\mathbf{x}\in\mathbb{R}^n\rvert\mathbf{w}\cdot\mathbf{x}+c\geq0\}$. Also, let $g\colon\mathbb{R}^n\to\mathbb{R}_+$ be a non-negative function.

If $h$ is convex with respect to $\mathbf{a}$, $b$ over the domain $\Omega$, then $f$ is convex in $K$.

Proof Let $\lambda\in[0,1]$ and $(\mathbf{a}_1,b_1),(\mathbf{a}_2,b_2)\in K$. Then, $$ \begin{aligned} f(\lambda\mathbf{a}_1+(1-\lambda)\mathbf{a}_2,\lambda b_1+(1-\lambda)b_2) &= \int_\Omega\!h(\lambda\mathbf{a}_1+(1-\lambda)\mathbf{a}_2,\lambda b_1+(1-\lambda)b_2,\mathbf{x})g(\mathbf{x})\,\mathrm{d}\mathbf{x} \\ &\le \int_\Omega\!\left[\lambda h(\mathbf{a}_1,b_1,\mathbf{x}) + (1-\lambda) h(\mathbf{a}_2,b_2,\mathbf{x})\right]g(\mathbf{x})\,\mathrm{d}\mathbf{x} \\ &= \lambda \int_\Omega h(\mathbf{a}_1,b_1,\mathbf{x}) g(\mathbf{x})d\mathbf{x} + (1-\lambda) \int_\Omega\!h(\mathbf{a}_2,b_2,\mathbf{x})g(\mathbf{x})\,\mathrm{d}\mathbf{x} \\ &= \lambda f(\mathbf{a}_1,b_1) + (1-\lambda) f(\mathbf{a}_2,b_2). \end{aligned} $$

So, I think this can be applied to my problem, as the function $h(\mathbf{a},b,\mathbf{x})=\mathbf{a}\cdot\mathbf{x}+b$ is convex (actually it is affine with respect to $\mathbf{a}$, $b$) with respect to $\mathbf{a}$, $b$.


A Counterexample?

Let $h(\mathbf{a},b,\mathbf{x})=\mathbf{a}\cdot\mathbf{x}+b+1$, which is affine w.r.t. $\mathbf{a},b$ over the domain $\Omega=\{\mathbf{x}\in\mathbb{R}^n \mid \mathbf{a}\cdot\mathbf{x}+b+1 \geq 0\}$. Also, let $g$ be the probability density function of an $n$-dimensional Gaussian with mean $\mu\in\mathbb{R}^n$ and covariance matrix $\Sigma\in\mathbb{S}_{++}^n$ (symmetric, positive-definite, $n\times n$). Then, the function $$ f(\mathbf{a},b)=\int_{\Omega}\! h(\mathbf{a},b,\mathbf{x})g(\mathbf{x}) \,\mathrm{d}\mathbf{x} $$ is argued to be convex from the above "Theorem", but it is evaluated as follows

$$ f(\mathbf{a},b) = \frac{\mathbf{a}\cdot\mu+b+1}{2} \left[ 1 - \operatorname{erf}\left(-\frac{\mathbf{a}\cdot\mu+b+1}{\sqrt{2\mathbf{a}^T\Sigma\mathbf{a}}}\right) \right] + \frac{\sqrt{\mathbf{a}^T\Sigma\mathbf{a}}}{2\pi} \exp\left( -\frac{(\mathbf{a}\cdot\mu+b+1)^2}{2\mathbf{a}^T\Sigma\mathbf{a}}\right), $$

which obviously is not convex in $(\mathbf{a},b)$.

Where is the mistake?

$\endgroup$
  • 1
    $\begingroup$ In order for the result to apply, the domain $\Omega$ can't depend on the variables $(a,b)$. $\endgroup$ – p.s. Aug 5 '14 at 20:08
  • $\begingroup$ Thanks a lot @p.s.! That explains a lot... $\endgroup$ – nullgeppetto Aug 5 '14 at 20:12

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.