Analytical solution to linear regression with constraints

Question

Consider the following minimization problem:

$||AC-S||_F \rightarrow \min$,

where $A$, $C$ and $S$ are real-valued matrices, $C$ is the unknown, and $||\cdot||_F$ is the Frobenius norm, subject to the following two constraints.

For all $i,j$

1. $\left|C_{ij}\right| \le 1$ and
2. $\left|C_{ij}-[C_{ij}]\right| \rightarrow \min$,

where $[]$ denotes the rounding to the closest integer.

While criterion 1 is a must, I'm more relaxed about criterion 2.

To best of my knowledge Tikhonov regularization would provide analytical solution if only criterion 1. was in place. Do I have any numerical/mathematical options to satisfy both criteria?

Answer 1

This can be formulated and solved as a Mixed Integer Quadratic Programming Problem (MIQP) by using Frobenius norm squared. Or it can be solved as a Mixed Integer Second Order Cone Problem (MISOCP) by making the objective function minimize t, and adding the constraint $\|AC-S\|_F \le t$

For example, if you have CVX Professional (Academic) with Gurobi or MOSEK solvers, you can formulate and solve the problem as follows.

cvx_begin
variable C(m,n) integer
minimize(norm(A*C-S,'fro'))
-1 <= C <= 1
cvx_end