Convex Optimization · Problem 9.32

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · gauss-newton-convex-nonlinear-least-squares

Problem

Gauss-Newton method for convex nonlinear least-squares problems. We consider a (nonlinear) least-squares problem, in which we minimize a function of the form f(x)=12∑i=1mfi(x)2,f(x) = \frac{1}{2} \sum_{i=1}^m f_i(x)^2, where fif_i are twice differentiable functions. The gradient and Hessian of ff at xx are given by ∇f(x)=∑i=1mfi(x)∇fi(x),∇2f(x)=∑i=1m(∇fi(x)∇fi(x)T+fi(x)∇2fi(x)).\nabla f(x) = \sum_{i=1}^m f_i(x) \nabla f_i(x), \qquad \nabla^2 f(x) = \sum_{i=1}^m \left( \nabla f_i(x) \nabla f_i(x)^T + f_i(x) \nabla^2 f_i(x) \right). We consider the case when ff is convex. This occurs, for example, if each fif_i is either nonnegative and convex, or nonpositive and concave, or affine. The Gauss-Newton method uses the search direction Δxgn=−(∑i=1m∇fi(x)∇fi(x)T)−1(∑i=1mfi(x)∇fi(x)).\Delta x_{\mathrm{gn}} = -\left( \sum_{i=1}^m \nabla f_i(x) \nabla f_i(x)^T \right)^{-1} \left( \sum_{i=1}^m f_i(x) \nabla f_i(x) \right). (We assume here that the inverse exists, i.e., the vectors ∇f1(x),…,∇fm(x)\nabla f_1(x), \ldots, \nabla f_m(x) span Rn\mathbf{R}^n.) This search direction can be considered an approximate Newton direction (see exercise 9.31), obtained by dropping the second derivative terms from the Hessian of ff. We can give another simple interpretation of the Gauss-Newton search direction Δxgn\Delta x_{\mathrm{gn}}. Using the first-order approximation fi(x+v)≈fi(x)+∇fi(x)Tvf_i(x + v) \approx f_i(x) + \nabla f_i(x)^T v we obtain the approximation f(x+v)≈12∑i=1m(fi(x)+∇fi(x)Tv)2.f(x + v) \approx \frac{1}{2} \sum_{i=1}^m (f_i(x) + \nabla f_i(x)^T v)^2. The Gauss-Newton search step Δxgn\Delta x_{\mathrm{gn}} is precisely the value of vv that minimizes this approximation of ff. (Moreover, we conclude that Δxgn\Delta x_{\mathrm{gn}} can be computed by solving a linear least-squares problem.) Test the Gauss-Newton method on some problem instances of the form fi(x)=(1/2)xTAix+biTx+1,f_i(x) = (1/2)x^T A_i x + b_i^T x + 1, with Ai∈S++nA_i \in \mathbf{S}^n_{++} and biTAi−1bi≤2b_i^T A_i^{-1} b_i \leq 2 (which ensures that ff is convex).

Related theory

Browse the problem library