Trust-region methods - Revision history

Fall2024 Wiki Team23 at 07:25, 13 December 2024

2024-12-13T07:25:45Z

← Older revision		Revision as of 03:25, 13 December 2024
Line 41:		Line 41:

	(2) <math>m_k(p) = f_k + \nabla f_k^T p + \frac{1}{2} p^T B_k p		(2) <math>m_k(p) = f_k + \nabla f_k^T p + \frac{1}{2} p^T B_k p
	</math> <math>s.t. \|\|p\|\| \leq \Delta_k		</math>   <math>s.t. \|\|p\|\| \leq \Delta_k
	</math>		</math>

Line 57:		Line 57:
	</math> must be determined at each iteration.		</math> must be determined at each iteration.

	(3) <math>p_k=\frac{f(x_k) - f(x_k+p_k)}{m_k(0) - m_k(p_k)} = \frac{actual\; ~~prediction~~}{predicted\; reduction}		(3) <math>p_k=\frac{f(x_k) - f(x_k+p_k)}{m_k(0) - m_k(p_k)} = \frac{actual\; reduction}{predicted\; reduction}
	</math>		</math>

Line 328:		Line 328:

	<math>m_1'(p)= -2+2p =0		<math>m_1'(p)= -2+2p =0
	</math> <math>p=1		</math>   <math>p=1
	</math>		</math>

Fall2024 Wiki Team23: minor edits

2024-12-13T07:20:38Z

minor edits

← Older revision		Revision as of 03:20, 13 December 2024
Line 41:		Line 41:

	(2) <math>m_k(p) = f_k + \nabla f_k^T p + \frac{1}{2} p^T B_k p		(2) <math>m_k(p) = f_k + \nabla f_k^T p + \frac{1}{2} p^T B_k p
	</math> <math>s.t. \|\|p\|\| \leq \Delta_k		</math> <math>s.t. \|\|p\|\| \leq \Delta_k
	</math>		</math>

Line 88:		Line 88:
	</math>. Consider the following:		</math>. Consider the following:

	<math>p_B= B_k^{-1} \nabla f_k		<math>p_B= -B_k^{-1} \nabla f_k
	</math>		</math>

Line 147:		Line 147:
	::determine <math>\tau		::determine <math>\tau
	</math> such that <math>p=p_j+\tau d_j		</math> such that <math>p=p_j+\tau d_j
	</math> minimizes (2) and satisfies <math>\|\|p\|\| ~~\leq~~ \Delta		</math> minimizes (2) and satisfies <math>\|\|p\|\| = \Delta
	</math>		</math>

	::return <math>p		::return <math>p
Line 164:		Line 164:
	::determine the positive value of <math>\tau		::determine the positive value of <math>\tau
	</math> such that <math>p=p_j+\tau d_j		</math> such that <math>p=p_j+\tau d_j
	</math> and satisfies <math>\|\|p\|\| ~~\leq~~ \Delta		</math> and satisfies <math>\|\|p\|\| = \Delta
	</math>		</math>

	::return <math>p		::return <math>p
Line 247:		Line 247:
	Step 2: form the quadratic model		Step 2: form the quadratic model

	<math>m_0(p) = ~~f_0~~ + \nabla f_0^T p + \frac{1}{2} p^T ~~B_0 p~~ = m_0(p) = 4 + (-4) p + \frac{1}{2} p^2(2)=4-4p+p^2		<math>m_0(p) = f(x_0) + \nabla f_0^T p + \frac{1}{2} p^T H_0 = m_0(p) = 4 + (-4) p + \frac{1}{2} p^2(2)=4-4p+p^2
	</math>		</math>

Line 322:		Line 322:
	Step 2: form the quadratic model		Step 2: form the quadratic model

	<math>m_1(p) = f(1) + \nabla f_0^T p + \frac{1}{2} p^~~TB_1~~= 1-2p+p^2		<math>m_1(p) = f(1) + \nabla f_0^T p + \frac{1}{2} p^TH_1= 1-2p+p^2
	</math>		</math>

Line 328:		Line 328:

	<math>m_1'(p)= -2+2p =0		<math>m_1'(p)= -2+2p =0
	</math> <math>p=1		</math> <math>p=1
	</math>		</math>

Fall2024 Wiki Team23: /* Conclusion */

2024-12-13T06:38:49Z

Conclusion

