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?

  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Commented Aug 25, 2017 at 12:31
  • $\begingroup$ Yes since the set $\{x/ Ax\le b\} $ is convex since A is linear $\endgroup$
    – Guy Fsone
    Commented Aug 25, 2017 at 12:32
  • $\begingroup$ 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? $\endgroup$ Commented Aug 25, 2017 at 12:35

1 Answer 1


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

The simplex algorithm (and others) are substantiated by theoretical results that gives characterizations of every possible situation.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .