FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » num-analysis
optimization / eigenvalues
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
Uwe Schmitt
science forum beginner


Joined: 27 Jul 2005
Posts: 10

PostPosted: Wed Jun 28, 2006 9:55 am    Post subject: optimization / eigenvalues Reply with quote
Hi,

I try to minimize

x' A x
-------- + lambda^2 || Cx ||^2
x' B'B x

If I choose lambda = 0, I get a generalized
eigenvalue problem.

In the case lambda != 0, I wrote the problem above as

min x'Ax + lambda^ || Cx ||^2 under the restriction ||Bx|| = 1

which leads to langrange formulation

Phi(x) = x'Ax + lambda^2 || Cx ||^2 + mu (1 - ||Bx||^2)

If I proceed I get in the end the following eigenvalue-problem

(A + lambda^2 C' C) x = mu B x

I tested it numerically but it did not work.
Is there a mistake in my derivation above or do I have to
look for bugs in my implementation ?


Greetings, Uwe.
Back to top
Peter Spellucci
science forum Guru


Joined: 29 Apr 2005
Posts: 702

PostPosted: Wed Jun 28, 2006 4:00 pm    Post subject: Re: optimization / eigenvalues Reply with quote
In article <1151488545$mail2nntp@hades.rz.uni-saarland.de>,
Uwe Schmitt <schmitt@num.uni-sb.de> writes:
Quote:

Hi,

I try to minimize

x' A x
-------- + lambda^2 || Cx ||^2
x' B'B x

(*)

Quote:

If I choose lambda = 0, I get a generalized
eigenvalue problem.

In the case lambda != 0, I wrote the problem above as

min x'Ax + lambda^ || Cx ||^2 under the restriction ||Bx|| = 1

which leads to langrange formulation

Phi(x) = x'Ax + lambda^2 || Cx ||^2 + mu (1 - ||Bx||^2)

If I proceed I get in the end the following eigenvalue-problem

(A + lambda^2 C' C) x = mu B x

I tested it numerically but it did not work.
Is there a mistake in my derivation above or do I have to
look for bugs in my implementation ?


Greetings, Uwe.



your original problem is x-norm dependent, your final equation not, clearly there
must be a bug in the derivation.
I guess that in truth you wanted to minimize

x'Ax/(x' B'B x) + lambda^2 ||Cx/||x|| ||^2
because otherwise you could choose
x= alpha*z
with z minimizing the first term and then let alpha->0 showing thta there is no
influence of the second term, whatever lambda is. if this is the case then
you would get a nasty nonlinear eigenvalue problem,
hence first think about the correct formulation of your problem
hth
peter
Back to top
Robert B. Israel
science forum Guru


Joined: 24 Mar 2005
Posts: 2151

PostPosted: Wed Jun 28, 2006 11:03 pm    Post subject: Re: optimization / eigenvalues Reply with quote
In article <1151488545$mail2nntp@hades.rz.uni-saarland.de>,
Uwe Schmitt <schmitt@num.uni-sb.de> wrote:
Quote:

Hi,

I try to minimize

x' A x
-------- + lambda^2 || Cx ||^2
x' B'B x

If I choose lambda = 0, I get a generalized
eigenvalue problem.

In the case lambda != 0, I wrote the problem above as

min x'Ax + lambda^ || Cx ||^2 under the restriction ||Bx|| = 1

which leads to langrange formulation

Phi(x) = x'Ax + lambda^2 || Cx ||^2 + mu (1 - ||Bx||^2)

If I proceed I get in the end the following eigenvalue-problem

(A + lambda^2 C' C) x = mu B x

Should be (A + lambda^2 C' C) x = mu B' B x
if A is symmetric, otherwise replace A here by (A+A')/2

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
Back to top
Pierre Asselin
science forum beginner


Joined: 01 May 2005
Posts: 24

PostPosted: Wed Jun 28, 2006 11:27 pm    Post subject: Re: optimization / eigenvalues Reply with quote
Uwe Schmitt <schmitt@num.uni-sb.de> wrote:

Quote:
I try to minimize

x' A x
-------- + lambda^2 || Cx ||^2
x' B'B x

[ ... ]
In the case lambda != 0, I wrote the problem above as

min x'Ax + lambda^ || Cx ||^2 under the restriction ||Bx|| = 1

That's not the same thing. The first term in the original expression
is invariant under rescaling of x, so you can restrict ||Bx|| with
no loss of generality; the second term doesn't have this property.


--
pa at panix dot com
Back to top
Google
Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Sat Jan 10, 2009 3:19 am | All times are GMT
Forum index » Science and Technology » Math » num-analysis
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Power Method and negative eigenvalues Skunk num-analysis 7 Wed Jul 19, 2006 10:19 pm
No new posts Optimization of noisy functions John Herman num-analysis 2 Sat Jul 15, 2006 2:33 pm
No new posts how to avoid overfitting in training ... gino Math 1 Fri Jul 07, 2006 5:54 am
No new posts what's the best algorithm to handle t... gino Math 13 Thu Jul 06, 2006 5:01 pm
No new posts where is the newsgroup/mailing-list f... gino Math 2 Thu Jul 06, 2006 4:57 pm

Adverse Credit Remortgage | Online Advertising | Ken follet | Mortgage | Loans
Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums


Powered by phpBB © 2001, 2005 phpBB Group

[ Time: 0.1947s ][ Queries: 16 (0.1223s) ][ GZIP on - Debug on ]