Numeric part

The numeric part receives Eq. (2) and (3), and computes numerical solutions to it. Let R be a region defined by Eq. (2) and (3) and $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ be an objective function which has the minimum point in $(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$-space.

$$\begin{eqnarray*}R & = & \{(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\bol... ...\mbox{\boldmath$x$ })=t_{r}, t_{1} \geq 0,\ldots,t_{r} \geq 0\}. \end{eqnarray*}$$

Since all the boundaries of region R are closed, if R is not empty then the objective function $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ has its minimum value in region R. Therefore, by computing the minimum value of $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ in R, a solution to Eq. (2) and (3) is obtained as the minimum point. In this way, the algebraic under constrained problem Eq. (2) and (3) results in the constraint satisfaction minimizing problem. If $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ does not have its minimum value in R, R is empty.

The minimum point of $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ in R is obtained by computing its extremal points. The extremal points are calculated by finding zero-points of differential of $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$. Thus, it is necessary to divide R into sub-regions in which differential of $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ is continuous.

 

$$\bigcup R_{ij},$$ R =

$$R\cap\{(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath... ...j}(i,1)}=\ldots=t_{a_{j}(i,j)}=0, t_{a_{j}(i,j+1)}>0,\ldots,t_{a_{j}(i,r)}>0\},$$ R_ij = (4)

where $\{a_{j}(i,1),\ldots,a_{j}(i,j)\}$ is a combination of j integers in the range of [1,r] and there exist _rC_j combinations. The suffix i is used to distinguish these combinations and changes from 1 to _rC_j.

If sub-region R_ij consists of a finite number of points, they are directly computed. Otherwise, stationary points of $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ and singular points of R_ij computed.

Stationary points and singular points

• Stationary points of $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$

  The stationary points of $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ are computed by Lagrange Multiplier Method. Firstly, Lagrange function $L(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ },\mbox{\boldmat... ...ambda$ },\mbox{\boldmath$\mu$ },\mbox{\boldmath$\nu$ },\mbox{\boldmath$\eta$ })$ is defined and its stationary points are calculated.
  

   

  $$L(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ },... ...ambda$ },\mbox{\boldmath$\mu$ },\mbox{\boldmath$\nu$ },\mbox{\boldmath$\eta$ }) u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })... ...box{\boldmath$x$ })+\sum_{k=1}^{q}\mu_{k}(g(\mbox{\boldmath$x$ })\cdot s_{k}-1)$$ =

  $$+\sum_{k=1}^{r}\nu_{k}(h(\mbox{\boldmath$x$ })-t_{k})+\sum_{k=1}^{j}\eta_{k}t_{a(i,k)},$$ (5)

  
  
  where $\lambda$, $\mu$, $\nu$ and $\eta$ are Lagrange Multipliers. Next, the stationary points which satisfy $t_{a(i,j+1)}>0,\ldots,t_{a(i,r)}>0$ are selected.
• Singular points of R_ij

  In sub-region R_ij, a point at which the $(p+q+r+j) \times (n+q+r)$ matrix of partial derivatives $J(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ has rank less than (p+q+r+j) is a singular point.
  

   

  $$J(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ }) \left(\frac{\partial W_{k}}{\partial z_{l}}\right)_{k=1,\ldots,p+q+r+j;\; l=1,\ldots,n+q+r},$$ =

  $$\left\{\begin{array}{l} f_{k}(\mbox{\boldmath$x$ })\;(k=1,\ldots,... ...p+q+r),\\ t_{a_{j}(i,k-p-q-r)}\;(k=p+q+r+1,\ldots,p+q+r+j), \end{array}\right.$$ W_k = (6)

  $$\left\{\begin{array}{l} x_{k}\;(k=1,\ldots,n),\\ s_{k-n}\;(k=n+1,\ldots,n+q),\\ t_{k-n-q}\;(k=n+q+1,\ldots,n+q+r), \end{array}\right.$$ z_l =

  
  
  Since a singular point is often missed when computing extremal points, it has to be searched in another method.

  The condition that $J(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ has rank less than (p+q+r+j) is equivalent to the condition that the row vectors of $J(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ are linearly dependent. Then, at a singular point, Eq. (7) is valid.
  

   

  $$\exists c_{1},\ldots,c_{p+q+r+j},\;\neg(c_{1}=\ldots=c_{p+q+r+j}=0)$$

  $$c_{1}\left\{\begin{array}{c} \frac{\partial W_{1}}{\partial z_{1}... ... \vdots\\ \frac{\partial W_{p+q+r+j}}{\partial z_{n+q+r}} \end{array}\right\} \left\{\begin{array}{c} 0\\ \vdots\\ 0 \end{array}\right\}.$$ = (7)

  
  
  Therefore, by solving an equation set obtained by appending $c_{k}=1\;(k=1,\ldots,p+q+r+j)$ to Eq. (4) and (7) one by one, singular points corresponding to $c_{k}\neq 0$ are computed.

$\Box$

If a finite number of extremal points or singular points exist, they are directly computed. Otherwise, in order to check whether there is a point which satisfies $t_{a(i,j+1)}>0,\ldots,t_{a(i,r)}>0$, the obtained equation set of extremal points or singular points is regarded as a new constraint set and the above computation is recursively executed.

In the case that there exist an infinite number of extremal points, the objective function $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ has to be replaced by another function $u^{\prime}(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$. The new objective function $u^{\prime}(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ must not be constant under the condition that $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ is constant. Because, since the extremal points of $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ define a locus which makes $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ constant, they are also extremal points of a function which is constant when $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ is constant. That is, if $u^{\prime}(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ is constant under the condition that $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ is constant, new extremal points of $u^{\prime}(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ obtained by the recursive computation are completely identical with the old.

The numeric part uses the new objective function $u^{\prime}(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ obtained by translation of $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ (Figure 5).

  

Figure 5: Replacement of the objective function

Figure 6 shows the procedures of computing numerical solutions.

  

Figure 6: Procedures of computing numerical solutions

First of all, it is checked whether sub-region R_ij consists of a finite number of points. If it does, the numerical solutions are computed. Otherwise, singular point loci of R_ij and stationary point loci of the objective function $u(\mbox{\boldmath$x$ },\mbox{\boldmath$s$ },\mbox{\boldmath$t$ })$ are computed. In the stationary point computation, a list of objective functions which have been already used is made in order to avoid applying the same function in the recursive computation. Then, it is checked whether each obtained locus have a finite number of points. The computation is recursively executed until there exist a finite number of solutions.