4
$\begingroup$

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.

$\endgroup$

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.