Linear program with multiple norm vectors

[gfd43tg]

Homework Statement

In the previous few modules you studied the problem of minimizing $\| Ax -b \|_{2}$ by choice of $x$. So
far you've done this in Matlab using either the backslash operator or the command pinv. Now
that you've been exposed to linear programming, you have the tools to solve two variations on
this problem, namely minimizing
1. $\| Ax -b \|_{1}$
2. $\| Ax -b \|_{\infty}$
Recall that the 1-norm of a vector $v$ with components $(v_{1}, \dots , v_{N})$ is defined to be

$\| v\|_{1} = \sum\limits_{i=1}^N|v_{i}|$,

and the 1-norm of the same vector is defined to be

$\|v\|_{\infty} = \underset{i}\max | v_{i} |$

and minimization of either of these norms can be represented as a linear program.
We have provided partial code for the function

x = regressionNorms(A,b,nFlag)

with inputs

1. A: the evaluated ''basis" matrix in the regression problem
2. b: the ''measurements" in the regression problem
3. nFlag: a number that is either 1, 2, or Inf, specifying which norm p to use when minimizing $\| Ax -b \|_{p}$

and output
1. x: minimizer of $\| Ax -b \|_{p}$

In particular, we have provided partial-code to set up and solve the case where $p = 1$ by transforming it into a linear program in standard form. You will complete the function using the backslash operator to solve the case where $p = 2$, and using the tools you learned in this module to solve the case where $p = \infty$ by transforming it into a linear program in standard form. For this latter case $(p = \infty)$, your code will include a call to lpsolver.

Homework Equations

The Attempt at a Solution

This is the code given in the problem

function x = regressionNorms(A,b,nFlag)
% You can assume that b is a column vector (no need to do error-checking) and
% that A and b have the same number of rows.  In principle, you would normally
% check those (and other conditions) and use ERROR if any necessary conditions
% are not met.
%

switch nFlag
   
   % finish code to solve the 1-norm problem
   case 1
      nr = size(A,1);  nc = size(A,2);
      c = [zeros(nc,1);  ones(nr,1) ];
      Aineq = [
         bineq = [
         [xT,~,~,~] = lpsolver(c,Aineq,bineq);
         x = xT(1:nc);
         
         % solves the least-squares problem
   case 2
   
   % Insert code here
   
   % solves the infinity-norm problem
   case Inf
      
      % Insert code here
      
   otherwise
      error('Unrecognized norm')
end

There is a lot of confusion for me here. I guess what they want in case 1 is to make the matrices Aineq and bineq to be the correct matrix size. I'll break up the 3 cases so that it is easier to digest, plus I am only working on one case at a time

CASE 1

   % finish code to solve the 1-norm problem
   case 1
      nr = size(A,1);  nc = size(A,2);
      c = [zeros(nc,1);  ones(nr,1) ];
      Aineq = [zeros(nr,nr+nc)]
         bineq = [zeros(nr,1)]
         [xT,~,~,~] = lpsolver(c,Aineq,bineq);
         x = xT(1:nc);

But this problem is so vague that I don't really understand what to do with it. lpsolver is a script that was given to us that will solve the linear program with the inputs A, b, and c (c is the vector that we are trying to either maximize or minimize), and A and b are components of the inequality $Ax \leq b$

Since the infinity norm is the largest norn in the vector, which vector would it be in this case? Is that the c vector or the b vector?

 

[gfd43tg]

I got case 2 correct!

% solves the least-squares problem
    case 2
        x = A\b;

How do you transform a 1-norm and infinite norm problem into a 2 norm problem? That is basically what I need to do. I have looked over the lecture slides that deal with this, and I can't figure out how to set it up for this problem.

 

[gfd43tg]

Finally got case 1

case 1
        nr = size(A,1);  nc = size(A,2);
        c = [zeros(nc,1);  ones(nr,1) ];
        Aineq = [A -eye(nr); -A -eye(nr)];
        bineq = [b; -b];
        [xT,~,~,~] = lpsolver(c,Aineq,bineq);
        x = xT(1:nc);