| (4 intermediate revisions by the same user not shown) | |||
| Line 11: | Line 11: | ||
'''(i)''' | '''(i)''' | ||
| − | <br> '''Solution: ''' <br> | + | <br> '''Solution 1: ''' <br> |
<math>\alpha_k</math> is the solution to <math>{d \over d\alpha}f(x^{(k)} + \alpha d^{(k)}) = 0 </math> | <math>\alpha_k</math> is the solution to <math>{d \over d\alpha}f(x^{(k)} + \alpha d^{(k)}) = 0 </math> | ||
| + | <math>{d \over d\alpha}f(x^{(k)} + \alpha d^{(k)}) = (x^{(k)T} + \alpha d^{(k)T}) Q d^{(k)} - d^{(k)T} b = 0</math> | ||
| + | |||
| + | <math>\therefore \alpha d^{(k)T} Q d^{(k)} = -x^{(k)T} Q d^{(k)} + d^{(k)T} b = (b - Qx^{(k)})^T d^{(k)} = - g^{(k)T} d^{(k)}</math> | ||
| + | |||
| + | <math>\therefore \alpha_k = - \frac {g^{(k)T} d^{(k)}} {d^{(k)T} Q d^{(k)}} </math> | ||
| + | |||
| + | <br> '''Solution 2: ''' <br> | ||
| + | Let <math> \Phi (\alpha) = f(x^{(k)} + \alpha d^{(k)}) </math> | ||
| + | |||
| + | then <math> {d \over d\alpha} \Phi (\alpha) = d^{(k)T} \nabla f(x^{(k)} + \alpha d^{(k)}) </math> | ||
| + | |||
| + | <math>f(x) = {1 \over 2} x^T Q x - x^T b + c, Q = Q^T > 0</math> | ||
| + | |||
| + | <math>\nabla f(x) = Qx - b</math> | ||
| + | |||
| + | so | ||
| + | |||
| + | <math> \begin{align} | ||
| + | {d \over d\alpha} \Phi (\alpha) & = d^{(k)T} (Q(x^{(k)} + \alpha d^{(k)}) - b) \\ | ||
| + | & = d^{(k)T} Q x^{(k)} + \alpha d^{(k)T} Q d^{(k)} - d^{(k)T} b \\ | ||
| + | & = d^{(k)T} (Q x^{(k)} - b) + \alpha d^{(k)T} Q d^{(k)} \\ | ||
| + | & = d^{(k)T} g^{(k)} + \alpha d^{(k)T} Q d^{(k)} = 0 \\ | ||
| + | \end{align} </math> | ||
| + | |||
| + | <math>\alpha_k = - \frac {d^{(k)T} g^{(k)}} {d^{(k)T} Q d^{(k)}} = - \frac {g^{(k)T} d^{(k)}} {d^{(k)T} Q d^{(k)}} = \frac {g^{(k)T} H_k g^{(k)}} {d^{(k)T} Q d^{(k)}}</math> | ||
| + | |||
| + | '''(ii)''' | ||
| + | <br> '''Solution 1: ''' <br> | ||
| + | <math>\because Q > 0,\ \therefore d^{(k)T} Q d^{(k)} > 0</math> | ||
| + | |||
| + | <math>\therefore \alpha_k > 0 \Leftrightarrow -g^{(k)T} d^{(k)} = g^{(k)T} H_k g^{(k)} > 0</math> | ||
| + | |||
| + | Therefore a sufficient condition is <math>H_k</math> is positive definite. | ||
| + | |||
| + | <br> '''Solution 2: ''' <br> | ||
| + | |||
| + | <math>\alpha_k > 0 \Rightarrow H_k = H_k^T > 0</math> | ||
| + | |||
| + | <br> '''Comment: ''' <br> Both solutions are similar and have the same result. <br> | ||
[[ QE2013 AC-3 ECE580|Back to QE2013 AC-3 ECE580]] | [[ QE2013 AC-3 ECE580|Back to QE2013 AC-3 ECE580]] | ||
Latest revision as of 11:10, 25 March 2015
QE2013_AC-3_ECE580-1
(i)
Solution 1:
$ \alpha_k $ is the solution to $ {d \over d\alpha}f(x^{(k)} + \alpha d^{(k)}) = 0 $
$ {d \over d\alpha}f(x^{(k)} + \alpha d^{(k)}) = (x^{(k)T} + \alpha d^{(k)T}) Q d^{(k)} - d^{(k)T} b = 0 $
$ \therefore \alpha d^{(k)T} Q d^{(k)} = -x^{(k)T} Q d^{(k)} + d^{(k)T} b = (b - Qx^{(k)})^T d^{(k)} = - g^{(k)T} d^{(k)} $
$ \therefore \alpha_k = - \frac {g^{(k)T} d^{(k)}} {d^{(k)T} Q d^{(k)}} $
Solution 2:
Let $ \Phi (\alpha) = f(x^{(k)} + \alpha d^{(k)}) $
then $ {d \over d\alpha} \Phi (\alpha) = d^{(k)T} \nabla f(x^{(k)} + \alpha d^{(k)}) $
$ f(x) = {1 \over 2} x^T Q x - x^T b + c, Q = Q^T > 0 $
$ \nabla f(x) = Qx - b $
so
$ \begin{align} {d \over d\alpha} \Phi (\alpha) & = d^{(k)T} (Q(x^{(k)} + \alpha d^{(k)}) - b) \\ & = d^{(k)T} Q x^{(k)} + \alpha d^{(k)T} Q d^{(k)} - d^{(k)T} b \\ & = d^{(k)T} (Q x^{(k)} - b) + \alpha d^{(k)T} Q d^{(k)} \\ & = d^{(k)T} g^{(k)} + \alpha d^{(k)T} Q d^{(k)} = 0 \\ \end{align} $
$ \alpha_k = - \frac {d^{(k)T} g^{(k)}} {d^{(k)T} Q d^{(k)}} = - \frac {g^{(k)T} d^{(k)}} {d^{(k)T} Q d^{(k)}} = \frac {g^{(k)T} H_k g^{(k)}} {d^{(k)T} Q d^{(k)}} $
(ii)
Solution 1:
$ \because Q > 0,\ \therefore d^{(k)T} Q d^{(k)} > 0 $
$ \therefore \alpha_k > 0 \Leftrightarrow -g^{(k)T} d^{(k)} = g^{(k)T} H_k g^{(k)} > 0 $
Therefore a sufficient condition is $ H_k $ is positive definite.
Solution 2:
$ \alpha_k > 0 \Rightarrow H_k = H_k^T > 0 $
Comment:
Both solutions are similar and have the same result.
Back to QE2013 AC-3 ECE580
