Minimizing norm( a_i x - ( y B_i + c_i ) ) with constraint

Hi all,

Given the signal vectors B_i and c_i, I have obtained a new signal vector a_i to find out vector y. Then to fine tune, I introduced a scalar x.

Now, I need to minimize the problem which is defined as follows:

norm( a_i x - ( y B_i + c_i ) ) s.t. norm(y_n)<=1. 

In matlab, how to solve this?

Variables here are x and y.

Further, 'a_i' is a vector of order (1 \times N),

x is a scalar (tuning parameter) ,

y is a vector of order (1 \times N), y_n is a term in vector y,

B_i is a matrice of (N \times N),

c_i is a vector of (1 \times N).

Answer 1

[Bruno Luong]

So you want more or less

Minimize | A*z - b |^2 with the constraint | z | <= 1.
where |.| designates the l2 norm.

I believe in your problem

    A := B.' % known
    z := y.' % unknown
    b := (a*x - c).' % known

To do that, first you do

    z = pinv(A)*b % if A is full rank it's z = A\b

Check if |z| <= 1, if yes you are done.

If not then solve the following problem this equality constraint

    Minimize | A*z - b |^2 with the constraint | z | = 1.

by using for example this function in File-exchange

    z = spherelsq(A,b,1);

Then get back

    y = z.'

Put all that together

A = B.';
b = (a*x - c).';
    
z = pinv(A)*b;
if norm(z,2) > 1
    z = spherelsq(A,b,1);
end
y = z.';

[Syam MS]

Function spherelsq(A,b,1) have the constraint |x| = c. Here norm of vector X is taken, my constraint instead is for the each element in the vector X.

Answer 2

[Bruno Luong]

If you have optimization toolbox you can do (see my other answer for definition of A, b and z)

z= fmincon(@(z) norm(A*z-b,2).^2, A\b, [], [], [], [], [], [], @norm1con)
% where this is the constraint
function [c, ceq] = norm1con(z)
c = sum(z.^2,1) - 1;
ceq = [];
end

I can check both of my methods give the same results

% test.m script
N = 10;
A = rand(N);
z = randn(N,1);
z = z/norm(z)*2;
b = A*z;

z = pinv(A)*b;
if norm(z,2) > 1
    z = spherelsq(A,b,1);
end

zmincon = fmincon(@(z) norm(A*z-b,2).^2, A\b, [], [], [], [], [], [], @norm1con);

% Check
z
zmincon
norm(z-zmincon) / norm(z)

function [c, ceq] = norm1con(z)
c = sum(z.^2,1) - 1;
ceq = [];
end

Result

>> test

Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

<stopping criteria details>

z =

   -0.5826
   -0.2210
    0.2825
   -0.4180
    0.4400
    0.0441
   -0.0615
    0.2073
   -0.1440
   -0.3070

zmincon =

   -0.5826
   -0.2210
    0.2825
   -0.4180
    0.4400
    0.0441
   -0.0615
    0.2073
   -0.1440
   -0.3070


ans =

   1.1762e-07

Look good to me