Cornell University Computational Optimization Open Textbook - Optimization Wiki - User contributions [en]

Trust-region methods

2021-12-15T02:58:07Z

Ty262:

Autor: Chun-Yu Chou, Ting-Guang Yeh, Yun-Chung Pan, Chen-Hua Wang (CHEME 6800, Fall 2021)
=Introduction=

Trust region method is a numerical optimization method that is employed to solve non-linear programming (NLP) problem. Instead of finding objective solution of the original function f, in each step the method defines a neighborhood around current best solution xk as a trust region f’ (typically by using quadratic model), which is capable of representing the f function appropriately, in order to derive the next point xk+1. Different from line search, the model selects the direction and step size simultaneously. For example, in a minimization problem, if the decrease in the value of optimal solution is not sufficient, we can conclude that the region is too large to get close to the minimizer of the objective function, so we will shrink the f’ to find the solution again. On the other hand, if such decrease is significant, it is believed that the model has adequate representation to the problem. Generally, the step direction depends on extent that the region is altered in the previous iteration.
=Methodology and theory=
'''Cauchy point calculation'''

Similar to line serach method which do not require optimal step lengths to be convergent, trust-region method is suffficient for global convergence purpose to find an approximate solution pk that lies within trust region. Cauchy step <math>P_{K}^{C}</math> is an unexpensive method( no matrix factorization) to solve trust-region subproblem. Furthermore, Cauchy point has been valued due to the fact that it can globally convergent. Following is a closed-form equations of the Cauchy point.

<math>p_k^c=-\tau _k\frac{\Delta k}{\left \| \ g_k \right \|}\ g_k</math>

if <math>g_k^TB_kg_k\leq 0</math>, <math>\tau _k=1</math>

otherewise, <math>\tau _k= min\left ( \left \| \bigtriangledown g_k \right \|^{3}/\left ( \bigtriangleup _k\bigtriangledown g_k^TB_kg_k \right ),1 \right ) </math>

Although it is unexpensive to apply Cauchy point, steepest descent methods sometimes performs poorly. Thus, we introduce some improving strategy. The improvement strategies is based on <math>B_k</math> where it contains valid curvature information about the function.

'''Dogleg method'''

This method can be used if <math>B_k</math> is a positive definite. The dogleg method finds an approximate solution by replacing the curved trajectory

for <math>p^*\left ( \bigtriangleup \right )</math> with a path consisting of two line segments. It chooses p to minimize the model m along this path, subject to the trust-region bound.

First line segments <math>p^U=-\frac{g^Tg}{g^TBg}g </math>, where <math>p^U</math>runs from the origin to the minimizer of m along the steepest descent direction.

While the second line segment run from <math>p^U</math>to <math>p^B</math>, we donate this trajectory by <math>\tilde{p}\left ( \tau \right )</math> for <math>\tau \in \left [ 0,2 \right ]</math>

Then a V-shaped trajectory can be determined by

<math>\tilde{p}=\tau p^U </math>, when <math>0\leq \tau \leq 1 </math>

<math>\tilde{p}= p^U+\left (\tau -1 \right )\left ( p^B-p^U \right ) </math>, when <math>1\leq \tau \leq 2 </math>

where <math>p^B </math>=opitimal solution of quadratic model

Although the dogleg strategy can be adapted to handle indefinite B, there is not much point in doing so because the full step <math>p^B</math> is not the unconstrained minimizer of m in this case. Instead, we now describe another strategy, which aims to include directions of negative

curvature in the space of trust-region steps.

'''Conjugated Gradient Steihaug’s Method ( CG-Steihaug)'''

This is the most widely used method for the approximate solution of the trust-region problem. The method works for quadratic models <math>m_{k}</math> defined by an arbitrary symmetric <math>B_k</math> . Thus, it is not necessary for <math>B_k</math> to be positive. CG-Steihaug has the advantage of Cauchy point calculation and Dogleg method which is super-linear convergence rate and unexpensive costs .

Given<math>\epsilon > 0 </math>

Set <math>p_0=0,r_0=g,d_0=-r_0 </math>

if<math>\left \| r_0 \right \|< \epsilon </math>

return <math>p=p0</math>

for <math>j=0,1,2,...</math>

if <math>d_j^TB_kd_j\leq 0 </math>

Find <math>\tau </math> such that minimizes <math>m\left ( p \right )</math> and satisfies<math>\left \| p \right \|=\Delta </math>

return p;

Set <math>\alpha _j=r_j^Tr_j/d_j^TB_kd_j</math>

Set <math> p_{j+1}=p_j+\alpha _jd_j</math>

if <math>\left \| p_{j+1} \right \|\geq \Delta</math>

Find <math>\tau \geq 0</math> such that <math>p=p_{j}+\tau d_{j}</math> satisfies <math>\left \| p \right \|=\Delta </math>

return p;

Set <math>r_{j+1}=r_j+\alpha _jB_kd_j</math>

if <math> \left \| r_{j+1} \right \|< \epsilon \left \| r_{0} \right \|</math>

return <math>p=p_{j+1}</math>

Set <math>\beta _{j+1} = r_{j+1}^{T}r_{j+1}/r_j^Tr_j</math>

Set <math>d_{j+1}= r_{j+1}+ \beta _{j+1}d_j</math>

end(for)

'''Global Convergence'''

To study the convergence of trust region, we have to study how much reduction can we achieve at each

iteration (similar to line search method). Thus, we derive an estimate in the following form:

<math>m_k\left ( 0 \right )-m_k\left ( p_k \right )\geq c_1\left \| \bigtriangledown f_k \right \|min\left ( \bigtriangleup k,\frac{\left \| \bigtriangledown f_k\right \|}{\left \| B_k \right \|} \right )</math> for <math>c_1\in \left [ 0,1 \right ]</math>

For cauchy point, <math>c_1</math>=0.5

that is

<math>m_k\left ( 0 \right )-m_k\left ( p_k \right )\geq 0.5\left \| \bigtriangledown f_k \right \|min\left ( \bigtriangleup k,\frac{\left \| \bigtriangledown f_k\right \|}{\left \| B_k \right \|} \right )</math>

we first consider the case of <math>\bigtriangledown f_k^TB_k\bigtriangledown f_k\leq 0</math>

<math>m_k\left ( p_k^c \right )-m_k\left ( 0 \right )\geq m_k\left ( \bigtriangleup _k\bigtriangledown f_k/\left \| \bigtriangledown f_k \right \| \right )</math>

<math>=-\frac{\bigtriangleup _k}{\left \| \bigtriangledown f_k \right \|}\left \| \bigtriangledown f_k \right \|^2+0.5\frac{\bigtriangleup _k^2}{\left \| \bigtriangledown f_k \right \|^2}\ \bigtriangledown f_k^TB_k\bigtriangledown f_k</math>

<math>\leq -\bigtriangleup _k\left \| \bigtriangledown f_k \right \|</math>

<math>\leq -\left \| \bigtriangledown f_k \right \|min\left ( \bigtriangleup _k,\frac{\left \| \bigtriangledown f_k \right \|}{B_k} \right )</math>

For the next case, consider <math>\bigtriangledown f_k^TB_k\bigtriangledown f_k> 0</math> and

<math>\frac{\left \| \bigtriangledown f_k \right \|^3}{\bigtriangleup _k\bigtriangledown f_k^TB_k\bigtriangledown f_k}\leq 1</math>

we then have <math>\tau =\frac{\left \| \bigtriangledown f_k \right \|^3}{\bigtriangleup _k\bigtriangledown f_k^TB_k\bigtriangledown f_k}</math>

so

<math>m_k\left ( p_k^c \right )-m_k\left ( 0 \right )= -\frac{\left \| \bigtriangledown f_k \right \|^4}{\bigtriangledown f_k^TB_k\bigtriangledown f_k}+0.5\bigtriangledown f_k^TB_k\bigtriangledown f_k\frac{\left \| \bigtriangledown f_k \right \|^4}{\left ( \bigtriangledown f_k^TB_k\bigtriangledown f_k \right )^2}</math>