← Older revision		Revision as of 02:38, 13 December 2024
Line 439:		Line 439:
	=Conclusion=		=Conclusion=
	Trust region methods provide a robust and efficient framework for solving optimization problems through the construction of a region around the current solution where an accurate simplified model approximates the objective function. This approach ensures convergence, even for nonlinear and complex problems encountered in fields such as engineering. The algorithm’s advantage lies in its adaptability, dynamically adjusting the trust region based on the accuracy of the model’s predictions, thereby ensuring global and, in some cases, superlinear convergence <ref>Zhang, J., Wu, L., & Zhang, X. (2007). A Trust Region Method for Optimization Problem with Singular Solutions. <em>Applied Mathematics and Optimization</em>, 56(3), 379–394. https://doi.org/10.1007/s00245-007-9009-6</ref>. Future research directions may involve improving the scalability of trust region methods for high-dimensional problems, integrating them with machine learning frameworks for better predictive modeling <ref>Lin, C.-J., Weng, R. C., & S. Sathiya Keerthi. (2008). Trust Region Newton Method for Logistic Regression. <em>Journal of Machine Learning Research</em>, 9(22), 627–650. https://doi.org/10.1145/1390681.1390703</ref>, and developing more efficient techniques to handle constraints and uncertainties in real-world applications.		Trust region methods provide a robust and efficient framework for solving optimization problems through the construction of a region around the current solution where an accurate simplified model approximates the objective function. This approach ensures convergence, even for nonlinear and complex problems encountered in fields such as engineering. The algorithm’s advantage lies in its adaptability, dynamically adjusting the trust region based on the accuracy of the model’s predictions, thereby ensuring global and, in some cases, superlinear convergence <ref>Zhang, J., Wu, L., & Zhang, X. (2007). A Trust Region Method for Optimization Problem with Singular Solutions. <em>Applied Mathematics and Optimization</em>, 56(3), 379–394. https://doi.org/10.1007/s00245-007-9009-6</ref>. Future research directions may involve improving the scalability of trust region methods for high-dimensional problems, integrating them with machine learning frameworks for better predictive modeling <ref>Lin, C.-J., Weng, R. C., & S. Sathiya Keerthi. (2008). Trust Region Newton Method for Logistic Regression. <em>Journal of Machine Learning Research</em>, 9(22), 627–650. https://doi.org/10.1145/1390681.1390703</ref>, and developing more efficient techniques to handle constraints and uncertainties in real-world applications.


	=References=		=References=

Fall2024 Wiki Team23 at 06:36, 13 December 2024

2024-12-13T06:36:11Z

← Older revision		Revision as of 02:36, 13 December 2024
Line 5:		Line 5:
	=Introduction=		=Introduction=

	Trust region methods are iterative optimization techniques designed to find local minima or maxima of objective functions, particularly in nonlinear problems (NLP), by iteratively refining approximations within dynamically adjusted trust regions ~~[1]~~. Unlike line search methods, which determine the step size along a predefined direction, trust region methods concurrently optimize both the direction and the magnitude of the step within a specified neighborhood around the current iterate.		Trust region methods are iterative optimization techniques designed to find local minima or maxima of objective functions, particularly in nonlinear problems (NLP), by iteratively refining approximations within dynamically adjusted trust regions<ref>Nocedal, J., & Wright, S. J. (2006). <em>Numerical optimization</em>. Springer.</ref>. Unlike line search methods, which determine the step size along a predefined direction, trust region methods concurrently optimize both the direction and the magnitude of the step within a specified neighborhood around the current iterate.

	The origins of these methods date back to Levenberg, who introduced a modified version of the Gauss-Newton method for solving nonlinear least squares problems by adding a damping term to control the step size. This approach was later rediscovered and refined by Morrison and Marquardt, ultimately gaining prominence as the Levenberg-Morrison-Marquardt method [2]. Subsequent advancements led to the development and standardization of trust region methods, further improving their robustness and application.		The origins of these methods date back to Levenberg, who introduced a modified version of the Gauss-Newton method for solving nonlinear least squares problems by adding a damping term to control the step size. This approach was later rediscovered and refined by Morrison and Marquardt, ultimately gaining prominence as the Levenberg-Morrison-Marquardt method <ref>Yuan, Y. (2015b). Recent advances in trust region algorithms. <em>Mathematical Programming</em>, 151(1), 249–281. https://doi.org/10.1007/s10107-015-0893-2</ref>. Subsequent advancements led to the development and standardization of trust region methods, further improving their robustness and application.

	The central core of trust region methods lies in the idea of constructing a simplified model — often a quadratic approximation — that represents the objective function near the current point. This model serves as a surrogate, guiding the search for the optimum within a bounded region around the current estimate. The size of the trust region is dynamically adjusted based on how well the model predicts the actual behavior of the objective function. If the model is predicting accurate behavior of the objective function, the size of the trust region is increased, allowing the algorithm to explore a larger area around the current solution; the trust region is reduced if otherwise ~~[3]~~.		The central core of trust region methods lies in the idea of constructing a simplified model — often a quadratic approximation — that represents the objective function near the current point. This model serves as a surrogate, guiding the search for the optimum within a bounded region around the current estimate. The size of the trust region is dynamically adjusted based on how well the model predicts the actual behavior of the objective function. If the model is predicting accurate behavior of the objective function, the size of the trust region is increased, allowing the algorithm to explore a larger area around the current solution; the trust region is reduced if otherwise <ref>Conn, A. R., Gould, N. I. M., & Toint, P. L. (2000). <em>Trust-region methods</em>. Siam.</ref>.

	=Algorithm Discussion=		=Algorithm Discussion=
Line 93:		Line 93:
	as the full Newton step where <math>\|\|p_k\|\|\leq \Delta_k		as the full Newton step where <math>\|\|p_k\|\|\leq \Delta_k
	</math>.		</math>.


	===The Dogleg Method===		===The Dogleg Method===
Line 120:		Line 121:
	</math> cannot guaranteed to be a meaningful solution since the method is not well-suited to handle negative <math>B_k		</math> cannot guaranteed to be a meaningful solution since the method is not well-suited to handle negative <math>B_k
	</math>.		</math>.


	===The Conjugated Gradient Steihaug’s Method===		===The Conjugated Gradient Steihaug’s Method===

	In contrast to the methods above, Steihaug’s method is designed to better handle large-scale trust region subproblems. It mitigates the limitations of slower convergence and the need for a positive definite Hessian. In addition, it handles negative curvature by enabling early termination when such directions are detected or when the trust region boundary is reached. These features make the method more scalable and robust, suited for large-scale or poorly conditioned optimization problems ~~[4]~~. The method is described as follows:		In contrast to the methods above, Steihaug’s method is designed to better handle large-scale trust region subproblems. It mitigates the limitations of slower convergence and the need for a positive definite Hessian. In addition, it handles negative curvature by enabling early termination when such directions are detected or when the trust region boundary is reached. These features make the method more scalable and robust, suited for large-scale or poorly conditioned optimization problems <ref>Grippo, L., & Sciandrone, M. (2023). Introduction to Methods for Nonlinear Optimization. In <em>Unitext</em>. Springer International Publishing. https://doi.org/10.1007/978-3-031-26790-1</ref>. The method is described as follows:

	given <math>\varepsilon > 0		given <math>\varepsilon > 0
Line 188:		Line 190:
	</math> is fundamental, as the Cauchy Point is obtained right after in <math>p_1		</math> is fundamental, as the Cauchy Point is obtained right after in <math>p_1
	</math>; this condition guarantees global convergence.		</math>; this condition guarantees global convergence.


	===Termination Criteria===		===Termination Criteria===

	The convergence of a trust region algorithm (1) depends on the accuracy of the approximate solution to the subproblem (2). It is desirable that the subproblem is approximated rather than solved exactly, provided the approximation guarantees the algorithm’s convergence ~~[5]~~. Fletcher proposes that the algorithm terminates when either of the following are small ~~[6]~~:		The convergence of a trust region algorithm (1) depends on the accuracy of the approximate solution to the subproblem (2). It is desirable that the subproblem is approximated rather than solved exactly, provided the approximation guarantees the algorithm’s convergence <ref>Dutta, S. (2016). <em>Optimization in Chemical Engineering</em>. Cambridge University Press.</ref>. Fletcher proposes that the algorithm terminates when either of the following are small <ref>Fletcher, R. (1987). <em>Practical Methods of Optimization</em> (2e), John Wiley and Sons.</ref>:

	# <math>f(x_k)-f(x_{k+1})		# <math>f(x_k)-f(x_{k+1})
Line 209:		Line 212:
	=Numerical example=		=Numerical example=

	===Example One ~~- Simple~~===		===Example One===

	'''This section introduces trust region methods and demonstrates their application using a simple function as a numerical example. Consider the following:		'''This section introduces trust region methods and demonstrates their application using a simple function as a numerical example. Consider the following:
Line 360:		Line 363:
	===Example Two - Himmulblau’s Function===		===Example Two - Himmulblau’s Function===

	The following demonstrates a more complex example of trust region methods. Himmulblau’s function is a well-known mathematical function used extensively in optimization testing and research ~~[7]~~. It is defined as two real variables and is characterized by having multiple global minima. The function is non-convex and multimodal, making it an excellent candidate for demonstrating the effectiveness of optimization algorithms. The following uses Steihaug’s method.		The following demonstrates a more complex example of trust region methods. Himmulblau’s function is a well-known mathematical function used extensively in optimization testing and research <ref>Himmelblau, D. M. (2018). <em>Applied nonlinear programming</em>. McGraw-Hill.</ref>. It is defined as two real variables and is characterized by having multiple global minima. The function is non-convex and multimodal, making it an excellent candidate for demonstrating the effectiveness of optimization algorithms. The following uses Steihaug’s method.

	The function is defined as the following:		The function is defined as the following:
