Optimisation problem (non-linear)

99 Views Asked by At

Having the following constants: $C$, $N_k (1\le k \le K)$ and $\lambda_{k,i}(1\le k \le K, 1 \le i \le N_k)$ in which: $\lambda_{k,i} > \lambda_{k,j} \quad 1 \le i < j \le N_k \quad1\le k \le K $

I have the following optimisation problem.

\begin{equation} \underset{C_1,\dots,C_K}{\text{maximize}} \sum_{k=1}^{K} h_k(C_k) \quad \text{[1]} \end{equation}

\begin{equation} \text{subject to:} \sum_{k=1}^{K} C_k= C \quad\text{[2]} \end{equation}

in which: \begin{equation} h_k(C_k) = \sum_{i=1}^{N_k}\lambda_{k,i}(1-e^{-\lambda_{k,i}\tau_k(C_k)}) \quad \text{[3]} \end{equation}

and $\tau_k(C_k)$ could be found as following: \begin{equation} \sum_{i=1}^{N_k}(1-e^{-\lambda_{k,i}\tau_k(C_k)})=C_k \quad \text{[4]} \end{equation}


EDIT: I've added my efforts and progress towards an answer below.

We can write Lagrange function as follows:

\begin{equation} \mathcal{L}(h,\alpha)=\sum_{k=1}^{K} h_k(C_k) - \alpha(\sum_{k=1}^{K} C_k- C)=0 \quad \text{[5]} \end{equation}

where $\alpha$ is the Lagrange multiplier. In order to achieve the maximum in $\mathcal{L}(h,\alpha)$, the $h_k(C_k)$ functions should satisfy:

\begin{equation} \frac{\partial\mathcal{L}}{\partial {C_k}}=\frac{dh_k({C_k})}{d{C_k}}-\alpha=0 \quad \text{[6]} \end{equation}

Let $h_k^{\prime}(\cdot)$ denote the derivative of the the function $h_k(\cdot)$, and define ${h_k^{\prime}}^{-1}(\cdot)$ as its inverse function. From [6] we get:

\begin{equation} h_k^{\prime}({C_k})=\alpha \quad \text{[7]} \end{equation}

Or equivalently

\begin{equation} {h_k^{\prime}}^{-1}(\alpha)=C_k \quad \text{[8]} \end{equation}

Applying the constraint in [2], we obtain: \begin{equation} \sum_{k=1}^{K} C_k= \sum_{k=1}^{K} {h_k^{\prime}}^{-1}(\alpha)=C \quad \text{[9]} \end{equation}

and $\alpha$ can be computed by solving the fixed-point equation given above.

Using [3] and [7] results in:

\begin{equation} h_k^{\prime}({C_k})= \frac{\partial\tau_k(C_k)}{\partial C_k}\sum_{i=1}^{N_k}\lambda_{k,i}^{2}e^{-\lambda_{k,i} \tau_k(C_k)} = \alpha \quad \text{[10]} \end{equation}

$\frac{\partial\tau_k(C_k)}{\partial C_k}$ in [10] could be obtained using [4] as follows:

\begin{equation} \frac{\partial}{\partial C_k} \big(\sum_{i=1}^{N_k}(1-e^{-\lambda_{k,i}\tau_k(C_k)})\big)= \frac{\partial C_k}{\partial C_k}\quad \text{[11]} \end{equation}

which could be simplified to :

\begin{equation} \frac{\partial\tau_k(C_k)}{\partial C_k} = \frac{1}{ \sum_{i=1}^{N_k} \lambda_{k,i}e^{-\lambda_{k,i}\tau_k(C_k)}}\quad \text{[12]} \end{equation}

Using [12] in [10] gives us: \begin{equation} h_k^{\prime}({C_k})=\frac{1}{ \sum_{i=1}^{N_k} \lambda_{k,i}e^{-\lambda_{k,i}\tau_k(C_k)}}\sum_{i=1}^{N_k}\lambda_{k,i}^{2}e^{-\lambda_{k,i} \tau_k(C_k)} = \alpha \quad \text{[13]} \end{equation}

Here, if we can find ${h_k^{\prime}}^{-1}(\alpha)=C_k$ as mentioned above in [7], we then can find $\alpha$ through [9]. I got stuck here. any idea?

1

There are 1 best solutions below

0
On

So, its obvious that $h_k^{\prime}(C_k) > 0$.

Having

\begin{equation} \frac{d^2h_k(C_k)}{dC_k^2} = \sum_{i=1}^{N_k}\lambda_{k,i}^2e^{-\lambda_{k,i}\tau_k(C_k)}g_{k,i} \quad \text{[14]} \end{equation}

in which

\begin{equation} g_{k,i} := \frac{d^2\tau_k(C_k)}{dC_k^2} - \lambda_{k,i}\big(\frac{d\tau_k(C_k)}{dC_k}\big)^2 \quad \text{[15]} \end{equation}

having our assumption in the question ($\lambda_{k,1}>\lambda_{k,2}>\dots>\lambda_{k,N_k}$) it is not difficult to show that:

\begin{equation} \frac{d^2h_k(C_k)}{dC_k^2} \le 0 \quad \text{[16]} \end{equation}

Assuming \begin{equation} \alpha = f_k(\tau_k) = \frac{1}{ \sum_{i=1}^{N_k} \lambda_{k,i}e^{-\lambda_{k,i}\tau_k}}\sum_{i=1}^{N_k}\lambda_{k,i}^{2}e^{-\lambda_{k,i} \tau_k} \quad \text{[17]} \end{equation} We only need to find $\alpha$ in a way that constraint [2] is met. It is possible if numerical techniques are used. So, since $\alpha>0$ and $\alpha$ is a decreasing function of $\tau_k$ as mentioned in [16], the maximum and minimum values of $\alpha$ could be obtained. Then $\alpha$ could be found using bisection method.

So, we have $\alpha_0$ in the beginning, then we can obtain $\tau_k$ for $1\le k \le K$ from [17] using numerical methods such as Newton's method. After finding $\tau_k$, the $C_k$ could be easily calculated through [4]. Then, if constraint [2] is not met, $\alpha_1$ is calculated using bisection method and so on.