<math>=-0.5\frac{\left \| \bigtriangledown f_k \right \|^4}{\bigtriangledown f_k^TB_k\bigtriangledown f_k}</math>

<math>\leq -0.5\frac{\left \| \bigtriangledown f_k \right \|^4}{\left \| B_k \right \|\left \| \bigtriangledown f_k \right \|^2}</math>

<math>=-0.5\frac{\left \| \bigtriangledown f_k \right \|^2}{\left \| B_k \right \|}</math>

<math>\leq -0.5\left \| \bigtriangledown f_k \right \|min\left ( \bigtriangleup _k,\frac{\left \| \bigtriangledown f_k \right \|}{\left \| B_k \right \|} \right )</math>,

since <math>\frac{\left \| \bigtriangledown f_k \right \|^3}{\bigtriangleup _k\bigtriangledown f_k^TB_k\bigtriangledown f_k}\leq 1</math> does not hold, thus

<math>\bigtriangledown f_k^TB_k\bigtriangledown f_k< \frac{\left \| \bigtriangledown f_k \right \|^3}{\bigtriangleup _k}</math>

From the definition of <math>p_c^k</math> , we have <math>\tau =1</math>, therefore

<math>m_k\left ( p_k^c \right )-m_k\left ( 0 \right )= -\frac{\bigtriangleup _k}{\left \| \bigtriangledown f_k \right \|}\left \| \bigtriangledown f_k \right \|^2+0.5\frac{\bigtriangleup _k^2}{\left \| \bigtriangledown f_k \right \|^2}\bigtriangledown f_k^TB_k\bigtriangledown f_k</math>

<math>\leq -\bigtriangleup _k\left \| \bigtriangledown f_k \right \|^2+0.5\frac{\bigtriangleup _k^2}{\left \| \bigtriangledown f_k \right \|^2}\frac{\left \| \bigtriangledown f_k \right \|^3}{\bigtriangleup _k}</math>

<math>=-0.5\bigtriangleup _k\left \| \bigtriangledown f_k \right \|</math>

<math>\leq -0.5\left \| \bigtriangledown f_k \right \|min\left ( \bigtriangleup _k,\frac{\left \| \bigtriangledown f_k \right \|}{\left \| B_k \right \|} \right )</math>

=Numerical example=

Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960<ref>H. H. Rosenbrock, An Automatic Method for Finding the Greatest or Least Value of a Function, ''The Computer Journal'', Volume 3, Issue 3, 1960, Pages 175–184, <nowiki>https://doi.org/10.1093/comjnl/3.3.175</nowiki></ref>, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's <code>fminunc</code> as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.
[[File:Trust-region method example trajectory.png|thumb|576x576px|Trust-region method trajectory of Rosenbrock function starting from (0,0). The data points represent the optimal solutions after each iteration, ending at iteration number 16 (1,1).]]

'''Iteration Process'''

'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
'''Approaches for a convex model problem'''

* Levenberg–Marquardt Steps

The objective function is iteratively approximated by a quadratic surface, and the estimate is updated. However, this method may fail to converge if the initial guess is too large or

too small. The trust region methods help to control the trust region size, preventing each step from being too far from the optimum.

* Powell Dogleg Steps

Compared to Levenberg–Marquardt steps, the objective function is iteratively approximated by a linear surface, and the estimate is updated as well. Besides, the Levenberg–

Marquardt steps provide an exact solution to the model problem, while the dogleg method provides only an approximate solution.

'''Approaches for a nonconvex model problem'''

If the exact Hessian is not positive definite, then a dogleg method that relies on Newton steps may be ascent steps or unbounded steps. Furthermore, the Levenberg–Marquardt method may not be flexible to exploit the size of the trust region. However, the trust region method can used to iteratively minimize a quadratic model of the Lagrangian subject to a possibly relaxed linearization of the problem constraints and a trust region constraint.

=Conclusion=
Trusted region is a powerful method that can update the objective function in each step to ensure the model is always getting improved while keeping the previously learnt knowledge as the baseline. Nowadays, trust region algorithms are widely used in machine learning, applied mathematics, physics, chemistry, biology, etc. It is believed that the trust region method will have more far-reaching development in a wider range of fields in the near future.

=References=
[1] J. Nocedal, S. J. Wright, ''Numerical Optimization''. Springer, 1999.

[2] W. Sun and Y.-x. Yuan, Optimization theory and methods : nonlinear programming. New York: Springer, 2006.

[3] S. Boyd, L. Vandenberghe, Convex Optimization. Cambridge University Press, 2009

[4] Trust region. (2020). Retrieved November 10, 2021, from <nowiki>https://en.wikipedia.org/wiki/Trust_region</nowiki>.<references />

Trust-region methods

2021-12-14T22:42:11Z

Ty262:

Autor: Chun-Yu Chou, Ting-Guang Yeh, Yun-Chung Pan, Chen-Hua Wang (CHEME 6800, Fall 2021)
=Introduction=

Trust region method is a numerical optimization method that is employed to solve non-linear programming (NLP) problem. Instead of finding objective solution of the original function f, in each step the method defines a neighborhood around current best solution xk as a trust region f’ (typically by using quadratic model), which is capable of representing the f function appropriately, in order to derive the next point xk+1. Different from line search, the model selects the direction and step size simultaneously. For example, in a minimization problem, if the decrease in the value of optimal solution is not sufficient, we can conclude that the region is too large to get close to the minimizer of the objective function, so we will shrink the f’ to find the solution again. On the other hand, if such decrease is significant, it is believed that the model has adequate representation to the problem. Generally, the step direction depends on extent that the region is altered in the previous iteration.
=Methodology and theory=
'''Cauchy point calculation'''

Similar to line serach method which do not require optimal step lengths to be convergent, trust-region method is suffficient for global convergence purpose to find an approximate solution pk that lies within trust region. Cauchy step <math>P_{K}^{C}</math> is an unexpensive method( no matrix factorization) to solve trust-region subproblem. Furthermore, Cauchy point has been valued due to the fact that it can globally convergent. Following is a closed-form equations of the Cauchy point.

<math>p_k^c=-\tau _k\frac{\Delta k}{\left \| \ g_k \right \|}\ g_k</math>

if <math>g_k^TB_kg_k\leq 0</math>, <math>\tau _k=1</math>

otherewise, <math>\tau _k= min\left ( \left \| \bigtriangledown g_k \right \|^{3}/\left ( \bigtriangleup _k\bigtriangledown g_k^TB_kg_k \right ),1 \right ) </math>

Although it is unexpensive to apply Cauchy point, steepest descent methods sometimes performs poorly. Thus, we introduce some improving strategy. The improvement strategies is based on <math>B_k</math> where it contains valid curvature information about the function.

'''Dogleg method'''

This method can be used if <math>B_k</math> is a positive definite. The dogleg method finds an approximate solution by replacing the curved trajectory

for <math>p^*\left ( \bigtriangleup \right )</math> with a path consisting of two line segments. It chooses p to minimize the model m along this path, subject to the trust-region bound.

First line segments <math>p^U=-\frac{g^Tg}{g^TBg}g </math>, where <math>p^U</math>runs from the origin to the minimizer of m along the steepest descent direction.

While the second line segment run from <math>p^U</math>to <math>p^B</math>, we donate this trajectory by <math>\tilde{p}\left ( \tau \right )</math> for <math>\tau \in \left [ 0,2 \right ]</math>

Then a V-shaped trajectory can be determined by

<math>\tilde{p}=\tau p^U </math>, when <math>0\leq \tau \leq 1 </math>

<math>\tilde{p}= p^U+\left (\tau -1 \right )\left ( p^B-p^U \right ) </math>, when <math>1\leq \tau \leq 2 </math>

where <math>p^B </math>=opitimal solution of quadratic model

Although the dogleg strategy can be adapted to handle indefinite B, there is not much point in doing so because the full step <math>p^B</math> is not the unconstrained minimizer of m in this case. Instead, we now describe another strategy, which aims to include directions of negative

curvature in the space of trust-region steps.

'''Conjugated Gradient Steihaug’s Method ( CG-Steihaug)'''

This is the most widely used method for the approximate solution of the trust-region problem. The method works for quadratic models <math>m_{k}</math> defined by an arbitrary symmetric <math>B_k</math> . Thus, it is not necessary for <math>B_k</math> to be positive. CG-Steihaug has the advantage of Cauchy point calculation and Dogleg method which is super-linear convergence rate and unexpensive costs .

Given<math>\epsilon > 0 </math>

Set <math>p_0=0,r_0=g,d_0=-r_0 </math>

if<math>\left \| r_0 \right \|< \epsilon </math>

return <math>p=p0</math>

for <math>j=0,1,2,...</math>

if <math>d_j^TB_kd_j\leq 0 </math>

Find <math>\tau </math> such that minimizes <math>m\left ( p \right )</math> and satisfies<math>\left \| p \right \|=\Delta </math>

return p;

Set <math>\alpha _j=r_j^Tr_j/d_j^TB_kd_j</math>

Set <math> p_{j+1}=p_j+\alpha _jd_j</math>

if <math>\left \| p_{j+1} \right \|\geq \Delta</math>

Find <math>\tau \geq 0</math> such that <math>p=p_{j}+\tau d_{j}</math> satisfies <math>\left \| p \right \|=\Delta </math>

return p;

Set <math>r_{j+1}=r_j+\alpha _jB_kd_j</math>

if <math> \left \| r_{j+1} \right \|< \epsilon \left \| r_{0} \right \|</math>

return <math>p=p_{j+1}</math>

Set <math>\beta _{j+1} = r_{j+1}^{T}r_{j+1}/r_j^Tr_j</math>

Set <math>d_{j+1}= r_{j+1}+ \beta _{j+1}d_j</math>

end(for)

'''Global Convergence'''

To study the convergence of trust region, we have to study how much reduction can we achieve at each

iteration (similar to line search method). Thus, we derive an estimate in the following form:

<math>m_k\left ( 0 \right )-m_k\left ( p_k \right )\geq c_1\left \| \bigtriangledown f_k \right \|min\left ( \bigtriangleup k,\frac{\left \| \bigtriangledown f_k\right \|}{\left \| B_k \right \|} \right )</math> for <math>c_1\in \left [ 0,1 \right ]</math>

For cauchy point, <math>c_1</math>=0.5

that is

<math>m_k\left ( 0 \right )-m_k\left ( p_k \right )\geq 0.5\left \| \bigtriangledown f_k \right \|min\left ( \bigtriangleup k,\frac{\left \| \bigtriangledown f_k\right \|}{\left \| B_k \right \|} \right )</math>

first consider the case of <math>\bigtriangledown f_k^TB_k\bigtriangledown f_k\leq 0</math>

<math>m_k\left ( p_k^c \right )-m_k\left ( 0 \right )\geq m_k\left ( \bigtriangleup _k\bigtriangledown f_k/\left \| \bigtriangledown f_k \right \| \right )</math>

=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960<ref>H. H. Rosenbrock, An Automatic Method for Finding the Greatest or Least Value of a Function, ''The Computer Journal'', Volume 3, Issue 3, 1960, Pages 175–184, <nowiki>https://doi.org/10.1093/comjnl/3.3.175</nowiki></ref>, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's <code>fminunc</code> as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.
[[File:Trust-region method example trajectory.png|thumb|576x576px|Trust-region method trajectory of Rosenbrock function starting from (0,0). The data points represent the optimal solutions after each iteration, ending at iteration number 16 (1,1).]]

'''Iteration Process'''

'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
'''Approaches for a convex model problem'''

* Levenberg–Marquardt Steps

The objective function is iteratively approximated by a quadratic surface, and the estimate is updated. However, this method may fail to converge if the initial guess is too large or

too small. The trust region methods help to control the trust region size, preventing each step from being too far from the optimum.

* Powell Dogleg Steps

Compared to Levenberg–Marquardt steps, the objective function is iteratively approximated by a linear surface, and the estimate is updated as well. Besides, the Levenberg–

Marquardt steps provide an exact solution to the model problem, while the dogleg method provides only an approximate solution.

'''Approaches for a nonconvex model problem'''

If the exact Hessian is not positive definite, then a dogleg method that relies on Newton steps may be ascent steps or unbounded steps. Furthermore, the Levenberg–Marquardt method may not be flexible to exploit the size of the trust region. However, the trust region method can used to iteratively minimize a quadratic model of the Lagrangian subject to a possibly relaxed linearization of the problem constraints and a trust region constraint.

=Conclusion=
Trusted region is a powerful method that can update the objective function in each step to ensure the model is always getting improved while keeping the previously learnt knowledge as the baseline. Nowadays, trust region algorithms are widely used in machine learning, applied mathematics, physics, chemistry, biology, etc. It is believed that the trust region method will have more far-reaching development in a wider range of fields in the near future.

=References=
[1] J. Nocedal, S. J. Wright, ''Numerical Optimization''. Springer, 1999.

[2] W. Sun and Y.-x. Yuan, Optimization theory and methods : nonlinear programming. New York: Springer, 2006.

[3] S. Boyd, L. Vandenberghe, Convex Optimization. Cambridge University Press, 2009

[4] Trust region. (2020). Retrieved November 10, 2021, from <nowiki>https://en.wikipedia.org/wiki/Trust_region</nowiki>.<references />

Trust-region methods

2021-12-14T20:24:59Z

Ty262:

Autor: Chun-Yu Chou, Ting-Guang Yeh, Yun-Chung Pan, Chen-Hua Wang (CHEME 6800, Fall 2021)
=Introduction=

Trust region method is a numerical optimization method that is employed to solve non-linear programming (NLP) problem. Instead of finding objective solution of the original function f, in each step the method defines a neighborhood around current best solution xk as a trust region f’ (typically by using quadratic model), which is capable of representing the f function appropriately, in order to derive the next point xk+1. Different from line search, the model selects the direction and step size simultaneously. For example, in a minimization problem, if the decrease in the value of optimal solution is not sufficient, we can conclude that the region is too large to get close to the minimizer of the objective function, so we will shrink the f’ to find the solution again. On the other hand, if such decrease is significant, it is believed that the model has adequate representation to the problem. Generally, the step direction depends on extent that the region is altered in the previous iteration.
=Methodology and theory=
'''Cauchy point calculation'''

Similar to line serach method which do not require optimal step lengths to be convergent, trust-region method is suffficient for global convergence purpose to find an approximate solution pk that lies within trust region. Cauchy step <math>P_{K}^{C}</math> is an unexpensive method( no matrix factorization) to solve trust-region subproblem. Furthermore, Cauchy point has been valued due to the fact that it can globally convergent. Following is a closed-form equations of the Cauchy point.

<math>p_k^c=-\tau _k\frac{\Delta k}{\left \| \ g_k \right \|}\ g_k</math>

if <math>g_k^TB_kg_k\leq 0</math>, <math>\tau _k=1</math>

otherewise, <math>\tau _k= min\left ( \left \| \bigtriangledown g_k \right \|^{3}/\left ( \bigtriangleup _k\bigtriangledown g_k^TB_kg_k \right ),1 \right ) </math>

Although it is unexpensive to apply Cauchy point, steepest descent methods sometimes performs poorly. Thus, we introduce some improving strategy. The improvement strategies is based on <math>B_k</math> where it contains valid curvature information about the function.

'''Dogleg method'''

This method can be used if <math>B_k</math> is a positive definite. The dogleg method finds an approximate solution by replacing the curved trajectory

for <math>p^*\left ( \bigtriangleup \right )</math> with a path consisting of two line segments. It chooses p to minimize the model m along this path, subject to the trust-region bound.