Line 426:		Line 429:

	===Engineering===		===Engineering===
	Trust region methods are widely used in engineering, particularly in structural optimization, to improve the stability and efficiency of design processes. These methods address challenges in high-dimensional design problems by iteratively refining solutions with defined trust regions,making them effective for complex objectives such as optimization of material distribution, minimizing stress, or improving flow geometries. For instance, Yano et al. ~~[8]~~ introduce a globally convergent method to accelerate topology optimization with trust region frameworks. This approach significantly reduces computational costs while maintaining accuracy in optimal design solutions.		Trust region methods are widely used in engineering, particularly in structural optimization, to improve the stability and efficiency of design processes. These methods address challenges in high-dimensional design problems by iteratively refining solutions with defined trust regions,making them effective for complex objectives such as optimization of material distribution, minimizing stress, or improving flow geometries. For instance, Yano et al. <ref>Yano, M., Huang, T., & Zahr, M. J. (2021). A globally convergent method to accelerate topology optimization using on-the-fly model reduction. <em>Computer Methods in Applied Mechanics and Engineering</em>, 375, 113635–113635. https://doi.org/10.1016/j.cma.2020.113635</ref> introduce a globally convergent method to accelerate topology optimization with trust region frameworks. This approach significantly reduces computational costs while maintaining accuracy in optimal design solutions.

	===Finance===		===Finance===
	Trust region methods are also increasingly applied in the financial sector as these methods ensure stable and reliable convergence even when dealing with complex, non-linear and volatile financial data. For example, in the study by Phua et al. ~~[9]~~, trust region methods were employed during the optimization of neural network training. This approach significantly improved the forecasting accuracy of major stick indices like DAX and NASDAQ by effectively managing high-dimensional and noisy financial datasets.		Trust region methods are also increasingly applied in the financial sector as these methods ensure stable and reliable convergence even when dealing with complex, non-linear and volatile financial data. For example, in the study by Phua et al. <ref>Phua, P. K. H., Xiaotian Zhu, & Chung Haur Koh. (n.d.). Forecasting stock index increments using neural networks with trust region methods. <em>Proceedings of the International Joint Conference on Neural Networks</em>, 2003. https://doi.org/10.1109/ijcnn.2003.1223354</ref>, trust region methods were employed during the optimization of neural network training. This approach significantly improved the forecasting accuracy of major stick indices like DAX and NASDAQ by effectively managing high-dimensional and noisy financial datasets.

	===Machine Learning===		===Machine Learning===
	Algorithms like ACKTR (Actor-Critic using Kronecker-Factored Trust Region) use trust regions to improve training stabilities and sample efficiencies in deep reinforcement learning. Specifically, ACKTR uses an approximation of the natural gradient to maintain a trust region during updates, preventing large and unstable parameter changes. This benefits facilitation of applications in robotics and autonomous systems ~~[10]~~.		Algorithms like ACKTR (Actor-Critic using Kronecker-Factored Trust Region) use trust regions to improve training stabilities and sample efficiencies in deep reinforcement learning. Specifically, ACKTR uses an approximation of the natural gradient to maintain a trust region during updates, preventing large and unstable parameter changes. This benefits facilitation of applications in robotics and autonomous systems <ref>Wu, Y., Elman Mansimov, Grosse, R. B., Liao, S., & Ba, J. (2017). Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation. <em>Neural Information Processing Systems</em>, 30, 5279–5288.</ref>.

	=Conclusion=		=Conclusion=
	Trust region methods provide a robust and efficient framework for solving optimization problems through the construction of a region around the current solution where an accurate simplified model approximates the objective function. This approach ensures convergence, even for nonlinear and complex problems encountered in fields such as engineering. The algorithm’s advantage lies in its adaptability, dynamically adjusting the trust region based on the accuracy of the model’s predictions, thereby ensuring global and, in some cases, superlinear convergence ~~[11]~~. Future research directions may involve improving the scalability of trust region methods for high-dimensional problems, integrating them with machine learning frameworks for better predictive modeling ~~[12]~~, and developing more efficient techniques to handle constraints and uncertainties in real-world applications.		Trust region methods provide a robust and efficient framework for solving optimization problems through the construction of a region around the current solution where an accurate simplified model approximates the objective function. This approach ensures convergence, even for nonlinear and complex problems encountered in fields such as engineering. The algorithm’s advantage lies in its adaptability, dynamically adjusting the trust region based on the accuracy of the model’s predictions, thereby ensuring global and, in some cases, superlinear convergence <ref>Zhang, J., Wu, L., & Zhang, X. (2007). A Trust Region Method for Optimization Problem with Singular Solutions. <em>Applied Mathematics and Optimization</em>, 56(3), 379–394. https://doi.org/10.1007/s00245-007-9009-6</ref>. Future research directions may involve improving the scalability of trust region methods for high-dimensional problems, integrating them with machine learning frameworks for better predictive modeling <ref>Lin, C.-J., Weng, R. C., & S. Sathiya Keerthi. (2008). Trust Region Newton Method for Logistic Regression. <em>Journal of Machine Learning Research</em>, 9(22), 627–650. https://doi.org/10.1145/1390681.1390703</ref>, and developing more efficient techniques to handle constraints and uncertainties in real-world applications.


	=References=		=References=

