help-octave
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

reposting min ||Pu-q||1 question


From: Ether Jones
Subject: reposting min ||Pu-q||1 question
Date: Sat, 3 May 2014 18:28:47 -0400


I am reposting the original question with several corrections.

I have an overdetermined linear system P*u = q + eps,

P is m by n, m > n.

u is n by 1.

q and eps are m by 1.

P and q are known; u and eps are unknown.


I want to find u which minimizes the L1 norm of eps;
in other words I want to minimize ||P*u-q||1

I do *not* want u to be constrained to be >= 0.

It's not clear to me how to solve this in Octave.

The objective is not smooth so that appears to rule out Octave's sqp().

The objective is not linear so that *appears* to rule out Octave's glpk().



However...

According to this web page:

http://cvxopt.org/examples/mlbook/l1.html

... minimizing ||P*u-q||1 is equivalent to the LP problem:

minimize 1'v
subject to
[P, -I; -P, I]*[u; v] <= [q,-q]

with m+n variables and 2m constraints.


And according to the Octave manual,

glpk() can solve problems of the form:

[ min | max ] C'*x

subject to

A*x [ "=" | "<=" | ">=" ] b
  x >= LB
  x <= UB


So if I create:

I = m by m identity matrix

A = [P, -I; -P, I]

b = [q; -q]

c = a vector of n zeros followed by m ones.

lb = -500

ub = 500

ctype = a vector of 2m "D" characters

vartype = a vector of n+m "C" characters

sense = []

param = []

... then I should be able to pass c, A, b, lb, ub, ctype, vartype, sense, and param

as described above to glpk (c, A, b, lb, ub, ctype, vartype, sense, param)



So my questions are:

1) Is there a better (more straightforward) way to do this?

2) If not, is my approach correct?


Thank you.



reply via email to

[Prev in Thread] Current Thread [Next in Thread]