First line segments <math>p^U=-\frac{g^Tg}{g^TBg}g </math>, where <math>p^U</math>runs from the origin to the minimizer of m along the steepest descent direction.

While the second line segment run from <math>p^U</math>to <math>p^B</math>, we donate this trajectory by <math>\tilde{p}\left ( \tau \right )</math> for <math>\tau \in \left [ 0,2 \right ]</math>

Then a V-shaped trajectory can be determined by

<math>\tilde{p}=\tau p^U </math>, when <math>0\leq \tau \leq 1 </math>

<math>\tilde{p}= p^U+\left (\tau -1 \right )\left ( p^B-p^U \right ) </math>, when <math>1\leq \tau \leq 2 </math>

where <math>p^B </math>=opitimal solution of quadratic model

Although the dogleg strategy can be adapted to handle indefinite B, there is not much point in doing so because the full step <math>p^B</math> is not the unconstrained minimizer of m in this case. Instead, we now describe another strategy, which aims to include directions of negative

curvature in the space of trust-region steps.

'''Conjugated Gradient Steihaug’s Method ( CG-Steihaug)'''

This is the most widely used method for the approximate solution of the trust-region problem. The method works for quadratic models <math>m_{k}</math> defined by an arbitrary symmetric <math>B_k</math> . Thus, it is not necessary for <math>B_k</math> to be positive. CG-Steihaug has the advantage of Cauchy point calculation and Dogleg method which is super-linear convergence rate and unexpensive costs .

Given<math>\epsilon > 0 </math>

Set <math>p_0=0,r_0=g,d_0=-r_0 </math>

if<math>\left \| r_0 \right \|< \epsilon </math>

return <math>p=p0</math>

for <math>j=0,1,2,...</math>

if <math>d_j^TBd_j\leq 0 </math>

Find <math>\tau </math> such that minimizes <math>m\left ( p \right )</math> and satisfies<math>\left \| p \right \|=\Delta </math>

return p;

Set <math>\alpha _j=r_j^Tr_j/d_j^TBd_j</math>

Set <math> p_{j+1}=p_j+\alpha _jd_j</math>

if <math>\left \| p_{j+1} \right \|\geq \Delta</math>

Find <math>\tau \geq 0</math> such that <math>p=p_{j}+\tau d_{j}</math> satisfies <math>\left \| p \right \|=\Delta </math>

return p;

Set <math>r_{j+1}=r_j+\alpha _jBd_j</math>

if <math> \left \| r_{j+1} \right \|< \epsilon \left \| r_{0} \right \|</math>

return <math>p=p_{j+1}</math>

Set <math>\beta _{j+1} = r_{j+1}^{T}r_{j+1}/r_j^Tr_j</math>

Set <math>d_{j+1}= r_{j+1}+ \beta _{j+1}d_j</math>

end(for)

'''Global Convergence'''

<math>m_k\left ( 0 \right )-m_k\left ( p_k \right )\geq c_1\left \| \bigtriangledown f_k \right \|min\left ( \bigtriangleup k,\frac{\left \| \bigtriangledown f_k\right \|}{\left \| B_k \right \|} \right )</math>

=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960<ref>H. H. Rosenbrock, An Automatic Method for Finding the Greatest or Least Value of a Function, ''The Computer Journal'', Volume 3, Issue 3, 1960, Pages 175–184, <nowiki>https://doi.org/10.1093/comjnl/3.3.175</nowiki></ref>, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's <code>fminunc</code> as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.
[[File:Trust-region method example trajectory.png|thumb|576x576px|Trust-region method trajectory of Rosenbrock function starting from (0,0). The data points represent the optimal solutions after each iteration, ending at iteration number 16 (1,1).]]

'''Iteration Process'''

'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
'''Approaches for a convex model problem'''

* Levenberg–Marquardt Steps

The objective function is iteratively approximated by a quadratic surface, and the estimate is updated. However, this method may fail to converge if the initial guess is too large or

too small. The trust region methods help to control the trust region size, preventing each step from being too far from the optimum.

* Powell Dogleg Steps

Compared to Levenberg–Marquardt steps, the objective function is iteratively approximated by a linear surface, and the estimate is updated as well. Besides, the Levenberg–

Marquardt steps provide an exact solution to the model problem, while the dogleg method provides only an approximate solution.

'''Approaches for a nonconvex model problem'''

If the exact Hessian is not positive definite, then a dogleg method that relies on Newton steps may be ascent steps or unbounded steps. Furthermore, the Levenberg–Marquardt method may not be flexible to exploit the size of the trust region. However, the trust region method can used to iteratively minimize a quadratic model of the Lagrangian subject to a possibly relaxed linearization of the problem constraints and a trust region constraint.

=Conclusion=
Trusted region is a powerful method that can update the objective function in each step to ensure the model is always getting improved while keeping the previously learnt knowledge as the baseline. Nowadays, trust region algorithms are widely used in machine learning, applied mathematics, physics, chemistry, biology, etc. It is believed that the trust region method will have more far-reaching development in a wider range of fields in the near future.

=References=
[1] J. Nocedal, S. J. Wright, ''Numerical Optimization''. Springer, 1999.

[2] W. Sun and Y.-x. Yuan, Optimization theory and methods : nonlinear programming. New York: Springer, 2006.

[3] S. Boyd, L. Vandenberghe, Convex Optimization. Cambridge University Press, 2009

[4] Trust region. (2020). Retrieved November 10, 2021, from <nowiki>https://en.wikipedia.org/wiki/Trust_region</nowiki>.<references />

Trust-region methods

2021-12-14T15:37:45Z

Ty262:

Trust-region methods

2021-12-14T03:27:16Z

Ty262: /* Methodology and theory */

Trust-region methods

2021-12-06T15:35:28Z

Ty262: /* Numerical example */

Trust-region methods

2021-12-06T15:32:43Z

Ty262: /* Numerical example */

File:Trust-region method example trajectory.png

2021-12-06T15:26:14Z

Ty262:

Trust-region method example trajectory

Trust-region methods

2021-12-06T15:25:06Z

Ty262: /* Numerical example */

File:Optimization trajectory of the example.jpg

2021-12-06T15:24:13Z

Ty262: Ty262 uploaded a new version of File:Optimization trajectory of the example.jpg

Optimization trajectory of the example

File:TRM Trajectory.jpg

2021-12-06T15:03:22Z

Ty262: Ty262 uploaded a new version of File:TRM Trajectory.jpg

Optimization trajectory of example

Trust-region methods

2021-12-06T14:58:08Z

Ty262: /* References */

Trust-region methods

2021-12-06T14:16:05Z

Ty262: /* References */

Trust-region methods

2021-12-06T14:12:08Z

Ty262: /* Numerical example */

Trust-region methods

2021-12-06T14:05:43Z

Ty262:

Trust-region methods

2021-12-06T14:04:01Z

Ty262:

Autor: Chun-Yu Chou, Ting-Guang Yeh, Yun-Chung Pan, Chen-Hua Wang, Fall 2021
=Introduction=

Trust region method is a numerical optimization method that is employed to solve non-linear programming (NLP) problem. Instead of finding objective solution of the original function f, in each step the method defines a neighborhood around current best solution xk as a trust region f’ (typically by using quadratic model), which is capable of representing the f function appropriately, in order to derive the next point xk+1. Different from line search, the model selects the direction and step size simultaneously. For example, in a minimization problem, if the decrease in the value of optimal solution is not sufficient, we can conclude that the region is too large to get close to the minimizer of the objective function, so we will shrink the f’ to find the solution again. On the other hand, if such decrease is significant, it is believed that the model has adequate representation to the problem. Generally, the step direction depends on extent that the region is altered in the previous iteration.
=Methodology and theory=
'''Cauchy point calculation'''

Similar to line serach method which do not require optimal step lengths to be convergent, trust-region method is suffficient for global convergence purpose to find an approximate solution pk that lies within trust region.

<math>p_{c}^{K}=-\tau _{k}\frac{\Delta k}{\left \| \bigtriangledown f_{k} \right \|}\bigtriangledown f_{k}</math>

if <math>\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k}\leq 0</math>, <math>\tau _{k}=1</math>

otherewise, <math>\tau _{k}= min\left ( \left \| \bigtriangledown f_{k} \right \|^{3}/\left ( \bigtriangleup _{k}\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k} \right ),1 \right ) </math>

'''Improving on the couchy point'''

The reason we improving on the couchy point is that we just implementing the steepest decent method with a particular choice of step length by using cauchy point. However, steepest decent performs poorly even if an optimial step length is used at every iteration.

<math>min m(p)=f+g^{T}p+\frac{1}{2}p^{T}B_{p} </math>, <math>p\in R^{n} </math> s.t. <math>\left \| p \right \|\leq \Delta </math>

'''Dogleg method'''

The dogleg method chooses p to minimize the model m along this path.Furthermore,gogled method is limited to

the trust-region bound. Since the dogleg path interacts the trust region at most one points and intersectin can be computed anlytically, there is no need to conduct a search.

<math>\tilde{p}=\tau p^{U} </math>, when <math>0\leq \tau \leq 1 </math>

<math>\tilde{p}= p^{U}+\left (\tau -1 \right )\left ( p^{B}-p^{U} \right ) </math>, when <math>1\leq \tau \leq 2 </math>

where <math>p^{U}=-\frac{g^{T}g}{g^{T}Bg}g </math>, <math>p^{B} </math>=opitimal solution of quadratic model

'''Steihau's approach'''

Given<math>\epsilon > 0 </math>

Set <math>p_{0}=0,r_{0}=g,d_{0}=-r_{0} </math>

if<math>\left \| r_{0} \right \|< \epsilon </math>

return p=p0

for j=0,1,2,.....

if <math>d_{j}^{T}Bd_{j}\leq 0 </math>

Find <math>\tau </math>such that minimizes m(p) and satisfies<math>\left \| p \right \|=\Delta </math>

return p;

Set <math>\alpha _{j}=r_{j}^{T}r_{j}/d_{j}^{T}Bd_{j}</math>

Set <math> p_{j+1}=p_{j}+\alpha _{j}d_{j}</math>

if <math>\left \| p_{j+1} \right \|\geq \Delta</math>

Find <math>\tau \geq 0</math> such that <math>p=p_{j}+\tau d_{j}</math> satisfies <math>\left \| p \right \|=\Delta </math>

return p;

Set <math>r_{j+1}=r_{j}+\alpha _{j}Bd_{j}</math>

if <math> \left \| r_{j+1} \right \|< \epsilon \left \| r_{0} \right \|</math>

return <math>p=p_{j+1}</math>

Set <math>\beta _{j+1} = r_{j+1}^{T}r_{j+1}/r_{j}^{T}r_{j}</math>

Set <math>d_{j+1}= r_{j+1}+ \beta _{j+1}d_{j}</math>

end(for)

=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's fminunc as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.

'''Iteration Process'''[[File:TRM Trajectory.jpg|thumb|557x557px|Optimization trajectory of the example]]'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
'''Approaches for a convex model problem'''

* Levenberg–Marquardt Steps

The objective function is iteratively approximated by a quadratic surface, and the estimate is updated. However, this method may fail to converge if the initial guess is too large or

too small. The trust region methods help to control the trust region size, preventing each step from being too far from the optimum.

* Powell Dogleg Steps

Compared to Levenberg–Marquardt steps, the objective function is iteratively approximated by a linear surface, and the estimate is updated as well. Besides, the Levenberg–

Marquardt steps provide an exact solution to the model problem, while the dogleg method provides only an approximate solution.

'''Approaches for a nonconvex model problem'''

If the exact Hessian is not positive definite, then a dogleg method that relies on Newton steps may be ascent steps or unbounded steps. Furthermore, the Levenberg–Marquardt method may not be flexible to exploit the size of the trust region. However, the trust region method can used to iteratively minimize a quadratic model of the Lagrangian subject to a possibly relaxed linearization of the problem constraints and a trust region constraint.

=Conclusion=
Trusted region is a powerful method that can update the objective function in each step to ensure the model is always getting improved while keeping the previously learnt knowledge as the baseline. Nowadays, trust region algorithms are widely used in machine learning, applied mathematics, physics, chemistry, biology, etc. It is believed that the trust region method will have more far-reaching development in a wider range of fields in the near future.

=References=
[1] J. Nocedal, S. J. Wright, ''Numerical Optimization''. Springer, 1999.

[2] W. Sun and Y.-x. Yuan, Optimization theory and methods : nonlinear programming. New York: Springer, 2006.

[3] S. Boyd, L. Vandenberghe, Convex Optimization. Cambridge University Press, 2009

[4] Trust region. (2020). Retrieved November 10, 2021, from <nowiki>https://en.wikipedia.org/wiki/Trust_region</nowiki>.

Trust-region methods

2021-11-29T02:19:23Z

Ty262:

Autor: Chun-Yu Chou (cc2398), Ting-Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021
=Introduction=

Trust region method is a numerical optimization method that is employed to solve non-linear programming (NLP) problem. Instead of finding objective solution of the original function f, in each step the method defines a neighborhood around current best solution xk as a trust region f’ (typically by using quadratic model), which is capable of representing the f function appropriately, in order to derive the next point xk+1. Different from line search, the model selects the direction and step size simultaneously. For example, in a minimization problem, if the decrease in the value of optimal solution is not sufficient, we can conclude that the region is too large to get close to the minimizer of the objective function, so we will shrink the f’ to find the solution again. On the other hand, if such decrease is significant, it is believed that the model has adequate representation to the problem. Generally, the step direction depends on extent that the region is altered in the previous iteration.
=Methodology and theory=
'''Cauchy point calculation'''

Similar to line serach method which do not require optimal step lengths to be convergent, trust-region method is suffficient for global convergence purpose to find an approximate solution pk that lies within trust region.

<math>p_{c}^{K}=-\tau _{k}\frac{\Delta k}{\left \| \bigtriangledown f_{k} \right \|}\bigtriangledown f_{k}</math>

if <math>\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k}\leq 0</math>, <math>\tau _{k}=1</math>

otherewise, <math>\tau _{k}= min\left ( \left \| \bigtriangledown f_{k} \right \|^{3}/\left ( \bigtriangleup _{k}\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k} \right ),1 \right ) </math>

'''Improving on the couchy point'''

The reason we improving on the couchy point is that we just implementing the steepest decent method with a particular choice of step length by using cauchy point. However, steepest decent performs poorly even if an optimial step length is used at every iteration.

<math>min m(p)=f+g^{T}p+\frac{1}{2}p^{T}B_{p} </math>, <math>p\in R^{n} </math> s.t. <math>\left \| p \right \|\leq \Delta </math>

'''Dogleg method'''

The dogleg method chooses p to minimize the model m along this path.Furthermore,gogled method is limited to

the trust-region bound. Since the dogleg path interacts the trust region at most one points and intersectin can be computed anlytically, there is no need to conduct a search.

<math>\tilde{p}=\tau p^{U} </math>, when <math>0\leq \tau \leq 1 </math>

<math>\tilde{p}= p^{U}+\left (\tau -1 \right )\left ( p^{B}-p^{U} \right ) </math>, when <math>1\leq \tau \leq 2 </math>

where <math>p^{U}=-\frac{g^{T}g}{g^{T}Bg}g </math>, <math>p^{B} </math>=opitimal solution of quadratic model

'''Steihau's approach'''

Given<math>\epsilon > 0 </math>

Set <math>p_{0}=0,r_{0}=g,d_{0}=-r_{0} </math>

if<math>\left \| r_{0} \right \|< \epsilon </math>

return p=p0

for j=0,1,2,.....

if <math>d_{j}^{T}Bd_{j}\leq 0 </math>

Find <math>\tau </math>such that minimizes m(p) and satisfies<math>\left \| p \right \|=\Delta </math>

