Projection on Polyhedral Cone

From Wikimization

(Difference between revisions)
Jump to: navigation, search
m (Projection onto isotone projection cones)
Line 16: Line 16:
Together with my coauthor A. B. Németh we recently discovered a very simple algorithm for projecting onto a special class of cones, the isotone projection cones.
Together with my coauthor A. B. Németh we recently discovered a very simple algorithm for projecting onto a special class of cones, the isotone projection cones.
-
The '''isotone projection cones''' are cones for which the projection onto the cone is isotone; that is, monotone with respect to the order induced by the cone. In <math>\mathbb R^n</math> the isotone projection cones are polyhedral cones generated by <math>n</math> linearly independent vectors (i.e., cones which define a lattice structure, or shortly latticial cones) such that the generators of the polar of the cone form pairwise nonacute angles. For example the nonnegative monotone cone (Example 2.13.9.4.2 in [http://meboo.convexoptimization.com/Meboo.html http://meboo.convexoptimization.com/Meboo.html]) is an isotone projection cone. The isotone projection cones were introduced by George Isac and A. B. Németh at the middle of 1980's and used for solving complementarity problems by George Isac, A. B. Németh and S. Z. Németh. For simplicity we shall call a matrix <math>\mathbf E</math> whose columns are the generators of an isotone projection cone '''isotone projection matrix'''. Recall that an L-matrix is a matrix whose diagonal entries are positive and off-diagonal entries are nonpositive. A matrix <math>\mathbf E</math> is an isotone projection matrix if and only if it is of the form
+
The '''isotone projection cones''' are cones for which the projection onto the cone is isotone; that is, monotone with respect to the order induced by the cone. In <math>\mathbb R^n</math> the isotone projection cones are polyhedral cones generated by <math>n</math> linearly independent vectors (i.e., cones which define a lattice structure, or shortly latticial cones) such that the generators of the polar of the cone form pairwise nonacute angles. For example the nonnegative monotone cone (Example 2.13.9.4.2 in [http://meboo.convexoptimization.com/Meboo.html http://meboo.convexoptimization.com/Meboo.html]) is an isotone projection cone. The isotone projection cones were introduced by George Isac and A. B. Németh at the middle of 1980's and used for solving complementarity problems by George Isac, A. B. Németh and S. Z. Németh. For simplicity we shall call a matrix <math>\mathbf E</math> whose columns are the generators of an isotone projection cone '''isotone projection matrix'''. Recall that an L-matrix is a matrix whose diagonal entries are positive and off-diagonal entries are nonpositive
 +
(see more at [http://en.wikipedia.org/wiki/Z-matrix_(mathematics) http://en.wikipedia.org/wiki/Z-matrix_(mathematics)]). A matrix <math>\mathbf E</math> is an isotone projection matrix if and only if it is of the form
<center>
<center>
<math>\mathbf E=\mathbf O\mathbf T^{-\frac12},</math>
<math>\mathbf E=\mathbf O\mathbf T^{-\frac12},</math>

Revision as of 04:08, 4 June 2009

This is an open problem in Convex Optimization. At first glance, it seems rather simple; the problem is certainly easily understood:

We simply want a formula for projecting a given point in Euclidean space on a cone described by the intersection of an arbitrary number of halfspaces;
we want the closest point in the polyhedral cone.

By "formula" I mean a closed form; an equation or set of equations (not a program, algorithm, or optimization).
A set of formulae, the choice of which is conditional, is OK as long as size of the set is not factorial (prohibitively large).

This problem has many practical and theoretical applications. Its solution is certainly worth a Ph.D. thesis in any Math or Engineering Department.

You are welcome and encouraged to write your thoughts about this problem here.


Projection onto isotone projection cones

Together with my coauthor A. B. Németh we recently discovered a very simple algorithm for projecting onto a special class of cones, the isotone projection cones.

The isotone projection cones are cones for which the projection onto the cone is isotone; that is, monotone with respect to the order induced by the cone. In LaTeX: \mathbb R^n the isotone projection cones are polyhedral cones generated by LaTeX: n linearly independent vectors (i.e., cones which define a lattice structure, or shortly latticial cones) such that the generators of the polar of the cone form pairwise nonacute angles. For example the nonnegative monotone cone (Example 2.13.9.4.2 in http://meboo.convexoptimization.com/Meboo.html) is an isotone projection cone. The isotone projection cones were introduced by George Isac and A. B. Németh at the middle of 1980's and used for solving complementarity problems by George Isac, A. B. Németh and S. Z. Németh. For simplicity we shall call a matrix LaTeX: \mathbf E whose columns are the generators of an isotone projection cone isotone projection matrix. Recall that an L-matrix is a matrix whose diagonal entries are positive and off-diagonal entries are nonpositive (see more at http://en.wikipedia.org/wiki/Z-matrix_(mathematics)). A matrix LaTeX: \mathbf E is an isotone projection matrix if and only if it is of the form

LaTeX: \mathbf E=\mathbf O\mathbf T^{-\frac12},

where LaTeX: \mathbf O is an orthogonal matrix and LaTeX: \mathbf T is a positive definite L-matrix.

The algorithm is a finite one that stops in at most LaTeX: n steps and finds the exact projection point. Suppose that we want to project onto a latticial cone and for each point we know a proper face of the cone onto which the point projects. Then, we could find the projection recursively, by projecting onto linear subspaces of decreasing dimensions. In case of isotone projection cones the isotonicity property provides us with the required information about such a proper face. The information is provided by the geometrical structure of the polar cone.

If a polyhedral cone can be written as a union of reasonably small number of isotone projection cones, then we could project a point onto the polyhedral cone by projecting onto the isotone projection cones and taking the minimum distance of the point from these cones. Due to the simplicity of the method of projecting onto an isotone projection cone, it is a challenging open question to find polyhedral cones which are a union of reasonably small number of isotone projection cones and for which the latter cones can be easily determined. We conjecture that the latticial cones which are subsets of the nonnegative orthant (and their isometric images) are such cones.

Scilab script of the algorithm:

// You are free to use, redistribute and modifiy this code if you include
// as a comment the author of the original code 
// (c) Sandor Zoltan Nemeth, 2009.
function p=piso(x,E)
   [n,n]=size(E)
   if det(E)==0 then 
      error ('The input cone must be an isotone projection cone'); return
   else
   V=inv(E) 
   U=-V'
   F=-V*U
   G=F-diag(diag(F))
      for i=1:n
         for j=1:n
            if G(i,j)>0 then
               error('The input cone must be an isotone projection cone'); return
            end
         end
      end
      I=[1:n]
      n1=n-1
      cont=1
      for k=0:n1
        //disp(cont,"cont=")
        [q1,l]=size(I)
	     E1=E
	     I1=I
	     if l-1>=1
	       highest=I(l)
	       if highest<n
	          for h=n:-1:highest+1
		    E1(:,h)=zeros(n,1)
	          end 
	       end
               for j=l-1:-1:1 
                  low=I(j)+1
                  high=I(j+1)-1
                  if high>=low
                     for m=high:-1:low
                     E1(:,m)=zeros(n,1)

                  end
               end
	       lowest=I(1)
	       if lowest>1
	          for w=lowest-1:-1:1
	             E1(:,w)=zeros(n,1)
 	          end
	       end
             end
       end
       if l==1 
	E1=zeros(n,n)
	E1(:,I(1))=E(:,I(1))
       end
     
         V1=pinv(E1)
         U1=-V1'
       //disp(x,"start x=")
       //disp(I,"I=")
   
	  //disp(U1,"U1=")
         //disp(V1,"V1=")
         for j=l:-1:1
          zz=x'*U1(:,I(j))
	  if zz>0 I1(j)=[]
            end       
         end
       //disp(I1,"I1=")
         [q2,ll]=size(I1)
            if cont==0 then p=x; return
            elseif ll==0 then p=zeros(n,1); return 
            else 
         //disp(E1,"E1=")
         //disp(V1,"V1=")
               A=E1*V1
         //disp(A,"A=")
               x=A*x
               //disp(x,"x=")
               p=x;
            end
            if ll==l cont=0
            else cont=1
            end 
         I=I1
      end
   end
endfunction

Can also be downloaded from here:

LaTeX: -Sándor Zoltán Németh


external links

More about projection on cones (and convex sets, more generally) can be found here (chapter E):

http://meboo.convexoptimization.com/Meboo.html

More about polyhedral cones can be found in chapter 2.

Personal tools