2
$\begingroup$

Context: Here is a question jump into my mind, when I met a problem in 1-dim case, I'm wondering if there is a generalization to higher dimensional $\mathbb R^n$ space:

Is the following statement true or false? If it's false, please give counter-example, if it's true, please prove that:

Suppose $f, g$ are two convex function $\mathbb R^n \rightarrow \mathbb R$ with unique minimum in $\mathbb R^n$. The minimum of function $f$ is denoted as $\vec{x^{(1)}}$; the minimum of function $g$ is denoted as $\vec{x^{(2)}}$. Suppose $\vec{x^*}$ is the minimum of $f + g$, then we have \begin{align} \min \{\vec{x^{(1)}_j}, \vec{x^{(2)}_j} \} \leq \vec{x^*_j} \leq \max \{\vec{x^{(1)}_j}, \vec{x^{(2)}_j} \} ~~~~~~~~~~\forall 1 \leq j \leq n. \end{align}

For $1$ dim case, the above statement is of course true; but what if in the high dimensions case $n \geq 2$?

$\endgroup$
2
  • $\begingroup$ Please give more context. Providing context not only assures that this is not simply copied from a homework assignment, but also allows answers to be better directed at where the problem lies and to be within the proper scope. Please avoid "I have no clue" questions. Defining keywords and trying a simpler, similar problem often helps. $\endgroup$
    – robjohn
    Jan 13, 2021 at 9:46
  • $\begingroup$ Thanks for remind, john :) I add some context to this question, pretty sure it's not a homework in any book I read now. $\endgroup$
    – 0o0o0o0
    Jan 17, 2021 at 6:06

1 Answer 1

5
$\begingroup$

Let $f(x,y)=2(x+1)^2+((x+y)+1)^2$ and $g(x,y)=(x-1)^2+((x+y)-1)^2$. Since the second partial derivatives of $f$ and $g$ are positive and both $H_f=\begin{bmatrix} 6 & 2 \\ 2 & 2 \end{bmatrix}$ and $H_g=\begin{bmatrix} 4 & 2 \\ 2 & 2 \end{bmatrix}$ are positive definite, $f$ and $g$ are strictly convex. The minimum for $f$ is at $(-1,0)$ and for $g$ at $(1,0)$. Since $0=\partial(f+g)/\partial y$ implies $x+y=0$ and $\partial(f+g)/\partial x=6x+2+4(x+y)$, $f+g$ achieves its minimum at $(-1/3,1/3)$. Thus the statement is false.

$\endgroup$
1
  • $\begingroup$ "Since the second partial derivatives of $f$ and $g$ are positive", you don't need this part of the argument for strict convexity; the Hessian being positive definite is sufficient $\endgroup$
    – LinAlg
    Jan 13, 2021 at 14:17

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.