# S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Sun, 19 May 2013 05:13:33 UTC

 All times are UTC [ DST ]

 Page 1 of 1 [ 9 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Constrained Optimization ProofPosted: Sat, 11 Feb 2012 06:44:44 UTC
 Senior Member

Joined: Thu, 19 Feb 2009 05:25:19 UTC
Posts: 114

Top

 Post subject: Re: Constrained Optimization ProofPosted: Sat, 11 Feb 2012 09:46:18 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6004
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
kingwinner wrote:

You know what is, not just and .

_________________

Top

 Post subject: Re: Constrained Optimization ProofPosted: Sat, 11 Feb 2012 11:23:19 UTC
 Senior Member

Joined: Thu, 19 Feb 2009 05:25:19 UTC
Posts: 114
outermeasure wrote:
kingwinner wrote:

You know what is, not just and .

Yes, φ(s)=f(x(s))=f((1-s) x_0 + s x_1). But how would that help?

First of all, am I on the right track by adding φ'(0)+φ''(0)≥0? If not, can you give me some hints on what to do next? It does not seem to lead to a contradiction.

Thanks.

Top

 Post subject: Re: Constrained Optimization ProofPosted: Sun, 12 Feb 2012 11:16:00 UTC
 Senior Member

Joined: Thu, 19 Feb 2009 05:25:19 UTC
Posts: 114
Struggled for another day...still can't get the proof to work.

So I've shown that
0 = φ'(0) = x1 o Qx0 - x0 o Qx0 - b o (x1-x0)
and 0 ≤ φ''(0) = x1 o Qx1 - x1 o Qx0 - x0 o Qx1 + x0 o Qx0

=> φ'(0)+φ''(0)≥0

I think from here I need to show that f(x1)-f(x0)≥0. This would be a contradiction.
But the problem is that the expression for φ'(0)+φ''(0) is a mess and doesn't seem to simplify to f(x1)-f(x0). What else can I do from here??

I know φ(s)=f(x(s))=f((1-s) x_0 + s x_1), but this may be negative or positive or zero.

Would someone be nice enough to help me out? Any input/comments is appreciated!

Top

 Post subject: Re: Constrained Optimization ProofPosted: Mon, 13 Feb 2012 00:17:55 UTC
 Senior Member

Joined: Thu, 19 Feb 2009 05:25:19 UTC
Posts: 114
0 = φ'(0) = x1 o Qx0 - x0 o Qx0 - b o (x1-x0)
and 0 ≤ φ''(0) = x1 o Qx1 - x1 o Qx0 - x0 o Qx1 + x0 o Qx0

=> φ'(0)+φ''(0)≥0

I think from here I need to show that f(x1)-f(x0)≥0. (which is a contradiction)

Will a Taylor expansion work? But the problem is I think this will introduce a remainder term...how can I get rid of the remainder?

Thanks.

Top

 Post subject: Re: Constrained Optimization ProofPosted: Mon, 13 Feb 2012 00:46:05 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6004
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
kingwinner wrote:
Struggled for another day...still can't get the proof to work.

So I've shown that
0 = φ'(0) = x1 o Qx0 - x0 o Qx0 - b o (x1-x0)
and 0 ≤ φ''(0) = x1 o Qx1 - x1 o Qx0 - x0 o Qx1 + x0 o Qx0

=> φ'(0)+φ''(0)≥0

I think from here I need to show that f(x1)-f(x0)≥0. This would be a contradiction.
But the problem is that the expression for φ'(0)+φ''(0) is a mess and doesn't seem to simplify to f(x1)-f(x0). What else can I do from here??

I know φ(s)=f(x(s))=f((1-s) x_0 + s x_1), but this may be negative or positive or zero.

Would someone be nice enough to help me out? Any input/comments is appreciated!

Fill in the blank: is a (blank) function of s.

_________________

Top

 Post subject: Re: Constrained Optimization ProofPosted: Mon, 13 Feb 2012 02:35:58 UTC
 Senior Member

Joined: Thu, 19 Feb 2009 05:25:19 UTC
Posts: 114
outermeasure wrote:
Fill in the blank: is a (blank) function of s.

Is it a convex function? How can this be proved?

Top

 Post subject: Re: Constrained Optimization ProofPosted: Mon, 13 Feb 2012 02:40:32 UTC
 Moderator

Joined: Wed, 30 Mar 2005 04:25:14 UTC
Posts: 12074
Location: Austin, TX
kingwinner wrote:
outermeasure wrote:
Fill in the blank: is a (blank) function of s.

Is it a convex function? How can this be proved?

Can you show the second derivative is always positive?

_________________
(\ /)
(O.o)
(> <)
This is Bunny. Copy Bunny into your signature to help him on his way to world domination

Top

 Post subject: Re: Constrained Optimization ProofPosted: Mon, 13 Feb 2012 02:57:05 UTC
 Senior Member

Joined: Thu, 19 Feb 2009 05:25:19 UTC
Posts: 114
kingwinner wrote:
outermeasure wrote:
Fill in the blank: is a (blank) function of s.

Is it a convex function? How can this be proved?

Can you show the second derivative is always positive?

By chain rule, φ''(s) = x1 o Qx1 - x1 o Qx0 - x0 o Qx1 + x0 o Qx0, is this correct?

So in particular, φ''(0) = x1 o Qx1 - x1 o Qx0 - x0 o Qx1 + x0 o Qx0 ≥0 (since φ has a local min at s=0)

But now the expression φ''(s) does NOT depend on s, then can I conclude from here that φ''(s) ≥0 for ALL s??? Is this a valid argument?

If so, then this must be a major breakthrough for me.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 9 posts ]

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous