Sequential quadratic programming - Revision history

Btantisujjatham at 15:42, 1 April 2022

2022-04-01T15:42:32Z

← Older revision		Revision as of 11:42, 1 April 2022
Line 91:		Line 91:
	<br/>		<br/>

	[[File:~~Code_for_Wiki~~.JPG\|frame\|Figure 2: MATLAB program for performing sequential Newton steps on quadratic subproblem.<span style="font-size: 12pt; position:relative; bottom: 0.3em;">10</span>]]		[[File:Code_for_Wiki2.JPG\|frame\|Figure 2: MATLAB program for performing sequential Newton steps on quadratic subproblem.<span style="font-size: 12pt; position:relative; bottom: 0.3em;">10</span>]]

	The first important limitation in using SQP is now apparent: the divergence matrix is not invertible because it is not full rank. We will switch to the quadratic minimization sub-problem above, but even with this alternate framework, the gradient of the constraints must be full rank. This can be handled for now by artificially constraining the problem a bit further so that the derivatives of the inequality constraints are not linearly dependent. This can be accomplished through a small modification to the <math>\mu_2</math> constraint. <br/>		The first important limitation in using SQP is now apparent: the divergence matrix is not invertible because it is not full rank. We will switch to the quadratic minimization sub-problem above, but even with this alternate framework, the gradient of the constraints must be full rank. This can be handled for now by artificially constraining the problem a bit further so that the derivatives of the inequality constraints are not linearly dependent. This can be accomplished through a small modification to the <math>\mu_2</math> constraint. <br/>

Btantisujjatham at 15:05, 1 April 2022

2022-04-01T15:05:49Z

← Older revision		Revision as of 11:05, 1 April 2022
Line 1:		Line 1:
			This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Sequential_quadratic_programming

	Authored by: Ben Goodman (ChE 345 Spring 2016) <br/>		Authored by: Ben Goodman (ChE 345 Spring 2016) <br/>
	Steward: Dajun Yue and Fenqi You<br/>		Steward: Dajun Yue and Fenqi You<br/>

Btantisujjatham at 14:57, 1 April 2022

2022-04-01T14:57:34Z

Show changes

Btantisujjatham: /* Example Problem */

2022-04-01T14:49:18Z

Example Problem

← Older revision		Revision as of 10:49, 1 April 2022
Line 130:		Line 130:
	<math>\text{ with } Z = \sin (u) \cos(v) + \cos(u) \sin(v)</math>		<math>\text{ with } Z = \sin (u) \cos(v) + \cos(u) \sin(v)</math>

			[[File:Code for Wiki.png\|thumb]]

	The first important limitation in using SQP is now apparent: the divergence matrix is not invertible because it is not full rank. We will switch to the quadratic minimization sub-problem above, but even with this alternate framework, the gradient of the constraints must be full rank. This can be handled for now by artificially constraining the problem a bit further so that the derivatives of the inequality constraints are not linearly dependent. This can be accomplished through a small modification to the <math>\mu_2</math> constraint.		The first important limitation in using SQP is now apparent: the divergence matrix is not invertible because it is not full rank. We will switch to the quadratic minimization sub-problem above, but even with this alternate framework, the gradient of the constraints must be full rank. This can be handled for now by artificially constraining the problem a bit further so that the derivatives of the inequality constraints are not linearly dependent. This can be accomplished through a small modification to the <math>\mu_2</math> constraint.

Btantisujjatham: /* Introduction */

2022-04-01T14:45:46Z

Introduction

← Older revision		Revision as of 10:45, 1 April 2022
Line 7:		Line 7:
	Sequential quadratic programming (SQP) is a class of algorithms for solving non-linear optimization problems (NLP) in the real world. It is powerful enough for real problems because it can handle any degree of non-linearity including non-linearity in the constraints. The main disadvantage is that the method incorporates several derivatives, which likely need to be worked analytically in advance of iterating to a solution, so SQP becomes quite cumbersome for large problems with many variables or constraints. The method dates back to 1963 and was developed and refined in the 1970's .[1] SQP combines two fundamental algorithms for solving non-linear optimization problems: an active set method and Newton’s method, both of which are explained briefly below. Previous exposure to the component methods as well as to Lagrangian multipliers and Karush-Kuhn-Tucker (KKT) conditions is helpful in understanding SQP. The abstracted, general problem below will be used for the remainder of this page to explain and discuss SQP:		Sequential quadratic programming (SQP) is a class of algorithms for solving non-linear optimization problems (NLP) in the real world. It is powerful enough for real problems because it can handle any degree of non-linearity including non-linearity in the constraints. The main disadvantage is that the method incorporates several derivatives, which likely need to be worked analytically in advance of iterating to a solution, so SQP becomes quite cumbersome for large problems with many variables or constraints. The method dates back to 1963 and was developed and refined in the 1970's .[1] SQP combines two fundamental algorithms for solving non-linear optimization problems: an active set method and Newton’s method, both of which are explained briefly below. Previous exposure to the component methods as well as to Lagrangian multipliers and Karush-Kuhn-Tucker (KKT) conditions is helpful in understanding SQP. The abstracted, general problem below will be used for the remainder of this page to explain and discuss SQP:

	<math>\begin{~~align~~}		<math>\begin{aligned}
	\min &\ f(x) & &\\		\min &\ f(x) &\\
	\text{s.t. } & h(x) & = 0 \\		\text{s.t. } & h(x) & = 0 \\
	\text{and } & g(x) & \leq 0		\text{and } & g(x) & \leq 0
	\end{~~align~~}</math>		\end{aligned}</math>

	with <math>f(x)</math>, <math>h(x)</math>, and <math>g(x)</math> each potentially non-linear. <math>x</math> is potentially a vector of many variables for the optimization, in which case <math>h(x)</math> and <math>g(x)</math>are systems.		with <math>f(x)</math>, <math>h(x)</math>, and <math>g(x)</math> each potentially non-linear. <math>x</math> is potentially a vector of many variables for the optimization, in which case <math>h(x)</math> and <math>g(x)</math>are systems.

