[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] [Fwd: Some questions about convexity of LP]

**From**: |
Andrew Makhorin |

**Subject**: |
Re: [Help-glpk] [Fwd: Some questions about convexity of LP] |

**Date**: |
Sun, 02 Mar 2014 18:41:17 +0400 |

>* Dear all,*
>* *
>* Consider the LP,*
>* min a'x + b'y*
>* s.t.*
>* Px + Qy + r = 0*
>* x_lb <= x <= x_ub*
>* y_lb <= y <= y_ub*
>* where x,y,r are vector in R^n, P,Q are n x n matrices.*
>* x_lb, x_ub, y_lb, y_ub are bounds of x, y.*
>* *
>* Q1. *
>* My guess is that the intersection of the feasible region of the problem*
>* and the hyper plane (x_k, y_k) where (x_k,y_k) are member of x and y, *
>* is a convex polygon. Is it always true?*
Yes, because any hyperplane is a convex set and the intersection of
convex sets results in a convex set. Polyhedrality is also preserved.
>* *
>* Q2. How can one find such intersection area?*
>* ----*
>* s.s.*
>* *
It depends on which description of the resulting set you need. One of
such descriptions would be simply the original constraints plus the
hyperplane equality constraint.