Interior-point method for NLP - Revision history

Apoorv12345 at 13:49, 7 December 2021

2021-12-07T13:49:34Z

← Older revision		Revision as of 09:49, 7 December 2021
Line 119:		Line 119:
	The above system can be arranged into symmetric linear system as follows:		The above system can be arranged into symmetric linear system as follows:

	<math>\begin{bmatrix} W_k + \Sigma_k & \nabla c(x_k) \\ \nabla c (x_k)^T & 0 \end{bmatrix} \begin{pmatrix} d_k^x \\ d_k^\lambda \end{pmatrix}</math> <math>= - \begin{pmatrix} \nabla f (x_k) + \nabla c (x_k) \lambda_k \\ c (x_k) \end{pmatrix}</math> where <math>\Sigma_k = X_k^{-1}Z_k</math> <math> ~~'''~~..Equation (*)~~'''~~ </math>		<math>\begin{bmatrix} W_k + \Sigma_k & \nabla c(x_k) \\ \nabla c (x_k)^T & 0 \end{bmatrix} \begin{pmatrix} d_k^x \\ d_k^\lambda \end{pmatrix}</math> <math>= - \begin{pmatrix} \nabla f (x_k) + \nabla c (x_k) \lambda_k \\ c (x_k) \end{pmatrix}</math> where <math>\Sigma_k = X_k^{-1}Z_k</math> <math> ........Equation (*) </math>

	We can then solve for <math>d_k^z </math> after finding the linear solution to <math>d_k^x </math> and <math>d_k^\lambda </math> with the following form of the explicit solution: <math>d_k^z = \mu_kX_k^{-1} e - z_k - \Sigma_k d_k^x </math> <math> ~~'''~~..Equation (**)~~'''~~ </math>		We can then solve for <math>d_k^z </math> after finding the linear solution to <math>d_k^x </math> and <math>d_k^\lambda </math> with the following form of the explicit solution: <math>d_k^z = \mu_kX_k^{-1} e - z_k - \Sigma_k d_k^x </math> <math> ........Equation (**) </math>

	=== Step size '''<math>(\alpha)</math>''' ===		=== Step size '''<math>(\alpha)</math>''' ===

Apoorv12345 at 13:48, 7 December 2021

2021-12-07T13:48:22Z

← Older revision		Revision as of 09:48, 7 December 2021
Line 119:		Line 119:
	The above system can be arranged into symmetric linear system as follows:		The above system can be arranged into symmetric linear system as follows:

	<math>\begin{bmatrix} W_k + \Sigma_k & \nabla c(x_k) \\ \nabla c (x_k)^T & 0 \end{bmatrix} \begin{pmatrix} d_k^x \\ d_k^\lambda \end{pmatrix}</math> <math>= - \begin{pmatrix} \nabla f (x_k) + \nabla c (x_k) \lambda_k \\ c (x_k) \end{pmatrix}</math> where <math>\Sigma_k = X_k^{-1}Z_k</math> <math> '''..Equation (*)''' </math>		<math>\begin{bmatrix} W_k + \Sigma_k & \nabla c(x_k) \\ \nabla c (x_k)^T & 0 \end{bmatrix} \begin{pmatrix} d_k^x \\ d_k^\lambda \end{pmatrix}</math> <math>= - \begin{pmatrix} \nabla f (x_k) + \nabla c (x_k) \lambda_k \\ c (x_k) \end{pmatrix}</math> where <math>\Sigma_k = X_k^{-1}Z_k</math> <math> '''..Equation (*)''' </math>

	We can then solve for <math>d_k^z </math> after finding the linear solution to <math>d_k^x </math> and <math>d_k^\lambda </math> with the following form of the explicit solution: <math>d_k^z = \mu_kX_k^{-1} e - z_k - \Sigma_k d_k^x </math> <math> '''..Equation (**)''' </math>		We can then solve for <math>d_k^z </math> after finding the linear solution to <math>d_k^x </math> and <math>d_k^\lambda </math> with the following form of the explicit solution: <math>d_k^z = \mu_kX_k^{-1} e - z_k - \Sigma_k d_k^x </math> <math> '''..Equation (**)''' </math>

	=== Step size '''<math>(\alpha)</math>''' ===		=== Step size '''<math>(\alpha)</math>''' ===

