# Are all linear programs convex?

A linear program is given as follows:

$$\min_{Ax \le b} \{c^T x\}$$

where A is a $n\times n$ matrix Is this always a convex optimization problem or does it depend on c?

• A typical definition is that convex optimization asks for best value of a convex function over a convex set, and by that definition linear programs are convex optimization problems. – hardmath Aug 25 '17 at 12:31
• Yes since the set $\{x/ Ax\le b\}$ is convex since A is linear – Guy Fsone Aug 25 '17 at 12:32
• Ok, but what can we say about feasibility? There might be a c for given contraints, that lead to a solution containing inifinty, right? So feasibility should depend on c? – HansPeterLoft Aug 25 '17 at 12:35

Of course is convex since the feasible region $S:=\{Ax\leq b:x\in\mathbb{R}^n\}$ of the problem is a convex set.
To proof it, consider $x,y\in S$ and an arbitrary convex combination $\alpha x+(1-\alpha)y$ with $\alpha\in(0,1)$ lets see that the convex combination is in $S$. $$A(\alpha x+(1-\alpha)y)=\alpha Ax+(1-\alpha)Ay\leq \alpha b+(1-\alpha)b=b$$ Of course, depending on the objective function $c^tx$ the problem may have an optimal solution (at least one in an extreme point of $S$) or be an unbounded problem, (only possible if $S$ is unbounded).