Minimizing $\| x A - B\|_F^2$ With a Constraint

Question

I have previously asked an optimization question Here. I will reiterate the question and simply add a constraint to it:

I have 2 known grayscale images (256×256 matrices) $A$ and $B$ and want to find the unknown scalar variable $x$ so that:

$$\text{Minimize} \quad \|xA-B\|_F^2$$ $$\text{So That All Of The Final Image Values (256x256) Remain Between} \quad 0 \leq xA-B \leq 256 $$

The previous solution works just fine but I want to know how to optimize $x$ considering the constraint. Is this considered a Linear Programming problem?

Thanks.

Answer 1

This can be solved as a linearly-constrained linear least squares problem, for which there are many available numerical solvers, accessible from a variety of computer languages and packages. Alternatively, by not squaring the Frobenius norm, it can be solved as a Second Order Cone Problem (SOCP), again for which there are a number of solvers.

Here is how it can be formulated in CVX (under MATLAB), which will transform it to an SOCP, and call a solver to solve it.

cvx_begin
variable x
minimize(norm(x*A-B,'fro'))
subject to
0 <= x*A - B <= 256
cvx_end