Constrained Optimization Proof

[kingwinner]

Homework Statement

Homework Equations

Constrined optimzation

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 x₀ is a local min point.
Suppose, on the contrary, that x₀ is NOT a global min point. Then there must exist a point x₁ s.t. f(x₁)<f(X₀).

Let x(s) = (1-s)x₀ + s x₁, s is any real number.
x(0)=x₀, x(1)=x₁
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) = x₁ o Qx₀ - x₀ o Qx₀ - b o (x₁-x₀)
and 0 ≤ φ''(0) = x₁ o Qx₁ - x₁ o Qx₀ - x₀ o Qx₁ + x₀ o Qx₀
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!

 

[kingwinner]

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.

 

[kingwinner]

By the way, I would like to clarify that A and Q are matrices and x is some point in R^d (in case you are confused with the question).

 

[Ray Vickson]

By the way, I would like to clarify that A and Q are matrices and x is some point in R^d (in case you are confused with the question).

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

 

[kingwinner]

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) = x₁ o Qx₀ - x₀ o Qx₀ - b o (x₁-x₀)
and 0 ≤ φ''(0) = x₁ o Qx₁ - x₁ o Qx₀ - x₀ o Qx₁ + x₀ o Qx₀

=> φ'(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.

 

[Ray Vickson]

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) = x₁ o Qx₀ - x₀ o Qx₀ - b o (x₁-x₀)
and 0 ≤ φ''(0) = x₁ o Qx₁ - x₁ o Qx₀ - x₀ o Qx₁ + x₀ o Qx₀

=> φ'(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.

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

 

[kingwinner]

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.

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

 

[kingwinner]

0 = φ'(0) = x₁ o Qx₀ - x₀ o Qx₀ - b o (x₁-x₀)
and 0 ≤ φ''(0) = x₁ o Qx₁ - x₁ o Qx₀ - x₀ o Qx₁ + x₀ o Qx₀

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

I think from here I need to show that f(x₁)-f(x₀)≥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?

 

[Ray Vickson]

0 = φ'(0) = x₁ o Qx₀ - x₀ o Qx₀ - b o (x₁-x₀)
and 0 ≤ φ''(0) = x₁ o Qx₁ - x₁ o Qx₀ - x₀ o Qx₁ + x₀ o Qx₀

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

I think from here I need to show that f(x₁)-f(x₀)≥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?

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

RGV

 

[kingwinner]

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.