Fall2024 Wiki Team23 at 23:12, 12 December 2024

2024-12-12T23:12:06Z

← Older revision		Revision as of 19:12, 12 December 2024
Line 71:		Line 71:


	~~'''~~Cauchy Point~~'''~~		===Cauchy Point===

	Identical to line search, there is no need to compute the subproblem (2) to achieve optimal minimum as the model improves itself with each iteration, meaning that as long as the step lies in the trust region and provides sufficient reduction, the algorithm can converge to the best solution. This sufficient reduction can be expressed as the Cauchy Point, that is:		Identical to line search, there is no need to compute the subproblem (2) to achieve optimal minimum as the model improves itself with each iteration, meaning that as long as the step lies in the trust region and provides sufficient reduction, the algorithm can converge to the best solution. This sufficient reduction can be expressed as the Cauchy Point, that is:
Line 94:		Line 94:
	</math>.		</math>.

	~~'''~~The Dogleg Method~~'''~~		===The Dogleg Method===

	The full Newton step, however, is not feasible when the trust region constraint is active. To handle such cases, the Dogleg method is used to approximate the subproblem (2). This method finds a solution that considers two line segments. The first line is the steepest descent direction:		The full Newton step, however, is not feasible when the trust region constraint is active. To handle such cases, the Dogleg method is used to approximate the subproblem (2). This method finds a solution that considers two line segments. The first line is the steepest descent direction:
Line 121:		Line 121:
	</math>.		</math>.

	~~'''~~The Conjugated Gradient Steihaug’s Method~~'''~~		===The Conjugated Gradient Steihaug’s Method===

	In contrast to the methods above, Steihaug’s method is designed to better handle large-scale trust region subproblems. It mitigates the limitations of slower convergence and the need for a positive definite Hessian. In addition, it handles negative curvature by enabling early termination when such directions are detected or when the trust region boundary is reached. These features make the method more scalable and robust, suited for large-scale or poorly conditioned optimization problems [4]. The method is described as follows:		In contrast to the methods above, Steihaug’s method is designed to better handle large-scale trust region subproblems. It mitigates the limitations of slower convergence and the need for a positive definite Hessian. In addition, it handles negative curvature by enabling early termination when such directions are detected or when the trust region boundary is reached. These features make the method more scalable and robust, suited for large-scale or poorly conditioned optimization problems [4]. The method is described as follows:
Line 189:		Line 189:
	</math>; this condition guarantees global convergence.		</math>; this condition guarantees global convergence.

	~~'''~~Termination Criteria~~'''~~		===Termination Criteria===

	The convergence of a trust region algorithm (1) depends on the accuracy of the approximate solution to the subproblem (2). It is desirable that the subproblem is approximated rather than solved exactly, provided the approximation guarantees the algorithm’s convergence [5]. Fletcher proposes that the algorithm terminates when either of the following are small [6]:		The convergence of a trust region algorithm (1) depends on the accuracy of the approximate solution to the subproblem (2). It is desirable that the subproblem is approximated rather than solved exactly, provided the approximation guarantees the algorithm’s convergence [5]. Fletcher proposes that the algorithm terminates when either of the following are small [6]:
