About the CONDOR algorithm.

To start the unconstrained version of the CONDOR algorithm, we will basically need:

• A starting point $x_{start}$
• A length $\rho_{start}$ which represents, basically, the initial distance between the points where the objective function will be sampled.
• A length $\rho_{end}$ which represents, basically, the final distance between the interpolation points when the algorithm stops.
  

DEFINITION: The local approximation $q_k(s)$ of $f(x)$ is valid in ${\cal B}_k(\rho)$ (a ball of radius $\rho$ around $x_k$) when $$\vert f(x_k+s)-q_k(s)\vert \leq \kappa \rho^2 \; \; \; \forall \Vert s \Vert \leq \rho$$ where $\kappa$ is a given constant independent of $x$.
We will approximatively use the following algorithm (for a complete description, see chapter 6):

1. Create an interpolation polynomial $q_0(s)$ of degree 2 which intercepts the objective function around $x_{start}$. All the points in the interpolation set $\cal Y$ (used to build $q(x)$) are separated by a distance of approximatively $\rho_{start}$. Set $x_k=$ the best point of the objective function known so far. Set $\rho_0=\rho_{start}$. In the following algorithm, $q_k(s)$ is the quadratical approximation of $f(x)$ around $x_k$, built by interpolation using $\cal Y$ (see chapter 3). $q_k(s)=f(x_k)+g_k^t s+ s^t H_k s$ where $g_k$ is the approximate gradient of $f(x)$ evaluated at $x_k$ and $H_k$ is the approximate Hessian matrix of $f(x)$ evaluated at $x_k$.
2. Set $\Delta_k=\rho_k$
3. Inner loop: solve the problem for a given precision of $\rho_k$.
   1. 1. Solve $$s_k=\min_{s \in \Re^n} q_k(s)$$ subject to $\Vert s\Vert _2 < \Delta_k$.
      2. If $\Vert s_k \Vert< \frac{1}{2}\rho_k$, then break and go to step 3(b) because, in order to do such a small step, we need to be sure that the model is valid.
      3. Evaluate the function $f(x)$ at the new position $x_k+s$. Update the trust region radius $\Delta_k$ and the current best point $x_k$ using classical trust region technique (following a scheme similar to Equation 2.20). Include the new $x_k$ inside the interpolation set $\cal Y$. Update $q_k(s)$ to interpolate on the new $\cal Y$.
      4. If some progress has been achieved (for example, $\Vert s_k \Vert>2 \rho$ or there was a reduction $f(x_{k+1})<f(x_k)$ ), increment k and return to step i, otherwise continue.
   2. Test the validity of $q_k(x)$ in ${\cal B}_k(\rho)$, like described in chapter 3.
      • Model is invalid:
        Improve the quality of the model $q_k(s)$: Remove the worst point of the interpolation set $\cal Y$ and replace it (one evaluation required!) with a new point $x_{new}$ such that: $\Vert x_{new} - x_k \Vert < \rho$ and the precision of $q_k(s)$ is substantially increased.
      • Model is valid:
        If $\Vert s_k \Vert>\rho_k$ go back to step 3(a), otherwise continue.
4. Reduce $\rho$ since the optimization steps are becoming very small, the accuracy needs to be raised.
5. If $\rho=\rho_{end}$ stop, otherwise increment k and go back to step 2.
   

From this description, we can say that $\rho$ and $\Delta_k$ are two trust region radius (global and local).
Basically, $\rho$ is the distance (Euclidian distance) which separates the points where the function is sampled. When the iterations are unsuccessful, the trust region radius $\Delta_k$ decreases, preventing the algorithm to achieve more progress. At this point, loop 3(a)i to 3(a)iv is exited and a function evaluation is required to increase the quality of the model (step 3(b)). When the algorithm comes close to an optimum, the step size becomes small. Thus, the inner loop (steps 3(a)i. to 3(a)iv.) is usually exited from step 3(a)ii, allowing to skip step 3(b) (hoping the model is valid), and directly reducing $\rho$ in step 4.
The most inner loop (steps 3(a)i. to 3(a)iv.) tries to get from $q_k(s)$ good search directions without doing any evaluation to maintain the quality of $q_k(s)$ (The evaluations that are performed on step 3(a)i) have another goal). Only inside step 3(b), evaluations are performed to increase this quality (called a ''model step'') and only at the condition that the model has been proven to be invalid (to spare evaluations!).
Notice the update mechanism of $\rho$ in step 4. This update occurs only when the model has been validated in the trust region ${\cal B}_k(\rho)$ (when the loop 3(a) to 3(b) is exited). The function cannot be sampled at point too close to the current point $x_k$ without being assured that the model is valid in ${\cal B}_k(\rho)$.
The different evaluations of $f(x)$ are used to:

(a)

guide the search to the minimum of $f(x)$ (see inner loop in the steps 3(a)i. to 3(a)iv.). To guide the search, the information gathered until now and available in $q_k(s)$ is exploited.

(b)

increase the quality of the approximator $q_k(x)$ (see step 3(b)). To avoid the degeneration of $q_k(s)$, the search space needs to be additionally explored.

(a) and (b) are antagonist objectives like usually the case in the exploitation/exploration paradigm. The main idea of the parallelization of the algorithm is to perform the exploration on distributed CPU's. Consequently, the algorithm will have better models $q_k(s)$ of $f(x)$ at disposal and choose better search direction, leading to a faster convergence.
CONDOR falls inside the class of algorithm which are proven to be globally convergent to a local (maybe global) optimum [CST97,CGT00b].
In the next chapters, we will see more precisely:

• Chapter 3: How to construct and use $q(x)$? Inside the CONDOR algorithm we need a polynomial approximation of the objective function. How do we build it? How do we use and validate it?
• Chapter 4: How to solve $$\delta_k=\min_{\delta \in \Re^n} q(x_k+\delta)$$ subject to $\Vert \delta \Vert _2 < \Delta_k$ ? We need to know how to solve this problem because we encounter it at step (3)(a)i. of the CONDOR algorithm.
• Chapter 5: How to solve approximately $$d_k=\min_{d \in \Re^n} \vert q(x_k+d)\vert$$ subject to $\Vert d \Vert _2 < \rho$ ? We need to know how to solve this problem because we encounter it when we want to check the validity (the precision) of the polynomial approximation.
• Chapter 6: The precise description of the CONDOR unconstrained algorithm.