Bjorn: /* Constraints and slack variables */

2013-08-14T14:39:00Z

Constraints and slack variables

← Older revision		Revision as of 09:39, 14 August 2013
Line 5:		Line 5:

	The upper and lower bounds on the ''m ''components of ''f ''(''x'') and ''AL x ''are said to define the ''general constraints'' of the problem. SNOPT converts the general constraints to equalities by introducing a set of ''slack variables''. For example, the linear constraint <math>5 \le 2x_1 + 3x_2 \le		The upper and lower bounds on the ''m ''components of ''f ''(''x'') and ''AL x ''are said to define the ''general constraints'' of the problem. SNOPT converts the general constraints to equalities by introducing a set of ''slack variables''. For example, the linear constraint <math>5 \le 2x_1 + 3x_2 \le
	+\infty</math> is replaced by <math>2x_1 + 3x_2 - s_1 = 0</math> together with the bounded slack <math>5\le s_1 \le +\infty</math>. SparseNP can therefore be written in the equivalent form		+\infty</math> is replaced by <math>2x_1 + 3x_2 - s_1 = 0\,</math> together with the bounded slack <math>5\le s_1 \le +\infty</math>. SparseNP can therefore be written in the equivalent form

	<math>		<math>

Elias at 14:33, 9 December 2011

2011-12-09T14:33:43Z

← Older revision		Revision as of 09:33, 9 December 2011
Line 61:		Line 61:
	<math>		<math>
	\min_{x,s} \quad q(x) \quad		\min_{x,s} \quad q(x) \quad
	\text{subject to} \quad Ax - s = b, \quad l \le \left(\begin{array}{c}{x \\ s}\end{array}\right) \le u,		\text{subject to} \quad Ax - s = b, \quad l \le \left(\begin{array}{c}x \\ s\end{array}\right) \le u,
	</math>		</math>

Line 85:		Line 85:

	<math>		<math>
	f(x,s,\pi) = f_0(x) - \pi^T (f(x) - s_N) + ~~\textonehalf~~(f(x) - S_N)^TD(f(x)-S_N)		f(x,s,\pi) = f_0(x) - \pi^T (f(x) - s_N) + (f(x) - S_N)^TD(f(x)-S_N)
	</math>		</math>

Line 115:		Line 115:
	<math>		<math>
	\text{subject to} \quad l \le \left(\begin{array}{c}		\text{subject to} \quad l \le \left(\begin{array}{c}
	x\\A_Lx - v + w}		x\\A_Lx - v + w
	\end{array}\right) \le u, \quad v \ge 0, \quad w \ge 0,		\end{array}\right) \le u, \quad v \ge 0, \quad w \ge 0,
	</math>		</math>
Line 138:		Line 138:
	</math>		</math>

	where ''γ'' is a nonnegative parameter (the ''elastic weight ''), and <math>~~\Obj~~(x) + \gamma e^T(v + w)</math> is called a ''composite objective'' (the <math>\ell_1</math> penalty function for the nonlinear constraints).		where ''γ'' is a nonnegative parameter (the ''elastic weight ''), and <math>f_0(x) + \gamma e^T(v + w)</math> is called a ''composite objective'' (the <math>\ell_1</math> penalty function for the nonlinear constraints).

	The value of <math>\gamma</math> may increase automatically by multiples of 10 if the optimal ''v ''and ''w ''continue to be nonzero. If <math>\gamma</math> is sufficiently large, this is equivalent to minimizing the sum of the nonlinear constraint violations subject to the linear constraints and bounds. A similar <math>\ell_1</math> formulation of SparseNP is fundamental to the <math>\ell_1</math> QP algorithm of Fletcher. See also Conn.		The value of <math>\gamma</math> may increase automatically by multiples of 10 if the optimal ''v ''and ''w ''continue to be nonzero. If <math>\gamma</math> is sufficiently large, this is equivalent to minimizing the sum of the nonlinear constraint violations subject to the linear constraints and bounds. A similar <math>\ell_1</math> formulation of SparseNP is fundamental to the <math>\ell_1</math> QP algorithm of Fletcher. See also Conn.

	The initial value of ''γ ''is controlled by the optional parameters Elastic mode and Elastic weight.		The initial value of ''γ ''is controlled by the optional parameters Elastic mode and Elastic weight.

Elias: Created page with "{{Part Of Manual|title=the SNOPT Manual|link=SNOPT}} Here we summarize the main features of the SQP algorithm used in SNOPT and introduce some terminology used in the d..."

2011-10-13T13:02:15Z

Created page with "{{Part Of Manual|title=the SNOPT Manual|link=SNOPT}} Here we summarize the main features of the SQP algorithm used in SNOPT and introduce some terminology used in the d..."

New page

{{Part Of Manual|title=the SNOPT Manual|link=[[SNOPT|SNOPT]]}}
Here we summarize the main features of the SQP algorithm used in SNOPT and introduce some terminology used in the description of the subroutine and its arguments. The SQP algorithm is fully described by Gill, Murray and Saunders.

==Constraints and slack variables==

The upper and lower bounds on the ''m ''components of ''f ''(''x'') and ''AL x ''are said to define the ''general constraints'' of the problem. SNOPT converts the general constraints to equalities by introducing a set of ''slack variables''. For example, the linear constraint <math>5 \le 2x_1 + 3x_2 \le
+\infty</math> is replaced by <math>2x_1 + 3x_2 - s_1 = 0</math> together with the bounded slack <math>5\le s_1 \le +\infty</math>. SparseNP can therefore be written in the equivalent form

<math>
\min_{x,s} \quad f_0(x)
</math>

<math>
\text{subject to} \quad
\left(\begin{array}{c}
f(x)\\
A_Lx
\end{array}\right) - s = 0,
l \le \left(\begin{array}{c}
x\\
s
\end{array}\right)
\le u.
</math>

The general constraints become the equalities ''f ''(''x'') ''- sN'' = 0 and ''ALx - sL ''= 0, where ''sL ''and ''sN ''are known as the ''linear ''and ''nonlinear ''slacks.

==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

conditions for optimality. At each iterate a QP subproblem is used to generate a search direction towards the next iterate ''x''k+1 . The constraints of the subproblem are formed from the linear constraints ''ALx - sL'' = 0 and the nonlinear constraint linearization

<math>
f(x_k) + f'(x_k)(x - x_k) - s_N = 0,
</math>

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

<math>
\begin{array}{ccc}
f'(x_k)x - s_N & = & f(x_k) + f(x_k)'x_k,\\
A_LX - s_L & = & 0,
\end{array}
</math>

where ''x ''and ''s ''are bounded above and below by ''u ''and ''l ''as before. If the ''m × n ''matrix ''A ''and ''m''-vector ''b ''are defined as

<math>
A = \left(\begin{array}{c}
f'(x_k)\\
A_L
\end{array}\right) \quad and \quad b = \left(\begin{array}{c}
-f(x_k)+f'(x_k)x_k\\
0
\end{array}\right),
</math>

then the QP subproblem can be written as

<math>
\min_{x,s} \quad q(x) \quad
\text{subject to} \quad Ax - s = b, \quad l \le \left(\begin{array}{c}{x \\ s}\end{array}\right) \le u,
</math>

where ''q''(''x'') is a quadratic approximation to a modified Lagrangian function.

==Minor iterations==

Solving the QP subproblem is itself an iterative procedure. The iterations of the QP solver are the ''minor ''iterations of the SQP method. At each minor iteration, the constraints ''Ax - s ''= ''b ''are (conceptually) partitioned into the form

<math>
Bx_B + Sx_S + Nx_N = b,
</math>