return p;

Set <math>\alpha _{j}=r_{j}^{T}r_{j}/d_{j}^{T}Bd_{j}</math>

Set <math> p_{j+1}=p_{j}+\alpha _{j}d_{j}</math>

if <math>\left \| p_{j+1} \right \|\geq \Delta</math>

Find <math>\tau \geq 0</math> such that <math>p=p_{j}+\tau d_{j}</math> satisfies <math>\left \| p \right \|=\Delta </math>

return p;

Set <math>r_{j+1}=r_{j}+\alpha _{j}Bd_{j}</math>

if <math> \left \| r_{j+1} \right \|< \epsilon \left \| r_{0} \right \|</math>

return <math>p=p_{j+1}</math>

Set <math>\beta _{j+1} = r_{j+1}^{T}r_{j+1}/r_{j}^{T}r_{j}</math>

Set <math>d_{j+1}= r_{j+1}+ \beta _{j+1}d_{j}</math>

end(for)

=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's fminunc as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.

'''Iteration Process'''[[File:TRM Trajectory.jpg|thumb|557x557px|Optimization trajectory of the example]]'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
'''Approaches for a convex model problem'''

* Levenberg–Marquardt Steps

The objective function is iteratively approximated by a quadratic surface, and the estimate is updated. However, this method may fail to converge if the initial guess is too large or

too small. The trust region methods help to control the trust region size, preventing each step from being too far from the optimum.

* Powell Dogleg Steps

Compared to Levenberg–Marquardt steps, the objective function is iteratively approximated by a linear surface, and the estimate is updated as well. Besides, the Levenberg–

Marquardt steps provide an exact solution to the model problem, while the dogleg method provides only an approximate solution.

'''Approaches for a nonconvex model problem'''

If the exact Hessian is not positive definite, then a dogleg method that relies on Newton steps may be ascent steps or unbounded steps. Furthermore, the Levenberg–Marquardt method may not be flexible to exploit the size of the trust region. However, the trust region method can used to iteratively minimize a quadratic model of the Lagrangian subject to a possibly relaxed linearization of the problem constraints and a trust region constraint.

=Conclusion=
Trusted region is a powerful method that can update the objective function in each step to ensure the model is always getting improved while keeping the previously learnt knowledge as the baseline. Nowadays, trust region algorithms are widely used in machine learning, applied mathematics, physics, chemistry, biology, etc. It is believed that the trust region method will have more far-reaching development in a wider range of fields in the near future.

=References=
[1] J. Nocedal, S. J. Wright, ''Numerical Optimization''. Springer, 1999.

[2] W. Sun and Y.-x. Yuan, Optimization theory and methods : nonlinear programming. New York: Springer, 2006.

[3] S. Boyd, L. Vandenberghe, Convex Optimization. Cambridge University Press, 2009

[4] Trust region. (2020). Retrieved November 10, 2021, from <nowiki>https://en.wikipedia.org/wiki/Trust_region</nowiki>.

Trust-region methods

2021-11-29T02:07:18Z

Ty262: /* References */

Autor: Chun-Yu Chou (cc2398), Ting-Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021
=Introduction=
=Problem formulation=

=Methodology and theory=
'''Cauchy point calculation'''

Similar to line serach method which do not require optimal step lengths to be convergent, trust-region method is suffficient for global convergence purpose to find an approximate solution pk that lies within trust region.

<math>p_{c}^{K}=-\tau _{k}\frac{\Delta k}{\left \| \bigtriangledown f_{k} \right \|}\bigtriangledown f_{k}</math>

if <math>\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k}\leq 0</math>, <math>\tau _{k}=1</math>

otherewise, <math>\tau _{k}= min\left ( \left \| \bigtriangledown f_{k} \right \|^{3}/\left ( \bigtriangleup _{k}\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k} \right ),1 \right ) </math>

'''Improving on the couchy point'''

The reason we improving on the couchy point is that we just implementing the steepest decent method with a particular choice of step length by using cauchy point. However, steepest decent performs poorly even if an optimial step length is used at every iteration.

<math>min m(p)=f+g^{T}p+\frac{1}{2}p^{T}B_{p} </math>, <math>p\in R^{n} </math> s.t. <math>\left \| p \right \|\leq \Delta </math>

'''Dogleg method'''

The dogleg method chooses p to minimize the model m along this path.Furthermore,gogled method is limited to

the trust-region bound. Since the dogleg path interacts the trust region at most one points and intersectin can be computed anlytically, there is no need to conduct a search.

<math>\tilde{p}=\tau p^{U} </math>, when <math>0\leq \tau \leq 1 </math>

<math>\tilde{p}= p^{U}+\left (\tau -1 \right )\left ( p^{B}-p^{U} \right ) </math>, when <math>1\leq \tau \leq 2 </math>

where <math>p^{U}=-\frac{g^{T}g}{g^{T}Bg}g </math>, <math>p^{B} </math>=opitimal solution of quadratic model

'''Steihau's approach'''

Given<math>\epsilon > 0 </math>

Set <math>p_{0}=0,r_{0}=g,d_{0}=-r_{0} </math>

if<math>\left \| r_{0} \right \|< \epsilon </math>

return p=p0

for j=0,1,2,.....

if <math>d_{j}^{T}Bd_{j}\leq 0 </math>

Find <math>\tau </math>such that minimizes m(p) and satisfies<math>\left \| p \right \|=\Delta </math>

return p;

Set <math>\alpha _{j}=r_{j}^{T}r_{j}/d_{j}^{T}Bd_{j}</math>

Set <math> p_{j+1}=p_{j}+\alpha _{j}d_{j}</math>

if <math>\left \| p_{j+1} \right \|\geq \Delta</math>

Find <math>\tau \geq 0</math> such that <math>p=p_{j}+\tau d_{j}</math> satisfies <math>\left \| p \right \|=\Delta </math>

return p;

Set <math>r_{j+1}=r_{j}+\alpha _{j}Bd_{j}</math>

if <math> \left \| r_{j+1} \right \|< \epsilon \left \| r_{0} \right \|</math>

return <math>p=p_{j+1}</math>

Set <math>\beta _{j+1} = r_{j+1}^{T}r_{j+1}/r_{j}^{T}r_{j}</math>

Set <math>d_{j+1}= r_{j+1}+ \beta _{j+1}d_{j}</math>

end(for)

=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's fminunc as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.

'''Iteration Process'''[[File:TRM Trajectory.jpg|thumb|557x557px|Optimization trajectory of the example]]'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
'''Approaches for a convex model problem'''

* Levenberg–Marquardt Steps

The objective function is iteratively approximated by a quadratic surface, and the estimate is updated. However, this method may fail to converge if the initial guess is too large or

too small. The trust region methods help to control the trust region size, preventing each step from being too far from the optimum.

* Powell Dogleg Steps

Compared to Levenberg–Marquardt steps, the objective function is iteratively approximated by a linear surface, and the estimate is updated as well. Besides, the Levenberg–

Marquardt steps provide an exact solution to the model problem, while the dogleg method provides only an approximate solution.

'''Approaches for a nonconvex model problem'''

If the exact Hessian is not positive definite, then a dogleg method that relies on Newton steps may be ascent steps or unbounded steps. Furthermore, the Levenberg–Marquardt method may not be flexible to exploit the size of the trust region. However, the trust region method can used to iteratively minimize a quadratic model of the Lagrangian subject to a possibly relaxed linearization of the problem constraints and a trust region constraint.

=Conclusion=
=References=
[1] J. Nocedal, S. J. Wright, ''Numerical Optimization''. Springer, 1999.

[2] W. Sun and Y.-x. Yuan, Optimization theory and methods : nonlinear programming. New York: Springer, 2006.

[3] Wikipedia page for Trust region.

Trust-region methods

2021-11-29T02:01:48Z

Ty262:

Trust-region methods

2021-11-29T01:22:57Z

Ty262: /* Methodology and theory */

