Consider the following problem:

$$\min_{x \in \mathbb{R}^n}f(x)=c^Tx$$ Subject to $ Ax=b$, where $A$ is full rank. Without any positive requirements (for instance, $x\ge0$), I want to show the following using Lagrange:

  • If the problem has a bounded optimal solution, then all the feasible solutions are optimal

I guess the non-negative requirement would give a standard LP. Not having such requirement allows to solve the problem without incurring in infeasability problema due to to the negativity. My idea, up to now, is to use a lagrangian $L(x,\lambda)= c^Tx -\lambda(Ax-b)$ and try to derive some necessary and sufficient conditions for its optimallity.

  • 1
    $\begingroup$ Welcome to MSE! I've seen this post has been marked as low quality. Unfortunately, I can't help you, but can you add more details and your attempt to solve the problem to avoid downvotes and prevent deletion? Good luck and hope you'll find the answer! $\endgroup$ – Cheesecake Feb 2 at 17:57
  • 1
    $\begingroup$ Re VerkhovtsevaKatya's comment, your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be closed. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ – Brian Feb 2 at 18:04
  • $\begingroup$ You may prove it without using Lagrange, right? $\endgroup$ – River Li Feb 22 at 6:26

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.