Finding minimum non-zero element in yalmip

[Per Dahlgaard Pedersen]

Hi

I am a great fan of YALMIP when formulating optimization problems in Matlab.

I have a vector x, 1x4 of sdpvar, using Yalmip, no negative values. 

I want to find the minimum non-zero element. 

My immediate attempt was min(x(x>0)). 

However conditional indexing is not supported inside sdpvar. 

Any help will be appreciated.

[Johan Löfberg]

The index of the minimum element is a horrible combinatorial object. 

The index is not available in the overloaded min operator (could be an easily added future feature). The only way to do this now is to use the sort operator, and pick out the first element. Note though, you will introduce loads of binary variables (16 in this case)

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.Sort

[Johan Löfberg]

Aha, minimum non-zero element, read it wrong.

Might require some other approach. But as I said, you will have to rely on some big-M (MILP) represented operator

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Category.Mixed-integerBasedNonlinearOperators

[Johan Löfberg]

A brute-force model is something along these lines

n = 10;

A = sprandn(2*n,n,.2);

b = randn(2*n,1);

x = sdpvar(n,1);

% Solve some model which typically generates many zeros

optimize([x>=0],norm(A*x-b,1))

value(x)

% BigM constant and zero-margin

M = 10;zeromargin = 0.0005;

% Find all non-zeros

nz = binvar(n,1);

Model = [0 <= x <= M, iff(x >= zeromargin, nz)]

% Find min among those 

minnonzero = sdpvar(1);

posofmin = binvar(n,1);

Model = [Model, x-M*(1-posofmin)-M*(1-nz) <= minnonzero  <= x+M*(1-nz), sum(posofmin)==1, posofmin <= nz]

% Penalize smallest non-zero

optimize([x>=0,Model],norm(A*x-b,1)+1*minnonzero)

value(x)

[Johan Löfberg]

Here is another horrible model, which uses variable indexing

Model = [0 <= x <= M, iff(x >= zeromargin, nz)]

expandedx = [M;x];

optimize(Model,norm(A*x-b,1)+1*min(expandedx(1 + nz.*(1:n)')))

(last example here http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.LogicProgramming)

[Per Dahlgaard Pedersen]

Hi Johan

Thanks for your very quick and detalied support.

I am inspired by all your proposals.

I think min(x(nnz(x))) is working also, if x is sorted.

Regards Per

[Johan Löfberg]

Indeed. And if x isn't sorted, you can do

z = sort(x);
y = min(z(nnz(x)))

Note though, using these complex operators individually will introduce a lot more binary variables than what one would have if a big-M model was developed from scratch