Optimization theory is the branch of applied mathematics whose purpose is to consider a mathematical expression in order to find a set of parameters that either maximize or minimize it. Being an applied discipline, problems usually arise from real-life situations including areas like science, engineering and finance (among many other). This section presents some basic concepts for completeness and is not meant to replace a treaty on the subject. The reader is encouraged to consult further references for more information.
Solution of linear weighted least squares problems
Consider the quadratic problem
$$\underset{h}{\text{min}}\phantom{\rule{0.277778em}{0ex}}{\parallel d-\mathbf{C}h\parallel}_{2}$$
which can be written as
$$\underset{h}{\text{min}}\phantom{\rule{0.277778em}{0ex}}{\left(d,-,\mathbf{C},h\right)}^{T}\left(d,-,\mathbf{C},h\right)$$
omitting the square root since this problem is a strictly convex one. Therefore its unique (and thus global) solution is found at the point where the partial derivatives with respect to the optimization variable are equal to zero. That is,
$$\begin{array}{cc}\hfill \frac{\partial}{\partial h}\left\{{\left(d,-,\mathbf{C},h\right)}^{T},\left(d,-,\mathbf{C},h\right)\right\}& =\frac{\partial}{\partial h}\left\{{d}^{T},d,-,2,{d}^{T},\mathbf{C},h,+,{\left(\mathbf{C},h\right)}^{T},\mathbf{C},h\right\}\hfill \\ & =-2{\mathbf{C}}^{T}d+2{\mathbf{C}}^{T}\mathbf{C}h=0\hfill \\ & \Rightarrow \phantom{\rule{0.277778em}{0ex}}{\mathbf{C}}^{T}\mathbf{C}h={\mathbf{C}}^{T}d\hfill \end{array}$$
The solution of
[link] is given by
$$h={\left({\mathbf{C}}^{T},\mathbf{C}\right)}^{-1}{\mathbf{C}}^{T}d$$
where the inverted term is referred
[link] ,
[link] as the
Moore-Pentrose pseudoinverse of
${\mathbf{C}}^{T}\mathbf{C}$ .
In the case of a weighted version of
[link] ,
$$\underset{h}{\text{min}}\phantom{\rule{0.277778em}{0ex}}{\parallel \sqrt{w}\left(d,-,\mathbf{C},h\right)\parallel}_{2}^{2}=\sum _{k}{w}_{k}{|{d}_{k}-{C}_{k}h|}^{2}$$
where
${C}_{k}$ is the
$k$ -th row of
$\mathbf{C}$ , one can write
[link] as
$$\underset{h}{\text{min}}\phantom{\rule{0.277778em}{0ex}}\left(\mathbf{W},(,d,-,\mathbf{C},h\right){)}^{T}\left(\mathbf{W},(,d,-,\mathbf{C},h\right))$$
where
$\mathbf{W}=\text{diag}\left(\sqrt{w}\right)$ contains the weighting vector
$w$ . The solution is therefore given by
$$h={\left({\mathbf{C}}^{T},{\mathbf{W}}^{T},\mathbf{W},\mathbf{C}\right)}^{-1}{\mathbf{C}}^{T}{\mathbf{W}}^{T}\mathbf{W}d$$
Newton's method and the approximation of linear systems in an
${l}_{p}$ Sense
Newton's method and
${l}_{p}$ Linear phase systems
Consider the problem
$$\underset{a}{\text{min}}\phantom{\rule{0.277778em}{0ex}}g\left(a\right)={\parallel A(\omega ;a)-D\left(\omega \right)\parallel}_{p}$$
for
$a\in {\mathbb{R}}^{M+1}$ . Problem
[link] is equivalent to the better posed problem
$$\begin{array}{ccc}\hfill \underset{a}{\text{min}}\phantom{\rule{0.277778em}{0ex}}f\left(a\right)=g{\left(a\right)}^{p}& =& {\parallel A(\omega ;a)-D\left(\omega \right)\parallel}_{p}^{p}\hfill \\ & =& \sum _{i=0}^{L}\mid {C}_{i}a-{D}_{i}{\mid}^{p}\hfill \end{array}$$
where
${D}_{i}=D\left({\omega}_{i}\right)$ ,
${\omega}_{i}\in [0,\pi ]$ ,
${C}_{i}=[{C}_{i,0},...,{C}_{i,M}]$ , and
$$\mathbf{C}=\left[\begin{array}{c}{C}_{0}\\ \vdots \\ {C}_{L}\end{array}\right]$$
The
$ij$ -th element of
$\mathbf{C}$ is given by
${C}_{i,j}=\text{cos}\phantom{\rule{1mm}{0ex}}{\omega}_{i}(M-j)$ , where
$0\le i\le L$ and
$0\le j\le M$ . From
[link] we have that
$$\nabla f\left(a\right)=\left[\begin{array}{c}\frac{\partial}{\partial {a}_{0}}f\left(a\right)\\ \vdots \\ \frac{\partial}{\partial {a}_{M}}f\left(a\right)\end{array}\right]$$
where
${a}_{j}$ is the
$j$ -th element of
$a\in {\mathbb{R}}^{M+1}$ and
$$\begin{array}{ccc}\hfill \frac{\partial}{\partial {a}_{j}}f\left(a\right)& =& \frac{\partial}{\partial {a}_{j}}\sum _{i=0}^{L}\mid {C}_{i}a-{D}_{i}{\mid}^{p}\hfill \\ & =& \sum _{i=0}^{L}\frac{\partial}{\partial {a}_{j}}\mid {C}_{i}a-{D}_{i}{\mid}^{p}\hfill \\ & =& p\sum _{i=0}^{L}\mid {C}_{i}a-{D}_{i}{\mid}^{p-1}\xb7\frac{\partial}{\partial {a}_{j}}\mid {C}_{i}a-{D}_{i}\mid \hfill \end{array}$$
Now,
$$\frac{\partial}{\partial {a}_{j}}\mid {C}_{i}a-{D}_{i}\mid =\text{sign}({C}_{i}a-{D}_{i})\xb7\frac{\partial}{\partial {a}_{j}}({C}_{i}a-{D}_{i})={C}_{i,j}\phantom{\rule{0.277778em}{0ex}}\text{sign}({C}_{i}a-{D}_{i})$$
where
$$\underset{u\left(a\right)\to {0}^{+}}{lim}\frac{\partial}{\partial {a}_{j}}\mid u\left(a\right){\mid}^{p}=\underset{u\left(a\right)\to {0}^{-}}{lim}\frac{\partial}{\partial {a}_{j}}\mid u\left(a\right){\mid}^{p}=0$$
$$\text{sign}\left(x\right)=\left\{\begin{array}{cc}1& x>0\hfill \\ 0& x=0\hfill \\ -1& x<0\hfill \end{array}\right)$$
Therefore the Jacobian of
$f\left(a\right)$ is given by
$$\nabla f\left(a\right)=\left[\begin{array}{c}p\sum _{i=0}^{L}{C}_{i,0}\phantom{\rule{0.277778em}{0ex}}\mid {C}_{i}a-{D}_{i}{\mid}^{p-1}\text{sign}({C}_{i}a-{D}_{i})\\ \vdots \\ p\sum _{i=0}^{L}{C}_{i,M-1}\phantom{\rule{0.277778em}{0ex}}\mid {C}_{i}a-{D}_{i}{\mid}^{p-1}\text{sign}({C}_{i}a-{D}_{i})\end{array}\right]$$
The
Hessian of
$f\left(a\right)$ is the matrix
${\nabla}^{2}f\left(a\right)$ whose
$jm$ -th element (
$0\le j,m\le M$ ) is given by
$$\begin{array}{ccc}\hfill {\nabla}_{j,m}^{2}f\left(a\right)=\frac{\partial {a}^{2}}{\partial {a}_{j}\partial {a}_{m}}f\left(a\right)& =& \frac{\partial}{\partial {a}_{m}}\frac{\partial}{\partial {a}_{j}}f\left(a\right)\hfill \\ & =& \sum _{i=0}^{L}p\phantom{\rule{0.222222em}{0ex}}{C}_{i,j}\phantom{\rule{0.277778em}{0ex}}\frac{\partial}{\partial {a}_{m}}\mid {D}_{i}-{C}_{i}a{\mid}^{p-1}\text{sign}({D}_{i}-{C}_{i}a)\hfill \\ & =& \sum _{i=0}^{L}\alpha \frac{\partial}{\partial {a}_{m}}b\left(a\right)d\left(a\right)\hfill \end{array}$$
where adequate substitutions have been made for the sake of simplicity. We have
$$\begin{array}{ccc}\hfill \frac{\partial}{\partial {a}_{m}}b\left(a\right)& =& \frac{\partial}{\partial {a}_{m}}\mid {C}_{i}a-{D}_{i}{\mid}^{p-1}\hfill \\ & =& (p-1){C}_{i,m}\mid {C}_{i}a-{D}_{i}{\mid}^{p-2}\text{sign}({C}_{i}a-{D}_{i})\hfill \\ \hfill \frac{\partial}{\partial {a}_{m}}d\left(a\right)& =& \frac{\partial}{\partial {a}_{m}}\text{sign}({D}_{i}-{C}_{i}a)=0\hfill \end{array}$$
Note that the partial derivative of
$d\left(a\right)$ at
${D}_{i}-{C}_{i}a=0$ is not defined. Therefore
$$\begin{array}{ccc}\hfill \frac{\partial}{\partial {a}_{m}}b\left(a\right)d\left(a\right)& =& b\left(a\right)\frac{\partial}{\partial {a}_{m}}d\left(a\right)+d\left(a\right)\frac{\partial}{\partial {a}_{m}}b\left(a\right)\hfill \\ & =& (p-1){C}_{i,m}\mid {C}_{i}a-{D}_{i}{\mid}^{p-2}{\text{sign}}^{2}({C}_{i}a-{D}_{i})\hfill \end{array}$$
Note that
${\text{sign}}^{2}({C}_{i}a-{D}_{i})=1$ for all
${D}_{i}-{C}_{i}a\ne 0$ where it is not defined. Then
$${\nabla}_{j,m}^{2}f\left(a\right)=p(p-1)\sum _{i=0}^{L}{C}_{i,j}{C}_{i,m}\phantom{\rule{0.277778em}{0ex}}\mid {C}_{i}a-{D}_{i}{\mid}^{p-2}$$
except at
${D}_{i}-{C}_{i}a=0$ where it is not defined.
Based on
[link] and
[link] , one can apply Newton's method to problem
[link] as follows,
- Given
${a}_{0}\in {\mathbb{R}}^{M+1}$ ,
$D\in {\mathbb{R}}^{L+1}$ ,
$\mathbf{C}\in {\mathbb{R}}^{L+1\times M+1}$
- For
$i=0,1,...$
- Find
$\nabla f\left({a}_{i}\right)$ .
- Find
${\nabla}^{2}f\left({a}_{i}\right)$ .
- Solve
${\nabla}^{2}f\left({a}_{i}\right)s=-\nabla f\left({a}_{i}\right)$ for
$s$ .
- Let
${a}_{+}={a}_{i}+s$ .
- Check for convergence and iterate if necessary.
Note that for problem
[link] the
Jacobian of
$f\left(a\right)$ can be written as
$$\nabla f\left(a\right)=p{\mathbf{C}}^{T}y$$
where
$$y=\mid \mathbf{C}{a}_{i}-D{\mid}^{p-1}\text{sign}(\mathbf{C}{a}_{i}-D)=\mid \mathbf{C}{a}_{i}-D{\mid}^{p-2}(\mathbf{C}{a}_{i}-D)$$
Also,
$${\nabla}_{j,m}^{2}f\left(a\right)=p(p-1)\phantom{\rule{0.277778em}{0ex}}{C}_{j}^{T}\mathbf{Z}{C}_{m}$$
where
$$\mathbf{Z}=\text{diag}\left(\mid ,\mathbf{C},{a}_{i},-,D,{\mid}^{p-2}\right)$$
and
$${C}_{j}=\left[\begin{array}{c}{C}_{0,j}\\ \vdots \\ {C}_{L,j}\end{array}\right]$$
Therefore
$${\nabla}^{2}f\left(a\right)=({p}^{2}-p){\mathbf{C}}^{T}\mathbf{Z}\mathbf{C}$$
From
[link] , the
Hessian
${\nabla}^{2}f\left(a\right)$ can be expressed as
$${\nabla}^{2}f\left(a\right)=({p}^{2}-p){\mathbf{C}}^{T}{\mathbf{W}}^{T}\mathbf{W}\mathbf{C}$$
where
$$\mathbf{W}=\text{diag}\left(\mid ,\mathbf{C},{a}_{i},-,D,{\mid}^{\frac{p-2}{2}}\right)$$
The matrix
$\mathbf{C}\in {\mathbb{R}}^{(L+1)\times (M+1)}$ is given by
$$\mathbf{C}=\left[\begin{array}{ccccccc}\text{cos}M{\omega}_{0}& \text{cos}(M-1){\omega}_{0}& \cdots & \text{cos}(M-j){\omega}_{0}& \cdots & \text{cos}{\omega}_{0}& 1\\ \text{cos}M{\omega}_{1}& \text{cos}(M-1){\omega}_{1}& \cdots & \text{cos}(M-j){\omega}_{1}& \cdots & \text{cos}{\omega}_{1}& 1\\ \vdots & \vdots & \ddots & \vdots & & \vdots & \vdots \\ \text{cos}M{\omega}_{i}& \text{cos}(M-1){\omega}_{i}& \cdots & \text{cos}(M-j){\omega}_{i}& \cdots & \text{cos}{\omega}_{i}& 1\\ \vdots & \vdots & & \vdots & \ddots & \vdots & \vdots \\ \text{cos}M{\omega}_{L-1}& \text{cos}(M-1){\omega}_{L-1}& \cdots & \text{cos}(M-j){\omega}_{L-1}& \cdots & \text{cos}{\omega}_{L-1}& 1\\ \text{cos}M{\omega}_{L}& \text{cos}(M-1){\omega}_{L}& \cdots & \text{cos}(M-j){\omega}_{L}& \cdots & \text{cos}{\omega}_{L}& 1\end{array}\right]$$
The matrix
$\mathbf{H}={\nabla}^{2}f\left(a\right)$ is positive definite (for
$p>1$ ). To see this, consider
$\mathbf{H}={\mathbf{K}}^{T}\mathbf{K}$ where
$\mathbf{K}=\mathbf{W}\mathbf{C}$ . Let
$z\in {\mathbb{R}}^{M+1}$ ,
$z\ne 0$ . Then
$${z}^{T}\mathbf{H}z={z}^{T}{\mathbf{K}}^{T}\mathbf{K}z={\parallel \mathbf{K}z\parallel}_{2}^{2}>0$$
unless
$z\in N\left(\mathbf{K}\right)$ . But since
$\mathbf{W}$ is diagonal and
$\mathbf{C}$ is full column rank,
$N\left(\mathbf{K}\right)=0$ . Thus
${z}^{T}\mathbf{H}z\ge 0$ (identity only if
$z=0$ ) and so
$\mathbf{H}$ is positive definite.
Newton's method and
${l}_{p}$ Complex linear systems
Consider the problem
$$\underset{x}{\text{min}}\phantom{\rule{0.277778em}{0ex}}e\left(x\right)={\parallel \mathbf{A}x-b\parallel}_{p}^{p}$$
where
$\mathbf{A}\in {\mathbb{C}}^{m\times n}$ ,
$x\in {\mathbb{R}}^{n}$ and
$b\in {\mathbb{C}}^{m}$ . One can write
[link] in terms of the real and imaginary parts of
$\mathbf{A}$ and
$b$ ,
$$\begin{array}{ccc}\hfill e\left(x\right)& =& \sum _{i=1}^{m}{|{A}_{i}x-{b}_{i}|}^{p}\hfill \\ & =& \sum _{i=1}^{m}{|\text{Re}\{{A}_{i}x-{b}_{i}\}+jIm\{{A}_{i}x-{b}_{i}\}|}^{p}\hfill \\ & =& \sum _{i=1}^{m}{|({R}_{i}x-{\alpha}_{i})+({Z}_{i}x-{\gamma}_{i})|}^{p}\hfill \\ & =& \sum _{i=1}^{m}{\left(\sqrt{{({R}_{i}x-{\alpha}_{i})}^{2}+{({Z}_{i}x-{\gamma}_{i})}^{2}}\right)}^{p}\hfill \\ & =& \sum _{i=1}^{m}{g}_{i}{\left(x\right)}^{p/2}\hfill \end{array}$$
where
$\mathbf{A}=\mathbf{R}+j\mathbf{Z}$ and
$b=\alpha +j\gamma $ . The gradient
$\nabla e\left(x\right)$ is the vector whose
$k$ -th element is given by
$$\frac{\partial}{\partial {x}_{k}}e\left(x\right)=\frac{p}{2}\sum _{i=1}^{m}\left[\frac{\partial}{\partial {x}_{k}},{g}_{i},\left(x\right)\right]{g}_{i}{\left(x\right)}^{\frac{p-2}{2}}=\frac{p}{2}{q}_{k}\left(x\right)\widehat{g}\left(x\right)$$
where
${q}_{k}$ is the row vector whose
$i$ -th element is
$$\begin{array}{cc}\hfill {q}_{k,i}\left(x\right)=\frac{\partial}{\partial {x}_{k}}{g}_{i}\left(x\right)& =2({R}_{i}x-\alpha {\alpha}_{i}){R}_{ik}+2({Z}_{i}x-\gamma {\gamma}_{i}){Z}_{ik}\hfill \\ & =2{R}_{ik}{R}_{i}x+2{Z}_{ik}{Z}_{i}x-[2{\alpha}_{i}{R}_{ik}+2{\gamma}_{i}{Z}_{ik}]\hfill \end{array}$$
Therefore one can express the gradient of
$e\left(x\right)$ by
$\nabla e\left(x\right)=\frac{p}{2}\mathbf{Q}\widehat{g}$ , where
$\mathbf{Q}=\left[{q}_{k,i}\right]$ as above. Note that one can also write the gradient in vector form as follows
$$\nabla e\left(x\right)=p\phantom{\rule{0.277778em}{0ex}}\left[{\mathbf{R}}^{T},\text{diag},(\mathbf{R}x-\alpha ),+,{\mathbf{Z}}^{T},\text{diag},(\mathbf{Z}x-\gamma )\right]\xb7\left[{\left({(\mathbf{R}x-\alpha )}^{2},+,{(\mathbf{Z}x-\gamma )}^{2}\right)}^{\frac{p-2}{2}}\right]$$
The Hessian
$\mathbf{H}\left(x\right)$ is the matrix of second derivatives whose
$kl$ -th entry is given by
$$\begin{array}{cc}\hfill {\mathbf{H}}_{k,l}\left(x\right)& =\frac{{\partial}^{2}}{\partial {x}_{k}\partial {x}_{l}}e\left(x\right)\hfill \\ \hfill & =\frac{\partial}{\partial {x}_{l}}\frac{p}{2}\sum _{i=1}^{m}{q}_{k,i}\left(x\right){g}_{i}{\left(x\right)}^{\frac{p-2}{2}}\hfill \\ & =\frac{p}{2}\sum _{i=1}^{m}\left[{q}_{k,i},\left(x\right),\frac{\partial}{\partial {x}_{l}},{g}_{i},{\left(x\right)}^{\frac{p-2}{2}},+,{g}_{i},{\left(x\right)}^{\frac{p-2}{2}},\frac{\partial}{\partial {x}_{l}},{q}_{k,i},\left(x\right)\right]\hfill \end{array}$$
Now,
$$\begin{array}{cc}\hfill \frac{\partial}{\partial {x}_{l}}{g}_{i}{\left(x\right)}^{\frac{p-2}{p}}& =\frac{p-2}{2}\left[\frac{\partial}{\partial {x}_{l}},{g}_{i},\left(x\right)\right]{g}_{i}{\left(x\right)}^{\frac{p-4}{2}}\hfill \\ & =\frac{p-2}{2}{q}_{l,i}\left(x\right){g}_{i}{\left(x\right)}^{\frac{p-4}{2}}\hfill \\ \hfill \frac{\partial}{\partial {x}_{l}}{q}_{k,i}\left(x\right)& =2{R}_{ik}{R}_{il}+2{Z}_{ik}{Z}_{il}\hfill \end{array}$$
Substituting
[link] and
[link] into
[link] we obtain
$${\mathbf{H}}_{k,l}\left(x\right)=\frac{p(p-2)}{4}\sum _{i=1}^{m}{q}_{k,i}\left(x\right){q}_{l,i}\left(x\right){g}_{i}{\left(x\right)}^{\frac{p-4}{4}}+p\sum _{i=1}^{m}({R}_{ik}{R}_{il}+{Z}_{ik}{Z}_{il}){g}_{i}{\left(x\right)}^{\frac{p-2}{2}}$$
Note that
$\mathbf{H}\left(x\right)$ can be written in matrix form as
$$\begin{array}{cc}\hfill \mathbf{H}\left(x\right)=& \frac{p(p-2)}{4}\left(\mathbf{Q},\phantom{\rule{0.277778em}{0ex}},\text{diag},\left(g,{\left(x\right)}^{\frac{p-4}{2}}\right),{\mathbf{Q}}^{T}\right)+\hfill \\ & p\left({\mathbf{R}}^{T},\text{diag},\left(g,{\left(x\right)}^{\frac{p-2}{2}}\right),\mathbf{R},+,{\mathbf{Z}}^{T},\text{diag},\left(g,{\left(x\right)}^{\frac{p-2}{2}}\right),\mathbf{Z}\right)\hfill \end{array}$$
Therefore to solve
[link] one can use Newton's method as follows: given an initial point
${x}_{0}$ , each iteration gives a new estimate
${x}^{+}$ according to the formulas
$$\begin{array}{ccc}\mathbf{H}\left({x}^{c}\right)s& =& -\nabla e\left({x}^{c}\right)\\ {x}^{+}& =& {x}^{c}+s\end{array}$$
where
$\mathbf{H}\left({x}^{c}\right)$ and
$\nabla e\left({x}^{c}\right)$ correspond to the Hessian and gradient of
$e\left(x\right)$ as defined previously, evaluated at the current point
${x}^{c}$ . Since the
$p$ -norm is convex for
$1<p<\infty $ , problem
[link] is convex. Therefore Newton's method will converge to the global minimizer
${x}^{\u2606}$ as long as
$\mathbf{H}\left({x}^{c}\right)$ is not ill-conditioned.