Learning From Data – A Short Course: Exercise 8.9

2016-11-18_1510592016-11-18_151120

Let u_{0} be optimal for (8.10), and let u_{1} be optimal for (8.11).

(a) Show that \max_{\alpha \geq 0} \alpha(c - a^{T}u_{0}) = 0.

If u_{0} is the optimal of (8.10) then it must satisfy the constraint  c - a^{T}u_{0} \leq 0, hence  \forall \alpha \geq 0, \alpha(c - a^{T}u_{0}) \leq 0. If  c - a^{T}u_{0}  = 0 then it doesn’t matter what \alpha is, \max_{\alpha \geq 0} \alpha(c - a^{T}u_{0}) = 0. If  c - a^{T}u_{0}  < 0 then we can always choose \alpha = 0, so \max_{\alpha \geq 0} \alpha(c - a^{T}u_{0}) = 0.

(b) Show that u_{1} is feasible for (8.10). To show this, suppose to the contrary that c - a^{T}u_{1} > 0. Show that the objective in (8.11) is infinite, where as u_{0} attains a finite objective of \frac{1}{2}u_{0}^{T}Qu_{0} + p^{T}u_{0}, which contradicts the optimality of u_{1}.

If  c - a^{T}u_{1} > 0 then solving for (8.11) is not equivalent to solving for (8.10). However, in such case \alpha will be positive infinity as we try to maximize  \alpha(c - a^{T}u_{1}), hence the objective in (8.11) will be infinite while u_{0} obtains the finite objective in (8.10), that means u_{1} is not the optimal of (8.11).

(c) Show that \frac{1}{2}u_{1}^{T}Qu_{1} + p^{T}u_{1} = \frac{1}{2}u_{0}^{T}Qu_{0} + p^{T}u_{0}, and hence that u_{1} is optimal for (8.10) and u_{0} is optimal for (8.11).

From contradiction proof (b), we can conclude that u_{1} must satisfy  c - a^{T}u_{1} \leq 0 (the constraint in (8.10)), hence the fact (a) also follows, then what’s left in (8.11) is \frac{1}{2}u_{1}^{T}Qu_{1} + p^{T}u_{1} (the optimization problem (8.11) is now equivalent to the optimization problem (8.10)). So if u_{1} is also optimal for (8.10) and u_{0} is also optimal for (8.11).

(d) Let u^{*} be any optimal solution for (8.11) with  \max_{\alpha \geq 0} \alpha(c - a^{T}u_{0}) attained at \alpha^{*}. Show that

    \[ \alpha^{*}(c - a^{T}u^{*}) = 0 \]

Either the constraint is exactly satisfied with  c - a^{T}u^{*} = 0, or \alpha^{*} = 0.

This is already discussed in (a). Exercise 8.13 suggest that the case  c - a^{T}u^{*} = 0 and \alpha^{*} = 0 may happen. I have opened a topic on this and been waiting for the answer.


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *