SNOPT - Revision history

Elias at 14:03, 9 December 2011

2011-12-09T14:03:22Z

← Older revision		Revision as of 09:03, 9 December 2011
Line 4:		Line 4:
	\begin{array}{cc}		\begin{array}{cc}
	\min_{x} & f_{0}(x)\\		\min_{x} & f_{0}(x)\\
	\text{subject to} & l \le \left(\begin{array}{c}{x \\ f(x) \\ A_L x }\end{array}\right) \le u		\text{subject to} & l \le \left(\begin{array}{c}x \\ f(x) \\ A_L x \end{array}\right) \le u
	\end{array}		\end{array}
	</math>		</math>


	where ''l ''and ''u ''are constant lower and upper bounds, ''f''<sub>0</sub> (''x'') is a smooth scalar objective function, ''A<sub>L</sub>'' is a sparse matrix, and ''f ''(''x'') is a vector of smooth nonlinear constraint functions ''{f<sub>i</sub> ''(''x'')''}''. An optional parameter maximize may specify that ''f''<sub>0</sub> (''x'') should be maximized instead of minimized.		where ''l ''and ''u ''are constant lower and upper bounds, ''f''<sub>0</sub> (''x'') is a smooth scalar objective function, ''A<sub>L</sub>'' is a sparse matrix, and ''f ''(''x'') is a vector of smooth nonlinear constraint functions ''{f<sub>i</sub> ''(''x'')''}''. An optional parameter maximize may specify that ''f''<sub>0</sub> (''x'') should be maximized instead of minimized.

Elias at 13:00, 13 October 2011

2011-10-13T13:00:19Z

Show changes

Elias: /* EXIT conditions */

2011-09-18T12:45:32Z

EXIT conditions

← Older revision		Revision as of 07:45, 18 September 2011
Line 1,451:		Line 1,451:
	</pre>		</pre>

	This exit implies that there may be errors in the subroutines that define the problem objective and constraints. If the objective derivatives appear to incorrect, a check has been made on some individual elements of the objective gradient array at the first point that satisfies the linear constraints. At least one component (G(''k'') or gObj(''j'') ) is being set to a value that disagrees markedly with its associated forward-difference estimate ~~''?f''0 ''~~/~~?xj ''~~. (The relative difference between the computed and estimated values is 1.0 or more.) This exit is a safeguard, since SNOPT will usually fail to make progress when the computed gradients are seriously inaccurate. In the process it may expend considerable effort before terminating with INFO 41 above.		This exit implies that there may be errors in the subroutines that define the problem objective and constraints. If the objective derivatives appear to incorrect, a check has been made on some individual elements of the objective gradient array at the first point that satisfies the linear constraints. At least one component (G(''k'') or gObj(''j'') ) is being set to a value that disagrees markedly with its associated forward-difference estimate <math>\partial f_0 / \partial x_j</math>. (The relative difference between the computed and estimated values is 1.0 or more.) This exit is a safeguard, since SNOPT will usually fail to make progress when the computed gradients are seriously inaccurate. In the process it may expend considerable effort before terminating with INFO 41 above.

	Check the function and gradient computation ''very carefully''. A simple omission (such as forgetting to divide ''f''<sub>0</sub> by 2) could explain everything. If ''f''0 or a component <math>partial \Obj/\partial x_j</math> is very large, then give serious thought to scaling the function or the nonlinear variables.		Check the function and gradient computation ''very carefully''. A simple omission (such as forgetting to divide ''f''<sub>0</sub> by 2) could explain everything. If ''f''<sub>0</sub> or a component <math>partial \Obj/\partial x_j</math> is very large, then give serious thought to scaling the function or the nonlinear variables.

	If you feel ''certain ''that the computed gObj(''j'') is correct (and that the forward-difference estimate is therefore wrong), you can specify Verify level 0 to prevent individual elements from being checked. However, the opti- mization procedure may have difficulty.		If you feel ''certain ''that the computed gObj(''j'') is correct (and that the forward-difference estimate is therefore wrong), you can specify Verify level 0 to prevent individual elements from being checked. However, the opti- mization procedure may have difficulty.

Elias: /* Description of the optional parameters */

2011-09-18T12:17:46Z

Description of the optional parameters

← Older revision		Revision as of 07:17, 18 September 2011
Line 317:		Line 317:
	\|}		\|}

	When Derivative level ''< ''3), the central-difference interval ''r ''is used near an optimal solution to obtain more accurate (but more expensive) estimates of gradients. Twice as many function evaluations are required compared to forward differencing. The interval used for the ''j''th variable is ''hj ''= ''r''(1 + ''\\|xj \\|''). The resulting derivative estimates should be accurate to ''O''(''r''2 ), unless the functions are badly scaled.		When Derivative level ''< ''3), the central-difference interval ''r ''is used near an optimal solution to obtain more accurate (but more expensive) estimates of gradients. Twice as many function evaluations are required compared to forward differencing. The interval used for the ''j''th variable is ''h<sub>j</sub> ''= ''r''(1 + ''<nowiki>\|</nowiki>xj<nowiki>\|</nowiki>''). The resulting derivative estimates should be accurate to ''O''(''r''<sup>2</sup> ), unless the functions are badly scaled.

	{\| cellpadding="10"		{\| cellpadding="10"
Line 333:		Line 333:
	\|}		\|}

	Except on restarts, a CRASH procedure is used to select an initial basis from certain rows and columns of the constraint matrix ( ''A - I ''). The Crash option ''i ''determines which rows and columns of ''A ''are eligible initially, and how many times CRASH is called. Columns of ''-I ''are used to pad the basis where necessary.		Except on restarts, a CRASH procedure is used to select an initial basis from certain rows and columns of the constraint matrix ( ''A - I ''). The Crash option ''i ''determines which rows and columns of ''A ''are eligible initially, and how many times CRASH is called. Columns of ''-I ''are used to pad the basis where necessary.

	{\|class="wikitable"		{\|class="wikitable"
Line 349:		Line 349:
	If ''i >= ''1, certain slacks on inequality rows are selected for the basis first. (If ''i >= ''2, numerical values are used to exclude slacks that are close to a bound.) CRASH then makes several passes through the columns of ''A'', searching for a basis matrix that is essentially triangular. A column is assigned to "pivot" on a particular row if the column contains a suitably large element in a row that has not yet been assigned. (The pivot elements ultimately form the diagonals of the triangular basis.) For remaining unassigned rows, slack variables are inserted to complete the basis.		If ''i >= ''1, certain slacks on inequality rows are selected for the basis first. (If ''i >= ''2, numerical values are used to exclude slacks that are close to a bound.) CRASH then makes several passes through the columns of ''A'', searching for a basis matrix that is essentially triangular. A column is assigned to "pivot" on a particular row if the column contains a suitably large element in a row that has not yet been assigned. (The pivot elements ultimately form the diagonals of the triangular basis.) For remaining unassigned rows, slack variables are inserted to complete the basis.

	The Crash tolerance ''r ''allows the starting procedure CRASH to ignore certain "small" nonzeros in each column of ''A''. If ''a''max is the largest element in column ''j'', other nonzeros ''~~aij~~ ''in the column are ignored if ''\\|~~aij \~~\| = a''max ''× r''. (To be meaningful, ''r ''should be in the range 0 ''=< r < ''1.)		The Crash tolerance ''r ''allows the starting procedure CRASH to ignore certain "small" nonzeros in each column of ''A''. If ''a''<sub>max</sub> is the largest element in column ''j'', other nonzeros ''a<sub>ij</sub> ''in the column are ignored if ''<nowiki>\|</nowiki>a<sub>ij</sub><nowiki>\|</nowiki> = a''<sub>max</sub> ''× r''. (To be meaningful, ''r ''should be in the range 0 ''<= r < ''1.)

	When ''r > ''0''.''0, the basis obtained by CRASH may not be strictly triangular, but it is likely to be nonsingular and almost triangular. The intention is to obtain a starting basis containing more columns of ''A ''and fewer (arbitrary) slacks. A feasible solution may be reached sooner on some problems.		When ''r > ''0''.''0, the basis obtained by CRASH may not be strictly triangular, but it is likely to be nonsingular and almost triangular. The intention is to obtain a starting basis containing more columns of ''A ''and fewer (arbitrary) slacks. A feasible solution may be reached sooner on some problems.

	For example, suppose the first ''m ''columns of ''A ''are the matrix shown under LU factor tolerance; i.e., a tridiag- onal matrix with entries ''-''1, 4, ''-''1. To help CRASH choose all ''m ''columns for the initial basis, we would specify Crash tolerance ''r ''for some value of ''r > ''1''/''4.		For example, suppose the first ''m ''columns of ''A ''are the matrix shown under LU factor tolerance; i.e., a tridiag- onal matrix with entries ''-''1, 4, ''-''1. To help CRASH choose all ''m ''columns for the initial basis, we would specify Crash tolerance ''r ''for some value of ''r > ''1''/''4.
Line 360:		Line 360:

	The keyword Derivative level specifies which nonlinear function gradients are known analytically and will be supplied to SNOPT. This is normally automatically set by TOMLAB.		The keyword Derivative level specifies which nonlinear function gradients are known analytically and will be supplied to SNOPT. This is normally automatically set by TOMLAB.
	{\|
			{\|class="wikitable"
	!i\|\|Meaning		!i\|\|Meaning
	\|-		\|-
Line 376:		Line 377:
	If ''i ''= 0 or 2, SNOPT will ''estimate ''the missing components of the objective gradient, using finite differences. However, it could increase the total run-time substantially, and there is less assurance that an acceptable solution will be located. If the nonlinear variables are not well scaled, it may be necessary to specify a nonstandard Difference interval (see below).		If ''i ''= 0 or 2, SNOPT will ''estimate ''the missing components of the objective gradient, using finite differences. However, it could increase the total run-time substantially, and there is less assurance that an acceptable solution will be located. If the nonlinear variables are not well scaled, it may be necessary to specify a nonstandard Difference interval (see below).

	If ''i ''= 0 or 1, SNOPT will estimate missing elements of the Jacobian. For each column of the Jacobian, one call is needed to estimate all missing elements in that column, if any. If Jacobian = sparse and the sparsity pattern of the Jacobian happens to be		If ''i ''= 0 or 1, SNOPT will estimate missing elements of the Jacobian. For each column of the Jacobian, one call is needed to estimate all missing elements in that column, if any. If Jacobian = sparse and the sparsity pattern of the Jacobian happens to be

	<math>		<math>
Line 397:		Line 398:
	\|}		\|}

	At each major iteration a line search is used to improve the merit function. A Derivative linesearch uses safeguarded cubic interpolation and requires both function and gradient values to compute estimates of the step ''ak ''. If some analytic derivatives are not provided, or a Nonderivative linesearch is specified, SNOPT employs a line search based upon safeguarded quadratic interpolation, which does not require gradient evaluations.		At each major iteration a line search is used to improve the merit function. A Derivative linesearch uses safeguarded cubic interpolation and requires both function and gradient values to compute estimates of the step ''a<sub>k</sub> ''. If some analytic derivatives are not provided, or a Nonderivative linesearch is specified, SNOPT employs a line search based upon safeguarded quadratic interpolation, which does not require gradient evaluations.

	A nonderivative line search can be slightly less robust on difficult problems, and it is recommended that the default be used if the functions and derivatives can be computed at approximately the same cost. If the gradients are very expensive relative to the functions, a nonderivative line search may give a significant decrease in computation time.		A nonderivative line search can be slightly less robust on difficult problems, and it is recommended that the default be used if the functions and derivatives can be computed at approximately the same cost. If the gradients are very expensive relative to the functions, a nonderivative line search may give a significant decrease in computation time.
Line 413:		Line 414:
	*For estimating missing derivatives.		*For estimating missing derivatives.

	In all cases, a derivative with respect to ''x<sub>j</sub>'' is estimated by perturbing that component of ''x ''to the value ''x<sub>j</sub>'' + ''h''<sub>1</sub>(1 + ''<nowiki>\|</nowiki>xj<nowiki>\|</nowiki>''), and then evaluating ''f''0 (''x'') or ''f ''(''x'') at the perturbed point. The resulting gradient estimates should be accurate to ''O''(''h''1 ) unless the functions are badly scaled. Judicious alteration of ''h''1 may sometimes lead to greater accuracy.		In all cases, a derivative with respect to ''x<sub>j</sub>'' is estimated by perturbing that component of ''x ''to the value ''x<sub>j</sub>'' + ''h''<sub>1</sub>(1 + ''<nowiki>\|</nowiki>x<sub>j</sub><nowiki>\|</nowiki>''), and then evaluating ''f''0 (''x'') or ''f ''(''x'') at the perturbed point. The resulting gradient estimates should be accurate to ''O''(''h''1 ) unless the functions are badly scaled. Judicious alteration of ''h''1 may sometimes lead to greater accuracy.

	{\| cellpadding="10"		{\| cellpadding="10"
Line 429:		Line 430:
	This keyword determines the initial weight ''γ'' associated with problem NP(''γ'').		This keyword determines the initial weight ''γ'' associated with problem NP(''γ'').

	At major iteration ''k'', if elastic mode has not yet started, a scale factor ~~''sk ''~~= 1 + ''g''(~~''xk ''~~) ~~''8 ''~~is defined from the current objective gradient. Elastic mode is then started if the QP subproblem is infeasible, or the QP dual variables are larger in magnitude than <math>\sigma_k\omega</math>. The QP is re-solved in elastic mode with <math>\gamma = \sigma_k\omega</math>.		At major iteration ''k'', if elastic mode has not yet started, a scale factor <math>\sigma_k = 1+\|\|g(x_k)\|\|_\infty</math> is defined from the current objective gradient. Elastic mode is then started if the QP subproblem is infeasible, or the QP dual variables are larger in magnitude than <math>\sigma_k\omega</math>. The QP is re-solved in elastic mode with <math>\gamma = \sigma_k\omega</math>.

	Thereafter, major iterations continue in elastic mode until they converge to a point that is optimal for problem NP(''γ''). If the point is feasible for SparseNP (''v ''= ''w ''= 0), it is declared locally optimal. Otherwise, ''γ'' is increased by a factor of 10 and major iterations continue. If ''γ'' has already reached a maximum allowable value, SparseNP is declared locally infeasible.		Thereafter, major iterations continue in elastic mode until they converge to a point that is optimal for problem NP(''γ''). If the point is feasible for SparseNP (''v ''= ''w ''= 0), it is declared locally optimal. Otherwise, ''γ'' is increased by a factor of 10 and major iterations continue. If ''γ'' has already reached a maximum allowable value, SparseNP is declared locally infeasible.


	{\| cellpadding="10"		{\| cellpadding="10"
Line 533:		Line 533:
	This controls the accuracy with which a steplength will be located along the direction of search each iteration. At the start of each line search a target directional derivative for the merit function is identified. This parameter determines the accuracy to which this target value is approximated.		This controls the accuracy with which a steplength will be located along the direction of search each iteration. At the start of each line search a target directional derivative for the merit function is identified. This parameter determines the accuracy to which this target value is approximated.

	*''t'' must be a real value in the range 0''.''0 ''= t = ''1''.''0.		*''t'' must be a real value in the range 0''.''0 ''<= t <= ''1''.''0.
	*The default value ''t ''= 0''.''9 requests just moderate accuracy in the line search.		*The default value ''t ''= 0''.''9 requests just moderate accuracy in the line search.
	*If the nonlinear functions are cheap to evaluate, a more accurate search may be appropriate; try ''t ''= 0''.''1, 0.01 or 0.001. The number of major iterations might decrease.		*If the nonlinear functions are cheap to evaluate, a more accurate search may be appropriate; try ''t ''= 0''.''1, 0.01 or 0.001. The number of major iterations might decrease.
Line 584:		Line 584:
	\|}		\|}

	The LU factorization implements a Markowitz-type search for a pivot that locally minimizes the fill-in subject to a threshold pivoting stability criterion. The default option is to use threshold partial pivoting. The options LU rook pivoting and LU complete pivoting are more expensive than partial pivoting but are more stable and better at revealing rank.		The LU factorization implements a Markowitz-type search for a pivot that locally minimizes the fill-in subject to a threshold pivoting stability criterion. The default option is to use threshold partial pivoting. The options LU rook pivoting and LU complete pivoting are more expensive than partial pivoting but are more stable and better at revealing rank.

	{\| cellpadding="10"		{\| cellpadding="10"

Elias: /* SPECS file checklist and defaults */

2011-09-18T11:09:40Z

SPECS file checklist and defaults

← Older revision		Revision as of 06:09, 18 September 2011
Line 244:		Line 244:
	Crash tolerance 0.1 *		Crash tolerance 0.1 *
	Linesearch tolerance 0.9 * smaller for more accurate search		Linesearch tolerance 0.9 * smaller for more accurate search
	Pivot tolerance 3.7e-11 * ?2/3		Pivot tolerance 3.7e-11 * e^2/3

	* QP subproblems		* QP subproblems
Line 264:		Line 264:
	* Nonderivative linesearch *		* Nonderivative linesearch *
	Function precision 3.0e-13 * ?0.8 (almost full accuracy)		Function precision 3.0e-13 * ?0.8 (almost full accuracy)
	Difference interval 5.5e-7 * (Function precision)1/2		Difference interval 5.5e-7 * (Function precision)^1/2
	Central difference interval 6.7e-5 * (Function precision)1/3		Central difference interval 6.7e-5 * (Function precision)^1/3
	New superbasics limit 99 * controls early termination of QPs		New superbasics limit 99 * controls early termination of QPs
	Objective row ObjRow * row number of objective in F(x)		Objective row ObjRow * row number of objective in F(x)
Line 275:		Line 275:

	* Hessian approximation		* Hessian approximation
	Hessian full memory * default if n= 75		Hessian full memory * default if n <= 75
	Hessian limited memory * default if n > 75		Hessian limited memory * default if n > 75
	Hessian frequency 999999 * for full Hessian (never reset)		Hessian frequency 999999 * for full Hessian (never reset)
Line 282:		Line 282:

	* Frequencies		* Frequencies
	Check frequency 60 * test row residuals ?Ax - s?		Check frequency 60 * test row residuals \|\|Ax - s\|\|
	Expand frequency 10000 * for anti-cycling procedure		Expand frequency 10000 * for anti-cycling procedure
	Factorization frequency 50 * 100 for LPs		Factorization frequency 50 * 100 for LPs

Elias: /* Treatment of constraint infeasibilities */

2011-09-18T10:53:26Z

Treatment of constraint infeasibilities

← Older revision		Revision as of 05:53, 18 September 2011
Line 135:		Line 135:
	===Treatment of constraint infeasibilities===		===Treatment of constraint infeasibilities===

	SNOPT makes explicit allowance for infeasible constraints. First, infeasible ''linear ''constraints are detected by solving the linear program (FLP)		SNOPT makes explicit allowance for infeasible constraints. First, infeasible ''linear'' constraints are detected by solving the linear program (FLP)

	<math>		<math>
Line 149:		Line 149:
	where ''e ''is a vector of ones, and the nonlinear constraint bounds are temporarily excluded from ''l ''and ''u''. This is equivalent to minimizing the sum of the general linear constraint violations subject to the bounds on ''x''. (The sum is the ''£''1 -norm of the linear constraint violations. In the linear programming literature, the approach is called ''elastic programming''.)		where ''e ''is a vector of ones, and the nonlinear constraint bounds are temporarily excluded from ''l ''and ''u''. This is equivalent to minimizing the sum of the general linear constraint violations subject to the bounds on ''x''. (The sum is the ''£''1 -norm of the linear constraint violations. In the linear programming literature, the approach is called ''elastic programming''.)

	The linear constraints are infeasible if the optimal solution of FLP has ''v ''= 0 or ''w ''= 0. SNOPT then terminates without computing the nonlinear functions.		The linear constraints are infeasible if the optimal solution of FLP has ''v ''≠ 0 or ''w ''≠ 0. SNOPT then terminates without computing the nonlinear functions.

	Otherwise, all subsequent iterates satisfy the linear constraints. (Such a strategy allows linear constraints to be used to define a region in which the functions can be safely evaluated.) SNOPT proceeds to solve SparseNP as given, using search directions obtained from the sequence of QP subproblems.		Otherwise, all subsequent iterates satisfy the linear constraints. (Such a strategy allows linear constraints to be used to define a region in which the functions can be safely evaluated.) SNOPT proceeds to solve SparseNP as given, using search directions obtained from the sequence of QP subproblems.

Elias: /* The merit function */

2011-09-18T10:51:14Z

The merit function

← Older revision		Revision as of 05:51, 18 September 2011
Line 116:		Line 116:
	</math>		</math>

	where ''D ''is a diagonal matrix of penalty parameters (''D<sub>ii</sub> = ''0). If (''x<sub>k</sub>, s<sub>k</sub> , p<sub>k</sub>'') denotes the current solution estimate and <math>(\hat{x}_k, \hat{t}_k, \hat{pi}_k)</math> denotes the QP solution, the line search determines a step <math>\alpha_k (0 < \alpha_k \le 1)</math> such that the new point		where ''D ''is a diagonal matrix of penalty parameters (''D<sub>ii</sub> >= ''0). If (''x<sub>k</sub>, s<sub>k</sub> , p<sub>k</sub>'') denotes the current solution estimate and <math>(\hat{x}_k, \hat{t}_k, \hat{pi}_k)</math> denotes the QP solution, the line search determines a step <math>\alpha_k (0 < \alpha_k \le 1)</math> such that the new point

	<math>		<math>

Elias: /* Minor iterations */

2011-09-18T10:49:22Z

Minor iterations

← Older revision		Revision as of 05:49, 18 September 2011
Line 106:		Line 106:
	If it appears that no improvement can be made with the current definition of ''B'', ''S'' and ''N '', a nonbasic variable is selected to be added to ''S'', and the process is repeated with the value of ''n<sub>S</sub> ''increased by one. At all stages, if a basic or superbasic variables encounters one of its bounds, the variables is made nonbasic and the value of ''n<sub>S</sub> '' is decreased by one.		If it appears that no improvement can be made with the current definition of ''B'', ''S'' and ''N '', a nonbasic variable is selected to be added to ''S'', and the process is repeated with the value of ''n<sub>S</sub> ''increased by one. At all stages, if a basic or superbasic variables encounters one of its bounds, the variables is made nonbasic and the value of ''n<sub>S</sub> '' is decreased by one.

	Associated with each of the ''m'' equality constraints ''Ax - s ''= ''b ''are the ''dual variables p''. Similarly, each variable in (''x, s'') has an associated ''reduced gradient dj ''. The reduced gradients for the variables ''x ''are the quantities ''g-A<sup>T</sup>π'', where ''g ''is the gradient of the QP objective, and the reduced gradients for the slacks are the dual variables ''p''. The QP subproblem is optimal if ''dj = ''0 for all nonbasic variables at their lower bounds, ''dj = ''0 for all nonbasic variables at their upper bounds, and ''dj ''= 0 for other variables, including superbasics. In practice, an ''approximate'' QP solution <math>(\hat{x}_k, \hat{t}_k, \hat{\pi}_k)</math> is found by relaxing these conditions.		Associated with each of the ''m'' equality constraints ''Ax - s ''= ''b ''are the ''dual variables p''. Similarly, each variable in (''x, s'') has an associated ''reduced gradient d<sub>j</Sub> ''. The reduced gradients for the variables ''x ''are the quantities ''g-A<sup>T</sup>π'', where ''g ''is the gradient of the QP objective, and the reduced gradients for the slacks are the dual variables ''p''. The QP subproblem is optimal if ''d<sub>j</sub> = ''0 for all nonbasic variables at their lower bounds, ''d<sub>j</sub> = ''0 for all nonbasic variables at their upper bounds, and ''d<sub>j</sub> ''= 0 for other variables, including superbasics. In practice, an ''approximate'' QP solution <math>(\hat{x}_k, \hat{t}_k, \hat{\pi}_k)</math> is found by relaxing these conditions.

	===The merit function===		===The merit function===

Elias: /* Introduction */

2011-09-18T10:32:06Z

Introduction

← Older revision		Revision as of 05:32, 18 September 2011
Line 1:		Line 1:
	==Introduction==		==Introduction==

	TOMLAB /SNOPT (hereafter referred to as SNOPT) is a general-purpose system for constrained optimization. It minimizes a linear or nonlinear function subject to bounds on the variables and sparse linear or nonlinear constraints. It is suitable for large-scale linear and quadratic programming and for linearly constrained optimization, as well as for general nonlinear programs of the form		TOMLAB /SNOPT (hereafter referred to as SNOPT) is a general-purpose system for constrained optimization. It minimizes a linear or nonlinear function subject to bounds on the variables and sparse linear or nonlinear constraints. It is suitable for large-scale linear and quadratic programming and for linearly constrained optimization, as well as for general nonlinear programs of the form (SparseNP)

	<math>		<math>
	\begin{array}{cc}		\begin{array}{cc}
	\~~min\limits_~~{x} & f_{0}(x) \\		\min_{x} & f_{0}(x)\\
	~~s/t~~ & l \le \~~mtx~~{c}{x \\ f(x) \\ A_{~~L}x~~ } \le u		\text{subject to} & l \le \left(\begin{array}{c}{x \\ f(x) \\ A_L x }\end{array}\right) \le u
	\end{array}		\end{array}
	</math>		</math>

	where ''l ''and ''u ''are constant lower and upper bounds, ''f''<sub>0</sub> (''x'') is a smooth scalar objective function, ''AL ''is a sparse matrix, and ''f ''(''x'') is a vector of smooth nonlinear constraint functions ''{fi ''(''x'')''}''. An optional parameter maximize may specify that ''f''<sub>0</sub> (''x'') should be maximized instead of minimized.		where ''l ''and ''u ''are constant lower and upper bounds, ''f''<sub>0</sub> (''x'') is a smooth scalar objective function, ''A<sub>L</sub>'' is a sparse matrix, and ''f ''(''x'') is a vector of smooth nonlinear constraint functions ''{f<sub>i</sub> ''(''x'')''}''. An optional parameter maximize may specify that ''f''<sub>0</sub> (''x'') should be maximized instead of minimized.

	Ideally, the first derivatives (gradients) of ''f''<sub>0</sub> (''x'') and ''fi ''(''x'') should be known and coded by the user.		Ideally, the first derivatives (gradients) of ''f''<sub>0</sub> (''x'') and ''f<sub>i</sub> ''(''x'') should be known and coded by the user.

	Note that upper and lower bounds are specified for all variables and constraints. This form allows full generality in specifying various types of constraint. Special values are used to indicate absent bounds (<math>l_j = -\infty</math> or <math>u_j = +\infty</math> for appropriate ''j''). Free variables and free constraints ("free rows") are ones that have both bounds infinite. Fixed variables and equality constraints have ''l<sub>j</sub> ''= ''u<sub>j</sub> ''.		Note that upper and lower bounds are specified for all variables and constraints. This form allows full generality in specifying various types of constraint. Special values are used to indicate absent bounds (<math>l_j = -\infty</math> or <math>u_j = +\infty</math> for appropriate ''j''). Free variables and free constraints ("free rows") are ones that have both bounds infinite. Fixed variables and equality constraints have ''l<sub>j</sub> ''= ''u<sub>j</sub> ''.
Line 22:		Line 22:
	If only the objective is nonlinear, the problem is ''linearly constrained ''(LC) and tends to solve more easily than the general case with nonlinear constraints (NC). For both cases, SNOPT applies a sparse sequential quadratic programming (SQP) method, using limited-memory quasi-Newton approximations to the Hessian of the Lagrangian. The merit function for steplength control is an augmented Lagrangian, as in the dense SQP solver NPSOL.		If only the objective is nonlinear, the problem is ''linearly constrained ''(LC) and tends to solve more easily than the general case with nonlinear constraints (NC). For both cases, SNOPT applies a sparse sequential quadratic programming (SQP) method, using limited-memory quasi-Newton approximations to the Hessian of the Lagrangian. The merit function for steplength control is an augmented Lagrangian, as in the dense SQP solver NPSOL.

	In general, SNOPT requires less matrix computation than NPSOL and fewer evaluations of the functions than the nonlinear algorithms in MINOS ~~[25, 1]~~.		In general, SNOPT requires less matrix computation than NPSOL and fewer evaluations of the functions than the nonlinear algorithms in MINOS.

	It is suitable for nonlinear problems with thousands of constraints and variables, and is efficient if many constraints and bounds are active at a solution. (Thus, ideally there should not be thousands of degrees of freedom.)		It is suitable for nonlinear problems with thousands of constraints and variables, and is efficient if many constraints and bounds are active at a solution. (Thus, ideally there should not be thousands of degrees of freedom.)

Elias: /* Major iterations */

2011-09-18T09:56:52Z

Major iterations

← Older revision		Revision as of 04:56, 18 September 2011
Line 56:		Line 56:
	===Major iterations===		===Major iterations===

	The basic structure of the SQP algorithm involves ''major ''and ''minor ''iterations. The major iterations generate a sequence of iterates ''{xk } ''that satisfy the linear constraints and converge to a point that satisfies the first-order		The basic structure of the SQP algorithm involves ''major ''and ''minor ''iterations. The major iterations generate a sequence of iterates ''{x<sub>k</sub>} ''that satisfy the linear constraints and converge to a point that satisfies the first-order

	conditions for optimality. At each iterate a QP subproblem is used to generate a search direction towards the next iterate ''xk''+1 . The constraints of the subproblem are formed from the linear constraints ''A<sub>L</sub>x - s<sub>L</sub>'' = 0 and the nonlinear constraint linearization		conditions for optimality. At each iterate a QP subproblem is used to generate a search direction towards the next iterate ''x''<sub>k+1</sub> . The constraints of the subproblem are formed from the linear constraints ''A<sub>L</sub>x - s<sub>L</sub>'' = 0 and the nonlinear constraint linearization

	<math>		<math>
	~~\Con~~(x_k) + ~~\Jac~~(x_k)(x - x_k) - ~~s\N~~ = 0,		f(x_k) + f'(x_k)(x - x_k) - s_N = 0,
	</math>		</math>

	where ''f l ''(''xk '') denotes the ''Jacobian matrix'', whose elements are the first derivatives of ''f ''(''x'') evaluated at ''x<sub>k</sub> ''. The QP constraints therefore comprise the ''m ''linear constraints		where ''f'''(''xk '') denotes the ''Jacobian matrix'', whose elements are the first derivatives of ''f ''(''x'') evaluated at ''x<sub>k</sub> ''. The QP constraints therefore comprise the ''m ''linear constraints

	<math>		<math>