Need help in coding convex optimization problem

1

Hi everyone,

I am new to CVX, and am trying to use it to solve a convex optimization problem. The problem can be written in the following manner:

minimize sum1( W(i,j) * |A(i,j)| )
subject to
N = A*X + U
sum2(N(:,j)’ * R(:,:,j) * N(:,j)) <= constant

Where sum1 is from i=1:n and j=1:n.
sum2 is from j=1:n
W and A are n x n matrices
N, X and U are n x m

When I write code for this, I get the following error:

sqlp stop: dual problem is suspected of being infeasible
Status: Infeasible
Optimal value (cvx_optval): +Inf

I know for sure that the above mentioned problem is convex. Any help would be appreciated!

2

The fact that the solver even began to work suggests that CVX agrees your problem is convex. (It would not have even begun if it did not). What it is saying is that the problem is infeasible: that there are no points that satisfy all the constraints.

If you are certain that the problem is feasible, then you’ve entered it into CVX incorrectly. However, you haven’t offered any source code, so there’s no way anyone can help you. Do look at this post to see how to format source code you include in your post.

3

Thanks Michael, I am having a look at the link you provided. Meanwhile, here is the code that I wrote:

function [A, W, obj] = algo3(X, U, S, delta, Rprime, Ebs, Beta)

    n = size(X,1);
    m = size(X,2);
    A = zeros(n,n);
    W = ones(n,n);
    
    for t = 1:500
        cvx_begin
            variable eta(n,m)
            expression constr;
            for k = 1 : m
                constr = constr + eta(:,k)'*Rprime(:,:,k)*eta(:,k);
            end
            obj = 0;
            for i=1:n
                for j=1:n
                    obj = obj + W(i,j)*abs(A(i,j));
                end
            end
            minimize obj;
            subject to
                eta == A*X + U
                for i = 1:n
                    for j = 1:m
                        if (isnan(S(i,j)) == 0)
                            if S(i,j) ~= 0
                                A(i,j) * S(i,j) >= delta;
                            else
                                -delta/2 <= A(i,j) <= delta/2
                            end
                        end
                    end
                end
                constr <= Beta*Ebs;
        cvx_end
        W = update(W,A);
    end

end
4

There is an extra set of constraints that I have added in the “subject to” block. These constrained are captured in the 2 nested for loops.

5

I see nothing obviously wrong with how you’ve entered the model, so my only conclusion is that it is indeed infeasible. You can try other solvers to see if they agree.

6

By the way, this

        obj = 0;
        for i=1:n
            for j=1:n
                obj = obj + W(i,j)*abs(A(i,j));
            end
        end

can just be replaced with this:

obj = sum(sum(W.*abs(A)));

You do indeed need two sum statements, because the inner one just sums up the columns.

7

Wait, the only variable you have declared is eta. Everything else is a constant? Your entire objective function is made up of constants?

8

Now that you mentioned it, I am trying to understand the problem with my code. So I want my objective function to solve for A iteratively (for a fixed number of iterations, lets say 500 times). I multiply absolute value of A(i,j) with W(i,j), and update W after each iteration of CVX solving the optimization problem. Should I be declaring A as a CVX variable? If yes, then can I initialize all elements of the CVX variable A to be zero before the first iteration even begins?

9

Every optimization variable must be declared as a variable in CVX, no exceptions. CVX does not consider initial values, so initializing A to be zero at the beginning does absolutely nothing. The value of A is determined entirely by the solution of the convex optimization problem.

I would suggest you go through the user’s guide and browse the examples so you can get a proper idea of how to use CVX.

10

You are absolutely right, the value of A is determined by the solution. I declared A as an n x n variable (but not W). But the problem still seems to be infeasible. I guess I should read more CVX examples to get a better understanding.

Thanks a lot for your help!