3
$\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 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
2
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.