Apoorv12345 at 17:39, 6 December 2021

2021-12-06T17:39:07Z

← Older revision		Revision as of 13:39, 6 December 2021
Line 284:		Line 284:
	We can now implement BPOPT solver using MATLAB to get the following results as illustrated by <ref>Design Optimisation-Interior point methods, <https://apmonitor.com/me575/index.php/Main/InteriorPointMethod> </ref>:		We can now implement BPOPT solver using MATLAB to get the following results as illustrated by <ref>Design Optimisation-Interior point methods, <https://apmonitor.com/me575/index.php/Main/InteriorPointMethod> </ref>:

	[[File:X1andx2.jpg\|left\|thumb\|'''Figure 3''': Variation of x1 and x2 as iterations progress [9]]]		[[File:X1andx2.jpg\|left\|thumb\|'''Figure 3''': Variation of x1 and x2 as iterations progress [11]]]

	From figure 3 we see that the solver has converged to following optimal values of x1 and x2 in '13' iterations.		From figure 3 we see that the solver has converged to following optimal values of x1 and x2 in '13' iterations.
	<math> x1 = 4.3198 </math> and <math> x2 = 1.1575 </math>		<math> x1 = 4.3198 </math> and <math> x2 = 1.1575 </math>

	[[File:Muvariation.jpg\|left\|thumb\|'''Figure 4''': Variation of 'μ' as iterations progress [9]]]		[[File:Muvariation.jpg\|left\|thumb\|'''Figure 4''': Variation of 'μ' as iterations progress [11]]]

Apoorv12345 at 17:37, 6 December 2021

2021-12-06T17:37:46Z

← Older revision		Revision as of 13:37, 6 December 2021
Line 157:		Line 157:

	[[File:Pseudocode.png\|left\|thumb\|364x364px\|'''Figure 2''': Pseudocode for Interior point method for NLP]]		[[File:Pseudocode.png\|left\|thumb\|364x364px\|'''Figure 2''': Pseudocode for Interior point method for NLP]]

Apoorv12345 at 17:36, 6 December 2021

2021-12-06T17:36:52Z

← Older revision		Revision as of 13:36, 6 December 2021
Line 157:		Line 157:

	[[File:Pseudocode.png\|left\|thumb\|364x364px\|'''Figure 2''': Pseudocode for Interior point method for NLP]]		[[File:Pseudocode.png\|left\|thumb\|364x364px\|'''Figure 2''': Pseudocode for Interior point method for NLP]]






Line 276:		Line 280:
	We can now implement BPOPT solver using MATLAB to get the following results as illustrated by <ref>Design Optimisation-Interior point methods, <https://apmonitor.com/me575/index.php/Main/InteriorPointMethod> </ref>:		We can now implement BPOPT solver using MATLAB to get the following results as illustrated by <ref>Design Optimisation-Interior point methods, <https://apmonitor.com/me575/index.php/Main/InteriorPointMethod> </ref>:

	[[File:X1andx2.jpg\|left\|thumb\|'''Figure 2''': Variation of x1 and x2 as iterations progress [9]]]		[[File:X1andx2.jpg\|left\|thumb\|'''Figure 3''': Variation of x1 and x2 as iterations progress [9]]]

	From figure 2 we see that the solver has converged to following optimal values of x1 and x2 in '13' iterations.		From figure 3 we see that the solver has converged to following optimal values of x1 and x2 in '13' iterations.
	<math> x1 = 4.3198 </math> and <math> x2 = 1.1575 </math>		<math> x1 = 4.3198 </math> and <math> x2 = 1.1575 </math>

	[[File:Muvariation.jpg\|left\|thumb\|'''Figure 3''': Variation of 'μ' as iterations progress [9]]]		[[File:Muvariation.jpg\|left\|thumb\|'''Figure 4''': Variation of 'μ' as iterations progress [9]]]


Line 300:		Line 304:


	In the figure 3 we can clearly see how the value of <math>' \mu ' </math> is decreasing as we progress towards the solution (increasing iterations).		In the figure 4 we can clearly see how the value of <math>' \mu ' </math> is decreasing as we progress towards the solution (increasing iterations).

Apoorv12345 at 17:34, 6 December 2021

2021-12-06T17:34:57Z

← Older revision		Revision as of 13:34, 6 December 2021
Line 149:		Line 149:

	The above described algorithm can be depicted in the form of the following pseudocode as illustrated by <ref> Interior point method for Optimization <https://www.youtube.com/watch?v=zm4mfr-QT1E> </ref>		The above described algorithm can be depicted in the form of the following pseudocode as illustrated by <ref> Interior point method for Optimization <https://www.youtube.com/watch?v=zm4mfr-QT1E> </ref>

	~~[[File:Pseudocode.png\|left\|thumb]]~~

	* Choose a '''feasible''' guess value of <math> x_o </math> and initialise <math> \lambda </math> and <math> z_o </math> by solving the above described equation.		* Choose a '''feasible''' guess value of <math> x_o </math> and initialise <math> \lambda </math> and <math> z_o </math> by solving the above described equation.
Line 158:		Line 156:
	* Check for convergence again and repeat steps if the solution is not within tolerance limit.		* Check for convergence again and repeat steps if the solution is not within tolerance limit.

			[[File:Pseudocode.png\|left\|thumb\|364x364px\|'''Figure 2''': Pseudocode for Interior point method for NLP]]

Apoorv12345 at 17:32, 6 December 2021

2021-12-06T17:32:08Z

← Older revision		Revision as of 13:32, 6 December 2021
Line 119:		Line 119:
	The above system can be arranged into symmetric linear system as follows:		The above system can be arranged into symmetric linear system as follows:

	<math>\begin{bmatrix} W_k + \Sigma_k & \nabla c(x_k) \\ \nabla c (x_k)^T & 0 \end{bmatrix} \begin{pmatrix} d_k^x \\ d_k^\lambda \end{pmatrix}</math> <math>= - \begin{pmatrix} \nabla f (x_k) + \nabla c (x_k) \lambda_k \\ c (x_k) \end{pmatrix}</math> where <math>\Sigma_k = X_k^{-1}Z_k</math> <math> ..Equation (*) </math>		<math>\begin{bmatrix} W_k + \Sigma_k & \nabla c(x_k) \\ \nabla c (x_k)^T & 0 \end{bmatrix} \begin{pmatrix} d_k^x \\ d_k^\lambda \end{pmatrix}</math> <math>= - \begin{pmatrix} \nabla f (x_k) + \nabla c (x_k) \lambda_k \\ c (x_k) \end{pmatrix}</math> where <math>\Sigma_k = X_k^{-1}Z_k</math> <math> '''..Equation (*)''' </math>

	We can then solve for <math>d_k^z </math> after finding the linear solution to <math>d_k^x </math> and <math>d_k^\lambda </math> with the following form of the explicit solution: <math>d_k^z = \mu_kX_k^{-1} e - z_k - \Sigma_k d_k^x </math> <math> ..Equation (**) </math>		We can then solve for <math>d_k^z </math> after finding the linear solution to <math>d_k^x </math> and <math>d_k^\lambda </math> with the following form of the explicit solution: <math>d_k^z = \mu_kX_k^{-1} e - z_k - \Sigma_k d_k^x </math> <math> '''..Equation (**)''' </math>

	=== Step size '''<math>(\alpha)</math>''' ===		=== Step size '''<math>(\alpha)</math>''' ===
Line 154:		Line 154:
	* Choose a '''feasible''' guess value of <math> x_o </math> and initialise <math> \lambda </math> and <math> z_o </math> by solving the above described equation.		* Choose a '''feasible''' guess value of <math> x_o </math> and initialise <math> \lambda </math> and <math> z_o </math> by solving the above described equation.
	* Once we have initial values then check for convergence, if it is within the 'tolerance limit' then we have reached the optimal solution. If not then, move to next step.		* Once we have initial values then check for convergence, if it is within the 'tolerance limit' then we have reached the optimal solution. If not then, move to next step.
	* Compute the search direction using the ~~equation~~() and ~~equation~~(*) as mentioned above.		* Compute the search direction using the Equation() and Equation(*) as mentioned above.
			* Perform back tracking line search by progressively decreasing the value of <math> \alpha </math> using merit function of Filter methods.
			* Check for convergence again and repeat steps if the solution is not within tolerance limit.

