= Solution
A practical choice is a <BFGS method>, using exact <gradients> and a <line search>. At dimension $d=100$, its $d$-by-$d$ inverse-<Hessian matrix> approximation is small, whereas forming a million rank-one contributions to the exact <Hessian matrix> is expensive. If $F(x)=\sum_i e^{\|x-a_i\|^2}$, the explicit <derivatives> are
$$
\nabla F=2\sum_i e^{\|x-a_i\|^2}(x-a_i),\qquad
H_F=\sum_i e^{\|x-a_i\|^2}\bigl(4(x-a_i)(x-a_i)^T+2I\bigr).
$$
The positive-definite <Hessian matrix> and <coercivity> show that the objective has one global minimizer.
For numerical stability one can minimize $\Phi=\log F$ instead, which has exactly the same minimizer. Put $r_i=\|x-a_i\|^2$, $w_i=e^{r_i}/\sum_j e^{r_j}$, and $\bar a=\sum_iw_i a_i$. Then the <logarithmic gradient of an exponential squared-distance sum> gives
$$
g(x):=\nabla\Phi(x)=2(x-\bar a),\qquad
\nabla^2\Phi=2I+4\sum_iw_i(a_i-\bar a)(a_i-\bar a)^T\succeq2I.
$$
Evaluate the weights as $e^{r_i-r_{\max}}/\sum_j e^{r_j-r_{\max}}$ to avoid <floating-point overflow>. A <Quasi-Newton method> step is
$$
x_{n+1}=x_n-\alpha_nH_n g(x_n),
$$
where $H_n$ is the positive-definite inverse-<Hessian matrix> approximation updated by <BFGS>, and $\alpha_n$ is chosen by a <line search>, for example one satisfying the <Wolfe conditions>. Under the standard smoothness and nondegeneracy assumptions at this strongly convex minimizer, full-memory <BFGS> has \b[local <superlinear convergence>]. An exact <Newton's method in optimization> would have local <quadratic convergence>, but pays for those much more expensive exact second <derivatives>.<Quasi-Newton Methods by NEOS Guide>[Opening construction and BFGS update: approximate Hessians from <gradients>; dense update cost of order d squared]{ref}
Back to article page
