Using ceil of an optimization variable

MIDCP
1

Hello, how is it possible to use ceil of an optimization variable in constraints in CVX?

2

You will need to use MIDCP capability. Do something along the lines of answers in https://or.stackexchange.com/questions/443/modeling-floor-function-exactly .

3

I want to write these constraints in CVX format, is it possible?

0<=p<=1
x = ceil (p)
w = find(x==1) %finding the index of nonzeros in p
inv_pos(...) <= min(d(w))

p is variable and d is constant.

4

You can do whatever you want (subject to MATLAB’s rules), with MATLAB variables. That is not the case for CVX variables or expressions.

You will have to introduce binary or integer (CVX) variables to do what you want. It can be cumbersome.

ceil is not supported by CVX, hence my previous post in this thread. Use of find on a CVX variable is unlikely to do what you want.

help cvx/find

 Disciplined convex/geometric programming information for find:
    When used in CVX models, find cannot deduce the numeric value of a
    CVX variable. So it returns the indices of elements that are 
    "structurally" nonzero; i.e., that are not *identically* zero.
    This is similar to the concept of structural nonzeros in sparse
    matrix factorizations. To illustrate the distinction, consider:
       variable x(3);
       x(2) == 0;
       y = [x(1);0;x(3)];
    In this case, find(x) returns [1;2;3] even though x(2) has been set
    to zero in an equality constraint. (After all, the overall model may
    be infeasible, in which case x(2) is arguably not zero.) However,
    find(y) will return [1;3], because y(2) is identically zero.
 
    When X is a CVX variable, the first two outputs of [I,J,V]=find(X) 
    are constant, and the third is a CVX variable containing the 
    structural nonzeros of X.
 
    find(X) places no convexity restrictions on its argument.
5

You may find it easier to use YALMIP, which provides automated logic capabilities absent from CVX. For instance, YALMIP support overloaded nnz.

Keep in mind that you will have to address the tolerance for what counts as non-zero. That is the trickiest part of ceil, number of non-zeros, etc.

6 
inv_pos(...) <= min(d(w))

This is one of my constraints. When I can’t use find inside CVX specification, it seems that I am not able to do what I want.
I couldn’t implement the ways on the link you wrote for ceil, but I used another way which answers correctly. However, using find inside CVX constraints results in errors.
Thanks for introducing YALIMP. I hope I can do my objective functions in CVX because unfortunately, I don’t have much time to learn a new toolbox, but I would use them for my next projects surely.

7

You ought to be able to adapt what is in https://www.cs.upc.edu/~erodri/webpage/cps/theory/lp/milp/slides.pdf . Introduce another vector variable,y, and constrain its element equal to a just large enough number (to be out of contention to “win” the min), for indices corresponding to (close enough to) zero x elements, and constrain to the corresponding element of d for non- (close enough to) zero x elments. Then use min(y) There might be a better way, but this should work. I leave the details to you…

8

Your solution is nice, but the problem is I don’t know how to distinguish the indices corresponding to (close enough to) zero x elements.
I mean considering I did this two constraint without any problem
0<=p<=1
x = ceil §
my problem is finding the indices of nonzeros or zeros.

9

Apply the logic within a for loop

for i = 1:n
x(i) >= small_number --> y(i) == d(i) else y(i) == U
end
where U is a chosen number > max(d)

I’ll leave you to worry about how to deal with the situation in which all elements of x “=” 0.

10

It seems that you used if/else logic here, but I cannot understand the implementation of your logic:
My code is:

cvx_begin
    variable p(n)
    variable b(n) binary
    variable y(n)
    minimize ...
    subject to
        0 <= p <=1
        p <= b <= p + (1-(1e-6))
        y <= 1e6 %large number
        for i = 1:n
            b(i) >= .5
            y(i) == d(i)
        end
         inv_pos(...)<= min(y);
cvx_end

I don’t whether this is what you mean or not, but this doesn’t work.

11

I meant for you to implement if else logic as per the link I provided.