1
$\begingroup$

Considering an LP with:

\begin{align} &\text{max}\ \ c\cdot x \\ &Ax\le b\\ & x\geq 0 \\ \end{align}

Assume this LP has two optimal solutions $u$ and $v$. Show for any $t \in [0,1]$ that $tu+(1-t)v$ is also an optimal solution. First show $tu-(1-t)v$ has the same value as $u$ in the objective function. Then show $tu+(1-t)v$ is feasible solution to the LP.

So I know since they're both optimal functions that means that $u$ and $v$ must have the same objective function value otherwise one isn't the optimal point. I don't know if it's a proof, but $tu+(1-t)v$ has to be feasible because it runs parallel to the points $u$ and $v$ which are both optimal so that means that $tu+(1-t)v$ is also optimal? But I don't think that's a sufficient proof if a proof at all.

We can show $tu+(1-t)v$ is feasible by $A(tu+(1-t)v)=A(tu+(1-t)v)=Atu+(1-t)Av \le bt+(1-t)b=b$ from the domain of x if it's in the epigraph of the function, but I don't know about showing $tu+(1-t)v$ as an optimal solution. I'd just say it is cause it runs parallel to $u$ and $v$, in the direction of the gradient?

$\endgroup$
1
$\begingroup$

To prove the objective value is optimal, notice $$c(tu+(1-t)v)=tcu+cv-tcv$$ We know $cu=cv$ since both $u, v$ are optimal. Therefore, $tcu+cv-tcv=cv$ so $tu+(1-t)v$ has an optimal objective value.

$\endgroup$
  • $\begingroup$ duh of course it's so obvious after you explained it. Thanks! $\endgroup$ – Dylan Y Sep 26 '19 at 18:10
0
$\begingroup$

This is true for any convex problem. It is true because the level sets of a convex function are convex, and the set of minimisers is a level set.

$\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.