non-linear and linear programming

5.pdf

Home >Mathematics homework help >non-linear and linear programming

APM462: Homework 5 Comprehensive assignment for first term 1

Due: Tue Nov 3 (before 9pm) on Crowdmark.

(1) Recall that in lecture I proved that at a regular point p, TpM ⊆ Tp and then said that equality follows from the Implicit Function Theorem. In this problem you are asked to prove Tp ⊆ TpM in a special case.

Let f : Rn → R be a C1 function. Recall from HW4 that the graph of f is the surface M := {(x, f(x)) ∈ Rn × R | x ∈ Rn} in Rn × R. (a) Let p := (x0, f(x0)) ∈M . Find the space Tp. (b) Show that Tp ⊆ TpM . That is show that any vector in the space

Tp is a tangent vector to M at p.

(2) Let f : Rn → R, and φ : R1 → Rn be C1 functions. Use Lagrange multipliers (1st order conditions) to show that the following two constrained optimization problems have the same solutions:

min f(x)

subject to h(x) = 0

x = φ(s)

s ∈ R1,

and

min f(φ(s))

subject to h(φ(s)) = 0

s ∈ R1.

Note: the first problem involves the variables x and s, while the second one only s.

(3) This question explores a surprising relationship called “linear programming duality” be- tween two related linear problems. If you took APM236 you would have seen duality

there. Here we will prove duality using the Kuhn-Tucker conditions.

Let A be an m × n matrix, b ∈ Rm, and c ∈ Rn. Consider the following two optimization problems, the “primal problem”:

max cTx

subject to Ax ≤ b x ≥ 0,

and the “dual problem”:

min bT p

subject to AT p ≥ c p ≥ 0.

Let x∗ be an primal optimal solution and p ∗ be an optimal dual

solution.

(a) Write the Kuhn-Tucker (1st order neccessary) conditions for x∗. Hint: use Lagrange multipliers p (for the Ax ≤ b constraints) and µ (for the x ≥ 0 constraints).

(b) Show that the Lagrange mutipliers p∗ for the optimal primal x∗ satisfy the constraints of the dual problem.

TAx∗ = p T ∗ b.

(d) Write the Kuhn-Tucker (1st order neccessary) conditions for p∗. Hint: use Lagrange multipliers x (for the AT p ≥ c constraints) and ν (for the p ≥ 0 constraints).

(e) Show that the Lagrange mutipliers x∗ for the optimal dual p∗

satisfy the constraints of the primal problem.

(f) Use the comlementary slackness conditions for the dual problem to show that cTx∗ = (p∗)TAx∗.

(g) Use the complementary slackness conditions to show that cTx∗ = (p∗)T b.

(4) Consider the following “continuous” optimization problem:

min ∫ c(x)h(x) dx

subject to 0 ≤ h(x) ≤ 1∫ h(x) dx = 1.

The solution to this problem is given in the following way. Let Is := {x | c(x) ≤ s} be the s-sublevel set of c(x). Note that the volume |Is| =

∫ Is

1 dx of Is is an increasing function of s. Choose s0 such that |Is0 | = 1. The optimal solution is the function:

h(x) =

{ 1 if x ∈ Is0 0 if x 6∈ Is0 .

In economic terms, h(x) is the density of a given resource as a function of the location x and c(x) is the cost of the resource at location x. This problem is about wanting to accumulate total of 1 unit of the resource in such a way as to minimize the cost.

(a) Explain why the solution makes sense in economic terms.

(b) Suppose the cost c(x) = 12x TQx for some positive definite n×n

symmetric matrix Q. Write a formula for the volume |Is| in terms of the matrix Q. Conclude that |Is| is a continuous, strictly increasing function of s. Note: this shows that for this cost, there exists s0 such that |Is0 | = 1. Hint: the level sets of c(x) are ellipses whose size depends on the e-values of Q.

We have not learned how to deal with these kind of “continuous” problems, but let us consider a related discrete problem where n ≥ N . Here N is a natural number:

min ∑n

i=1 cihi

subject to 0 ≤ hi ≤ 1 for all i∑n i=1 hi = N.

(c) Assume that the entries ci of the cost vector c are all distinct. Use the Kuhn-Tucker conditions to prove that the optimal solu- tion to the discrete problem is (mostly) “all or nothing”. That is prove that except for possibly one i, hi is 0 or 1 for all other i’s.

(5) Let R > 0 and assume the following problem has a solution:

min f(x, y, z)

subject to x2 + y2 ≤ R2.

Note that the Kuhn-Tucker conditions (*) are:

∇f(x, y, z) + µ

2x2y 0

 = 00

 µ(x2 + y2 −R2) = 0, µ ≥ 0.

(a) Write the Kuhn-Tucker conditions for the following problem using Lagrange multipliers µ1 and µ2:

min f(r cos θ, r sin θ, z)

subject to r −R ≤ 0 −r ≤ 0

(b) Show that the conditions you found in part (a) imply the Kuhn- Tucker conditions (*). Start by expressing µ in terms of µ1 and µ2. There should be two cases to consider: when r = 0 and when r 6= 0.