Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Showing convexity of a discrete function

  1. Jun 14, 2014 #1
    Suppose we have a function ##f:\mathbb{N}\times\mathbb{N}\to\mathbb{R}_+## that is
    • increasing: ##f(x+e_i)\geq f(x)## for any ##x\in\mathbb{N}^2## and ##i\in\{1,2\}##;
    • convex: ##f(x+2e_i)-f(x+e_i)\geq f(x+e_i)-f(x)## for any ##x\in\mathbb{N}^2## and ##i\in\{1,2\}##.
    How could one show that a function ##g(x):=cf(x)-\max\{c_1\left(f(x)-f(x-e_1)\right),c_2\left(f(x)-f(x-e_2)\right)\}## for ##c=\max\{c_1,c_2\}## (##c_1,c_2\geq0##) is also convex wrt definition above?
     
  2. jcsd
  3. Jun 14, 2014 #2

    verty

    User Avatar
    Homework Helper

    Have you tried substituting g into that convexity inequality?
     
  4. Jun 16, 2014 #3
    So far I did case-by-case analysis branching on terms, at which maxima for ##f(x+2e_i)##, ##f(x+e_i)## and ##f(x)## are achieved. Six of eight cases went rather smooth, but two cases are giving me problems.

    Case 1:
    Case 2:
    I guess the proof lies in rearranging the terms in a smart way and then applying the assumptions and properties. One can also use that ##f## is also supermodular, that is ##f(x+e_1+e_2)+f(x)\geq f(x+e_1)+f(x+e_2)## for any ##x\in\mathbb{N}^2##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Showing convexity of a discrete function
  1. Convex function (Replies: 2)

Loading...