1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear program with multiple norm vectors

  1. Jul 23, 2014 #1

    Maylis

    User Avatar
    Gold Member

    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. jcsd
  3. Jul 24, 2014 #2

    Maylis

    User Avatar
    Gold Member

    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:

    Last edited: Jul 24, 2014
  4. Jul 24, 2014 #3

    Maylis

    User Avatar
    Gold Member

    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);
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Linear program with multiple norm vectors
Loading...