Autor: Chun-Yu Chou (cc2398), Ting-Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021
=Introduction=
=Problem formulation=

=Methodology and theory=
'''Cauchy point calculation'''

<math>p_{c}^{K}=-\tau _{k}\frac{\Delta k}{\left \| \bigtriangledown f_{k} \right \|}\bigtriangledown f_{k}</math>

if <math>\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k}\leq 0</math>, <math>\tau _{k}=1</math>

otherewise, <math>\tau _{k}= min\left ( \left \| \bigtriangledown f_{k} \right \|^{3}/\left ( \bigtriangleup _{k}\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k} \right ),1 \right ) </math>

'''Improving on the couchy point'''

<math>min m(p)=f+g^{T}p+\frac{1}{2}p^{T}B_{p} </math>, <math>p\in R^{n} </math> s.t. <math>\left \| p \right \|\leq \Delta </math>

'''Dogleg method'''

<math>\tilde{p}=\tau p^{U} </math>, when <math>0\leq \tau \leq 1 </math>

<math>\tilde{p}= p^{U}+\left (\tau -1 \right )\left ( p^{B}-p^{U} \right ) </math>, when <math>1\leq \tau \leq 2 </math>

where <math>p^{U}=-\frac{g^{T}g}{g^{T}Bg}g </math>, <math>p^{B} </math>=opitimal point

'''Steihau's approach'''

Given<math>\epsilon > 0 </math>

Set<math>p_{0}=0,r_{0}=g,d_{0}=-r_{0} </math>

if<math>\left \| r_{0} \right \|< \epsilon </math>

return p=p0

for j=0,1,2,.....

if <math>d_{j}^{T}Bd_{j}\leq 0 </math>

Find <math>\tau </math>such that minimizes m(p) and satisfies<math>\left \| p \right \|=\Delta </math>

return p;

Set

Set

=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's fminunc as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.

'''Iteration Process'''[[File:TRM Trajectory.jpg|thumb|557x557px|Optimization trajectory of the example]]'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
'''Approaches for a convex model problem'''

* Levenberg–Marquardt Steps

The objective function is iteratively approximated by a quadratic surface, and the estimate is updated. However, this method may fail to converge if the initial guess is too large or

too small. The trust region methods help to control the trust region size, preventing each step from being too far from the optimum.

* Powell Dogleg Steps

Compared to Levenberg–Marquardt steps, the objective function is iteratively approximated by a linear surface, and the estimate is updated as well. Besides, the Levenberg–

Marquardt steps provide an exact solution to the model problem, while the dogleg method provides only an approximate solution.

'''Approaches for a nonconvex model problem'''

If the exact Hessian is not positive definite, then a dogleg method that relies on Newton steps may be ascent steps or unbounded steps. Furthermore, the Levenberg–Marquardt method may not be flexible to exploit the size of the trust region. However, the trust region method can used to iteratively minimize a quadratic model of the Lagrangian subject to a possibly relaxed linearization of the problem constraints and a trust region constraint.

=Conclusion=
=References=

Trust-region methods

2021-11-29T01:19:04Z

Ty262: /* Methodology and theory */

Autor: Chun-Yu Chou (cc2398), Ting-Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021
=Introduction=
=Problem formulation=

=Methodology and theory=
'''Cauchy point calculation'''

<math>p_{c}^{K}=-\tau _{k}\frac{\Delta k}{\left \| \bigtriangledown f_{k} \right \|}\bigtriangledown f_{k}</math>

if <math>\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k}\leq 0</math>, <math>\tau _{k}=1</math>

otherewise, <math>\tau _{k}= min\left ( \left \| \bigtriangledown f_{k} \right \|^{3}/\left ( \bigtriangleup _{k}\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k} \right ),1 \right ) </math>

'''Improving on the couchy point'''

<math>min m(p)=f+g^{T}p+\frac{1}{2}p^{T}B_{p} </math>, <math>p\in R^{n} </math> s.t. <math>\left \| p \right \|\leq \Delta </math>

'''Dogleg method'''

<math>\tilde{p}=\tau p^{U} </math>, when <math>0\leq \tau \leq 1 </math>

<math>\tilde{p}= p^{U}+\left (\tau -1 \right )\left ( p^{B}-p^{U} \right ) </math>, when <math>1\leq \tau \leq 2 </math>

where <math>p^{U}=-\frac{g^{T}g}{g^{T}Bg}g </math>, <math>p^{B} </math>=opitimal point

'''Steihau's approach'''

Given<math>\epsilon > 0 </math>

Set<math>p_{0}=0,r_{0}=g,d_{0}=-r_{0} </math>

return

for j=0,1,2,.....

if

Find such that minimizes m(p) and satisfies

return p;

Set

Set

=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's fminunc as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.

'''Iteration Process'''[[File:TRM Trajectory.jpg|thumb|557x557px|Optimization trajectory of the example]]'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
'''Approaches for a convex model problem'''

* Levenberg–Marquardt Steps

The objective function is iteratively approximated by a quadratic surface, and the estimate is updated. However, this method may fail to converge if the initial guess is too large or

too small. The trust region methods help to control the trust region size, preventing each step from being too far from the optimum.

* Powell Dogleg Steps

Compared to Levenberg–Marquardt steps, the objective function is iteratively approximated by a linear surface, and the estimate is updated as well. Besides, the Levenberg–

Marquardt steps provide an exact solution to the model problem, while the dogleg method provides only an approximate solution.

'''Approaches for a nonconvex model problem'''

If the exact Hessian is not positive definite, then a dogleg method that relies on Newton steps may be ascent steps or unbounded steps. Furthermore, the Levenberg–Marquardt method may not be flexible to exploit the size of the trust region. However, the trust region method can used to iteratively minimize a quadratic model of the Lagrangian subject to a possibly relaxed linearization of the problem constraints and a trust region constraint.

=Conclusion=
=References=

Trust-region methods

2021-11-29T01:02:53Z

Ty262: /* Methodology and theory */

Autor: Chun-Yu Chou (cc2398), Ting-Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021
=Introduction=
=Problem formulation=

=Methodology and theory=
'''Cauchy point calculation'''

<math>p_{c}^{K}=-\tau _{k}\frac{\Delta k}{\left \| \bigtriangledown f_{k} \right \|}\bigtriangledown f_{k}</math>

if <math>\bigtriangledown f_{k}^{T}B_{k}\bigtriangledown f_{k}\leq 0</math>, <math>\tau _{k}=1</math>

'''Improving on the couchy point'''

'''Dogleg method'''

'''Steihau's approach'''

=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's fminunc as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.

'''Iteration Process'''[[File:TRM Trajectory.jpg|thumb|557x557px|Optimization trajectory of the example]]'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
'''Approaches for a convex model problem'''

* Levenberg–Marquardt Steps

The objective function is iteratively approximated by a quadratic surface, and the estimate is updated. However, this method may fail to converge if the initial guess is too large or

too small. The trust region methods help to control the trust region size, preventing each step from being too far from the optimum.

* Powell Dogleg Steps

Compared to Levenberg–Marquardt steps, the objective function is iteratively approximated by a linear surface, and the estimate is updated as well. Besides, the Levenberg–

Marquardt steps provide an exact solution to the model problem, while the dogleg method provides only an approximate solution.

'''Approaches for a nonconvex model problem'''

If the exact Hessian is not positive definite, then a dogleg method that relies on Newton steps may be ascent steps or unbounded steps. Furthermore, the Levenberg–Marquardt method may not be flexible to exploit the size of the trust region. However, the trust region method can used to iteratively minimize a quadratic model of the Lagrangian subject to a possibly relaxed linearization of the problem constraints and a trust region constraint.

=Conclusion=
=References=

Trust-region methods

2021-11-29T00:44:11Z

Ty262:

Autor: Chun-Yu Chou (cc2398), Ting-Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021
=Introduction=
=Problem formulation=

=Methodology and theory=
Cauchy point calculation

Improving on the couchy point

Dogleg method

