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$
$\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 Aug 25 '17 at 12:31
-
$\begingroup$ Yes since the set $\{x/ Ax\le b\} $ is convex since A is linear $\endgroup$ – Guy Fsone Aug 25 '17 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$ – HansPeterLoft Aug 25 '17 at 12:35
Add a comment
|
$\begingroup$
$\endgroup$
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.
