1
$\begingroup$

Let us be given a function $f(x_1,\dots,x_{10})$ of multiple variables $x_1,\dots,x_{10}$ given that $\sum_{i=1}^{10} x_i \leq 7$. How do we solve the following problem?

$$ \begin{equation} \begin{aligned} \max_{\{x_i\}, i=1,\dots,10} \quad & f(x_1,\dots,x_{10})\\ \textrm{s.t.} \quad & \sum_{i=1}^{10} x_i \leq 7\\ & x_i \in X_i, X_i = [0,10] \\ \end{aligned} \end{equation} $$

I with my professor are trying to work on building a neural network in such a way that we have multiple output from each layer. For example there are $n$ neurons in the $i^{th}$ layer, there will be, let us say $k$ outputs of each size $n$. Similarly, the next layer will also have same number of output and we will look at all the possible ways to connect $k$ outputs of the $i^{th}$ layer and $k$ outputs of the $(i+1)^{st}$ layer. And we take the max of the output in each layer while updating the loss function. My professor told me that this boils down to finally become a DP problem.

Improve this question
$\endgroup$
9
  • $\begingroup$ Any additional information, such as the contribution of each $x_i$ is independent of all $x_j, j\ne i$ or all $x_i$s are integral? $\endgroup$
    – greybeard
    May 10 at 18:42
  • 1
    $\begingroup$ If the variables are integers, there are only 19448 options to try. $\endgroup$
    – Yuval Filmus
    May 10 at 18:52
  • $\begingroup$ Please edit the question to indicate whether the variables must be integers, or if not, what domain they come from. $\endgroup$
    – D.W. ♦
    May 13 at 6:32
  • $\begingroup$ "$k$ outputs of each size $n$": what ?? $\endgroup$
    – Yves Daoust
    May 13 at 8:42
  • $\begingroup$ If all $X_i$ are identical, why $i$ ? And due to the sum and positiveness constraints, $x_i\le 7$ must hold anyway. $\endgroup$
    – Yves Daoust
    May 13 at 8:43

2 Answers 2

Reset to default
1
$\begingroup$

There are only 19448 combinations of $x$'s that meet the constraints. If $f$ is arbitrary, the best you can do is enumerate all 19448 combinations and see which leads to the largest value of $f$. There is no faster algorithm. Dynamic programming does not seem relevant.

If you know something about the structure of $f$ (e.g., it is a separable function), then it might be possible to do better.

Improve this answer
$\endgroup$
0
$\begingroup$

I do not see a dynamic programming solution. I highly doubt there is one (especially, a polynomial time).

Improve this answer
$\endgroup$

Your Answer

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

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