0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}} $$

$\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.