2.5 A Final Example

As a third example, consider the constrained problem in the variables $x_1 ,\cdots$, $x_{100}$ and y

$${\rm minimize} \;\;\;\;{\scriptstyle \frac{1}{2}}((x_1 - x_{100}) x_2 + y)^2 + 2 x_1^2 + 2 x_1^{ } x_{100}^{ }$$ (2.18)

subject to the constraints

$$x_1 x_{i + 1} + (1 + {\scriptstyle \frac{2}{i}}) x_i x_{100} + y \leq 0 \;\;\;\;(1 \leq i \leq 99),$$ (2.19)

$$0 \leq (\sin x_i)^2 \leq {\scriptstyle \frac{1}{2}}\;\;\;\;(1 \leq i \leq 100),$$ (2.20)

$$(x_1 + x_{100} )^2 = 1$$ (2.21)

and the simple bounds

$$-1 \leq x_i \leq i \;\;\;\;(1 \leq i \leq 100).$$ (2.22)

As before, there are a number of ways of casting this problem in the form (2.1)-(2.4). We chose to decompose the problem as follows:

1. the objective function comprises two groups, the first of which uses the non-trivial group function $g (\alpha ) = {\scriptstyle \frac{1}{2}}\alpha^2$. This group contains a single linear element; the element function is y. There is also a nonlinear element $( x_1 - x_{100} ) x_2$. This element function has three elemental variables, $v_1$, $v_2$ and $v_3$, say (with $v_1 = x_1$, $v_2 = x_{100}$ and $v_3 = x_2$); there is a useful transformation from elemental to internal variables of the form $u_1 = v_1 - v_2$ and $u_2 = v_3$ and the element function may then be represented as $u_1 u_2$. The second group may be considered as a quadratic objective group, and written as ${\scriptstyle \frac{1}{2}}( h_{1,1} x_1 x_1 + h_{1,100} x_1 x_{100} + h_{100,1} x_{100} x_1 )$, where $h_{1,1} = 4$ and $h_{1,100} =$ $h_{100,1} = 2$.

2. The next set of groups, inequality constraints, $x_1 x_{i+1} + (1 + 2/i) x_i x_{100} + y \leq 0 \; {\rm for} \; 1 \leq i \leq 99$ are of the form (2.4) with no lower bounds. Each uses the trivial group function $g ( \alpha ) = \alpha$ and contains a single linear element, $y$, and two nonlinear elements $x_i x_{i+1}$ and $(1 + 2/i) x_i x_{100}$. Both nonlinear elements are of the same type, $p_1 v_1 v_2$, for appropriate variables $v_1$ and $v_2$ and parameter $p_1$, and there is no useful transformation to internal variables.

3. The following set of groups, again inequality constraints, $0 \leq (\sin{x_i})^2 \leq {\scriptstyle \frac{1}{2}}\;$ for $\; 1 \leq i \leq 100$, are of the form (2.4) with both lower and upper bounds. Each uses the non-trivial group function $g (\alpha ) = \alpha^2$ and contains a single nonlinear element of the type $sin v_1$ for an appropriate variable $v_1$. Notice that the group types for these groups and for the objective function group are both of the form $g( \alpha ) = p_1 \alpha^2$, for some parameter $p_1$, and it may prove more convenient to use this form to cover both sets of groups.

4. The last group, an equality constraint, $(x_1 + x_{100} )^2 - 1 = 0$, is of the form (2.3). Again, this group uses the trivial group function $g ( \alpha ) = \alpha$ and contains a single linear element, $-1$, and a single nonlinear element of the type $( v_1 + v_2 )^2$ for appropriate elemental variables $v_1$ and $v_2$. Once more, a single internal variable, $u_1 = v_1 + v_2$ can be used and the element is then represented as $u_1^2$.

Thus we see that we can consider our problem to be made up of 201 groups of two different types as well as an quadratic objective group so we will have to provide our optimization procedure with function and derivative values for these at some stage. There are 200 nonlinear elements of four different types and again this means that we shall have to provide function and derivative values for these. As for the previous example, there is so much structure to this problem that it would be inefficient to pass the data group-by-group and element-by-element. Again, we will introduce ways to specify this repetitious structure using a convenient shorthand.