5
$\begingroup$

Supposing I have complex square matrices $B_i$ and $C_i$ ($i = 1,\dots,N$) of dimension $4 \times 4$.

  1. Is there an effective algorithm for solving the following problem?

$$\begin{align} A=&\underset{A\in\mathbb{C}^{4\times 4}}{\text{argmin}}\sum_{i=1}^{N}{\left\|AB_iA^{-1}-C_i\right\|}\\ \,\\ &\text{subject to }\left\{\begin{matrix}A_{12}=A_{13}=A_{42}=A_{43}=0\\A_{11}+A_{41}=1\\ A_{14}+A_{44}=1\end{matrix}\right. \end{align} $$ Here $\left\|\cdot\right\|$ is a matrix norm. I currently use $\left\|M\right\| = \sigma_{max}(M)$ where $\sigma_{max}(M)$ is the largest singular value of $M$. But if the other choice of the norm could simplify the problem that would be also very helpful.

  1. How can I make sure that there exists only one unique solution for $A$?

Update

I am pretty sure that the solution exists for the invertible $A$. Matrices $B_i$ and $C_i$ are pretty close for all $i$ (I have $N=15$) so I expect the solution to be somewhere nearby $A=I$.

Generally my case looks like follows. I know that there exists such $C_i^t$ that make objective function equal to zero. In this case I can transform the problem to a convex one by minimizing $\sum\left\|AB_i-C_iA\right\|$. This works just perfectly when I use CVX toolbox for MATLAB. However, I don't know the exact $C_i^t$ but have some rough estimations $C_i$.

The best results that I had so far were achieved with the help of genetic optimization algorithm. But the problems that:

  • It takes a lot of time to find a minimum. The task looks simple at the first glance so I thought there could be a special solver for this.
  • Every time I have a slightly different solution and I still can't understand why: because there are many local minimums nearby the global one or because the global minimum is degenerate. So the question (2) is also crucial for me as I am able to reduce or increase $N$.
$\endgroup$
13
  • 2
    $\begingroup$ There is never one unique solution for $A$: If some matrix $A$ minimizes the function, then for any non-zero real scalar $\alpha$ the matrix $\alpha A$ gives the same value of the function. Consider asking whether the solution is unique up to re-scaling. $\endgroup$ Apr 29, 2019 at 18:12
  • $\begingroup$ @MarkFischler Thank you, I've edited the post to make the problem more clear $\endgroup$
    – Krivoi
    Apr 29, 2019 at 18:28
  • 1
    $\begingroup$ Are you even sure that the minimum is attained? I mean, in the unrestricted problem (any non-degenerate A allowed) you cannot diagonalize $B=\begin{bmatrix}1 & 1\\0&1\end{bmatrix}$ to the identity matrix exactly but you can come arbitrarily close. $\endgroup$
    – fedja
    Apr 29, 2019 at 23:36
  • 1
    $\begingroup$ Since you have some freedom on the objective function, can you also change it to $\sum \|AB_iA^{-1}-C_i\|_F^2$, with squares and the Frobenius norm, which looks like it's a simpler problem? $\endgroup$ Apr 30, 2019 at 7:00
  • 2
    $\begingroup$ @Krivoj: $\sum\|AB_i-C_iA\|_F^2$ is a quadratic polynomial in the entries of $A$ and the quadratic optimization problem is much simpler; I would say "trivial" if I were sure that the matrix of the associated quadratic form is invertible. Also, that $B_i$ and $C_i$ are close does not yet guarantee that the solution exists, much less that it is close to $I$: just replace the top right $1$ by $\varepsilon$ in my example. Nothing will change. $\endgroup$
    – fedja
    Apr 30, 2019 at 11:19

1 Answer 1

1
$\begingroup$

Regardless of the norm, this is a non-convex optimization problem, having non-convex objective function and linear constraints. This can be formulated and numerically solved to local or global minimum by a variety of off-the shelf numerical optimization solvers.

The one-norm (1 in MATLAB norm), infinity-norm (Inf in MATLAB norm), and Frobenius norm ('fro' in MATLAB norm) are more readily handled than the operator 2-norm, i.e., largest singular value (2 in MATLAB norm).

Here are formulations using YALMIP under MATLAB. The numerical difficulty (run time) to solve these depends on the input data. Local minimization should be fast; gloval minimization may take a while. You will have to decide what constitutes "effective".

B = rand(4,4) + 1i*rand(4,4); C = rand(4,4) + 1i*rand(4,4); % random test data
A = sdpvar(4,4,'full','complex'); % declare A as a (not necessarily hermitian) 4 by 4 complex matrix variable
invA = sdpvar(4,4,'full','complex'); % declare invA as a (not necessarily hermitian) 4 by 4 complex matrix variable
Constraints = [-100 <= A(:) <= 100,-100 <= invA(:) <= 100]; % somewhat arbitrarily constrained elements of A and invA to keep things bounded
Constraints = [Constraints,A*invA == eye(4)]; % add constraint to force invA to be inv(A)
Constraints = [Constraints,A(1,2)==0,A(1,3)==0,A(4,2)==0,A(4,3)==0,A(1,1)+A(4,1)==1,A(1,4)+A(4,4)==1]; % add the other constraints
Objective = norm(A*B*invA - C,'fro'); % objective function using Frobenius norm
optimize(Constraints,Objective,sdpsettings('solver','baron')) % solve to global optimality using BARON global optimizer

Alternatively, change solver to BMIBNB global optimizer using knitro or fmincon as local solver, and Objective may be changed to use 1 or Inf norm.

optimize(Constraints,Objective,sdpsettings('solver','bmibnb','bmibnb.uppersolver','knitro'))
optimize(Constraints,Objective,sdpsettings('solver','bmibnb','bmibnb.uppersolver','fmincon'))

Or KNITRO or FMINCON as local solver for local minimum for 1, Inf, or 'fro' norm.

optimize(Constraints,Objective,sdpsettings('solver','knitro')) 
optimize(Constraints,Objective,sdpsettings('solver','fmincon')) 

To use operator 2-norm (or 1, 'fro', or Inf), use PENLAB or PENBMI as local solver, possibly in conjunction with BMIBNB as global solver as

optimize(Constraints,Objective,sdpsettings('solver','penlab')) 
optimize(Constraints,Objective,sdpsettings('solver','penbmi')) 
optimize(Constraints,Objective,sdpsettings('solver','bmibnb','bmibnb.uppersolver','penlab'))
optimize(Constraints,Objective,sdpsettings('solver','bmibnb','bmibnb.uppersolver','penbmi'))

The lower and upper bound constraints on elements of A and invA may not be necessary for the local optimizers, but are needed for the global optimizers BARON and BMIBNB.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.