xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

APM462: -无代写

时间：2024-07-09

APM462: Midterm Project

Due: Sat July 13 before 11:59pm

Submit your solutions to the homework on Crowdmark.

(1) Let C ⊂ Rn be a nonempty closed convex set and a ∈ Rn a point outside of

C. Suppose x0 ∈ C is the projection of a onto C, that is |x0 − a| ≤ |x− a|

for all x ∈ C. Prove that x0 is unique.

(2) Let D = {(x, y) ∈ R2|x2 + y2 ≤ r} ⊂ R2 and let ∂D denote its boundary.

Let d : D → R be the distance from a point a ∈ D to its boundary:

d(a) = min

x∈∂D

|a− x|.

Prove that d is a concave function on D.

(3) Let C ⊂ Rn be the non negative orthant (C = {(x1, . . . , xn) ∈ Rn|xi ≥

0, i = 1, . . . , n}) and f : Rn → R be convex. Consider the following

problem

minimise f(x)

subject to x ∈ C

and assume that it has a minimiser. Prove that if there exists some y ∈ C

such that there is some v ∈ ∂f(y) with v ∈ intC, then the set of minimisers

to the problem is bounded.

(4) Consider the set C = {(x, y) ∈ R2|x2 + y2 ≤ 1, y ≥ 0, y ≤ x}. Let δC(x, y)

be its indicator function. Let (x0, y0) be a boundary point of C. Find

∂δC(x0, y0).

(5) Consider the following problem:

minimise f(x, y) = (x− 1)2 + (y − 3)2

subject to g(x, y) = |x|+ 2y − 2 ≤ 0

(a) Solve the problem using subdifferentials.

(b) Convert this problem into an equivalent minimisation problem which

you can apply the KKT conditions to. Then use the KKT FONC to

find candidates for minimisers. Do you get the same candidates as in

part a?

(6) Consider the following problem:

minimise f(x, y) = 3x2 − 2y

subject to g(x, y) = |x+ 2|+ |y − 3| − 1 ≤ 0

(a) Find ∂f(x, y) and ∂g(x, y).

1

(b) Solve the problem using subdifferentials.

(7) Consider the following problem:

minimise f(x, y) = max{|x|, y + 2}

subject to g1(x, y) = 2x

2 + y2 − 1 ≤ 0

g2(x, y) = |x| − 2y − 1 ≤ 0

(a) Find ∂f(x, y), ∂g1(x, y), and ∂g2(x, y).

(b) Solve the problem using subdifferentials.

The following 3 problems—the ones indexed by Roman numerals—are

for practice only and are not to be turned in.

I. Let x = (x1, . . . , xn) ∈ Rn. The ℓ∞ norm of a vector is defined as follows:

|x|∞ = max

1≤i≤n

|xi|.

Let f(x) = |x|∞. Find ∂f(0).

II. Let f : Rn → R be convex and C1. Prove that ∂f(x) = {∇f(x)}.

III. On the interval [1, 3], approximate the function x2 by the affine function

ax+ b such that the quantity

sup

x∈[1,3]

|x2 − (ax+ b)|

is minimised.

2

学霸联盟

Due: Sat July 13 before 11:59pm

Submit your solutions to the homework on Crowdmark.

(1) Let C ⊂ Rn be a nonempty closed convex set and a ∈ Rn a point outside of

C. Suppose x0 ∈ C is the projection of a onto C, that is |x0 − a| ≤ |x− a|

for all x ∈ C. Prove that x0 is unique.

(2) Let D = {(x, y) ∈ R2|x2 + y2 ≤ r} ⊂ R2 and let ∂D denote its boundary.

Let d : D → R be the distance from a point a ∈ D to its boundary:

d(a) = min

x∈∂D

|a− x|.

Prove that d is a concave function on D.

(3) Let C ⊂ Rn be the non negative orthant (C = {(x1, . . . , xn) ∈ Rn|xi ≥

0, i = 1, . . . , n}) and f : Rn → R be convex. Consider the following

problem

minimise f(x)

subject to x ∈ C

and assume that it has a minimiser. Prove that if there exists some y ∈ C

such that there is some v ∈ ∂f(y) with v ∈ intC, then the set of minimisers

to the problem is bounded.

(4) Consider the set C = {(x, y) ∈ R2|x2 + y2 ≤ 1, y ≥ 0, y ≤ x}. Let δC(x, y)

be its indicator function. Let (x0, y0) be a boundary point of C. Find

∂δC(x0, y0).

(5) Consider the following problem:

minimise f(x, y) = (x− 1)2 + (y − 3)2

subject to g(x, y) = |x|+ 2y − 2 ≤ 0

(a) Solve the problem using subdifferentials.

(b) Convert this problem into an equivalent minimisation problem which

you can apply the KKT conditions to. Then use the KKT FONC to

find candidates for minimisers. Do you get the same candidates as in

part a?

(6) Consider the following problem:

minimise f(x, y) = 3x2 − 2y

subject to g(x, y) = |x+ 2|+ |y − 3| − 1 ≤ 0

(a) Find ∂f(x, y) and ∂g(x, y).

1

(b) Solve the problem using subdifferentials.

(7) Consider the following problem:

minimise f(x, y) = max{|x|, y + 2}

subject to g1(x, y) = 2x

2 + y2 − 1 ≤ 0

g2(x, y) = |x| − 2y − 1 ≤ 0

(a) Find ∂f(x, y), ∂g1(x, y), and ∂g2(x, y).

(b) Solve the problem using subdifferentials.

The following 3 problems—the ones indexed by Roman numerals—are

for practice only and are not to be turned in.

I. Let x = (x1, . . . , xn) ∈ Rn. The ℓ∞ norm of a vector is defined as follows:

|x|∞ = max

1≤i≤n

|xi|.

Let f(x) = |x|∞. Find ∂f(0).

II. Let f : Rn → R be convex and C1. Prove that ∂f(x) = {∇f(x)}.

III. On the interval [1, 3], approximate the function x2 by the affine function

ax+ b such that the quantity

sup

x∈[1,3]

|x2 − (ax+ b)|

is minimised.

2

学霸联盟