Content deleted Content added
→Algorithm: wikilink |
m →Algorithm: all TeX to png |
||
Line 8:
===Algorithm===
'''Step 1.''' Initialization. Let <math>k \leftarrow 0</math> and let <math>x_0 \!</math> be any point in <math>\mathbf{P}</math>.
'''Step 2.''' Convergence test. If <math> \nabla f(x_k)=0</math> then Stop, we have found the minimum.
'''Step 3.''' Direction-finding subproblem. The approximation of the problem that is obtained by replacing the function f with its first-order [[Taylor series|Taylor expansion]] around <math>x_k \!</math> is found. Solve for <math>\bar{x}_k</math>:
:Minimize <math>f(x_k) + \nabla^T f(x_k) \bar{x}_k</math>
:Subject to <math>\bar{x}_k \epsilon \mathbf{P}</math>
:(note that this is a Linear Program. <math>x_k \!</math> is fixed during Step 3, while the minimization takes place by varying <math>\bar{x}_k</math> and is equivalent to minimization of <math>\nabla^T f(x_k) \bar{x}_k</math>).
'''Step 4.''' Step size determination. Find <math>\lambda \!</math> that minimizes <math> f(x_k+\lambda(\bar{x}_k-x_k))</math> subject to <math>0 \le \lambda \le 1</math> . If <math>\lambda = 0 \!</math> then Stop, we have found the minimum.
'''Step 5.''' Update. Let <math>x_{k+1}\leftarrow x_k+\lambda(\bar{x}_k-x_k)</math>, let <math>k \leftarrow k+1</math> and go back to Step 2.
| |||