代写Optimization and Algorithms 2022 Exam调试数据库编程

日期：2025-01-09 05:22

Optimization and Algorithms

November 17, 2022

Exam: Part A

1. Positioning without covering a set.  Consider the set

S = {x = (x1 , . . . , xn) ∈ Rn :  - 1 ≤ xi  ≤ 1,  for  1 ≤ i ≤ n} .

(In dimension n = 2, the set S looks like a filled square.)

We want to position a ball

B(c) = {x ∈ Rn :  Ⅱx - cⅡ2  ≤ r}

such that the center c of the ball is as close as possible to a given point d ∈ Rn and such that the ball does not cover the set  S  (that is, we do not want to have S ≤ B(c)). The radius r > 0 of the ball is given and cannot be changed.

For future reference, let V C Rn  be the set of vectors of size n whose components are either 1 or -1. For example, in dimension n = 2, we have

Note that, for n = 2, the set V is the set of vertices of the square S.  (For general n, the set V has 2n  elements.)

Consider the following optimization problems.

One of these optimization is suitable for the given context.

Which one?

Write your answer (A, B, C, D, E, or F) in the box at the top of page 1

Hint: think about this problem in dimension n = 2.

2. Unconstrained optimization.  Consider the optimization problem

where

The point

is a global minimizer of (7) for one of the following choices of d:

Which one?

Write your answer (A, B, C, D, E, or F) in the box at the top of page 1

3. Least-squares.  Let A ∈ Rm×n  and b ∈ Rm  be given, with n being an even number, and consider the following optimization problems:

where rev : Rn → Rn is the map that returns the input written in reverse order (that is, written from the last component to the first component).  Examples (for n = 4):

where sort : Rn  → Rn  is the map that returns the input sorted in ascending order. Examples (for n = 4):

where  circ : Rn  → Rn  is the  map that  returns the input circulated by one component  (that is,  the first component of the input  x becomes the second component of the output, the second component of x becomes the third com- ponent of the output, and so on, and the last component of x becomes the first component of the output). Examples (for n = 4):

where  cent : Rn  → Rn  is  the map that shifts the input so that it becomes centered at the origin;  more precisely,  given the input  x, the map subtracts from x the average of the components of x.  Examples (for n = 4):

where trim : Rn  → Rn  is the map that trims one component at the beginning and at the end of the input;  that is,  given the input  x, the map zeroes the first and last components of x, while keeping the other components of x intact. Examples (for n = 4):

where swap : Rn → Rn  is the map that swaps each consecutive pair of compo- nents of x (that is, given x = (x1 , x2 , . . . , xn), it swaps x1  with x2 , thenx3  with x4 , and so on, until xn-1  with xn). Examples (for n = 4):

       

One of the above problems is not a least-squares problem. Which one?

Write your answer (A, B, C, D, E, or F) in the box at the top of page 1

4. Newton algorithm.  Consider the Newton algorithm with the generic update equation given by

x k+1 = x k + Qkdk ,                                                (8)

where Qk  denotes the stepsize.

Suppose that the Newton algorithm is applied to the function f : R2 → R,

f (a, b) = (2a - b)2 + b2,

and suppose that the current iterate is

One of the following vectors is then the vector dk  in (8).

Which one?

Write your answer (A, B, C, D, E, or F) in the box at the top of page 1

Exam: Part B

1. Convex problem.  Show that the following problem is convex,

where the vectors ak   ∈ Rn   (for  1  ≤ k  ≤ K)  and c ∈ Rn.   The  numbers  bk   (for 1 ≤ k ≤ K), λ > 0, r > 0, and P > 0 are also given.

The function φ : R → R is defined as

The function ψ : R → R is defined as

2. Equivalent problems?   Bob wants to compute a point in the hyperplane H(s, r) = {x ∈ Rn : sT x = r } that is closest to given points pk ∈ Rn , for  1 ≤ k ≤ K, in the mean squared-distance sense.  That is, Bob wants to find a global minimizer of the problem

Alice claims that this problem is equivalent to compute a point in the hyperplane H(s, r) that is closest to the center-of-mass of the points pk, for 1 ≤ k ≤ K.  That is, Alice claims that the global minimizers of (2) are the same as the global minimizers of

Is  Alice  correct  or wrong?   If you  think  Alice  is  wrong,  then  provide  a  counter- example: that is, provide an hyperplane H(s, r) and points p1 , . . . , pK  such that the global minimizers of (2) and (3) are not the same.  If you think Alice is correct, then prove that the global minimizers of  (2) and  (3) are the same  (for any hyperplane H(s, r) and points p1 , . . . , pK ).

3. Distance between two parallel hyperplanes.  Consider two parallel hyperplanes in Rn given by

H1 = {x ∈ Rn : sT x = r1 } ,  and H2  = {x ∈ Rn : sT x = r2 } ,

where s is a nonzero vector in Rn , andr1  andr2  are two distinct numbers (r1 r2 ). We wish to find the distance between these two hyperplanes. That is, denoting this distance by d (H1, H2 ), we wish to compute

d (H1, H2 ) = inf {Ⅱx1  - x2 Ⅱ2  : x1  ∈ H1, x2  ∈ H2} .                        (4)

Give a closed-form expression for the distance d (H1, H2 ) in terms of s, r1 , and r2 . Hint: use KKT conditions on the problem (4).

4. Dead-zone quadratic penalty. The dead-zone quadratic penalty function with bandwidth B > 0 is the function φ : Rn → R defined as

φB (x) = (ⅡxⅡ2 - B) . 

Let H(s, r) be a given hyperplane

H(s, r) ={x ∈ Rn : sT x = r } ,

with s ∈ Rn  and r ∈ R.

Give a closed-form expression for a global minimizer of the problem

where  c  ∈ Rn   and  B  >  0  are  given.    Assume  that  c  is  not  in  the  hyperplane (c ∈/ H(s, r)) and that s is a nonzero vector (s ≠ 0).