4
$\begingroup$

Let $f:~ [0,1]^3 \rightarrow \mathbb{R}$ be

$$ f(x_0,x_1,x_2)= \log \left[ \left(1+\frac{x_0}{1+x_0+\frac{x_1}{2}+\frac{x_2}{4}}\right) \left(1+\frac{x_1}{1+x_1+\frac{x_2}{2}+\frac{x_0}{4}}\right) \left(1+\frac{x_2}{1+x_2+\frac{x_0}{2}+\frac{x_1}{4}}\right) \right]. $$

My guess is that $f$ is a concave function. The standard approach to prove multivariate concavity is to find the Hessian matrix and prove that it is non-positive definite. However, it seems to be an overwhelming approach for this function. Can we somehow use the structure of $f$ to prove or disprove the concavity?

Edit1: The general form is $f:~ [0,1]^n \rightarrow \mathbb{R}$ $$ f(x_0,x_1,\ldots,x_{n-1})= \log \left[ \prod_{k=0}^{n-1}\left(1+\frac{x_k}{1+\sum_{j=0}^{n-1}q^jx_{(k+j)~\text{mod}~n}}\right) \right], 0<q<1. $$

Edit2: I changed the notation and started the indices from zero to make the general case accurate.

Improve this question
$\endgroup$
15
  • 3
    $\begingroup$ Did you write down the minors of Hessian matrix? It may be ugly, but working. $\endgroup$
    – Fedor Petrov
    Commented Jun 29, 2018 at 17:01
  • 2
    $\begingroup$ And likewise for $n$ variables, $\log\prod_{k=1}^n(1+\frac{x_k}{ 1+\sum_{j=1}^{n-1} q^jx_{k+j}})$ with indexes cyclically mod $n$. $\endgroup$
    – Wolfgang
    Commented Jun 29, 2018 at 19:12
  • 1
    $\begingroup$ Interestingly, looking at is as f(x) = f1(x) + f2(x) + f3(x), then f1(x), f2(x), f3(x) are not concave individually, but their sum is, so they all combine perfectly to produce concavity $\endgroup$
    – Mark L. Stone
    Commented Jun 29, 2018 at 19:16
  • 2
    $\begingroup$ Should be $\log\prod_{k=1}^n(1+\frac{x_k}{ 1+\sum_{j=0}^{n-1} q^jx_{k+j}})$ $\endgroup$
    – Wolfgang
    Commented Jun 29, 2018 at 19:30
  • 2
    $\begingroup$ Bonus points to whoever can figure out how (I'm not saying it can be done) to model f(x) using a combination of exponential and (rotated) quadratic cones, thereby allowing it to be entered and used in CVX. This would also prove concavity for general n. See, for example, sections 5.1 and 5.2 of MOSEK Modeling Cookbook docs.mosek.com/MOSEKModelingCookbook-letter.pdf . $\endgroup$
    – Mark L. Stone
    Commented Jun 29, 2018 at 21:13

1 Answer 1

Reset to default
6
$\begingroup$

Maple 2018 does it by

restart; 
 A := log((1+x[1]/(1+x[1]+(1/2)*x[2]+(1/4)*x[3]))*(1+x[2]/(1+x[2]+
(1/2)*x[3]+(1/4)*x[1]))*(1+x[3]/(1+x[3]+(1/2)*x[2]+(1/4)*x[3]))):
H := VectorCalculus:-Hessian(A, [x[1], x[2], x[3]]):
LinearAlgebra:-IsDefinite(H, query = 'negative_semidefinite')
assuming x[1]>=0,x[1]<=1,x[2]>=0,x[2]<=1,x[3]>=0,x[3]<=1;

true

Addition. Maple cracks the Wolfgang's modification too, but only for concrete values of $n$:

restart; n := 25: xx := [seq(x[j], j = 1 .. n)]:
A := log(mul(1+x[k]/(1+add(q^j*x[k+j], j = 0 .. n-1)), k = 1 .. n)):
H := VectorCalculus:-Hessian(A, xx):
LinearAlgebra:-IsDefinite(H, query = 'negative_semidefinite')
assuming seq(x[s]>=0,s=1..n),seq(x[s]<=1,s=1..n),q>0,q<1

true

Improve this answer
$\endgroup$
1
  • $\begingroup$ Could you define the new general form with modulo function in Maple? $\endgroup$
    – James
    Commented Jul 2, 2018 at 2:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .