Linear least squares with quadratic equality constraint

[Srikanth Patala]

Hello Prof. Lofberg,

I have a problem where I am trying to find $x$ such $Ax = 0$ and x(1)^2 + x(2)^2 + .... x(N)^2 = N is my constraint.

The typical size of the matrix $A$ is 60000X45 and that of $x$ is 45X1.

I am not entirely sure how to go about solving this and after some amount of searching online for solutions, I found your post on math stackexchange (https://math.stackexchange.com/questions/1009403/linear-least-squares-with-quadratic-equality-constraint).

I installed YALMIP and tried to solve the example that you posted in your answer. I use the following code:

clear all; clc;

A = randn(10,5);
b = rand(10,1);
x = sdpvar(5,1);

p = (A*x-b)'*(A*x-b);
h = 1-x(1)^2-x(2)^2;

[diagnostics,xhat] = solvemoment(h == 0,p)
xhat{1}

Unfortunately, I get the following error:

############################################################

Error using svd
Input to SVD must not contain NaN or Inf.

Error in extractsolution>numranks (line 108)
    [U{i},S{i},V{i}] = svd(moment{i});

Error in extractsolution (line 23)
[U,S,V,ranks] = numranks(moment);

Error in solvemoment (line 142)
    x_extract = extractsolution(momentsstructure,options);

Error in quad1_constraint (line 10)
[diagnostics,xhat] = solvemoment(h == 0,p)

############################################################

Do you happen to know the cause of this error? If it helps, I am using MATLAB R2019a. Thank you for your help.

[Johan Löfberg]

find any x satisfying Ax==0 (just compute null-space x = Hz and then pick any random vector z) and then normalize x= x/norm(x)*sqrt(N)

Doing it by solving the huge nonconvex quadratic model would be crazy (and the question doesn't even apply since they are solving a problem with an objective while you re only looking for a point in the intersection of a plane and an sphere)

[Srikanth Patala]

Prof. Lofberg,

You are absolutely right and I had actually tried computing null-space first. The problem is that the matrix $A$ comes from experimental measurements and there are errors associated with these measurements. The result is that the null space does not exist. That is, when I compute null(A), I simply get an empty matrix.

Because of the errors in $A$, I am looking for something that minimizes the norm of $Ax$. I do not want the trivial solution of $x=0$, so I added the constraint that the norm of $x$ be equal to $N$, where $N$ is the dimension of $x$.

May be what I am looking for is an approximate null space of $A$. Would you happen to know any methods of solving this problem? Any help is greatly appreciated. Thank you.

[Johan Löfberg]

So what you want to do is minimize ||Ax||^2 = x'*A'*A*x under  ||x||^2=N? That the definition of smallest eigenvalue of A'*A and associated (scaled) eigenvector

[Srikanth Patala]

That makes complete sense. Thank you for your help.