If I have an optimization problem as follows:
\begin{equation}
\label{eqn:for3b}
\begin{aligned}
(\mathbf{P}_1) \phantom{10} & \max_{\boldsymbol{x}} \phantom{5} \text{ln}\Bigg(1 + \sum_{i=1}^Ix_ia_i\Bigg) – \sum_{i=1}^Ix_ib_i.
\end{aligned}
\end{equation}
\begin{eqnarray}
\text{ s.t. } \quad \sum_{i=1}^I x_i a_i \leq N, \label{eqn:for3c} \\
0 \leq x_i \leq 1, \forall i \in [1, I]
\end{eqnarray}
how to find the optimal solution formula of $x_i, \forall i \in [1,I]$? As far as I understand, we need to obtain Lagrangian expression first:
\begin{equation}
\label{eqn:for3a}
\begin{aligned}
L(x,\lambda,\sigma) &= \text{ln}\Bigg(1 + \sum_{i=1}^Ix_ia\Bigg) – \sum_{i=1}^Ix_ib + \lambda_1(N – \sum_{i=1}^I x_i a_i – \sigma_1) + \lambda_2(x_1 – \sigma_2) \\
&+ \lambda_3(1 – x_1 – \sigma_3) + … + \lambda_{I+1}(x_I – \sigma_{I+1}) + \lambda_{I+2}(1 – x_I – \sigma_{I+2}).
\end{aligned}
\end{equation}
However, since it has many $x$'s, how can I obtain the general optimal $x^*_i, \forall i \in [1,I]$ formula? I also think that I can use the relaxation solution of Knapsack problem. However, due to the variables are within the logarithmic formula, is there any possible way to solve it analytically?
Find an optimal solution formula analytically when the variables are within natural logarithm
optimizationpartial derivative
Best Answer
You will need to use the Karush-Kuhn-Tucker conditions. The linearity constraint qualification (LCQ) holds since all the constraints are linear.
Expressing the problem vectorially is perhaps more helpful, which gives $$\begin{align*}\max_{\boldsymbol x}\quad&\ln(1+\boldsymbol a^\top \boldsymbol x)-\boldsymbol b^\top \boldsymbol x\\ \text{s.t.}\quad&\boldsymbol a^\top \boldsymbol x-N\leq 0&[\lambda]\\ &\boldsymbol x-\boldsymbol e\leq \boldsymbol 0&[\boldsymbol\mu]\\ &\boldsymbol -\boldsymbol x\leq \boldsymbol 0&[\boldsymbol\nu] \end{align*}$$
KKT necessary conditions on an optimum $\boldsymbol x^*$ are $$\begin{align*} \frac{1}{1+\boldsymbol a^\top \boldsymbol x^*}\boldsymbol a-\boldsymbol b=\lambda\boldsymbol a+\boldsymbol\mu-\boldsymbol \nu&&\text{Stationarity}\\ \boldsymbol a^\top \boldsymbol x^*-N\leq 0&&\text{Primal Feasibility}\\ \boldsymbol x^*-\boldsymbol e\leq \boldsymbol 0&&\text{Primal Feasibility}\\ \boldsymbol -\boldsymbol x^*\leq \boldsymbol 0&&\text{Primal Feasibility}\\ \lambda\geq 0 &&\text{Dual Feasibility}\\ \boldsymbol\mu\geq \boldsymbol 0 &&\text{Dual Feasibility}\\ \boldsymbol\nu\geq \boldsymbol 0 &&\text{Dual Feasibility}\\ \lambda[\boldsymbol a^\top \boldsymbol x^*-N]=0&&\text{Complementarity}\\ \boldsymbol\mu^\top[\boldsymbol x^*-\boldsymbol e]=\boldsymbol 0&&\text{Complementarity}\\ \boldsymbol\nu^\top[-\boldsymbol x^*]=\boldsymbol 0&&\text{Complementarity} \end{align*}$$
The stationarity conditions give a linear system of equations $A\boldsymbol x^*=\boldsymbol d$ where $\boldsymbol d=(1-\lambda)\boldsymbol a -\boldsymbol \mu+\boldsymbol \nu-\boldsymbol b$ and $A=(\boldsymbol a-\boldsymbol d)\boldsymbol a ^\top$. So If there is a solution, it would be at $\boldsymbol x^*=A^{-1}\boldsymbol d$.
Then we just need to determine the dual variables $\lambda$, $\boldsymbol \mu$ and $\boldsymbol \nu$. Unfortunately, this is where things start to depend too much on the precise values of the constants $\boldsymbol a$, $\boldsymbol b$, and $N$. You will basically need to do case-checking on the complementary conditions, for each individual dual variable $\mu_i$, and $\lambda_i$, to choose which are zero, and which are non-zero. That would give $2^{2I+1}$ cases to check against the KKT sufficient condition, which is that $\frac{\boldsymbol a\boldsymbol a^\top}{1+\boldsymbol a ^\top\boldsymbol x^*}$ is positive semi-definite over the set of vectors $\boldsymbol s$ orthogonal to the active constraints, i.e. over the set $\left\{\begin{bmatrix}s\\\hline\boldsymbol t\\\hline\boldsymbol u\end{bmatrix}: \begin{cases}s[\boldsymbol a^\top \boldsymbol x-N]=0&\text{if }\lambda>0\\ t_i[x_i-1]=0&\text{if }\mu_i>0,\quad\forall{i}\in[1,I] \\ u_i[-x_i]=0&\text{if }\nu_i>0,\quad\forall{i}\in[1,I]\end{cases}\right\}$
Needless to say, if all these constants do not have fixed values, then obtaining a nice closed-form expression is elusive. The solvers automate this process, sometimes taking clever shortcuts. This kind of explicit work can be helpful for understanding the structure of the problem and the general "shape" of the solution, but not for the solution itself. The problem is in far too much of a general form for that (consider, by way of analogy, the knapsack problem, where the solution depends heavily on the costs and volumes involved).