MATLAB Central Newsreader - Approaches to solve constrained mixed-norm optmization problema

Approaches to solve constrained mixed-norm optmization problema

Prime Mover — Mon, 17 Aug 2009 14:30:58 -0400

Dear friends,

What are the approaches available in MATLAB to solve a problem to find
a vector of parameters r such that the sum

|| W*r - s ||^2 + lambda1*| r | + lambda2*|| H*r - p ||^2

is minimized?

W and H are matrices with known values; s and p are vector with known
values; and lambda1 and lambda2 are a set of given weights.

Thank you all for the cooperation.

Re: Approaches to solve constrained mixed-norm optmization problema

Torsten Hennig — Mon, 17 Aug 2009 14:49:15 -0400

> Dear friends,
>
> What are the approaches available in MATLAB to solve
> a problem to find
> a vector of parameters r such that the sum
>
> || W*r - s ||^2 + lambda1*| r | + lambda2*|| H*r - p
> ||^2
>
> is minimized?
>
> W and H are matrices with known values; s and p are
> vector with known
> values; and lambda1 and lambda2 are a set of given
> weights.
>
> Thank you all for the cooperation.
>

What norms do you mean in the expression to be
minimized ?

||.|| = 2-norm , |.| = oo-norm or 1-norm ?

Best wishes
Torsten.

Re: Approaches to solve constrained mixed-norm optmization problema

Emilson — Mon, 17 Aug 2009 16:35:17 -0400

On 17 ago, 11:49, Torsten Hennig <Torsten.Hen...@umsicht.fhg.de>
wrote:
> > Dear friends,
>
> > What are the approaches available in MATLAB to solve
> > a problem to find
> > a vector of parameters r such that the sum
>
> > || W*r - s ||^2 + lambda1*| r | + lambda2*|| H*r - p
> > ||^2
>
> > is minimized?
>
> > W and H are matrices with known values; s and p are
> > vector with known
> > values; and lambda1 and lambda2 are a set of given
> > weights.
>
> > Thank you all for the cooperation.
>
> What norms do you mean in the expression to be
> minimized ?
>
> ||.|| = 2-norm , |.| = oo-norm or 1-norm ?
>
> Best wishes
> Torsten.- Ocultar texto das mensagens anteriores -
>
> - Mostrar texto das mensagens anteriores -

This is gonna be a mixed-norm problem:

|| Wr - s || and || Hr - p || = L2-norm; | r | = L1-norm

Thanks for asking.

Re: Approaches to solve constrained mixed-norm optmization problema

Bruno Luong — Mon, 17 Aug 2009 19:21:01 -0400

Emilson <emilsonpl@gmail.com> wrote in message <2a703ae3-f962-43d2-b3f0-6e226ca70490@k30g2000yqf.googlegroups.com>...

>
> || Wr - s || and || Hr - p || = L2-norm; | r | = L1-norm
>

Here are few though. First without restrict the generality, let's assume there is only one L2 term (put them together):

J2(r) := || A r - b ||^2 = alpha*|| Wr - s || ^2 + beta*|| Hr - p ||^2

A, b are matrices derived from the known parameters.

Our main objective function is

J0(r) := J2(r) + |r|

Let r2/r0 are respectively solutions minimizing J2/J0. I believe (!) we can show the *sign* of r0 and r2 (components) are identical.

Thus we can replace the pb minimizing J0(r) + |r| by

Minimizing:
J0(r) + <s,r>
<s,r>>=0

where s := sign(r2)

This problem is a box quadratic least-square minimization, thus it can be solved with an appropriate algorithm.

I hope my intuition is good and I don't make any false reasoning.

Bruno

Re: Approaches to solve constrained mixed-norm optmization problema

Johan L?fberg — Tue, 18 Aug 2009 11:12:01 -0400

The standard approach is to write it as a QP

