Finding a function that give the optimal value for an expression

Question

I'm trying to optimize the following equation: $$\mathrm{argmax}_{f}\left\{ \sum_{i=1}^{n}\left(n-i+1\right)f\left(i\right)^{2}\cdot c_{i}+\sum_{i=1}^{n}\left(n-i\right)f\left(i\right)|\sum_{t=1}^{n}f\left(t\right)=0\text{ and }\sum_{t=1}^{n}f\left(t\right)^{2}=k\right\} $$

I need to find a function $f:[n]\rightarrow\{-1,0,1\}$ such that I meet the constraints, And $c_i$ is another parameter that is dependent on $i$, and $k\in[n]$.

I am not too sure how to even approach this, maybe I should use some machine learning algorithm, I am not looking for an answer just maybe a nudge in the correct direction to how one approaches a problem like this. Thanks

Answer 1

I am not sure which is the best solution but below I will describe an approach based on Dynamic Programming that will be able to compute the answer in $O\left(n^4\max_i|c_i|\right)$ (which may be even reduced to $O\left(n^3\max_i|c_i|\right)$ if you ignore the sum $(S)$ dimension in the following states).

Below I assume that $k$ and $(c_i)$ are given beforehand.

---

Let $$F(f) = \sum_{i=1}^n (n-i+1)f(i)^2 c_i + \sum_{i=1}^n (n-i)f(i),\quad \text{for a function } f:[n]\to\{-1,0,1\}$$ Notice that \begin{align} F(f) = (n+1)\sum_{i=1}^n f(i)^2 c_i + n \sum_{i=1}^n f(i) - \sum_{i=1}^n \left(if(i)^2c_i +if(i) \right) \end{align}

This is the expression you want to maximize under some constraints. Suppose that \begin{align} G(N, C, S, W) &= \max_{f:[N]\to\{-1, 0, 1\}}\left(F(f)\quad\Big|\quad \sum_{t=1}^N f(t) = S\ \land\ \sum_{t=1}^N f(t)^2 = C\ \land \ \sum_{i=1}^N f(i)^2 c_i = W\right) \\ &= \max_{f:[N]\to\{-1, 0, 1\}}\left((N+1)W + NS -\sum_{i=1}^N (if(i)^2c_i + if(i))\quad\Big|\\\quad \sum_{t=1}^N f(t) = S\ \land\ \sum_{t=1}^N f(t)^2 = C\ \land \ \sum_{i=1}^N f(i)^2 c_i = W\right) \end{align}

and let $G_A(N, C, S, W)$ be the set of functions that achieve the maximum. Let's name the set $\mathcal{F}(S,C,W)$ as follows for simplicity $$\mathcal{F}(N,S,C,W) = \{f:[N]\to\{-1,0,1\}\quad\Big|\quad \sum_{t=1}^N f(t) = S\ \land\ \sum_{t=1}^N f(t)^2 = C\ \land \ \sum_{i=1}^N f(i)^2 c_i = W\}$$ i.e the set of functions under the constaints $N, S,C,W$. So now $$G(N, C, S, W) = \max_{f\in\mathcal{F}(N,S,C,W)}(F(f))$$

Obviously you want to find a function of $$A = \bigcup_{w} G_A(n, k,0,w)$$ where $w$ iterates through all the possible values (which are bounded below by $-\sum c_i$ and above by $\sum c_i$)

---

Basically $G(N,C,S,W)$ is the best answer of $F(f)$ over all functions $f$ such that we consider $n=N$ in our problem and $C,S,W$ are some conditions over the functions. We previously saw that we can retrieve the answer iterating through all the parameters $N, C,S,W$ that we want (which are of the form $n, k, 0, w$ for some $w$).

Now this representation is important because knowing the parameters $N,C,S,W$ of a state (and obviously $G(N,C,S,W)$) we can easily compute the value of neighboring states. In other words, the functions can be computed recursively. Namely \begin{align} G(N, C,S, W) = \max_{f\in\mathcal{F}(N,S,C,W)}& \left((N+1)W + NS -\sum_{i=1}^N (if(i)^2c_i + if(i)\right)\\ =\max &\Big\{\max_{f\in\mathcal{F}(N,S,C,W);f(N)=0} \left((N+1)W + NS -\sum_{i=1}^N (if(i)^2c_i + if(i)\right) \\ &,\max_{f\in\mathcal{F}(N,S,C,W);f(N)=1} \left((N+1)W + NS -\sum_{i=1}^N (if(i)^2c_i + if(i)\right) \\ &,\max_{f\in\mathcal{F}(N,S,C,W);f(N)=-1} \left((N+1)W + NS -\sum_{i=1}^N (if(i)^2c_i + if(i)\right)\Big\} \\ =\max &\Big\{G(N-1,C, S, W) + W + S \\ &,G(N-1, C-1, S-1, W-c_N )+W+S-1 \\ &,G(N-1, C-1, S+1, W-c_N) + W+S+1\Big\} \end{align}

---

Even if I did the calculations incorrectly the core idea is the same, computing the new value is easy given that you have the parameters $N',C',S',W'$. So if you decide to start comptuing $G(N, \cdot,\cdot,\cdot)$, you just look at the values/states of $G(N-1,\cdot,\cdot,\cdot)$ and you take cases upon the value of $f$ at $N$, $f(N)$, which only has $3$ possible values.

The neighboring states of $N,C,S,W$ are

• $N-1, C, S, W$, because by choosing $f(N)=0$, states of $N-1, C, S, W$ end up in $N,C,S,W$
• $N-1, C-1, S-1, W-c_N$, because with $f(N)=1$, states $N-1, C-1, S-1, W-c_N$ end up in $N,C,S,W$
• $N-1, C-1, S+1, W-c_N$, because with $f(N)=-1$, states $N-1, C-1, S-1, W-c_N$ end up in $N,C,S,W$

For computing $G_A(N,C,S,W)$ you can do something similar (comparing the previous states and seeing which previou state (perhaps all three) gives the maximum value of $G(N,C,S,W)$ and take their union.