How to use qld function without the error message

Specific domains Optimization
1

I have a convex polyhedral cone defined as \{Ax,x\geq 0\}. I want to determine whether a point y lies in this cone. To do so, I solve the following linear programming problem:

\begin{align*} \operatorname{Minimize}&: (x_1 + x_2 + ...+ x_n) \\ \text{Subject to}&:\\ x &\geq 0,\\ y - Ax &= 0. \end{align*}

The existence of a feasible solution in the linear programming problem is equivalent to y belongs to the convex polyhedral cone \{Ax,x\geq 0\}.
The point y = (-1, -1)^\top is not a point in the convex polyhedral cone when A = I.
Solving the Linear Programming Problem: Let’s solve the following linear programming problem:

Q=zeros(2,2);
p=[1;1];
b=-[1;1];
C=eye(2,2);
ci=[0;0];
cs=[];
me=2;
[x ,lagr ,info] = qld(Q, p, C, b, ci, cs, me )

However, it currently stops with the error message:

qld: The constraints are inconsistent.

Desired Outcome: I expect the solver to return info == 10 and I want to continue the conditional branches based on the value of info.
How can I proceed the code without the error message and stopping the execution?

2

Hello,

You are right, when 3 output arguments are provided no error should be raised, can you create an issue at Issues · scilab / scilab · GitLab ?

In the meantime, if you just need an information on feasibility, could you use karmarkar (karmarkar - Solves a linear optimization problem.) ?

p=[1;1]
b=-[1;1]
A=eye(2,2);
[xopt,fopt,exitflag]=karmarkar(A,b,p);
exitflag

--> exitflag
 exitflag  = 

  -1.

-1 means no feasible solution.

S.

3

Mr. mottelet.
I greatly appreciate your advice !
When I ran the simulation karmarkar worked fine for many parameters, but I got error messages “karmarkar: Wrong value for input argument #4. x0 does not satisfy the equality constraints.” for the following parameters.Is there a solution to avoid the error?

Aeq=[
1,1,-1,-1,0;
0,1,1,0,-1;
-1,-1,-1,-1,-1
]

beq=[
0;
1;
-1
]

f=[1,1,1,1,1]

[xopt,fopt,exitflag]=karmarkar(Aeq,beq,f)

4

To solve your feasibiity problem (until qld is fixed, likely in next version of Scilab), you can use qp_solve (not qpsolve, which cannot work in silent mode). Since qp_solve does not accept bounds you just have to reshape the x\geq 0 constraint as a general linear constraint. For example in the above case

A = [1,1,-1,-1,0;
   0,1,1,0,-1;
  -1,-1,-1,-1,-1];
y = [0;1;-1];

[m,n] = size(A);
Q = eye(n,n);
p = zeros(n,1);
C = [A;eye(n,n)]';
b = [y;zeros(n,1)];
[x,i,iter,f,info] = qp_solve(Q,p,C,b,m)

you get the minimum norm positive x and info==0:

 x  = 

   1.850D-17
   0.5000000
   0.5
   5.136D-34
  -3.772D-33
 i  = 

   2.
   8.
   1.
   7.
   3.
   0.
   0.
   0.
 iter  = 

   6.
   0.
 f  = 

   0.25
 info  = 

   0.

and for the trivial case you gave at the begining of the topic:

A = eye(2,2);
y = [-1;-1];

[m,n] = size(A);
Q = eye(n,n);
p = zeros(n,1);
C = [A;eye(n,n)]';
b = [y;zeros(n,1)];
[x,i,iter,f,info] = qp_solve(Q,p,C,b,m)

you get a warning and info==1:

qp_solve: Warning: The minimization problem has no solution. The results may be inaccurate.

 x  = 

  -1.
  -1.
 i  = 

   1.
   2.
   0.
   0.
 iter  = 

   3.
   0.
 f  = 

   1.
 info  = 

   1.
5

Dear Stephen,
I execute your suggested code.But I have error message as follows:
“karmarkar: Wrong value for input argument #4. x0 is not positive.”

6

karmarkar seems also broken (see karmarkar fails solving trivial problem (#17227) · Issues · scilab / scilab · GitLab), use qp_solve instead (see my above answer).

S.

7

Dear mottelet,
Thanks a lot to your reply.
I could run the simulation successfully. But whenever an infeasible solution is found, I receive warning messages:
“qp_solve: Warning: The minimization problem has no solution. The results may be inaccurate.”
Is there any way not to display this message?

8

You can suppress the warnings with:

warning("off")

S.

9

I think the description of the matrix C in the help file of qp_solve is incorrect. The help file suggests multiplying matrix C from the left by an n-dimensional column vector x,
x^\top C(:,j)=b(j)
but the dimensions of x and the number of rows in C (which is me+md) do not match. When I set up C as per the help file,

C = [A;eye(n,n)]’ //same as help instruction

I encountered the following error:

qp_solve: Wrong value for input argument #5: me must be an integer in the range 0 to 2.

I believe the correct formula involves multiplying x from the right.
C(:,j)x=b(j)
and right code according to this interpretation

C = [A;eye(n,n)]

However, I received a different error message.

qp_solve: Wrong value for input argument #5: me must be an integer in the range 0 to 2.

Since the number of columns in C is 2, there shouldn’t be an error, but I can’t figure out the cause.Please tell me a solution.

A =[1,1;2,1;3,2;4,1]
y = [5;2;3;2];

[m,n] = size(A);
Q = eye(n,n);
p = zeros(n,1);
C = [A;eye(n,n)]' //same as help instruction
//C = [A;eye(n,n)];  //right formula
disp("size(C)",size(C))
b = [y;zeros(n,1)];
[x,i,iter,f,info] = qp_solve(Q,p,C,b,m)
disp(info)
10

Hello,

In an optimisation problem you cannot have more equalities constraints than the dimension of the unknown, which is 2 in your case (2 non redundant equality constraints already uniquely determine the solution). That’s why qld complains.

When there are less generating vectors that the dimension of the space, testing wether a given vector is in the cone cannot be made with a linear program.

If I understand your example, the cone \mathcal{C} you are considering is a subset of \mathbb{R}^4 since y=(5,2,3,2)^\top and is generated as the positive span of vectors

a_1=(1,2,3,4)^\top,\quad a_2=(1,1,2,1)^\top.

In that case you have less generating vectors (2) than the dimension of the space (4), so testing weither y is a positive combination of these two vectors should be made first by verifying that y is actually in \operatorname{span (a_1,a_2)}. For example you can check the rank of matrix (a_1,a_2,y):

-> M = [1 2 3 4;1 1 2 1;5 2 3 2]'
 M  = 

   1.   1.   5.
   2.   1.   2.
   3.   2.   3.
   4.   1.   2.

--> rank(M)
 ans  =

   3.

here the rank is 3 so y is not a combination of a_1 and a_2, hence does not belong to the cone. If we test another vector, e.g. z=(2,3,5,5)^\top, we have

--> M = [1 2 3 4;1 1 2 1;2 3 5 5]'
 M  = 

   1.   1.   2.
   2.   1.   3.
   3.   2.   5.
   4.   1.   5.

--> rank(M)
 ans  =

   2.

hence z belongs to \operatorname{span (a_1,a_2)} and the coefficients are uniquely obtained with

--> [1 2 3 4;1 1 2 1]'\[2 3 5 5]'
 ans  =

   1.0000000
   1.0000000

S.