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

[Andrew Makhorin]

> 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.