1
$\begingroup$

Given that all functions $f_i(x):\mathbb{R}^n\to\mathbb{R}$ are piece-wise linear convex functions, prove that $F(x)=\sum_{i=1}^m f_i(x)$, for $m$ functions, is also a piece-wise linear convex function.

The definition to be used for piece-wise linear is $f_i = \max\{c_j^Tx + d_j\}$, where $c_j\in \mathbb{R}^n$ and $d_j\in\mathbb{R}$, and $\forall j\in J$, an index set associated with function $f_i$. And for each function $f_i$ there is a unique index set $J$ and its own sets $\{d_j\},\{c_j\}$.

I dont know how better to word that, sorry. I hope its well understood.

The definition for a convex function is as such: $\forall x,y$ in domain, $\forall \lambda\in[0,1]$, $f(\lambda x + (1-\lambda)y)\le \lambda f(x) + (1-\lambda) f(y)$.

Ive already proven that the sum of convex functions is convex, without regard for piece-wise linear. What I cant seem to show is that the sum of piece-wise linear functions (using the required definition) is also piece-wise linear.

Ive been working on this for three days. Any pointers or suggestions would be greatly appreciated. Ive also already proven using an inductive argument that it holds for $m>2$, but I cant seem to show the base case $m=2$. So Ive done quite a bit of this problem already. Just need help proving the base case of the piece-wise linear portion.

$\endgroup$
  • $\begingroup$ It is important to note that the sum has a finite number of elements. $\endgroup$ – LinAlg Apr 5 '18 at 0:43
3
$\begingroup$

Note that that $\max_i a_i + \max_j b_j = \max_{i,j} (a_i+b_j)$.

Hence $\max_i (c_i^T x + d_i) + \max_j ({c'_j}^T x + d'_j) = \max_{i,j} ((c_i+c'_j)^T x + (d_i + d'_j) $.

Hence the sum of two convex piecewise linear functions is a convex piecewise linear function. Induction shows the rest.

Aside:

Let $A,B \subset \mathbb{R}$ be non empty.

Then $a+b \le \sup A + \sup B$ for all $a \in A, b \in B$ and so $\sup (A+B) \le \sup A + \sup B$.

For any $a\in A, b \in B$ we have $\sup(A+B) \ge a+b$. Now take the $\sup$ over $a \in A$ to get $\sup(A+B) \ge \sup A +b$ and repeat over $b \in B$ to get the desired result.

$\endgroup$
  • $\begingroup$ This crossed my mind but its not generally true, is it? The sums of maximums dont generally equal the maximum of sums. Perhaps it does under certain conditions but we are dealing in $n$ dimensional vector space. $\endgroup$ – CogitoErgoCogitoSum Apr 4 '18 at 23:38
  • $\begingroup$ In general, $\sup(A+B) = \sup A+ \sup B$. $\endgroup$ – copper.hat Apr 4 '18 at 23:47
  • $\begingroup$ Counter claim: math.stackexchange.com/questions/1671111/… Sums of maxs dont equal maxs of sums $\endgroup$ – CogitoErgoCogitoSum Apr 4 '18 at 23:47
  • $\begingroup$ Am I not understanding something? $\endgroup$ – CogitoErgoCogitoSum Apr 4 '18 at 23:47
  • $\begingroup$ What is the relevance of the linked question? $\endgroup$ – copper.hat Apr 4 '18 at 23:49

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.