Hessian matrix and epigraphs

315 Views Asked by At

I'm working on a homework assignment concerning convex optimization and I came across a problem involving the convexity of the function and the convexity of the domain of the function.

Consider the function $f : [0,1]^3 \in R$ with the following form $$ f(x,y,z) = xlnx + ylnz + zlnz + \alpha ( x + y + z - 1) $$

The gradient

$$ \nabla f(x,y,z) = (lnx + \alpha + 1)\vec{i} + (lny + \alpha + 1)\vec{j} + (lnz + \alpha + 1)\vec{k} $$

The hessian matrix:

$$ \left[ \begin{array}{ccc} \frac{1}{x} & 0 & 0 \\ 0 & \frac{1}{y} & 0 \\ 0 & 0 & \frac{1}{z} \\ \end{array} \right] $$

Since for the interior of the function of which is $[0,1]$ does it follow that the epigraphs that are formed would be positive semidefinite since the hessian matrix is positive definite?

And therefore would the domain of the function also be convex since the cartesian product of the epigraphs would result in a convex set?

2

There are 2 best solutions below

0
On BEST ANSWER

As requested, my comments promoted to an answer, with a little extra commentary.

Here's a basic definition of convexity: a function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is convex if its domain $\mathop{\textbf{dom}} f$ is a convex set and if $$f(\alpha x+(1-\alpha)y)\leq \alpha f(x)+(1-\alpha) f(y) \quad \forall x,y\in\mathop{\textbf{dom}} f,~0\leq\alpha\leq 1.$$ So proving the convexity of a function's domain is a fundamental part of proving convexity of the function itself. For instance, the function $$g(x)=x^2 \qquad \mathop{\textbf{dom}} g = (-\infty,1] \cup [1,\infty)$$ is not convex; $x^2$ is itself the quintissential convex function, but the domain is not convex. On the other hand, the function $$h(x)=1/x, \qquad \mathop{\textbf{dom}} h=(0,+\infty)$$ is convex, even though $1/x$ is not convex if considered over the entire real line.

In many cases, the domain of a function is trivial; that is, $\mathbb{R}^n$. Artificially restricted domains like $g$ above, or even your example, are frankly not common. More common are domains restricted to the region where the function is well defined, like $-\ln x$, or when considering a convex branch of a function, like $h$ above.

In your case, the domain is almost handed to you. The set $[0,1]^3$ is trivially convex, being the Cartesian product of intervals. But you must also confirm that the function is defined and finite on that interval. In this case, this is true if you use the $0\cdot\ln 0=0$ convention, which is reasonable to do since it's the limiting behavior of $x\ln x$. So the domain of $f$ truly is $[0,1]^3$.

A common practice in convex analysis, by the way, is to define functions on the extended real number line $[-\infty,+\infty]$. Then the domain of a convex function simply becomes the set of points over which the function is finite. For instance: $$g(x) = \begin{cases} x^2 & x \leq 1 \text{ or } x \geq +1 \\ +\infty & -1<x<+1 \end{cases} \qquad h(x) = \begin{cases} 1/x & x>0 \\ +\infty & x \leq 0 \end{cases}$$ Your function becomes $$f(x,y,z)=\begin{cases} x\ln x+(y+z)\ln z+\alpha(x+y+z−1) & (x,y,z)\in[0,1]^3\\ +\infty & \text{otherwise} \end{cases}$$ It takes a bit of care to work with the extended real number line; you need to be careful not to do $\infty-\infty$ or $0\cdot \infty$. The reward is that all of this domain discussion disappears. In fact, a slightly modified secant test for convexity still works: an extended real function $f:\mathbb{R}^n\rightarrow[-\infty,+\infty]$ is convex iff $$f(\alpha x+(1-\alpha)y) \leq \alpha f(x) + (1-\alpha) f(y) \qquad \forall x,y\in\mathbb{R}^n, ~0<\alpha<1$$ Try this on $h(x)$ above, for instance: it works even if $x$ or $y$ is negative.

2
On
  1. This is a really interesting function as it is the Lagrangian for constrained maximum information entropy, of, for example, a probability distribution on a set with 3 points.

  2. One can see that $f$ is convex since it is the sum of convex functions.

  3. I'm not clear what you are trying to get at in terms of the Hessian. Positive semi-definiteness of the Hessian at all points in the domain does imply convexity of a function, so that would be an alternative proof of convexity. See Theorem 3.37 here for example.

  4. One can show that the domain $[0,1]^3$ directly through the definition of convexity - pick two points, find a third directly inbetween them, and verify that the third point is also in the domain. It's the unit cube.

Convex Set

Convex Function