Cone projection algorithm by Demetris Christopoulos

Cone projection algorithm

Also available as: PDF, LaTeX.

1Definition of the Cone Projection Problem and Algorithm

We have the data set $(x_i,\phi _i),i=1,2,\ldots ,n$ which has emerged from a convex function f at least $C^{(2)}[x_1,x_n]$ by the process:

$\phi _{i}=f(x_{i})+\epsilon _{i},\,\,\epsilon \sim iid(0,\sigma ^2\,I_n)$

We want to find the vector y that has the smallest euclidean distance from $\phi$ subject to the requirement of convexity $A\,y\geq {0}$ , thus we have to solve the next primal optimization problem:

$\begin {matrix} \text {min}\,\left \{\sum _{i=1}^{n}\,\left (y_{i}-\phi _{i}\right )^{2}=\left (y-\phi \right )^{T}\,\left (y-\phi \right )\right \}\\ \\ \text {subject to:}\,\left (-A\,y\right )\leq {0} \\ \end {matrix} \label {eq:primal1}$

There are two equivalent versions for the matrix A of the convexity inequalities constraints. The first one is is to observe that we have strict inequalities:

$x_{1}<x_{2}<\cdots <x_{n}$

so starting from the definition of convexity we proceed to the inequalities:

$\begin {matrix} {\frac {y_{{i+2}}-y_{{i+1}}}{x_{{i+2}}-x_{{i+1}}}}\geq {\frac {y_{{i+1}}-y_{{i}}}{x_{{i+1}}-x_{{i}}}} \\ \\ \left ( y_{{i+2}}-y_{{i+1}} \right ) \left ( x_{{i+1}}-x_{{i}} \right ) \geq \left ( y_{{i+1}}-y_{{i}} \right ) \left ( x_{{i+2}}-x_{{i+1}} \right ) \\ \\ \left ( x_{{i+2}}-x_{{i+1}} \right ) y_{{i}}+ \left ( x_{{i}}-x_{{i+2}} \right ) y_{{i+1}}+ \left ( x_{{i+1}}-x_{{i}} \right ) y_{{i+2}}\geq {0}\\ \end {matrix}$

By constructing now all the above inequalities for $i=1,2,\ldots ,n-2$ we have formulated the matrix $A^{(i)}$ .

$\label {eq:ai} A^{(i)}=\begin {pmatrix} x_{3}-x_{2}&x_{{1}}-x_{{3}}&x_{2}-x_{1}&0&\cdots &0 \\ 0&x_{{4}}-x_{{3}}&x_{{2}}-x_{{4}}&x_{{3}}-x_{{2}}&0&0\\ \ddots &\ddots &\ddots &\ddots &\ddots &\ddots \\ 0&0&0& x_{{n}}-x_{{n-1}} & x_{{n-2}}-x_{{n}} &x_{{n-1}}-x_{{n-2}} \\ \end {pmatrix}$

The second way is obtained if we have equal spaced $x_i$ -data. Then it is easy to eliminate the same positive quantity $\Delta {x}=x_{j+1}-x_{j}$ from all inequalities:

$\begin {matrix} \left ( x_{{i+2}}-x_{{i+1}} \right ) y_{{i}}+ \left ( x_{{i}}-x_{{i+2}} \right ) y_{{i+1}}+ \left ( x_{{i+1}}-x_{{i}} \right ) y_{{i+2}}\geq {0} \\ \\ \left ( \Delta {x}\right )y_{{i}}-\left ( 2\Delta {x}\right ) y_{{i+1}}+\left ( \Delta {x}\right )y_{{i+2}}\geq {0} \\ \\ y_{{i}}-2 y_{{i+1}}+ y_{{i+2}}\geq {0} \\ \end {matrix}$

again with $i=1,2,\ldots ,n-2$ and create the matrix $A^{(ii)}$ .

$\label {eq:aii} A^{(ii)}=\begin {pmatrix} 1&-2&1&0&\cdots &0 \\ 0&1&-2&1&\cdots &0\\ \ddots &\ddots &\ddots &\ddots &\ddots &\ddots \\ 0&0&\cdots &1&-2&1 \end {pmatrix}$

Every algorithm that solves the Cone Projection Problem is called a Cone Projection Algorithm.

Alternative definitions:

by Demetris Christopoulos

Add my definition

Ontology information: