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!

Constrained Optimization Proof

  1. Feb 10, 2012 #1
    1. The problem statement, all variables and given/known data
    optim4.JPG


    2. Relevant equations
    Constrined optimzation


    3. The attempt at a solution
    ("o" means dot product)
    Let M={x|Ax=c} and f(x)=(1/2)x o Qx - b o x
    Suppose x0 is a local min point.
    Suppose, on the contrary, that x0 is NOT a global min point. Then there must exist a point x1 s.t. f(x1)<f(X0).

    Let x(s) = (1-s)x0 + s x1, s is any real number.
    x(0)=x0, x(1)=x1
    Let φ(s)=f(x(s)), s is any real number. Then φ has a local min at s=0.
    => φ'(0)=0 and φ''(0)≥0 (1st and 2nd order necessary conditions for a local min)

    By chain rule, 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
    and I'm stuck here...how can I arrive at a contradiction from here? I tried adding them to get φ'(0)+φ''(0)≥0, but it doesn't seem to help.

    Any help would be much appreciated!
     
  2. jcsd
  3. Feb 11, 2012 #2
    Am I on the right track by adding φ'(0)+φ''(0)≥0? If not, can someone give me some hints on what to do next? It does not seem to lead to a contradiction.

    Thanks.
     
  4. Feb 11, 2012 #3
    By the way, I would like to clarify that A and Q are matrices and x is some point in Rd (in case you are confused with the question).
     
  5. Feb 11, 2012 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    The fact that you are restricting yourself to an affine feasible set is crucial. You need to think about what happens when you project x down onto the feasible set. For example, assuming the matrix A is mxn with m < n and full row rank, the feasible set is an (n-m)-dimensional hyperplane, and within that hyperplane you can choose a basis consisting of (n-m) vectors, then write the objective a quadratic in the (n-m) coefficients in the expansion of x in terms of that basis. You then have an unconstrained problem in fewer dimensions, and you are assuming you have a local minimum. I won't say any more, but just give a simple example to show what is happening.

    Suppose we want to minimize f(x1,x2) = 2x1^2 - x2^2, (a non-convex function) over the line L: x1 - x2 = 0. A basis for feasible points is the vector (1,1), and any feasible x has the form (t,t), t in R. For such points the objective is f_L(t) = t^2, which certainly is a convex function.

    RGV
     
    Last edited: Feb 11, 2012
  6. Feb 11, 2012 #5
    I'm sorry, but I don't understand the point you're making in relation to this proof.

    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?

    Thanks.
     
    Last edited: Feb 11, 2012
  7. Feb 11, 2012 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I was ignoring your proof and going back to first principles. The point is: the constraint is absolutely crucial. Just look at the little example I gave.

    RGV
     
  8. Feb 12, 2012 #7
    OK, surely without the constriant the statement can be false. But we are given that the constraint IS to be satisfied in this situation, and asked to PROVE that local min => global min under these assumptions.

    So I struggled for another day...still can't get the proof to work. :frown:

    Would someone be nice enough to help me out with the proof? Any input/comments/hints is appreciated!
     
  9. Feb 12, 2012 #8
    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?
     
  10. Feb 12, 2012 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I think that I have given all the help/hints allowed by Forum rules.

    RGV
     
  11. Feb 12, 2012 #10
    Let M={x|Ax=c} and f(x)=(1/2)x o Qx - b o x.
    I think you're suggesting there is an eaiser way to do the proof and I should probably discard my method? So I think you're suggesting that f: M->R is a convex function. But how can this be rigorously proved?

    Now A is not necessarily invertible, in fact A is not even necessarily a square matrix, so we can't solve for x in Ax=c by taking inverse, and plug it into f(x).

    Thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook