# Linear program with multiple norm vectors

1. Jul 23, 2014

### Maylis

1. The problem statement, all variables and given/known data
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

Code (Text):
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.

2. Relevant equations

3. The attempt at a solution
This is the code given in the problem
Code (Text):
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
Code (Text):

% 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?

Last edited: Jul 23, 2014
2. Jul 24, 2014

### Maylis

I got case 2 correct!

Code (Text):
% 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.

#### Attached Files:

File size:
1.2 MB
Views:
75
• ###### slides part 2.pdf
File size:
781.6 KB
Views:
69
Last edited: Jul 24, 2014
3. Jul 24, 2014

### Maylis

Finally got case 1

Code (Text):
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);