Line 209:		Line 209:
	=Numerical example=		=Numerical example=

	~~'''~~Simple ~~Function<br />~~'''This section introduces trust region methods and demonstrates their application using a simple function as a numerical example. Consider the following:		===Example One - Simple===

			'''This section introduces trust region methods and demonstrates their application using a simple function as a numerical example. Consider the following:

	<math>f(x)=(x-2)^2		<math>f(x)=(x-2)^2
Line 223:		Line 225:


	Iteration 1:		'''Iteration 1:'''

	To calculate, begin the initial point at <math>x_0=0		To calculate, begin the initial point at <math>x_0=0
Line 298:		Line 300:


	Iteration 2:		'''Iteration 2: '''

	The point now is at <math>x_1=1		The point now is at <math>x_1=1
Line 356:		Line 358:
	</math>, and therefore terminates.		</math>, and therefore terminates.

			===Example Two - Himmulblau’s Function===
	~~'''~~Himmulblau’s Function~~'''~~

	The following demonstrates a more complex example of trust region methods. Himmulblau’s function is a well-known mathematical function used extensively in optimization testing and research [7]. It is defined as two real variables and is characterized by having multiple global minima. The function is non-convex and multimodal, making it an excellent candidate for demonstrating the effectiveness of optimization algorithms. The following uses Steihaug’s method.		The following demonstrates a more complex example of trust region methods. Himmulblau’s function is a well-known mathematical function used extensively in optimization testing and research [7]. It is defined as two real variables and is characterized by having multiple global minima. The function is non-convex and multimodal, making it an excellent candidate for demonstrating the effectiveness of optimization algorithms. The following uses Steihaug’s method.
Line 382:		Line 383:

	</math>		</math>
			[[File:Trust-Region-Radius.png\|300px\|right\|thumb\|The figure illustrates how the trust region radius adjusts throughout the optimization process, reflecting the optimizer’s confidence in the model’s predictions.]]


	Due to the complexities in the calculations involved in the trust region method algorithm, the '''minimize''' function with the '''<nowiki/>'trust-constr'''' method from the SciPy library in Python can be utilized to solve this problem. Consider the following implementation:		Due to the complexities in the calculations involved in the trust region method algorithm, the '''minimize''' function with the '''<nowiki/>'trust-constr'''' method from the SciPy library in Python can be utilized to solve this problem. Consider the following implementation:
Line 387:		Line 390:
	'''minimize(method=’trust-constr’)'''		'''minimize(method=’trust-constr’)'''

	Iteration 1:		'''Iteration 1:'''

	To calculate, begin the optimization with the initial guess as <math>(-4.0, 0)		To calculate, begin the optimization with the initial guess as <math>(-4.0, 0)
Line 396:		Line 399:
	</math>.		</math>.

	Iteration 2:		[[File:Trust-Region-Heatmap.png\|300px\|right\|thumb\|The figure shows the trajectory of the optimizer from the initial guess to the found minimum over the contour plot of Hummuelblau’s function.]]


			'''Iteration 2:'''

	In this iteration, the updated point <math>(-4.0, 0)		In this iteration, the updated point <math>(-4.0, 0)
Line 403:		Line 409:
	</math>. The optimal solution obtained from the previous iteration is retained for the next step.		</math>. The optimal solution obtained from the previous iteration is retained for the next step.

	Iteration 3:
			'''Iteration 3:'''

	With the updated point <math>(-3.382, -0.786)		With the updated point <math>(-3.382, -0.786)
Line 416:		Line 423:

	=Applications=		=Applications=
	~~'''Approach on Newton~~ methods ~~on Riemannian manifold'''~~		Trust region methods are applied in optimization problems across various domains due to their robustness, adaptability, and efficiency in handling complex constraints. Their ability to balance local and global optimization strategies makes them invaluable in solving high-dimensional, nonlinear, and constrained problems. These application areas include:

			===Engineering===
			Trust region methods are widely used in engineering, particularly in structural optimization, to improve the stability and efficiency of design processes. These methods address challenges in high-dimensional design problems by iteratively refining solutions with defined trust regions,making them effective for complex objectives such as optimization of material distribution, minimizing stress, or improving flow geometries. For instance, Yano et al. [8] introduce a globally convergent method to accelerate topology optimization with trust region frameworks. This approach significantly reduces computational costs while maintaining accuracy in optimal design solutions.

	~~'''Approach on policy~~ optimization~~'''~~		===Finance===
			Trust region methods are also increasingly applied in the financial sector as these methods ensure stable and reliable convergence even when dealing with complex, non-linear and volatile financial data. For example, in the study by Phua et al. [9], trust region methods were employed during the optimization of neural network training. This approach significantly improved the forecasting accuracy of major stick indices like DAX and NASDAQ by effectively managing high-dimensional and noisy financial datasets.

			===Machine Learning===
			Algorithms like ACKTR (Actor-Critic using Kronecker-Factored Trust Region) use trust regions to improve training stabilities and sample efficiencies in deep reinforcement learning. Specifically, ACKTR uses an approximation of the natural gradient to maintain a trust region during updates, preventing large and unstable parameter changes. This benefits facilitation of applications in robotics and autonomous systems [10].

	=Conclusion=		=Conclusion=
			Trust region methods provide a robust and efficient framework for solving optimization problems through the construction of a region around the current solution where an accurate simplified model approximates the objective function. This approach ensures convergence, even for nonlinear and complex problems encountered in fields such as engineering. The algorithm’s advantage lies in its adaptability, dynamically adjusting the trust region based on the accuracy of the model’s predictions, thereby ensuring global and, in some cases, superlinear convergence [11]. Future research directions may involve improving the scalability of trust region methods for high-dimensional problems, integrating them with machine learning frameworks for better predictive modeling [12], and developing more efficient techniques to handle constraints and uncertainties in real-world applications.


	=References=		=References=

Fall2024 Wiki Team23: /* Algorithm Discussion */

2024-12-12T08:05:03Z

Algorithm Discussion

← Older revision		Revision as of 04:05, 12 December 2024
Line 93:		Line 93:
	as the full Newton step where <math>\|\|p_k\|\|\leq \Delta_k		as the full Newton step where <math>\|\|p_k\|\|\leq \Delta_k
	</math>.		</math>.



	'''The Dogleg Method'''		'''The Dogleg Method'''
Line 136:		Line 134:
	</math>		</math>

	return <math>p_0 = p_j		:return <math>p_0 = p_j
	</math>;		</math>;

Line 142:		Line 140:
	</math>,		</math>,

	if <math>d_j^TBd_j\leq0		:if <math>d_j^TBd_j\leq0
	</math>		</math>

	determine <math>\tau		::determine <math>\tau
	</math> such that <math>p=p_j+\tau d_j		</math> such that <math>p=p_j+\tau d_j
	</math> minimizes (2) and satisfies <math>\|\|p\|\| \leq \Delta		</math> minimizes (2) and satisfies <math>\|\|p\|\| \leq \Delta
	</math>		</math>

	return <math>p		::return <math>p
	</math>;		</math>;

	set <math>\alpha _j =\frac{r_j^Tr_j}{d_j^TBd_j}		:set <math>\alpha _j =\frac{r_j^Tr_j}{d_j^TBd_j}
	</math>;		</math>;

	set <math>p_{j+1} = \alpha _jd_j		:set <math>p_{j+1} = \alpha _jd_j
	</math>;		</math>;

	if <math>\|\|p_{j+1}\|\| \geq \Delta		:if <math>\|\|p_{j+1}\|\| \geq \Delta
	</math>;		</math>;

	determine the positive value of <math>\tau		::determine the positive value of <math>\tau
	</math> such that <math>p=p_j+\tau d_j		</math> such that <math>p=p_j+\tau d_j
	</math> and satisfies <math>\|\|p\|\| \leq \Delta		</math> and satisfies <math>\|\|p\|\| \leq \Delta
	</math>		</math>

	return <math>p		::return <math>p
	</math>;		</math>;

	set <math>r_{j+1}=r_j+\alpha_jBd_j		:set <math>r_{j+1}=r_j+\alpha_jBd_j
	</math>;		</math>;

	if <math>\|\|r_{j+1}\|\| \leq \varepsilon		:if <math>\|\|r_{j+1}\|\| \leq \varepsilon
	</math>		</math>

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

	set <math>\beta_{j+1}=\frac{r_{j+1}^Tr_{j+1}}{r_{j+1}r_j}		:set <math>\beta_{j+1}=\frac{r_{j+1}^Tr_{j+1}}{r_{j+1}r_j}
	</math>;		</math>;

	set <math>d_{j+1}= -r_{j+1}+\beta_{j+1}d_j		:set <math>d_{j+1}= -r_{j+1}+\beta_{j+1}d_j
	</math>;		</math>;

Line 288:		Line 286:
	Step 6: update trust region and accept/reject step		Step 6: update trust region and accept/reject step

	Acceptant criteria for the ratio is typically as ~~the following~~ (may vary):		Acceptant criteria for the ratio are typically as follows (may vary):

	If <math>p<0.25		If <math>p<0.25
Line 296:		Line 294:
	In the example, <math>p		In the example, <math>p
	</math> is greater than <math>p>0.75		</math> is greater than <math>p>0.75
	</math>, thus the trust region should be ~~expand~~ and the step is accepted. Suppose the trust region radius is doubled (i.e. to <math>2.0		</math>, thus the trust region should be expanded and the step is accepted. Suppose the trust region radius is doubled (i.e. to <math>2.0
	</math>).		</math>).

Line 319:		Line 317:
	Step 2: form the quadratic model		Step 2: form the quadratic model

	<math>m_1(p) = f(1) + \nabla f_0^T p + \frac{1}{2} p^~~TH_1~~= 1-2p+p^2		<math>m_1(p) = f(1) + \nabla f_0^T p + \frac{1}{2} p^TB_1= 1-2p+p^2
	</math>		</math>

Line 361:		Line 359:
	'''Himmulblau’s Function'''		'''Himmulblau’s Function'''

	The following demonstrates a more complex example of trust region methods. Himmulblau’s function is a well-known mathematical function used extensively in optimization testing and research [7]. It is defined ~~for~~ two real variables and is characterized by having multiple global minima. The function is non-convex and multimodal, making it an excellent candidate for demonstrating the effectiveness of optimization algorithms. The following uses Steihaug’s method.		The following demonstrates a more complex example of trust region methods. Himmulblau’s function is a well-known mathematical function used extensively in optimization testing and research [7]. It is defined as two real variables and is characterized by having multiple global minima. The function is non-convex and multimodal, making it an excellent candidate for demonstrating the effectiveness of optimization algorithms. The following uses Steihaug’s method.

	The function is defined as the following:		The function is defined as the following:

Fall2024 Wiki Team23 at 07:48, 12 December 2024

2024-12-12T07:48:25Z

← Older revision		Revision as of 03:48, 12 December 2024
Line 412:		Line 412:
	</math> was obtained.		</math> was obtained.

	The following shows the remaining iterations:		The following shows the remaining iterations: <br>
			[[File:Iterations.png\|500px\|Caption]] <br>
			The convergence achieved at iteration 11 with <math>x=-3.779,y= -3.283 </math> and <math>f(x) = 0</math>.


	=Applications=		=Applications=
	'''Approach on Newton methods on Riemannian manifold'''		'''Approach on Newton methods on Riemannian manifold'''


	'''Approach on policy optimization'''		'''Approach on policy optimization'''

Fall2024 Wiki Team23: /* References */

2024-12-12T06:39:54Z

References

← Older revision		Revision as of 02:39, 12 December 2024
Line 424:		Line 424:

	=References=		=References=

	~~<references />~~

Fall2024 Wiki Team23: numeric examples

2024-12-12T06:36:06Z

numeric examples

← Older revision		Revision as of 02:36, 12 December 2024
Line 362:		Line 362:

	The following demonstrates a more complex example of trust region methods. Himmulblau’s function is a well-known mathematical function used extensively in optimization testing and research [7]. It is defined for two real variables and is characterized by having multiple global minima. The function is non-convex and multimodal, making it an excellent candidate for demonstrating the effectiveness of optimization algorithms. The following uses Steihaug’s method.		The following demonstrates a more complex example of trust region methods. Himmulblau’s function is a well-known mathematical function used extensively in optimization testing and research [7]. It is defined for two real variables and is characterized by having multiple global minima. The function is non-convex and multimodal, making it an excellent candidate for demonstrating the effectiveness of optimization algorithms. The following uses Steihaug’s method.

			The function is defined as the following:

			<math>f(x,y)=(x^2+y-11)^2+(x+y^2-7)^2

			</math>

			where <math>x
			</math> and <math>y
			</math> are real numbers.

			The four global minima of the function are at:

			# <math>(3.0,2.0)
			</math>
			# <math>(-2.805, 3.131)
			</math>
			# <math>(-3.779,-3.283)
			</math>
			# <math>(3.584,-1.848)

			</math>

			Due to the complexities in the calculations involved in the trust region method algorithm, the '''minimize''' function with the '''<nowiki/>'trust-constr'''' method from the SciPy library in Python can be utilized to solve this problem. Consider the following implementation:

			'''minimize(method=’trust-constr’)'''

			Iteration 1:

			To calculate, begin the optimization with the initial guess as <math>(-4.0, 0)
			</math> and trust region radius as <math>1.0
			</math>. The optimal solution achieved from this iteration is <math>(-3.382, -0.786)
			</math>, yield a function value of <math>95.453
			</math>. The initial point gives a sufficient prediction, thus, increase the trust region radius to <math>7.0
			</math>.

			Iteration 2:

			In this iteration, the updated point <math>(-4.0, 0)
			</math> and radius <math>7.0
			</math> are used to find a new step. However, an insufficient prediction was obtained, leading to a decrease in the trust region radius to <math>0.7
			</math>. The optimal solution obtained from the previous iteration is retained for the next step.

			Iteration 3:

			With the updated point <math>(-3.382, -0.786)
			</math> trust region radius <math>0.7
			</math>, a new point at <math>(-3.072, -1.413)
			</math> was obtained.

			The following shows the remaining iterations:

	=Applications=		=Applications=

Fall2024 Wiki Team23: /* Algorithm Discussion */

2024-12-12T06:25:08Z

Algorithm Discussion

Show changes