min ||[Wr-s;sqrt(lambda2)*(Hr-p)||^2 + lambda1*sum(t)

s.t

-t < r < t

where t is a new set of variables of dimension length(r).

You decision variables are thus x=[r;t]. Write the objective in standard form 0.5*x'Q*x+c'*x and constraints as Ax<b and use, e.g., quadprog.

Or be lazy and use the modelling language YALMIP (free toolbox for MATLAB)

r = sdpvar(n,1);
objective = (W*r - s)'*(W*r-s) + lambda1*norm(r,1)+(H*r - p)'*(H*r-p)
solvesdp([],objective)
double(r)

Prime Mover <emilsonpl@gmail.com> wrote in message <26c8a015-8817-4b87-a0b3-1d22e6464c2d@z31g2000yqd.googlegroups.com>...
> Dear friends,
>
> What are the approaches available in MATLAB to solve a problem to find
> a vector of parameters r such that the sum
>
> || W*r - s ||^2 + lambda1*| r | + lambda2*|| H*r - p ||^2
>
> is minimized?
>
> W and H are matrices with known values; s and p are vector with known
> values; and lambda1 and lambda2 are a set of given weights.
>
> Thank you all for the cooperation.
>
>

Re: Approaches to solve constrained mixed-norm optmization problema

Emilson — Tue, 18 Aug 2009 11:17:47 -0400

On 18 ago, 08:12, "Johan L?fberg" <loefb...@control.ee.ethz.ch> wrote:
> The standard approach is to write it as a QP
>
> min ||[Wr-s;sqrt(lambda2)*(Hr-p)||^2 + lambda1*sum(t)
>
> s.t
>
> -t < r < t
>
> where t is a new set of variables of dimension length(r).
>
> You decision variables are thus x=[r;t]. Write the objective in standard form 0.5*x'Q*x+c'*x and constraints as Ax<b and use, e.g., quadprog.
>
> Or be lazy and use the modelling language YALMIP (free toolbox for MATLAB)
>
> r = sdpvar(n,1);
> objective = (W*r - s)'*(W*r-s) + lambda1*norm(r,1)+(H*r - p)'*(H*r-p)
> solvesdp([],objective)
> double(r)
>
>
>
> Prime Mover <emilso...@gmail.com> wrote in message <26c8a015-8817-4b87-a0b3-1d22e6464...@z31g2000yqd.googlegroups.com>...
> > Dear friends,
>
> > What are the approaches available in MATLAB to solve a problem to find
> > a vector of parameters r such that the sum
>
> > || W*r - s ||^2 + lambda1*| r | + lambda2*|| H*r - p ||^2
>
> > is minimized?
>
> > W and H are matrices with known values; s and p are vector with known
> > values; and lambda1 and lambda2 are a set of given weights.
>
> > Thank you all for the cooperation.- Ocultar texto das mensagens anteriores -
>
> - Mostrar texto das mensagens anteriores -

Well, thank you tow for posting. I guess I will start with quadprog
and see I why I'll get.

Cheers.

Re: Approaches to solve constrained mixed-norm optmization problema

Bruno Luong — Tue, 18 Aug 2009 14:58:06 -0400

"Johan L?fberg" <loefberg@control.ee.ethz.ch> wrote in message <h6e2a1$h2k$1@fred.mathworks.com>...
> The standard approach is to write it as a QP
>
> min ||[Wr-s;sqrt(lambda2)*(Hr-p)||^2 + lambda1*sum(t)
>
> s.t
>
> -t < r < t
>
> where t is a new set of variables of dimension length(r).

I'm glad to learn the "standard" approach. Thanks.

Bruno

Re: Approaches to solve constrained mixed-norm optmization problema

Matt — Tue, 18 Aug 2009 17:05:21 -0400

Prime Mover <emilsonpl@gmail.com> wrote in message <26c8a015-8817-4b87-a0b3-1d22e6464c2d@z31g2000yqd.googlegroups.com>...
> Dear friends,
>
> What are the approaches available in MATLAB to solve a problem to find
> a vector of parameters r such that the sum
>
> || W*r - s ||^2 + lambda1*| r | + lambda2*|| H*r - p ||^2
>
> is minimized?
>
> W and H are matrices with known values; s and p are vector with known
> values; and lambda1 and lambda2 are a set of given weights.
==================

The title of your post says that this is a constrained problem, yet you haven't mentioned any constraints on r. If there are no constraints, then I would be interested to know how the following Majorize-Minimize approach performs. It can easily be modified for box constraints on r:

1. First, reformulate the objective function as suggested by others to be in the form

f(x) = 1/2 *x'*Q*x+b*x

2. Proceed according to the following algorithm

MajCurvs=sum(abs(Q)<2);
ImportantQuantity=lambda1./MajCurvs;

r=InitialValue;

for ii=1:numIterations

QuadGradient=Q*x+b;

  Center=r-QuadGradient./MajCurvs;
  Candidate1=Center-ImportantQuantity;
  Candidate2=Center+ImportantQuantity;

  r=Candidate1.*(Candidate1>0)+ Candidate2.*(Candidate2<0);

end

Re: Approaches to solve constrained mixed-norm optmization problema

Matt — Tue, 18 Aug 2009 17:23:21 -0400

"Matt " <xys@whatever.com> wrote in message <h6en0h$7i0$1@fred.mathworks.com>...

> 1. First, reformulate the objective function as suggested by others to be in the form
>
> f(x) = 1/2 *x'*Q*x+b*x

Make that

f(r) = 1/2 *r'*Q*r+b*r +lambda1*|r|