I am considering the following LP problem:

$$ \begin{array}{cl} \text{maximize} & c^Tx\\ \text{subject to} & a^Tx\geq0 \\ & 0\leq x\leq x^\max \end{array} $$ where $c,a\in\mathbb{R}^{M\times 1}$ and $c_i>0$ for all $i=1,2,\ldots,M$. I want to find the optimal $x$ in the closed-form.

To do so, I firstly write the Lagrangian as $$ L=c^T x +\theta a^Tx+\varphi^Tx+\psi^T\left(x^\max-x\right). $$ Then, the KKT conditions are provided as follows:

$$ \begin{array}{rl} \frac{\partial L}{\partial x_{i}}=c_{i}+\theta a_{i}+\varphi_{i}-\psi_{i} &=& 0,\\ \theta a^Tx &=& 0,\\ \varphi_{i}x_i &=& 0, \\ \psi_{i}\left(x^\max_i-x_i\right) &=& 0, \\ \end{array} $$ and $\theta\geq0, \varphi_{i}\geq0, \psi_{i}\geq0$ for all $i=1,2,\ldots,M$.

Now I can get that when $a^T x^\max \geq0$, the optimal solution is $x^\star=x^\max$. (It is obvious as $c_i>0$).

But when the optimal solution is on the boundary of $a^Tx^\star=0$, I can only find out that $x_i^\star=x_i^\max$ if $a_i>0$.

Could someone help me on this? Thanks in advance.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.