上に凸な問題なんてないでしょ。ultralinearということだものね。
定数O(1)を除けば線形O(n)が最善で、あとはO(n log n)、O(n^2)、
多項式、指数とふつう区分が問題なのは全部下に凸だよね。だから
上に凸とか下に凸とか問題にしてもあまり意味がない。