9
$\begingroup$

Given two positive definite matrices $A, B \in \Bbb R^{n \times n}$, is there a way to construct a convex function $f: \Bbb R^n \to \Bbb R$ such that $$\nabla^2f(x)=A \qquad \text{and} \qquad \nabla^2f(y)=B$$ for two distinct $x,y \in \Bbb R^n$ (say $x=0_n$, $y=1_n$)?

I've tried the usual suspects (stuff with quadratics, exponentials, etc) without going anywhere.

$\endgroup$

2 Answers 2

4
+50
$\begingroup$

Let us try to construct an example explicitly as $h(x)=f(g(x))$ where $f\colon\Bbb R\to\Bbb R$ and $g\colon\Bbb R^n\to\Bbb R$. The Hessian of $h$ is $$ \nabla^2 h(x)=f''(g(x))\nabla g(x)\nabla g(x)^T+f'(g(x))\nabla^2 g(x).\tag{1} $$ 1. Define for $T>0$ the function $$ f_T(t)=\begin{cases}\frac{t^2}{T}-\frac{t^3}{3T^2}, & t\le T\\ t-\frac{T}{3}, & t>T.\end{cases} $$ It is straightforward to verify that $f_T\in C^2$, convex and increasing for $t\ge 0$. Furthermore, $$ f_T'(0)=0,\quad f_T''(T)=0,\quad f_T'(T)=1.\tag{2} $$ 2. Define $g(x)=\frac12(x-a)^TB(x-a)$ for a fixed $a\in\Bbb R^n$ and a positive definite $B$. We have $$ \nabla g(x)=B(x-a),\quad\nabla^2 g(x)=B.\tag{3} $$ 3. Set $T=g(b)$ for a fixed $b\in\Bbb R^n$, $b\ne a$. Then $T>0$ and $h_1(x)=f_{g(b)}(g(x))$ is convex (as a composition of convex non-negative $g$ with convex and increasing for non-negative arguments $f$). Moreover, from (1)-(3) we have $$ \nabla^2 h_1(a)=f''(0)\cdot 0+0\cdot B=0,\quad \nabla^2 h_1(b)=0\cdot\nabla g(b)\nabla g(b)^T+1\cdot B=B. $$ 4. Similarly we can construct $h_2(x)$ with $$ \nabla^2 h_2(b)=0,\quad\nabla^2 h_2(a)=A $$ and take $h=h_1+h_2$.

$\endgroup$
1
  • $\begingroup$ Very nice construction, thanks a lot! $\endgroup$
    – Nitrogen
    Mar 15, 2017 at 10:02
3
$\begingroup$

Let $M$ be a positive number to be chosen later. For $z\in\mathbb{R}^n$, define $$f_1(z) = \frac12 \langle Az,z-x\rangle + M\langle z-x, x-y\rangle$$ and
$$f_2(z) = \frac12 \langle Bz,z-y\rangle + M\langle z-y, y-x\rangle$$
Note that $\nabla^2 f_1\equiv A$ and $\nabla^2 f_2\equiv B$; also, $f_1(x)=0$ and $f_2(y)=0$. Choose $M$ large enough so that $f_1(y)<0$ and $f_2(x)<0$; this is possible because the term multiplied by $M$ is negative in both cases.

Let $f=\max(f_1,f_2)$. This is a convex function whose Hessian is $A$ where $f_1>f_2$, and is $B$ where $f_1<f_2$. The inequalities $f_1>f_2$ and $f_1<f_2$ determine disjoint open sets $U,V$ that contain $x$ and $y$, respectively.

If a smooth function is desired, convolve $f$ with a compactly supported smooth bump $\phi$. When the diameter of $\operatorname{supp}\phi$ is smaller than $$\min(\operatorname{dist}(x, \partial U), \operatorname{dist}(y, \partial V))$$ the Hessian at $x$ will remain $A$ because in a neighborhood of $x$, $$\nabla^2 (f*\phi) = \nabla^2 (f_1*\phi) = (\nabla^2 f_1)*\phi=A$$ Same for $y$.

$\endgroup$
1
  • $\begingroup$ Nice construction! However, I am not so comfortable with the use of convolution with bump function. How do you prove that $f *\phi$ is still convex? $\endgroup$
    – Nitrogen
    Mar 12, 2017 at 9:38

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.