6
$\begingroup$

Consider the following system of $n$ equations:

\begin{equation}f_j^2 = x_j^2\sum_{i=1}^n A_{ij} f_i \tag{$\star$} \end{equation}

where $A_{ij}\geq 0$ are known constants and where $x_j>0$ for all $j$. I am interested in the concavity properties (log-concavity or quasi-concavity) of $f_j$ as a function of the vector $x$. In general, $f_j$ is not concave.

Under what conditions on the $A_{ij}$'s is $f_j$ a log-concave or quasi-concave function of the vector $x$?

A few observations:

  1. The system has a trivial solution at $f=0$. Taking the square root on both sides of the equation, we can use Theorem 3 in this note to find that there is a unique non-trivial positive solution $f$ for a given $x$.
  2. The same note shows that we can reach this solution by iterating on the mapping. Therefore, if we start with log-concave (for instance) functions and keep iterating we should converge to a log-concave solution if the mapping preserves log-concavity. Sadly, summation does not preserve log-concavity (or quasi-concavity).
  3. By iterating on the mapping we get the following nested radicals structure $$f_j=x_j\sqrt{\sum_lA_{lj}x_l\sqrt{\sum_iA_{il}x_i\sqrt{\dots}}}$$
  4. $f$ is homogeneous of degree 2 in $x$. There are some results about the concavity of homogenous polynomial (see for instance the top of page 127) but again they do not apply directly here. Maybe another version of these results would?
  5. In simple cases in which we can solve the problem by hand, I find log-concave solutions. For instance, with $A_{ij}=1$ if $i=j$ and 0 otherwise we get $f_j=x_j^2$ which is log-concave. I am hoping that this is a general property of the solution.

Motivation:

  • I am interested in the optimization problem $$ \max_{0\leq x_j\leq 1,\,\forall j} \log\left(\sum_{j=1}^n f_j(x)\right)+\log\left(L-\sum_{j=1}^n x_j\right) $$ where $f_j$ satisfies equation $\star$ above and where $L>n$.
  • Understanding the concavity of $f_j$ is a step in understanding the concavity of the objective function.
  • It is possible to replace the equality in $\star$ by $\leq$ and consider an optimization problem with respect to both $f$ and $x$ with the modified equation $\star$ as a constraint.
  • One restriction that would natural in the context of my problem would be to set $A_{ii}=0$ for all $i$.

Please feel free to assume additional assumptions on the problem if needed.

Improve this question
$\endgroup$
11
  • $\begingroup$ What's the question in your post ? $\endgroup$
    – dohmatob
    Sep 13, 2016 at 8:47
  • $\begingroup$ @dohmatob Under what conditions on the $A_{ij}$'s is $f_j$ a log-concave or quasi-concave function of the vector $x$. I've edited the question for clarity. $\endgroup$
    – user_lambda
    Sep 13, 2016 at 12:59
  • $\begingroup$ Cute question but I'm curious if you have tried the "brain-free" approach (i.e., numerical simulations) already, and, if you have, what it indicated. $\endgroup$
    – fedja
    Sep 21, 2016 at 21:43
  • 2
    $\begingroup$ The system $f^2=x^2(2f+1g), g^2=y^2(0f+1g)$ has solution $f=x(x+\sqrt{x^2+y^2})$, which is not quasi-concave near the $x$-axis, so down the drain goes the hope that the quasi-concavity property is universal. At this point you'd rather tell what you really need if you want the further discussion to be reasonably productive... $\endgroup$
    – fedja
    Sep 22, 2016 at 3:29
  • 1
    $\begingroup$ Well, we have already figured out that it isn't in general, so that won't work. Moreover, even in some cases when the individual $f_j$ are good (say, $A=I$), the compound expression you have may be bad. This leaves very little chance for showing anything like what you've requested unless your $A$ is some very special matrix. If so, what is it? $\endgroup$
    – fedja
    Sep 23, 2016 at 19:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.