Maximizing summation given a constraint

1,347

In general, if you want to optimize the differentiable function $f$ subject to a single linear constraint $\mathbf{b} \cdot \mathbf{x}=0$, the optimal point should satisfy $\nabla f(\mathbf{x}^*)=s\mathbf{b}$ for some scalar $s$. Geometrically this means that, if you consider the constraint to be a plane, the gradient must be normal/perpendicular to that plane.

In this case, the equations can be solved in closed form. I'm assuming that $c_k >1$ and you're looking for the maximum such that $x_k \in (-c_k,+\infty)$. Otherwise the function is potentially unbounded and no finite maximizer exists. $$ \begin{aligned} f(\mathbf{x}) &= \sum_{k=1}^n \frac{a_k c_k}{b_k}\left(1 - \frac{c_k-1}{x_k+c_k}\right)\\ (\nabla f(\mathbf{x}))_k &= \frac{a_k c_k(c_k-1)}{b_k(x_k+c_k)^2} \end{aligned} $$ Letting $(\nabla f(\mathbf{x}))_k = s b_k$, and solving for $x_k$ gives $x_k = -c_k+ \sqrt{\frac{a_k c_k (c_k-1)}{s b_k^2}}$. Then to simplify, let $d=1/\sqrt{s}$. Solve for $d$ by enforcing the linear constraint, giving the final answer:

$$ \boxed{ \begin{aligned} x_k &= -c_k+d \frac{\sqrt{a_k c_k (c_k-1)}}{b_k}\\ d&=\frac{\sum_{k=1}^n b_k c_k}{\sum_{k=1}^n \sqrt{a_k c_k (c_k-1)}} \end{aligned}} $$

Share:
1,347

Related videos on Youtube

tjc59
Author by

tjc59

Updated on August 01, 2022

Comments

  • tjc59
    tjc59 over 1 year

    I am writing a software-based algorithm to calculate an optimal solution and I am completely stuck. I need to maximize the following summation with respect to x:

    $ \sum_{k=1}^n {a_k(1+x_k) \over b_k(1+ x_k/c_k)} $ where $ a_k (0:1), c_k (0:\infty) $ and $b_k(0:\infty)$ are all constants.

    I am subject to the following constraint:

    $ \sum_{k=1}^n b_k*x_k$ = 0

    I have found the derivative of my equation, but I am having trouble figuring out how to calculate a solution for all values of n.

    Any help or advice you could provide would be greatly appreciated! Thanks in advance.