I have an optimization like below:

$\text{ minimize } \sum_k - \log_2 x_k $

$\text{subject to: } x_k \leq q , k =1,2, \cdots, N .$

I can form the Lagrange of the problem as below:

$L(x, \lambda) = \sum_{k=1}^{N} - \log_2 x_k + \sum_{k=1}^{N} \lambda_k (x_k -q) $

But How can I find KKT conditions for this? Moreover, How can I solve the problem analytically from there? I know I can solve it through some nonlinear optimization solver software but for now I am only interested in solving the problem analytically so that I can get an exact form of x.


The simple solution (without KKT): it is easy to see that the problem is actually decoupled, i.e. the condition $0<x_k\le q$ affects only one term $\log_2x_k$ in the objective function. It makes it possible to minimize over $x_k$ each term independently, i.e. $$ \min\sum_{k=1}^n(-\log_2 x_k)=\sum_{k=1}^n\min_{0<x_k\le q}(-\log_2x_k)= \sum_{k=1}^n(-\log_2q)=-n\log_2q. $$ The "hard" solution (by KKT): motivate first that the minimum exists. Prove that the boundary $x_k=0$ is never active at the minimum, so we can cut it off to make the set compact, the function is continuous $\Rightarrow$ can apply Weierstrass theorem. Thus, we can use KKT that looks like "$\nabla L=0$ + the complementary slackness conditions + feasibility", i.e. for all $k=1,\ldots,n$ $$ \left\{ \begin{array}{lll} -\frac{1}{x_k\ln 2}+\lambda_k&=&0,\\ \lambda_k(x_k-q)&=&0,\\ \lambda_k\ge 0,\ 0<x_k\le q. \end{array} \right. $$ The first and the third conditions give that $\lambda_k\ne 0$ for all $k$, thus, the second equation gives $x_k=q$. Substitute to the objective function to get $-n\log_2q$.

| cite | improve this answer | |

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.