Underdetermined inequality constraint detected?

1

I am trying to implement your Consensus-based DSVM algorithm
(Algorithm 1 MoM-DSVM) in MATLAB, and use CVX toolbox…
this is a part of my matlab:

maximize ( -1/2*x_var’*lokMAT{j}*x_var + (ones(Nj,1) +
lokMAT1{j}*EF{j})'*x_var )

where:
-lokMAT1{j} = YE{j}*EX{j}/U{j};
-lokMAT{j}= lokMAT1{j}*EX{j}'*YE{j};

when I run, I found this warning:

Warning: Underdetermined inequality constraints detected.
CVX cannot solve this problem; but it is likely unbounded.

In cvxprob.solve at 83

What happen with this statement? How can I solved this problem?
Do you some suggestion to correct this problem… and suggestion to
implement your algorithm 1 MoM-DSVM?

Hope and waiting for your reply for answer,

2

You haven’t offered enough of your model to offer any sort of assistance, I’m afraid. Please edit your question and include the entire model. And take note of these instructions for including code in your posts so that it’s readable. Thanks!

3

This is my code…

**% make adjacency matrix**
nodeWSN = randi([0 1],10);
for i=1:10
	for j=1:10
    	if (i==j) nodeWSN(i,j)=0; end
	end
end
**% get the number of nodes**
[MAX_NODE COL] = size(nodeWSN);
**% get neighborhood index of node k**
for k = 1:MAX_NODE
	idxAdj{k} = find(nodeWSN(k,:),MAX_NODE);
end
J = MAX_NODE;
QUIET    = 0;
MAX_ITER = 1000;
eta = 10;
**% generate the training set with label/class**
n = 2; Nj = 10; N = Nj/2; M = Nj/2;
for j=1:MAX_NODE
	*% positive examples -- array*
	Y = [randn(1,N); randn(1,M)];
	`% negative examples -- array` 
	X = [randn(1,N); randn(1,M)];
	x = [X Y]; 
	y = [ones(1,N) -ones(1,M)];
	tmp = [ -((ones(n,1)*y).*x)' -y']; 
	A{j} = tmp;
end
% t = 0;
piMAT = [0 0 0; 0 0 0; 0 0 1];
lambda ={};
**% initialize**
for j = 1:MAX_NODE,
	YE{j} = diag(A{j}(:,3));
	EX{j} = [A{j}(:,1:2),ones(Nj,1)];
	U{j} = (1+2*eta*sum(nodeWSN(j,:))).*eye(n+1) - piMAT;
	VE{j} = randn(n+1,1);
	alpha{j} = randn(n+1,1);
end
**% ===== START ===**
*% t+1*
for t = 1:MAX_ITER
	*%== STEP #1: hitung fj(t)*
	for j=1:MAX_NODE
		[p q] = size(idxAdj{j});
		sumVE{j}(:,1) = zeros(n+1,1); % n = p+1
		for i=1:q
			sumVE{j}(:,1) = sumVE{j}(:,1) + (VE{j}(:,1) + VE{idxAdj{j}(1,i)}(:,1)); 
		end
		EF{j}(:,1) = 2.*alpha{j}(:,1) - eta.*sumVE{j}(:,1);  
	end
	for j=1:MAX_NODE
		% ===== COMPUTE EQ 1  / COMPUTE lambda_j(t+1)
		cvx_begin quiet
			variable x_var(Nj)
			maximize ( (-1/2)*x_var'*YE{j}*EX{j}/U{j}*EX{j}'*YE{j}*x_var + (ones(Nj,1) + YE{j}*EX{j}/U{j}*EF{j})'*x_var )
		cvx_end
		lambda{j}(:,1) = x_var;
	end
end
4

I’ll let mcg answer, so this is just a comment.

You haven’t defined eta in the code above.

Please begin all comment lines with %, so that your code can be directly copied and pasted into a MATLAB session.

Also, if you are having difficulties with CVX, don’t invoke it using the quiet option.

5

This is interesting, but I am stumped. This is just an unconstrained quadratic form. Why are you solving it with CVX? It should be solvable with just a linear system solve.

6

Thank you Mark.
Ups… eta is missing :smile:

7

Hi Michael,
thank you for interested on this model.
I am implementing consensus-based distributed svm from Forero’s paper in http://www.jmlr.org/papers/volume11/forero10a/forero10a.pdf (eq 16)
But may be I am wrong how to implement in CVX :frowning:

8

I’m afraid I can’t help people build models out of papers. I limit my assistance here to CVX usage issues. What I think is occurring is that the model that you have constructed is an unconstrained quadratic with a rank deficient Hessian. It is trivial to find with linear systems techniques.

1 Like
9

@ Mark:
Sorry since I wasns’t allowed to post more than three replies to the other forum (being a new user), I am writing a reply to your questions here:

Yes,
Precision_matrix = inverse(Covariance_matrix)

Actually,
- (lambdanorm(L,1) -lambda(1/variance)*N) is a part of maximize{},
the paranthesis was missing

CVX optimization variable here is L (Laplacian matrix)

In the code
X = precision matrix
||X||_1 = 1-norm of X ,defined as:
||X||_1 = (norm(L,1) + (1/variance)*N) %% relation between L matrix to be
%% determined and precision matrix.

10

The above is the continuation of the thread at How an underdetermined system of linear equations are solved by CVX? - #7 by Mark_L_Stone .

Perhaps you can show a complete MATLAB/CVX code, which makes sense, and which includes all input data (use small matrices, such as 3 by 3 or 4 by 4).

The first thing you need to do is to understand the optimization problem you are solving, and given the input data, why it is a convex optimization problem.

General advice:

11

Precision to adjacency_1
Precision to adjacency_1826×691 108 KB

Hope this snippet clears things up further.

eqn 7 is to be solved for L .

The other eqn involving ‘norm_1_of_theta’ is the required relation between l and theta.
theta = precision matrix.

12

No, that is not clear to me. But you are the one who wishes to solve it, so you should put in the effort to understand the paper, and exactly what convex optimization problem you are solving. And if there is no convex optimization problem resulting, then CVX can’t be used to solve it.