Linear constraints

We want to find $x^* \in$   $\mbox{$\cal R$}$$^{n}$ which satisfies:

$$\mbox{$\cal F$} (x^*)= \min_x \mbox{$\cal F$} (x) \; \; A x \geq b , \; A \in \Re^{n \times m}, b \in \Re^{m}$$ (8.3)

where $n$ is the dimension of the search space and $m$ is the number of linear constraints.

Active set - Null space method

The material of this section is based on the following reference: [Fle87].

Figure 8.1: Violation of a constraint.

At each step $s_k$ computed from 8.1, we check if one of the $m$ linear constraints has been violated. On the figure 8.1, the linear constraint $a^t x \geq b$ has been violated and it's thus "activated". Without loosing generality, let's define $A_a \in \Re^{n \times m_a}$ and $b_a \in \Re^{m_a}$ the set of the $m_a$ active constraints.

Figure 8.2: A search in the reduced space of the active constraints gives as result $y$

Let $Y$ and $Z$ be $n \times m_a$ and $n \times (n-m_a)$ matrices respectively such that $[Y:Z]$ is non-singular, and in addition let $A_a Y=I$ and $A_a Z=0$. The step must be feasible, so we must have to $A_a s \geq b_a$. A solution to this equation is given by: $s=Y b_a + Z y$ where $y$ can be any vector. Indeed, we have the following: $A_a s = A_a (Y b_a+ Z y)= A_a Y b_a+ A_a Z y= b_a$. The situation is illustrated in figure 8.2. We will choose $y$ as the solution of

$$\min_y q(x_k+Y b_a+Z y) \; \; \Vert Z y \Vert \leq \Delta_r$$ (8.4)

with $\Delta_r = \sqrt{ \Delta^2 - \Vert Y b_a \Vert^2 }$. In other words, $y$ is the minimum of the quadratical approximation of the objective function limited to the reduced space of the active linear constraints and limited to the trust region boundaries. We have already developed an algorithm able to compute $y$ in chapter 4.
When using this method, there is no difference between " approach 1" and "approach 2".
This algorithm is very stable in regards to rounding error. It's very fast because we can make Newton step (quadratical convergence speed) in the reduced space. Beside, we can use software developed in chapter 4. For all these reasons, it has been chosen and implemented. It will be fully described in chapter 9.

Gradient Projection Methods

The material of this section is based on the following reference: [CGT00e].
In these methods, we will follow the "steepest descent steps": we will follow the gradient. When we enter the infeasible space, we will simply project the gradient into the feasible space. A straightforward (unfortunately false) extension to this technique is the "Newton step projection algorithm" which is illustrated in figure 8.3. In this figure the current point is $x_k=O$. The Newton step ($s_k$) lead us to point P which is infeasible. We project P into the feasible space: we obtain B. Finally, we will thus follow the trajectory OAB, which seems good.

Figure 8.3: "newton's step projection algorithm" seems good.

In figure 8.4, we can see that the "Newton step projection algorithm" can lead to a false minimum. As before, we will follow the trajectory OAB. Unfortunately, the real minimum of the problem is C.

Figure 8.4: "newton's step projection algorithm" is false.

We can therefore only follow the gradient,not the Newton step. The speed of this algorithm is thus, at most, linear, requiring many evaluation of the objective function. This has little consequences for "approach 1" but for "approach 2" it's intolerable. For these reasons, the Null-space method seems more promising and has been chosen.