how can i prove that mathematical proof about feasible solution is found at boundary point?
also want to ask about why feasible region must be composed of a convex set. is there any mathematical proof about this?
A feasible solution is any point in the feasible set, both interior points as well as boundary points can be feasible solutions, it depends on your optimization problem.
For a Linear programming problem, the feasible region is a polyhedral set, which can have extreme directions and extreme points, if the polyhedron above is a bounded set, it can have a finite number of extreme points only.
By representation theorem, for a bounded polyhedral set, any point in the set can be expressed as a convex combination of the extreme points of the set: substitute this expression in the expression for cost function as f= cT*x, cT is transpose of vector c, the cost vector. you can see that this linear form is bounded both above and below, the lower bound is fmin which is associated with the extreme point corresponding to lowest value of the objective function and upper bounded by fmax, which is associatef with that extreme point corresponding to the largest value of the objective function.
A feasible region need not always be a convex set, but optimization of convex/concave functions over convex set, is called convex programming , it is mathematically very well studied and has many interesting features associated with it.
The proof can be found in the following book:
Non Linear Programming : Theory and Algorithms (3rd edition), by Bazaara, Sherali and Shetty.
I also recommend the following books for a deeper understanding of Linear programming and other types of Mathematical Programming problems:
1. Convex Analysis, by R. T
Rockafellar
2. Lectures on Convex sets, by Valeriu Soltan
3. Convexity and Optimization in finite dimensions, by J. Stoer and C. Witzgall
4. Operations Research by Hamdy S. Taha
5. Linear programming: An introduction to Finite Improvement Algorithms, by Daniel Solow
Hope this helps.
Regards
D. Ghosh
- Badges
- Science topic
- Similar topics
- Mathematics