6
$\begingroup$

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?

$\endgroup$
3
  • $\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

4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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