CGO rbfSolve description

This page is part of the CGO Manual. See CGO Manual.

{{#switch: | left =

{{#switch:{{#if: | {{{smallimage}}} | }} | none =

| #default =

}} {{#if:{{#if: | {{{smallimageright}}} | }} | {{#ifeq:{{#if: | {{{smallimageright}}} | }}|none | | }} }}

| #default =

{{#switch: | none =

| #default =

}}

{{#if: | {{#ifeq:|none

 | 

| }} }}

}} Following is a detailed description of the rbfSolve algorithm.

Summary

The manual considers global optimization of costly objective functions, i.e. the problem of finding the global minimum when there are several local minima and each function value takes considerable CPU time to compute. Such problems often arise in industrial and financial applications, where a function value could be a result of a time- consuming computer simulation or optimization. Derivatives are most often hard to obtain, and the algorithms presented make no use of such information.

The emphasis is on a new method by Gutmann and Powell, A radial basis function method for global optimization. This method is a response surface method, similar to the Efficient Global Optimization (EGO) method of Jones. The TOMLAB implementation of the Radial Basis Function (RBF) method is described in detail.

Introduction

The task of global optimization is to find the set of parameters x in the feasible region $\Omega \subset R^{d}$ for which the objective function f(x) obtains its smallest value. In other words, a point $x^{\ast }$ is a global optimizer to f (x) on $\Omega$, if $f(x^{\ast })\leq f(x)$. On the other hand, a point ${\hat {x}}$ is a local optimizer to f (x), if f (x) = f (x) for all x in some neighborhood around x. Obviously, when the objective function has several local minima, there could be solutions that are locally optimal but not globally optimal and standard local optimization techniques are likely to get stuck before the global minimum is reached. Therefore, some kind of global search is needed to find the global minimum with some reliability.

Previously a Matlab implementations of the DIRECT has been made, the new constrained DIRECT and the Efficient Global Optimization (EGO) algorithms. The implementations are part of the TOMLAB optimization environment. The implementation of the DIRECT algorithm is further discussed and analyzed in Bjorkman, Holmström. Since the objective functions in our applications often are expensive to compute, we have to focus on very efficient methods. At the IFIP TC7 Conference on System Modelling and Optimization in Cambridge 1999, Hans-Martin Gutmann presented his work on the RBF algorithm. The idea of the RBF algorithm is to use radial basis function interpolation to define a utility function (Powell). The next point, where the original objective function should be evaluated, is determined by optimizing on this utility function. The combination of our need for efficient global optimization software and the interesting ideas of Powell and Gutmann led to the development of an improved RBF algorithm implemented in Matlab.

The RBF Algorithm

Our RBF algorithm is based on the ideas presented by Gutmann, with some extensions and further development. The algorithm is implemented in the Matlab routine rbfSolve.

The RBF algorithm deals with problems of the form

${\begin{array}{ll}\min \limits _{x}&f(x)\\\mathrm {s.t.} &{\begin{array}{ccccc}x_{L}&\leq &x&\leq &x_{U}\end{array}},\end{array}}$

where $f\in R$ and $x,x_{L},x_{U}\in R^{d}$. We assume that no derivative information is available and that each function evaluation is very expensive. For example, the function value could be the result of a time-consuming experiment or computer simulation.

Description of the Algorithm

We now consider the question of choosing the next point where the objective function should be evaluated. The idea of the RBF algorithm is to use radial basis function interpolation and a measure of 'bumpiness' of a radial function, σ say. A target value $f_{n}^{*}$ is chosen that is an estimate of the global minimum of f . For each $y\neq \{x_{1},...,x_{n}\}$ there exists a radial basis function that satisfies the interpolation conditions

$s_{y}(x_{i})=f(x_{i}),\quad i=1,...,n,$

$s_{y}(y)=f_{n}^{*}$

The next point x_n+1 is calculated as the value of y in the feasible region that minimizes $\sigma (s_{y})$. It turns out that the function $y\mapsto \sigma (s_{y})$ is much cheaper to compute than the original function.

Here, the radial basis function interpolant s_n has the form

$s_{n}(x)=\sum \limits _{i=1}^{n}\lambda _{i}\phi \left(\left\|x-x_{i}\right\|_{2}\right)+b^{T}x+a,$

with $\lambda _{1},\ldots ,\lambda _{n}\in R$, $b\in R^{d}$, $a\in R$ and $\phi$ is either cubic with $\phi (r)=r^{3}$ or the thin plate spline $\phi (r)=r^{2}\log r$. Gutmann considers other choices of $\phi$ and of the additional polynomial, but later concludes that the situation in the multiquadric and Gaussian cases is disappointing.

The unknown parameters $\lambda _{i}$, b and a are obtained as the solution of the system of linear equations

$\left({\begin{array}{ll}\Phi &P\\P^{T}&0\end{array}}\right)\left({\begin{array}{c}\lambda \\c\end{array}}\right)=\left({\begin{array}{c}F\\0\end{array}}\right)$

where $\Phi$ is the n × n matrix with $\Phi _{ij}=\phi \left(\left\|x_{i}-x_{j}\right\|_{2}\right)$ and

$P=\left({\begin{array}{cc}x_{1}^{T}&1\\x_{2}^{T}&1\\.&.\\.&.\\x_{n}^{T}&1\end{array}}\right),\lambda =\left({\begin{array}{c}\lambda _{1}\\\lambda _{2}\\.\\.\\\lambda _{n}\end{array}}\right),c=\left({\begin{array}{c}b_{1}\\b_{2}\\.\\.\\b_{d}\\a\end{array}}\right),F=\left({\begin{array}{c}f(x_{1})\\f(x_{2})\\.\\.\\f(x_{n})\end{array}}\right).$

$s_{y}$ could be obtained accordingly, but there is no need to do that as one is only interested in $\sigma (s_{y})$. Powell shows that if the rank of P is d + 1, then the matrix

$\left({\begin{array}{cc}\Phi &P\\P^{T}&0\end{array}}\right)$

is nonsingular and the linear system (4) has a unique solution.

For s_n it is

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma(s_y) = \sigma(s_n) + \mu_n(y) \left[s_n(y)-f_n^*\right]^2 }

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma(s_n) = \sum\limits_{i=1}^n \lambda_i s_n(x_i). }

Further, it is shown that Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma(s_y)} is

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y \notin \{x_1, \ldots ,x_n\}} .

Thus minimizing Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma(s_y)} subject to constraints is equivalent to minimizing g_n defined as

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_n(y) = \mu_n(y)\left[s_n(y)-f_n^*\right]^2,\ \ y \in \Omega \setminus \left\{x_1, \ldots ,x_n \right\}, }

where Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_n(y)} is the coefficient corresponding to y of the Lagrangian function L that satisfies Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(x_i)=0} , Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1, \ldots, n} and L(y) = 1. It can be computed as follows. F is extended to

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi_y = \left( \begin{array}{cc} \Phi & \phi_y \\ \phi_y^T & 0 \end{array} \right), }

where Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\phi_{y})_i=\phi(\left\|y-x_i\right\|_2)} , Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1, \ldots ,n} and P is extended to

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_y = \left( \begin{array}{c} P \\ y^T \ \ 1 \end{array} \right). }

Then Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_n(y)} is the (n + 1)-th component of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v \in R^{n+d+2}} that solves the system

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\begin{array}{cc} \Phi_y & P_y \\ P_y^T & 0 \end{array} \right) v = \left(\begin{array}{l} 0_{n} \\ 1 \\ 0_{d+1} \end{array} \right). }

We use the notation 0_n and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0_{d+1}} for column vectors with all entries equal to zero and with dimension n and (d + 1), respectively. The computation of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_n(y)} is done for many different y when minimizing Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_n(y)} . This requires Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^3)} operations if not exploiting the structure of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi_y} and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_y} . Hence it does not make sense to solve the full system each time. A better alternative is to factorize the interpolation matrix and update the factorization for each y. An algorithm that requires Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)} operations is described in #Factorizations and Updates.

When there are large differences between function values, the interpolant has a tendency to oscillate strongly. It might also happen that Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min s_n(y)} is much lower than the best known function value, which leads to a choice of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*} that overemphasizes global search. To handle these problems, large function values are in each iteration replaced by the median of all computed function values. Note that Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_n} and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_n} are not defined at Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1, \ldots ,x_n} and

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim\limits_{y \rightarrow x_i} \mu_n(y) = \infty, ~~i=1, \ldots, n. }

This will cause problems when Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_n} is evaluated at a point close to one of the known points. The function Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h_n(x)} defined by

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h_n(x) ~=~ \left\{ \begin{array}{cl} \frac{1}{g_n(x)}, & x \notin\left\{x_1, \ldots ,x_n\right\} \\ 0, & x \in\left\{x_1, \ldots ,x_n\right\} \end{array} \right. }

