1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Leaving aside that the objective function doesn't seem to be written out correctly, this is easy to formulate and numerically solve as a convex optimization problem in CVX, CVXPY, or similar tool. As for the objective function, there is a single $x_ib_i$ term by its lonesome in the objective function, which doesn't make sense because it depends on $i$. Is there supposed to be a a sum over $i$ of $x_ib_i$? If so, that presents no complicaton to CVX or CVXPY. $\endgroup$ Sep 23 '19 at 14:56
  • $\begingroup$ Sorry I forget to add sum. I know that I can solve it using many tools, however, is it possible to explain it analytically? @MarkL.Stone $\endgroup$
    – bnbfreak
    Sep 24 '19 at 0:17
1
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ Thanks a lot for the detailed explanation. It helps me a lot. $\endgroup$
    – bnbfreak
    Sep 24 '19 at 6:28

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.