Steihau's approach

=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's fminunc as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.

'''Iteration Process'''[[File:TRM Trajectory.jpg|thumb|557x557px|Optimization trajectory of the example]]'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
'''Approaches for a convex model problem'''

* Levenberg–Marquardt Steps

The objective function is iteratively approximated by a quadratic surface, and the estimate is updated. However, this method may fail to converge if the initial guess is too large or

too small. The trust region methods help to control the trust region size, preventing each step from being too far from the optimum.

* Powell Dogleg Steps

Compared to Levenberg–Marquardt steps, the objective function is iteratively approximated by a linear surface, and the estimate is updated as well. Besides, the Levenberg–

Marquardt steps provide an exact solution to the model problem, while the dogleg method provides only an approximate solution.

'''Approaches for a nonconvex model problem'''

If the exact Hessian is not positive definite, then a dogleg method that relies on Newton steps may be ascent steps or unbounded steps. Furthermore, the Levenberg–Marquardt method may not be flexible to exploit the size of the trust region. However, the trust region method can used to iteratively minimize a quadratic model of the Lagrangian subject to a possibly relaxed linearization of the problem constraints and a trust region constraint.

=Conclusion=
=References=

File:CodeCog 1.gif

2021-11-28T18:28:43Z

Ty262:

Trust-region methods

2021-11-28T00:43:20Z

Ty262: /* Numerical example */

Autor: Chun-Yu Chou (cc2398), Ting-Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021
=Introduction=
=Problem formulation=
=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's fminunc as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.

'''Iteration Process'''[[File:TRM Trajectory.jpg|thumb|557x557px|Optimization trajectory of the example]]'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
=Conclusion=
=References=

Trust-region methods

2021-11-27T06:09:56Z

Ty262: /* Numerical example */

Trust-region methods

2021-11-27T06:04:01Z

Ty262: /* Numerical example */

Autor: Chun-Yu Chou (cc2398), Ting Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021
=Introduction=
=Problem formulation=
=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's fminunc as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.

'''Iteration Process'''[[File:TRM Trajectory.jpg|thumb|557x557px|Optimization trajectory of the example]]'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot.

'''Iteration 2:''' Start with '''<math>x=0.25
</math>, <math>y=0
</math>'''. The new iteration gives a good prediction, which increases the trust-region's size. The new optimal solution within the trust-region is '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''.

'''Iteration 3:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is <math>x=0.371151679
</math>, <math>y=0.124075855

</math>.

...

'''Iteration 7:''' Start with '''<math>x=0.765122406
</math>, <math>y=0.560476539

</math>'''. The new iteration gives a poor prediction, which decreases the trust-region's size to improve the model's validity. The new optimal solution within the trust-region is '''<math>x=0.804352654

</math>, ''' <math>y=0.645444179

</math>.

'''Iteration 8:''' Start with '''<math>x=0.804352654

</math>, <math>y=0.645444179

</math>'''.The new iteration gives a poor prediction, therefore current best solution is unchanged and the radius for the trust-region is decreased.

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''.

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
=Conclusion=
=References=

Trust-region methods

2021-11-27T05:47:22Z

Ty262: /* Numerical example */

Autor: Chun-Yu Chou (cc2398), Ting Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021
=Introduction=
=Problem formulation=
=Numerical example=
Here we will use the trust-region method to solve a classic optimization problem, the Rosenbrock function. The Rosenbrock function is a non-convex function, introduced by Howard H. Rosenbrock in 1960, which is often used as a performance test problem for optimization algorithms. This problem is solved using MATLAB's fminunc as the solver, with 'trust-region' as the solving algorithm which uses the preconditioned conjugate method.

The function is defined by

<math>\min f(x,y)=100(y-x^2)^2+(1-x)^2</math>

The starting point chosen is <math>x=0</math> <math>y=0
</math>.
[[File:TRM Trajectory.jpg|thumb|565x565px|Optimization trajectory of the example]]

'''Iteration Process'''

'''Iteration 1:''' The algorithm starts from the initial point of <math>x=0</math>, <math>y=0
</math>. The Rosenbrock function is visualized with a color coded map. For the first iteration, a full step was taken and the optimal solution (<math>x=0.25</math>, <math>y=0
</math>) within the trust-region is denoted as a red dot. For each consecutive iteration,

'''Iteration 2:''' Start with '''<math>x=0.263177536
</math>, <math>y=0.061095029
</math>'''

'''Iteration 3:''' Start with <math>x=0.371151679
</math>, <math>y=0.124075855

</math>

'''Iteration 4:''' Start with '''<math>x=0.539493472
</math>, <math>y=0.262714248

</math>'''

'''Iteration 5:''' Start with '''<math>x=0.608557768
</math>, <math>y=0.36557268

</math>'''

...

At the 16th iteration, the global optimal solution is found, '''<math>x=1
</math>, <math>y=1

</math>'''

{| class="wikitable"
|+Summary of all iterations
!Iterations
!f(x)
!x
!y
!Norm of step
!First-order optimality
|-
|1
|1
|0.25
|0
|1
|2
|-
|2
|0.953125
|0.263178
|0.061095
|0.25
|12.5
|-
|3
|0.549578
|0.371152
|0.124076
|0.0625
|1.63
|-
|4
|0.414158
|0.539493
|0.262714
|0.125
|2.74
|-
|5
|0.292376
|0.608558
|0.365573
|0.218082
|5.67
|-
|6
|0.155502
|0.765122
|0.560477
|0.123894
|0.954
|-
|7
|0.117347
|0.804353
|0.645444
|0.25
|7.16
|-
|8
|0.0385147
|0.804353
|0.645444
|0.093587
|0.308
|-
|9
|0.0385147
|0.836966
|0.69876
|0.284677
|0.308
|-
|10
|0.0268871
|0.90045
|0.806439
|0.0625
|0.351
|-
|11
|0.0118213
|0.953562
|0.90646
|0.125
|1.38
|-
|12
|0.0029522
|0.983251
|0.9659
|0.113247
|0.983
|-
|13
|0.000358233
|0.99749
|0.994783
|0.066442
|0.313
|-
|14
|1.04121e-05
|0.999902
|0.999799
|0.032202
|0.0759
|-
|15
|1.2959e-08
|1
|1
|0.005565
|0.00213
|-
|16
|2.21873e-14
|1
|1
|0.000224
|3.59E-06
|}

=Applications=
=Conclusion=
=References=

File:TRM Trajectory.jpg

2021-11-27T05:29:32Z

Ty262:

Optimization trajectory of example

File:Optimization trajectory of the example.jpg

2021-11-27T05:24:07Z

Ty262: Ty262 uploaded a new version of File:Optimization trajectory of the example.jpg

Optimization trajectory of the example

File:Optimization trajectory of the example.jpg

2021-11-27T05:19:25Z

Ty262:

Optimization trajectory of the example

Trust-region methods

2021-11-27T05:16:43Z

Ty262: /* Numerical example */

Trust-region methods

2021-11-27T05:12:58Z

Ty262: /* Numerical example */

Trust-region methods

2021-11-27T02:18:18Z

Ty262:

Autor: Chun-Yu Chou (cc2398), Ting Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021
=Introduction=
=Problem formulation=
=Numerical example=
=Applications=
=Conclusion=
=References=

Trust-region methods

2021-10-22T19:40:56Z

Ty262:

Autor: Chun-Yu Chou (cc2398), Ting Guang Yeh (ty262), Yun-Chung Pan (yp392), Chen-Hua Wang (cw893), Fall 2021

Trust-region methods

2021-10-22T19:40:24Z

Ty262: Created page with "Autor: Chun-Yu Chou(cc2398) Ting Guang Yeh(ty262) Yun-Chung Pan (yp392) Chen-Hua Wang (cw893) Fall 2021"

Autor: Chun-Yu Chou(cc2398) Ting Guang Yeh(ty262) Yun-Chung Pan (yp392) Chen-Hua Wang (cw893) Fall 2021