is differentiable everywhere on Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega} , and is thus a better choice as objective function. Instead of minimizing Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_n(y)} one may minimize Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -h_n(y)} . In our implementation we instead minimize Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -\log (h_n(y))} . By this we avoid a flat minimum and numerical trouble when Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h_n(y)} is very small.

The Choice of f *

For the value of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle $f_n^*} it should hold that

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^* \in \left[-\infty,\min\limits_{y \in \Omega} s_n(y)\right]. }

The case Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*=\min\limits_{y \in \Omega} s_n(y)} is only admissible if Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min\limits_{y \in \Omega} s_n(y)<s_n(x_i)} , <mah>i=1, \ldots, n</math>. There are two special cases for the choice of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*} . In the case when Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*=\min\limits_{y \in \Omega} s_n(y)} , then minimizing is equivalent to

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min\limits_{y \in \Omega} s_n(y). }

In the case when Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*=-\infty} , then minimizing is equivalent to

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min\limits_{y \in \Omega \setminus \left\{x_1, \ldots ,x_n \right\} } \mu_n(y). }

So how should Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*} be chosen? If Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*=-\infty} , then the algorithm will choose the new point in an unexplored region, which is good from a global search point of view, but the objective function will not be exploited at all. If Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*=\min\limits_{y \in \Omega} s_n(y)} , the algorithm will show good local behaviour, but the global minimum might be missed. Therefore, there is a need for a mixture of values for Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*} close to and far away from Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min\limits_{y \in \Omega} s_n(y)} . Gutmann describes two different strategies for the choice of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*} .

The first strategy, denoted idea 1, is to perform a cycle of length N + 1 and choose Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*} as

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^* = \min\limits_{y \in \Omega} s_n(y)-W \cdot \left(\max\limits_i f(x_i)- \min\limits_{y \in \Omega} s_n(y)\right), }

with

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W = \left[\frac{(N-(n-n_{init}))\mathrm{mod}(N+1)}{N}\right]^2, }

where Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_{init}} is the number of initial points. Here, N = 5 is fixed and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max\limits_i f(x_i)} is not taken over all points, except for the first step of the cycle. In each of the subsequent steps the Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-n_{max}} points with largest function value are removed (not considered) when taking the maximum. Hence the quantity Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max\limits_i f(x_i)} is decreasing until the cycle is over. Then all points are considered again and the cycle starts from the beginning. More formally, if Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n-n_{init})\mathrm{mod}(N+1)=0} , Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_{max}=n} , otherwise

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_{max}=\max\left\{2,n_{max}-\mathrm{floor}((n-n_{init})/N)\right\} }

The second strategy, denoted idea 2, is to consider Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*} as the optimal value of

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{ll} \min & f^*(y) \\ \mathrm{s.t.} & \mu_n(y)\left[s_n(y)-f^*(y) \right]^2 \leq \alpha_n^2 \\ & y \in \Omega, \end{array} }

and then perform a cycle of length N + 1 on the choice of an . Here, N = 3 is fixed and

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lll} \alpha_n & = & \frac{1}{2}\left( \max\limits_i f(x_i)- \min\limits_{y \in \Omega} s_n(y) \right),\ \ n=n_0,n_0+1 \\ \alpha_{n_0+2} & = & \min\left\{1,\frac{1}{2}\left( \max\limits_i f(x_i)- \min\limits_{y \in \Omega} s_n(y) \right) \right\} \\ \alpha_{n_0+3} & = & 0, \end{array} }

where Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_0} is set to n at the beginning of each cycle. For this strategy, Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max\limits_i f(x_i)} is taken over all points in all parts of the cycle.

Note that for a fixed y the optimal Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^*(y)} is the one for which

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_n(y)\left[s_n(y)-f^*(y)\right]^2 = \alpha_n^2. }

Substituting this equality constraint into the objective simplifies the problem to the minimization of

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^*(y) = s_n(y) - \alpha_n/\sqrt{\mu_n(y)}. }

Denoting the minimizer by Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^*} , and choosing Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*=f^*(y^*)} , it is evident that Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^*} minimizes Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_n(y)\left[s_n(y)-f_n^*\right]^2} and hence Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_n(y)} .

For both strategies (idea 1 and idea 2), a check is performed when Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n-n_{init})\mathrm{mod}(N+1)=N} . This is the stage when a purely local search is performed, so it is important to make sure that the minimizer of sn is not one of the interpolation points or too close to one. The test used is

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{min}-\min\limits_{y \in \Omega} s_n(y) \leq 10^{-4} \max\left\{1,|f_{min}|\right\}, }

where Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{min}} is the best function value found so far, i.e. Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min\limits_i f(x_i)} , Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1, \ldots ,n} . For the first strategy (idea 1), then

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*=\min\limits_{y \in \Omega} s_n(y)-10^{-2}\max\left\{1,|f_{min}|\right\}, }

otherwise Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n^*} is set to 0. For the second strategy (idea 2), then an (or more correctly Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_{n_0+3}} ) is set

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_{n_0+3}=\min\left\{1,\frac{1}{2}\left( \max\limits_i f(x_i)- \min\limits_{y \in \Omega} s_n(y) \right) \right\}, }

otherwise Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_{n_0+3}} is set to 0.

Factorizations and Updates

In Powell, a factorization algorithm is presented for the solution. The algorithm makes use of the conditional definiteness of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi} , i.e. Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda^T \Phi \lambda > 0, ~\lambda \neq 0} and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P^T \lambda=0} . If

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = \left(\begin{array}{cc} Y & Z \end{array} \right) \left(\begin{array}{c} R \\ 0 \end{array} \right) }

is the QR decomposition of P , then the columns of Z span the null space of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P^T} , and every Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda} with Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P^T \lambda=0} can be expressed as Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda=Z z} for some vector z. Thus the conditional positive definiteness implies that

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z^T Z^T \Phi Z z > 0, ~z \in R^{n-d-1} ~~\backslash~ \{0\}. }

This shows that Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z^T \Phi Z} is positive definite, and thus its Cholesky factorization

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z^T \Phi Z = L L^T }

exists. This property can be used to solve (4) as follows. Consider the interpolation condition Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi \lambda+Pc=F} in (4). Multiply from left by Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z^T} and replace Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda} by Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z z} . Because Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z^T P=0} , the interpolation condition simplifies to

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z^T \Phi Z z = Z^T F. }

Solving this system using the Cholesky factorization gives z. Then compute Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda=Z z} and solve

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P c = F-\Phi \lambda }

for c using the QR decomposition of P as

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Rc = Y^T\! (F - \Phi \lambda). }

The same principle can be applied to solve (12) for a given y to get Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_n(y)} . In analogy to the discussion above, if the extended matrices Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi_y} and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_y} in (10) and (11), respectively, are given, and if

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z_{y}^T P_y = 0 }

and

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z_{y}^T \Phi_y Z_{y} = L_y L_y^T }

is the Cholesky factorization, then the vector

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v = Z_{y} z(y) }

yields Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_n(y) = v_{n+1}} , where z(y) solves

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z_{y}^T \Phi_y Z_{y} z = Z_{y} \left( \begin{array}{c} 0_n \\ 1 \end{array} \right). }

The Cholesky factorization is the most expensive part of this procedure. It requires Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n^3)} operations. As Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_n(y)} must be computed for many different y this is inacceptable. However, if one knows the QR factors of P and the Cholesky factor of Z T FZ , the QR factorization of P_y and the new Cholesky factor L_y can be computed in Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)} operations.

The new Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi(y)} is

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi_y = \left( \begin{array}{cc} \Phi & \phi_y \\ \phi_y^T & 0 \end{array} \right), }

where Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_y)_i=\phi(\left\|y-x_i\right\|_2)} , Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1, \ldots ,n} . The new P (y) is

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_y = \left( \begin{array}{c} P \\ y^T \ \ 1 \end{array} \right). }

Compute the QR factorization of P_y, defined in (10). Given Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P=QR} , the QR factorization of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_y} may be written as

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_y = Q_y R_y = \left( \begin{array}{cc} Q & 0 \\ 0 & 1 \end{array} \right) H R_y, }

where Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} is an orthogonal matrix obtained by d + 1 Givens rotations and for Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=d+2, \ldots, n} the i-th column of H is the i-th unit vector. Denote Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B=Q^T \Phi Q} . Using Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi_y} as defined in (10) consider the expanded B matrix

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lll} B_y & = & Q_y^T \Phi_y Q_y = H^T \left( \begin{array}{cc} Q^T & 0 \\ 0 & 1 \end{array} \right) \Phi_y \left( \begin{array}{cc} Q & 0 \\ 0 & 1 \end{array} \right) H = \\ & = & H^T \left( \begin{array}{cc} B & Q^T \phi_y \\ \phi_y^T Q & 0 \end{array} \right) H. \end{array} }

