How to minimize the Frobenius norm subject to quadratic inequality constraints?

189 Views Asked by At

I want to solve the following optimization problem. Given, two $m \times n$ matrices, $A$ and $B$,

$$\begin{array}{ll} \underset{B}{\text{minimize}} & \| A - B \|_F^2\\ \text{subject to} & \displaystyle\sum_{i=1}^{m} B_{i,j}^2 \le 1, \quad \forall j=1,2,\dots,n\end{array}$$


At first, I tried the method in this article in page 4. The author proposed an algorithm for all problems like the following

enter image description here

According to the article, I transformed it into a dual problem.And I tried to solve the dual problem(maximize the lagrange dual function $D(\lambda)$ ) to obtain the solution of the original problem.

enter image description here

The author calculated the gradient and Hessian for $\lambda$.

enter image description here

Although I didn't work out the calculation,I used the result to solve the problem. This is a constrained optimization problem.I added a quadratic penalty term and Newtown's method to solve this.


Here are my MATLAB codes:

lambda_2 refers to vector $\lambda$ and lambda_1 refers to $\Lambda$

clc;clear;
%%  An example of failure
seed=931316785;
rng(seed);
A=rand(5,4);
B=rand(5,4);
%%
col=size(A,2);
lambda_2=ones(1,col)';
lambda_1=diag(lambda_2);
H=eye(col);%initial Hessian matrix
I=eye(col);%%initial gradient
sigma=2;
g=ones(col,1);
penalty=zeros(1,col)';
for k=1:10
    for i =1:col
        penalty(i)=min(lambda_2(i),0);
    end
    inv_m=pinv(I+lambda_1);%Auxiliary operation
    m=(inv_m*A')*A*inv_m;%Auxiliary operation
    for i = 1:col
        for j = 1:col
            H(i,j)=-2*m(i,j)*inv_m(i,j);
        end
    end
    n=A*inv_m;%Auxiliary operation
    for i =1:col
        g(i)=norm(n(:,i),2)^2-1-sigma*penalty(i);
    end
    lambda_2=lambda_2-pinv(H)*g;
    lambda_1=diag(lambda_2);
    B=A*inv_m;
end

But this result doesn't not converge.I don't know what went wrong.

I would appreciate if you could help me to solve the problem. Both modifying the code or adoting an another algorithm are OK. Thank you!