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*}

$\endgroup$
5
  • $\begingroup$ Where does this come from? $\endgroup$
    – Igor Rivin
    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
    May 6, 2015 at 10:21
  • 1
    $\begingroup$ This is a concave maximization problem, just use any convex optimization approach... $\endgroup$
    – Suvrit
    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
    May 9, 2015 at 7:54
  • 1
    $\begingroup$ Try using cvxr.com on some small problems to get an idea. $\endgroup$
    – Suvrit
    May 9, 2015 at 15:51

1 Answer 1

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}.$$

$\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
    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$ May 10, 2015 at 3:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.