I'm trying to apply the gradient method in this video to a polynomial of degree 3: https://www.youtube.com/watch?v=yuqB-d5MjZA
I understood a case when this method was successfully applied to a logarithmic objective function, but this degree 3 polynomial gives me headaches (I'm an IT person). First I'm not even sure that this method can be applied here, since the objective function can be concave.
The problem:
Maximize over the $x_n$ variables: $$f(x) = \sum_{n=1}^{N}{\left. {a_n} {{{x_n}}^{3}}+{b_n} {{{x_n}}^{2}}+{c_n} {x_n}+{d_n}\right.}$$
Where $$g(x) = \sum_{n=1}^{N}{\left. {x_n}\right.} = C \ \ \ \ is \ a \ constant$$
and the $a_n, b_n, c_n, d_n$ values are constants, and $x_n ≥ 0$
With the gradient method: ∇f(x) = λ ∇g(x)
Where:
$\mbox{}\\∇f(x) = \begin{pmatrix}3 {a_1} {{{x_1}}^{2}}+2 {b_1} {x_1}+{c_1}\\ 3 {a_2} {{{x_2}}^{2}}+2 {b_2} {x_2}+{c_2}\\ ...\\ 3 {a_N} {{{x_N}}^{2}}+2 {b_N} {x_N}+{c_N}\end{pmatrix}$ $ \ \ \ ∇g(x) = \begin{pmatrix}1\\ 1\\ ...\\ 1\end{pmatrix}$
From which follows:
$$3 {a_n} {{{x_n}}^{2}}+2 {b_n} {x_n}+{c_n}-\lambda =0$$
Now would come the part when I express $x_n$ from the above equation and substitute it into the restriction for the $x_n$ sum. But the roots are hideous:
${x_n}=-\frac{\sqrt{3 {a_n} \lambda -3 {a_n} {c_n}+{{{b_n}}^{2}}}+{b_n}}{3 {a_n}} \ $ and $ \ {x_n}=\frac{\sqrt{3 {a_n} \lambda -3 {a_n} {c_n}+{{{b_n}}^{2}}}-{b_n}}{3 {a_n}}$
My first problem is the multiple roots. Should I try all $2^n$ combinations of the minus/plus versions? My second problem is that I cannot extract the lambdas from under the square root (after the substitution).
Could someone give me some hint how to solve this optimization problem?
(I give an example use case: $x_n$ are the amounts of money spent on certain advertisements. The polynomials are trend lines for specific advertisements (including their targeting), which predict the number of clicks for certain spend amounts, based on past samples. Task is to distribute budget C among all advertisements in a way that maximizes the total number of clicks.)
UPDATE: I've simplified the problem to sum of polynomials.
The method of Lagrange multipliers can be be used whenever you need to extremise a function subject to a constraint (see Wikipedia for proofs).
With these sorts of problems, once you get the expression for $$\nabla f(x) - \lambda \nabla g(x),$$ it’s time to be clever. In particular, in this case, you get $$3 a_n x_n^2+ 2 b_n x_n + c_n - \lambda = 0.$$ As you’ve pointed out, this is not easy to solve. However, since $\lambda$ can only take one value, this tells us that the $x_n$ can only take one of two predetermined values, say $A$ and $B$ (with, let’s say, $A\leq B$). Which of the two values do we want?
The $2^n$ possibilities you mention arise since they all represent extreme points (also known as stationary points) of your $f$. However, since you’re asking to maximise $$f(x) = \sum_{n=1}^N a_n x_n^3 + b_n x_n^2 + c_n x_n + d_n,$$ we can look at which of $A$ or $B$ does so. So long as even one of them is positive — which holds since $x_n \geq 0$ —, I claim the maximiser of $a_n x_n^3 + b_n x_n^2 + c_n x_n + d_n$ and hence of $f$ is going to be $B$. (Why?)
If that’s the case, then, we get that $\forall n\ \ x_n = B.$ You can now use the constraint to fix $x_n= C/n$, since all of the $x_n$ are the same.