Closed form solution

Question

I have the following optimization problem: $$\min_{\mathbf{G}} \|\mathbf{B(A+G)\|_F^2} \quad{} \\\text{subject to} \quad{} \mathbf{\|C^T(A+G)\|_F^2\leq \gamma \|A^T(A+G)\|_F^2 } \quad{}, \\ \mathbf{\|I-A^T(A+G)\|_F^2 \leq \alpha}$$

$\mathbf{I}$ is the identity matrix, $\mathbf{B} \in R^{P\times N}$, $\mathbf{A} \in R^{N\times M} $, $\mathbf{C} \in R^{N\times K}$ and are all known. $\mathbf{\|\cdot\|_F}$ is the frobenius norm, $\mathbf{(\cdot)^T}$ is the transpose and $\gamma, \alpha$ are constants. $\mathbf{A}$ and $\mathbf{C}$ are a subset of the size $N$ identity matrix.

Is there any closed form solution? and if not I would be grateful if you could point me to a solver that can solve this numerically. Any help is greatly appreciated.

Answer 1

I was a bit too pessimistic in my comment regarding the relaxation. If the second constraint is tight at optimality, the two models are equivalent. Solve the relaxation, and if the original constraints are satisfied, the original problem has been solved. Hence, in some cases, the problem can be solved somewhat easily as it is a convex quadratically constrained program (or more generally, a second-order cone program)

Here is a trial example implemented in the MATLAB Toolbox YALMIP (developed by me). As the data is random, I don't know how relevant the test is, but when the underlying solver (I used gurobi) finds a solution to the relaxation, the solution is correct.

p = 5;
n = 4;
m = 3;
k = 2;
alpha = 1;
gamma = 1;

B = randn(p,n);
A = randn(n,m);
C = randn(n,m);
G = sdpvar(n,m,'full');

Objective = norm(B*(A+G),'fro');

C1 = norm(eye(m)-A'*(A+G),'fro')^2 <= alpha;
bound = alpha + 2*trace((A+G)'*A)-m;
C2 = norm(C'*(A+G),'fro')^2 <= gamma*bound;

solvesdp([C1,C2],Objective)
% Display values
alpha - norm(eye(m) - A'*(A+G),'fro')^2
gamma*norm(A'*(A+G),'fro')^2 - norm(C'*(A+G),'fro')^2