1

I'm having a hard time proving to myself that the following function is convex: $$f'(x')= \inf_{Ax = x'} f(x)$$

where $f(x)$ is convex.

i.e., I'm trying to show

$$f'(tx_1+(1-t)x_2) \le tf'(x_1)+(1-t)f'(x_2)\tag{1}$$

where $t\in[0,1]$ By definition,

$$f'(tx_1+(1-t)x_2) \le f(tx_1+(1-t)x_2) \le tf(x_1)+(1-t)f(x_2)$$

But how does this relate this to $(1)$?

Paul Sinclair
  • 43,643
user 89084w
  • 27
  • Your "by definition" inequality is inaccurate, in that you didn't account for the action of $A$ in your definition of $f'$. You could have written it correctly as $$f'(tAx_1 + (1-t)Ax_2) \le f(tx_1 + (1-t)x_2) ...$$ I presume $x \in \Bbb R^n, x' \in \Bbb R^m$ and $A : \Bbb R^n \to \Bbb R^m$ is a surjective linear map? – Paul Sinclair Nov 29 '19 at 13:40
  • any info given on $A$ ? – Ahmad Bazzi Nov 29 '19 at 13:41

1 Answers1

2

Problem: Suppose $f(x)$ is convex. Prove that $g(y) = \inf\limits_{Ax = y} f(x)$ is convex.

Proof: Let $t\in [0, 1]$. We need to prove that $$g(t y_1 + (1-t)y_2) \le t g(y_1) + (1-t)g(y_2).\tag{1}$$

Let $\epsilon > 0$. From the definition of infimum, there exists $x_1$ and $x_2$ such that $Ax_1=y_1$, $Ax_2 = y_2$, $f(x_1) \le g(y_1) + \epsilon$ and $f(x_2) \le g(y_2) + \epsilon$. Thus, we have \begin{align} g(ty_1 + (1-t)y_2) &\le f(tx_1 + (1-t)x_2)\\ & \le tf(x_1) + (1-t)f(x_2) \\ &\le t (g(y_1) + \epsilon) + (1-t)(g(y_2) + \epsilon)\\ & = tg(y_1) + (1-t)g(y_2) + \epsilon. \end{align} Since this holds for any $\epsilon > 0$, (1) holds. We are done.

Reference: Boyd and Vandenberghe, "Convex Optimization".

River Li
  • 37,323