3
$\begingroup$

For a matrix $c (m\times n)$ of non-negative constants, find values of $\lambda_1, \lambda_2, \ldots, \lambda_n$ that satisfy $\sum_{k=1}^n \lambda_k = 1$, $\lambda_k \ge 0 \, \forall k$ and maximize

\begin{equation*} L = \sum_{i=1}^m \log \sum_{k=1}^n \lambda_k c_{i,k} \end{equation*}

Improve this question
$\endgroup$
5
  • $\begingroup$ Where does this come from? $\endgroup$
    – Igor Rivin
    Commented May 6, 2015 at 10:15
  • $\begingroup$ I am on a project relating to machine learning. I need to find lambda values that best match data, constant matrix c in this case $\endgroup$
    – Vuong Bui
    Commented May 6, 2015 at 10:21
  • 1
    $\begingroup$ This is a concave maximization problem, just use any convex optimization approach... $\endgroup$
    – Suvrit
    Commented May 6, 2015 at 12:50
  • $\begingroup$ I will study more. Can you recommend some method that is suitable for this problem? Does it converge in this case? $\endgroup$
    – Vuong Bui
    Commented May 9, 2015 at 7:54
  • 1
    $\begingroup$ Try using cvxr.com on some small problems to get an idea. $\endgroup$
    – Suvrit
    Commented May 9, 2015 at 15:51

1 Answer 1

Reset to default
1
$\begingroup$

Not an answer, but an extended comment.

The problem is equivalent to maximizing $$e^L = \prod_{i=1}^m \sum_{k=1}^n \lambda_k c_{i,k}.$$

By the AGM inequality, we have $$e^L \leq \left( \frac{1}{m} \sum_{i=1}^m \sum_{k=1}^n \lambda_k c_{i,k} \right)^m = \left( \frac{1}{m} \sum_{k=1}^n \lambda_k C_k\right)^m,$$ where $C_k = \sum_{i=1}^m c_{i,k}$.

It is easy to maximize this upper bound. Namely, $$\sum_{k=1}^n \lambda_k C_k \leq \max_k C_k = C_{k_0},$$ where equality can be achieved by taking $\lambda_{k_0} = 1$ and all the other $\lambda$'s equal 0. Therefore, $$e^L \leq \left( \frac{C_{k_0}}{m} \right)^m$$ and thus $$L \leq m\log \frac{C_{k_0}}{m}.$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very interesting, thanks a lot. But in our application, $n$ is so small, while $m$ is much greater than n, so the equality condition of the AGM inequality rarely occurs. Futher more, I am interested in the $\lambda$ values, not the maximum L values. However, thanks for the upper bound. $\endgroup$
    – Vuong Bui
    Commented May 10, 2015 at 1:55
  • 1
    $\begingroup$ @Vuong Bui: This analysis suggests that $\lambda$'s should be biased towards the indices $k$ with large column sums $C_k$. $\endgroup$
    – Max Alekseyev
    Commented May 10, 2015 at 3:47

You must log in to answer this question.

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