Multiplications from the right and left with H affects only the first (d + 1) rows and columns and the last row and the last columns of the matrix in the middle. (Remember, d is the dimension of the problem). Hence

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_y = \left( \begin{array}{ccc} \ast & \ast & \ast \\ \ast & Z^T \Phi Z & v \\ \ast & v^T & \gamma \end{array} \right), }

where * denotes entries not important for the moment. From the form of B_y it follows that

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z_{y}^T \Phi Z_{y} = \left( \begin{array}{cc} Z^T \Phi Z & v \\ v^T & \gamma \end{array} \right) }

holds. The Cholesky factorization of Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z^T \Phi Z} is already known. The new Cholesky Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_y} factor is found by solving the lower triangular system Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L l = v} for l, computing Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta=\sqrt{\gamma-l^Tl}} , and setting

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_y = \left( \begin{array}{cc} L & 0 \\ l^T & \beta \end{array} \right). }

It is easily seen that Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_y L_y^T = Z_{y}^T \Phi_y Z_{y}} because

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{lll} L_y L_y^T & = & \left( \begin{array}{cc} L & 0 \\ l^T & \beta \end{array} \right) \left( \begin{array}{cc} L^T & l \\ 0 & \beta \end{array} \right) = \left( \begin{array}{cc} L L^T & L l \\ l^T L & l^T l + \beta^2 \end{array} \right) = \\ & = & \left( \begin{array}{cc} Z^T \Phi Z & v \\ v^T & \gamma \end{array} \right) = Z_{y}^T \Phi_y Z_{y}. \end{array} }

Note that in practice we do the following: First compute the factorization of P , i.e. Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_y=Q_yR_y} , using Givens rotations. Then, since we are only interested in v and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} in (42), it is not necessary to compute the matrix B_y in (41). Setting v to the last column in Q_yand computing Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{v}=\Phi_y^T \hat{v}=\Phi_y \hat{v}} (Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Phi_y} is symmetric), gives v and Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} by multiplying the last (n - d) columns in Q_y by Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle tilde{v}} , i.e.

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \begin{array}{cc} v \\ \gamma \end{array} \right)= \begin{array}{ll} Q_{y_{\cdot i}}^T \tilde{v}, & i=d+2, \ldots ,n+1. \end{array} }

Using this algorithm, v and γ are computed using ((n + 1) + (n - d)) inner products instead of the two matrix multiplications in (41).

Note that the factorization algorithm is a normal 'null-space' method for solving an optimization problem involving linear equality constraints. The system of linear equations in (4) defines the necessary conditions for a stationary point to the unconstrained quadratic programming (QP) problem

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min_{\lambda, c} \quad \frac{1}{2} \lambda^T \Phi \lambda + \lambda^T (P c -F). }

Viewing c as Lagrange multipliers for the linear equalities in (4), (47) is equivalent to the QP problem in λ defined as

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min_{\lambda} \quad \frac{1}{2} \lambda^T \Phi \lambda - F^T\lambda \quad \text{subject to} \quad P^T \lambda = 0. }

The first condition in the conditional positive definiteness definition is the same as saying that the reduced Hessian must be positive definite at the solution of the QP problem if that solution is to be unique.

The type of update procedure described above is suitable each time an optimal point y = xn+1 is added. However, when evaluating all candidates y an even more efficient algorithm can be formulated. What is needed is a black-box procedure to solve linear systems with a general right-hand side:

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\begin{array}{cc} \Phi & P \\ P^T & 0 \end{array}\right) \left(\begin{array}{c} \lambda \\ c \end{array}\right) = \left(\begin{array}{c} g \\ r \end{array}\right). }

Using the QR-factorization in (28) the steps

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{ccc} R^T v & = & r,\\ Z^T \Phi Zw & = & Z^T(g - \Phi Yv),\\ \lambda &=& Yv + Zw,\\ R c &=& Y^T(g - \Phi \lambda) \end{array} }

simplify when r = 0 as in (4), but all steps are useful for solving the extended system (49); see next.

For each of many vectors y, the extended system takes the form

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\begin{array}{cc|c} \Phi & \phi & P\\ \phi^T & 0 & p^T\\ \hline P^T & p & 0 \end{array}\right) \left(\begin{array}{c} \bar{\lambda} \\ \mu \\ \bar{c} \end{array}\right) = \left(\begin{array}{c} 0 \\ 1 \\ 0 \end{array}\right), }

where Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^T = (\,y^T\ \ 1\,)} . This permutes to

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\begin{array}{cc|c} \Phi & P & \phi\\ P^T & 0 & p\\ \hline \phi^T & p^T & 0 \end{array}\right) \left(\begin{array}{c} \bar{\lambda}\\ \bar{c} \\ \mu \end{array}\right) = \left(\begin{array}{c} 0 \\ 0 \\ 1 \end{array}\right), }

which may be solved by block-LU factorization (also known as the Schur-complement method). It helps that most of the right-hand side is zero. The solution is given by the steps

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\begin{array}{cc} \Phi & P \\ P^T & 0 \end{array}\right) \left(\begin{array}{c} \hat{\lambda} \\ \hat{c} \end{array}\right) = \left(\begin{array}{c} \phi \\ p \end{array}\right), }

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu = -1 / (\phi^T \hat{\lambda} + p^T \hat{c}), }

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\begin{array}{c} \bar{\lambda} \\ \bar{c} \end{array}\right) = -\mu \left(\begin{array}{c} \hat{\lambda} \\ \hat{c} \end{array}\right). }

Thus, each y requires little more than solving for Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\hat{\lambda},\hat{c})} using the current factorizations (two operations each with Q, R and L). This is cheaper than updating the factors for each y, and should be reliable unless the matrix in (4) is nearly singular. The updating procedure is best numerically, and it is still needed once when the final Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = x_{n+1}} is chosen.

A Compact Algorithm Description

Section #Description of the Algorithm-#Factorizations and Updates described all the elements of the RBF algorithm as implemented in our Matlab routine rbfSolve, but our discussion has covered several pages. We now summarize everything in a compact step-by-step description. Steps 2, 6 and 7 are different in idea 1 and idea 2.

	idea 1	idea 2
1:	Choose n initial points x1 , . . . , xn (normally the 2d box corner points defined by the variable bounds). Compute Fi = f (xi ), i = 1, 2, . . . , n and set ninit = n.
2:	Start a cycle of length 6.	Start a cycle of length 4.
3:	If the maximum number of function evalua- tions reached, quit.
4:	Compute the radial basis function interpolant sn by solving the system of linear equations (4).
5:	Solve the minimization problem min sn (y). y??
6:	Compute f * in (18) corresponding to the current position in the cycle.	Compute an in (22) corresponding to the current position in the cycle.
7:	New point xn+1 is the value of y that mini- mizes gn (y) in (9).	New point xn+1 is the value of y that min- imizes f *(y) in (24).
8:	Compute Fn+1 = f (xn+1 ) and set n = n + 1.
9:	If end of cycle, go to 2. Otherwise go to 4.

Some Implementation Details

The first question that arise is how to choose the points Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1, \ldots ,x_{n_{init}}} to include in the initial set. We only consider box constrained problems, and choose the corners of the box as initial points, i.e. Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_{init}=2^d} . Starting with other points is likely to lead to the corners during the iterations anyway. But as Gutmann suggests, having a "good" point beforehand, one can include it in the initial set.

The subproblem

Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{ll} \min\limits_{y \in \Omega} & s_n(y) \end{array}, }

is itself a problem which could have more than one local minima. To solve (51) (at least approximately), we start from the interpolation point with the least function value, i.e. Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle mathrm{argmin} f(x_i)} , Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1, \ldots ,n} , and perform a local search. In many cases this leads to the minimum of s_n . Of course, there is no guarantee that it does. We use analytical expressions for the derivatives of sn and perform the local optimization using ucSolve in TOMLAB running the inverse BFGS algorithm.

To minimize Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_n(y)} for the first strategy, or Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^*(y)} for the second strategy, we use our Matlab routine glbSolve implementing the DIRECT algorithm (see the TOMLAB manual). We run glbSolve for 500 function evaluations and choose x_n+1 as the best point found by glbSolve. When Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n-n_{init})\mathrm{mod}(N+1)=N} (when a purely local search is performed) and the minimizer of sn is not too close to any of the interpolation points, i.e. (25) is not true, glbSolve is not used to minimize Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_n(y)} or Failed to parse (SVG with PNG fallback (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^*(y)} . Instead, we choose the minimizer of (51) as the new point x_n+1. The TOMLAB routine AppRowQR is used to update the QR decomposition.

Our experience so far with the RBF algorithm shows that for the second strategy (idea2), the minimum of (24) is very sensitive for the scaling of the box constraints. To overcome this problem we transform the search space to the unit hypercube. This algorithm improvement is necessary to avoid rank deficiency in the interpolation matrix for the train design problem.

In our implementation it is possible to restart the optimization with the final status of all parameters from the previous run.