The Non-Substitution Theorem, Uniqueness of Solution and Convex combinations of basic optimal solutions for linear optimization
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909565819289600 |
|---|---|
| author | Lahiri, Somdeb |
| author_facet | Lahiri, Somdeb |
| contents | Our first result is a statement of a somewhat general form of a non-substitution theorem for linear programming problems, along with a very easy proof of the same. Subsequently, we provide an easy proof of theorem 1 in a 1979 paper of Olvi L. Mangasarian, based on a new result in terms of two statements that are each equivalent to a given solution of a linear programming problem being its unique solution. We also provide a simple proof of the result that states that the set of optimal solutions of a bounded linear optimization problem is the set of all convex combinations of its basic optimal solutions and the set of basic optimal solutions are the extreme points of the set of optimal solutions. We do so by appealing to the lemma due to Farkas and the well-known result that states that if a linear optimization problem has an optimal solution, it has at least one basic optimal solution. Both results we appeal to have easy proofs. We do not appeal to any version of the Klein-Milman Theorem or any result in advanced polyhedral combinatorics to obtain our results. As an application of this result, we obtain a simple proof of the Birkhoff-von Neumann Theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_14150 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Non-Substitution Theorem, Uniqueness of Solution and Convex combinations of basic optimal solutions for linear optimization Lahiri, Somdeb Optimization and Control 15A51, 52A20, 90C05, 90C31, 90C46, 90C49 Our first result is a statement of a somewhat general form of a non-substitution theorem for linear programming problems, along with a very easy proof of the same. Subsequently, we provide an easy proof of theorem 1 in a 1979 paper of Olvi L. Mangasarian, based on a new result in terms of two statements that are each equivalent to a given solution of a linear programming problem being its unique solution. We also provide a simple proof of the result that states that the set of optimal solutions of a bounded linear optimization problem is the set of all convex combinations of its basic optimal solutions and the set of basic optimal solutions are the extreme points of the set of optimal solutions. We do so by appealing to the lemma due to Farkas and the well-known result that states that if a linear optimization problem has an optimal solution, it has at least one basic optimal solution. Both results we appeal to have easy proofs. We do not appeal to any version of the Klein-Milman Theorem or any result in advanced polyhedral combinatorics to obtain our results. As an application of this result, we obtain a simple proof of the Birkhoff-von Neumann Theorem. |
| title | The Non-Substitution Theorem, Uniqueness of Solution and Convex combinations of basic optimal solutions for linear optimization |
| topic | Optimization and Control 15A51, 52A20, 90C05, 90C31, 90C46, 90C49 |
| url | https://arxiv.org/abs/2408.14150 |