Apoorv12345 at 17:28, 6 December 2021

2021-12-06T17:28:05Z

← Older revision		Revision as of 13:28, 6 December 2021
Line 119:		Line 119:
	The above system can be arranged into symmetric linear system as follows:		The above system can be arranged into symmetric linear system as follows:

	<math>\begin{bmatrix} W_k + \Sigma_k & \nabla c(x_k) \\ \nabla c (x_k)^T & 0 \end{bmatrix} \begin{pmatrix} d_k^x \\ d_k^\lambda \end{pmatrix}</math> <math>= - \begin{pmatrix} \nabla f (x_k) + \nabla c (x_k) \lambda_k \\ c (x_k) \end{pmatrix}</math> where <math>\Sigma_k = X_k^{-1}Z_k</math>		<math>\begin{bmatrix} W_k + \Sigma_k & \nabla c(x_k) \\ \nabla c (x_k)^T & 0 \end{bmatrix} \begin{pmatrix} d_k^x \\ d_k^\lambda \end{pmatrix}</math> <math>= - \begin{pmatrix} \nabla f (x_k) + \nabla c (x_k) \lambda_k \\ c (x_k) \end{pmatrix}</math> where <math>\Sigma_k = X_k^{-1}Z_k</math> <math> ..Equation (*) </math>

	We can then solve for <math>d_k^z </math> after finding the linear solution to <math>d_k^x </math> and <math>d_k^\lambda </math> with the following form of the explicit solution: <math>d_k^z = \mu_kX_k^{-1} e - z_k - \Sigma_k d_k^x </math>		We can then solve for <math>d_k^z </math> after finding the linear solution to <math>d_k^x </math> and <math>d_k^\lambda </math> with the following form of the explicit solution: <math>d_k^z = \mu_kX_k^{-1} e - z_k - \Sigma_k d_k^x </math> <math> ..Equation (**) </math>

	=== Step size '''<math>(\alpha)</math>''' ===		=== Step size '''<math>(\alpha)</math>''' ===
Line 153:		Line 153:

	* Choose a '''feasible''' guess value of <math> x_o </math> and initialise <math> \lambda </math> and <math> z_o </math> by solving the above described equation.		* Choose a '''feasible''' guess value of <math> x_o </math> and initialise <math> \lambda </math> and <math> z_o </math> by solving the above described equation.
	*		* Once we have initial values then check for convergence, if it is within the 'tolerance limit' then we have reached the optimal solution. If not then, move to next step.
			* Compute the search direction using the equation() and equation(*) as mentioned above.

Apoorv12345 at 17:21, 6 December 2021

2021-12-06T17:21:57Z

← Older revision		Revision as of 13:21, 6 December 2021
Line 152:		Line 152:
	[[File:Pseudocode.png\|left\|thumb]]		[[File:Pseudocode.png\|left\|thumb]]

			* Choose a '''feasible''' guess value of <math> x_o </math> and initialise <math> \lambda </math> and <math> z_o </math> by solving the above described equation.
			*

Apoorv12345 at 17:15, 6 December 2021

2021-12-06T17:15:11Z

← Older revision		Revision as of 13:15, 6 December 2021
Line 218:		Line 218:


			The following overview on Barrier vs primal-dual method was given by <ref>Ryan Tibshirani."Primal-Dual Interior-Point methods <https://www.stat.cmu.edu/~ryantibs/convexopt/lectures/primal-dual.pdf> </ref>

			* Both methods are motivated in terms of perturbed KKT conditions.
			* Primal dual interior point methods take one Newton step and then move to next step i.e. there are no separate inner and outer loops.
			* Primal dual interior point iterates are not necessarily feasible.
			* Primal-dual interior-point methods are often more efficient, as they can exhibit better than linear convergence.

	== Numerical Example ==		== Numerical Example ==