Home > manopt > tools > smallestinconvexhull.m

smallestinconvexhull

PURPOSE ^

Computes a minimal norm convex combination of given tangent vectors in Manopt.

SYNOPSIS ^

function [u_norm, coeffs, u] = smallestinconvexhull(M, x, U, tol)

DESCRIPTION ^

 Computes a minimal norm convex combination of given tangent vectors in Manopt.

 function [u_norm, coeffs, u] = smallestinconvexhull(M, x, U)
 function [u_norm, coeffs, u] = smallestinconvexhull(M, x, U, tol)

 M is a manifold as returned by a Manopt factory.
 x is a point on this manifold.
 U is a cell containing N tangent vectors U{1} to U{N} at x.
 tol (default: 1e-8): tolerance for solving the quadratic program.
 
 This function computes u, a tangent vector at x contained in the convex
 hull spanned by the N vectors U{i}, with minimal norm (according to the
 Riemannian metric on M). This is obtained by solving a convex quadratic
 program involving the Gram matrix of the given tangent vectors.
 The quadratic program is solved using Matlab's built-in quadprog,
 which requires the optimization toolbox. If this toolbox is not
 available, consider replacing with CVX for example.


 u_norm is the norm of the smallest vector u.
 coeffs is a vector of length N with entries in [0, 1] summing to 1.
 u is the sought vector: u = coeffs(1)*U{1} + ... + coeffs(N)*U{N}.

 Nicolas Boumal, Feb. 19, 2013
 Modified April 6, 2016 to work with Manopt.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function [u_norm, coeffs, u] = smallestinconvexhull(M, x, U, tol)
0002 % Computes a minimal norm convex combination of given tangent vectors in Manopt.
0003 %
0004 % function [u_norm, coeffs, u] = smallestinconvexhull(M, x, U)
0005 % function [u_norm, coeffs, u] = smallestinconvexhull(M, x, U, tol)
0006 %
0007 % M is a manifold as returned by a Manopt factory.
0008 % x is a point on this manifold.
0009 % U is a cell containing N tangent vectors U{1} to U{N} at x.
0010 % tol (default: 1e-8): tolerance for solving the quadratic program.
0011 %
0012 % This function computes u, a tangent vector at x contained in the convex
0013 % hull spanned by the N vectors U{i}, with minimal norm (according to the
0014 % Riemannian metric on M). This is obtained by solving a convex quadratic
0015 % program involving the Gram matrix of the given tangent vectors.
0016 % The quadratic program is solved using Matlab's built-in quadprog,
0017 % which requires the optimization toolbox. If this toolbox is not
0018 % available, consider replacing with CVX for example.
0019 %
0020 %
0021 % u_norm is the norm of the smallest vector u.
0022 % coeffs is a vector of length N with entries in [0, 1] summing to 1.
0023 % u is the sought vector: u = coeffs(1)*U{1} + ... + coeffs(N)*U{N}.
0024 %
0025 % Nicolas Boumal, Feb. 19, 2013
0026 % Modified April 6, 2016 to work with Manopt.
0027 
0028 % This file is part of Manopt: www.manopt.org.
0029 % Original author: Nicolas Boumal, June 28, 2016.
0030 % Contributors:
0031 % Change log:
0032 %
0033 %   June 28, 2016 (NB):
0034 %       Adapted for Manopt from original code by same author (Feb. 19, 2013)
0035 
0036 % Example code: pick a manifold, a point, and a collection of tangent
0037 % vectors at that point, then get the smallest vector in the convex hull
0038 % of those:
0039 %
0040 % M = spherefactory(5);
0041 % x = M.rand();
0042 % N = 3;
0043 % U = cell(N,1);
0044 % for k = 1 : N, U{k} = M.randvec(x); end
0045 % [u_norm, coeffs, u] = smallestinconvexhull(M, x, U)
0046 
0047     % We simply need to solve the following quadratic program:
0048     % minimize ||u||^2 such that u = sum_i s_i U_i, 0 <= s_i <= 1
0049     %                            and sum_i s_i = 1
0050     %
0051     % This is equivalent to solving:
0052     %  min s'*G*s s.t. 0 <= s <= 1, s'*ones = 1, with G(i, j) = <U_i, U_j> (Gram matrix)
0053     % Then our solution is s_1 U_1 + ... + s_N U_N.
0054     
0055     
0056     % Compute the Gram matrix of the given tangent vectors
0057     N = numel(U);
0058     G = grammatrix(M, x, U);
0059     
0060     % Solve the quadratic program.
0061     % If the optimization toolbox is not available, consider replacing with
0062     % CVX.
0063     
0064     if ~exist('tol', 'var') || isempty(tol)
0065         tol = 1e-8;
0066     end
0067     
0068     opts = optimset('Display', 'off', 'TolFun', tol);
0069     [s_opt, cost_opt] ...
0070           = quadprog(G, zeros(N, 1),     ...  % objective (squared norm)
0071                      [], [],             ...  % inequalities (none)
0072                      ones(1, N), 1,      ...  % equality (sum to 1)
0073                      zeros(N, 1),        ...  % lower bounds (s_i >= 0)
0074                      ones(N, 1),         ...  % upper bounds (s_i <= 1)
0075                      [],                 ...  % we do not specify an initial guess
0076                      opts);
0077 
0078     % Norm of the smallest tangent vector in the convex hull:
0079     u_norm = real(sqrt(2*cost_opt));
0080 
0081     % Keep track of optimal coefficients
0082     coeffs = s_opt;
0083     
0084     % If required, construct the vector explicitly.
0085     if nargout >= 3
0086         u = lincomb(M, x, U, coeffs);
0087     end
0088                  
0089 end

Generated on Fri 08-Sep-2017 12:43:19 by m2html © 2005