where the ''basis matrix B'' is square and nonsingular. The elements of ''xB'', ''xS'' and ''xN'' are called the ''basic'', ''superbasic ''and ''nonbasic ''variables respectively; they are a permutation of the elements of ''x ''and ''s''. At a QP solution, the basic and superbasic variables will lie somewhere between their bounds, while the nonbasic variables will normally be equal to one of their bounds. At each iteration, ''xS'' is regarded as a set of independent variables that are free to move in any desired direction, namely one that will improve the value of the QP objective (or the sum of infeasibilities). The basic variables are then adjusted in order to ensure that (''x, s'') continues to satisfy ''Ax - s ''= ''b''. The number of superbasic variables (''nS '', say) therefore indicates the number of degrees of freedom remaining after the constraints have been satisfied. In broad terms, ''nS ''is a measure of ''how nonlinear ''the problem is. In particular, ''nS'' will always be zero for LP problems.

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 ''nS ''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 ''nS '' 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-ATπ'', 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.

==The merit function==

After a QP subproblem has been solved, new estimates of the SparseNP solution are computed using a line search on the augmented Lagrangian merit function

<math>
f(x,s,\pi) = f_0(x) - \pi^T (f(x) - s_N) + \textonehalf(f(x) - S_N)^TD(f(x)-S_N)
</math>

where ''D ''is a diagonal matrix of penalty parameters (''Dii >= ''0). If (''xk, sk , pk'') 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>
\left(\begin{array}{c}
x_{k+1}\\s_{k+1}\\\pi_{k+1}
\end{array}\right)
= \left(\begin{array}{c}
x_k\\s_k\\\pi_k
\end{array}\right) + \alpha_k \left(\begin{array}{c}
\hat{x}_k-x_k\\\hat{s}_k-s_k\\\hat{\pi}_k-\pi_k
\end{array}\right)
</math>

gives a ''sufficient decrease ''in the merit function. When necessary, the penalties in ''D ''are increased by the minimum-norm perturbation that ensures descent for ''M ''.

As in NPSOL, ''sN'' is adjusted to minimize the merit function as a function of ''s'' prior to the solution of the QP subproblem.

==Treatment of constraint infeasibilities==

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

<math>
\min_{x,v,w} \quad e^T(v + w)
</math>

<math>
\text{subject to} \quad l \le \left(\begin{array}{c}
x\\A_Lx - v + w}
\end{array}\right) \le u, \quad v \ge 0, \quad w \ge 0,
</math>

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.

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.

If a QP subproblem proves to be infeasible or unbounded (or if the dual variables ''π ''for the nonlinear constraints become large), SNOPT enters "elastic" mode and thereafter solves the problem (NP(γ))

<math>
\min_{x,v,w} \quad f_0(x) + \gamma e^T(v + w)
</math>

<math>
\text{subject to} \quad l \le \left(\begin{array}{c}
x\\f(x) - v + w \\A_Lx
\end{array}\right)
\le u \quad v \ge 0, \quad w \ge 0
</math>

where ''γ'' is a nonnegative parameter (the ''elastic weight ''), and <math>\Obj(x) + \gamma e^T(v + w)</math> is called a ''composite objective'' (the <math>\ell_1</math> penalty function for the nonlinear constraints).

The value of <math>\gamma</math> may increase automatically by multiples of 10 if the optimal ''v ''and ''w ''continue to be nonzero. If <math>\gamma</math> is sufficiently large, this is equivalent to minimizing the sum of the nonlinear constraint violations subject to the linear constraints and bounds. A similar <math>\ell_1</math> formulation of SparseNP is fundamental to the <math>\ell_1</math> QP algorithm of Fletcher. See also Conn.

The initial value of ''γ ''is controlled by the optional parameters Elastic mode and Elastic weight.

SNOPT Description of the SQP method - Revision history

Bjorn: /* Constraints and slack variables */

Elias at 14:33, 9 December 2011

Elias: Created page with "{{Part Of Manual|title=the SNOPT Manual|link=SNOPT}} Here we summarize the main features of the SQP algorithm used in SNOPT and introduce some terminology used in the d..."