Btantisujjatham: /* Introduction */

2022-04-01T14:45:05Z

Introduction

← Older revision		Revision as of 10:45, 1 April 2022
Line 9:		Line 9:
	<math>\begin{align}		<math>\begin{align}
	\min &\ f(x) & &\\		\min &\ f(x) & &\\
	\text{s.t. } & h(x) & & = 0 \\		\text{s.t. } & h(x) & = 0 \\
	\text{and } & g(x) & & \leq 0		\text{and } & g(x) & \leq 0
	\end{align}</math>		\end{align}</math>

Btantisujjatham at 14:44, 1 April 2022

2022-04-01T14:44:27Z

← Older revision		Revision as of 10:44, 1 April 2022
Line 1:		Line 1:
			This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Quadratic_programming
	Authored by: Ben Goodman (ChE 345 Spring 2016)		Authored by: Ben Goodman (ChE 345 Spring 2016)

Btantisujjatham at 14:44, 1 April 2022

2022-04-01T14:44:02Z

← Older revision		Revision as of 10:44, 1 April 2022
Line 1:		Line 1:


	Authored by: Ben Goodman (ChE 345 Spring 2016)		Authored by: Ben Goodman (ChE 345 Spring 2016)

Btantisujjatham: /* Conclusion */

2022-04-01T14:43:47Z

Conclusion

← Older revision		Revision as of 10:43, 1 April 2022
Line 141:		Line 141:

	= Conclusion =		= Conclusion =
	SQP is powerful enough to be used in commercial software but also burdened by some intricacy. In addition to the complication from needing full-rank constraint gradients, the divergence matrix can be very difficult or laborious to assemble analytically. Commercial SQP packages include checks for the feasibility of the sub-problem in order to account for rank deficiencies. In addition to fmincon, SNOPT and FILTERSQP are two other commercial SQP packages, and each uses a different non-linear method to solve the quadratic subproblem.[1] Line search methods and trust-region methods are trusted options for this step, and sub-gradient methods have also been proposed. The other common modification to SQP (ubiquitous to commercial packages) is to invoke quasi-Newton methods in order to avoid computing the Hessian entirely. SQP is thus very much a family of algorithms rather than a stand-alone tool for optimization. At its core, it is a method for turning large, very non-linear problems into a sequence of small quadratic problems to reduce the computational expense of the problem.		SQP is powerful enough to be used in commercial software but also burdened by some intricacy. In addition to the complication from needing full-rank constraint gradients, the divergence matrix can be very difficult or laborious to assemble analytically. Commercial SQP packages include checks for the feasibility of the sub-problem in order to account for rank deficiencies. In addition to fmincon, SNOPT and FILTERSQP are two other commercial SQP packages, and each uses a different non-linear method to solve the quadratic subproblem.[1] [[Line search methods]] and [[trust-region methods]] are trusted options for this step, and sub-gradient methods have also been proposed. The other common modification to SQP (ubiquitous to commercial packages) is to invoke [[quasi-Newton methods]] in order to avoid computing the Hessian entirely. SQP is thus very much a family of algorithms rather than a stand-alone tool for optimization. At its core, it is a method for turning large, very non-linear problems into a sequence of small quadratic problems to reduce the computational expense of the problem.

	= Sources =		= Sources =
	[1] Nocedal, J. and Wright, S. Numerical Optimization, 2nd. ed., Ch. 18. Springer, 2006.		[1] Nocedal, J. and Wright, S. Numerical Optimization, 2nd. ed., Ch. 18. Springer, 2006.
	[2] You, Fengqi. Lecture Notes, Chemical Engineering 345 Optimization. Northwestern University, 2015.		[2] You, Fengqi. Lecture Notes, Chemical Engineering 345 Optimization. Northwestern University, 2015.

Btantisujjatham: /* The SQP Algorithm */

2022-04-01T14:42:35Z

The SQP Algorithm

← Older revision		Revision as of 10:42, 1 April 2022
Line 42:		Line 42:

	Recall:		Recall:
			<math>\lambda L = \begin{bmatrix} \frac{dL}{dx} \\ \frac{dL}{d\lambda} \\ \frac{dL}{d\mu} \end{bmatrix} = \begin{bmatrix} \nabla f + \lambda \nabla h + \mu \nabla g^{} \\ h \\ g^{} \end{bmatrix}</math>


	Then		Then
			<math>
			\nabla^2 L = \begin{bmatrix}\nabla_xx^2 L & \nabla h & \nabla g \\
			\nabla h & 0 & 0 \\
			\nabla g & 0 & 0
			\end{bmatrix}
			</math>