So suppose we have a set of vectors $X$ and we want to approximate the maximum of the following:

$\prod_{x \in X} b \cdot x$

where the components of $b$ sum to $1$

If it matters the components of each $x$ sum to $1$ as well.

What algorithm would you use to do this?

Sorry if this belongs on the mathematics exchange, I was stuck between the two

  • $\begingroup$ Are you familiar with linear programming? $\endgroup$ – Pål GD Mar 30 '19 at 21:43
  • 1
    $\begingroup$ Yes. But this objective function is nonlinear isn't it? $\endgroup$ – Justin Perez Mar 30 '19 at 23:56
  • $\begingroup$ Interesting problem! The mention that you want to approximate the maximum makes me think you might be asking from a practical perspective. If so, can you share any information about typical problem parameters (e.g., number of dimensions, size of the set $X$)? Have you considered trying some generic method like gradient descent or Newton's method? $\endgroup$ – D.W. Mar 31 '19 at 17:26
  • $\begingroup$ Thanks! The size of $X$ in my application is around 10, and the dimensions of the vectors are around 500. I had not considered gradient descent since I was both unsure of how to calculate the derivative of a function like this where the size of set of vectors is not known before hand, and also because I was not sure that there was guaranteed to be only one local maximum. I had not considered newton's method since I thought that method was designed to find roots not maxima. I was leaning towards was some kind of Monte Carlo approximation of the maximum, but I was unsure of how to go about this. $\endgroup$ – Justin Perez Mar 31 '19 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.