Skip to main content

Convex Optimization · Separation, conjugates, and subgradients

Let C=[-1,1]² ⊂ ℝ² and let z=(3,2)

Problem

Convex Optimization practice problem

Let C=[−1,1]2⊂R2C=[-1,1]^2\subset\mathbb R^2 and let z=(3,2)z=(3,2). Equip R2\mathbb R^2 with the Euclidean inner product. Do not treat CC as a spectrahedron and do not pass through a Fenchel conjugate.

1. Compute the Euclidean projection p=ΠC(z)p=\Pi_C(z) by clipping each coordinate independently to [−1,1][-1,1]. Compute the distance ∥z−p∥\|z-p\| exactly.

2. Set n=z−pn=z-p. Prove the variational inequalityn⋅(x−p)≤0for every x∈C.n\cdot(x-p)\le 0\qquad\text{for every }x\in C.3. Compute the support value σC(n)=max⁡x∈Cn⋅x\sigma_C(n)=\max_{x\in C}n\cdot x and the pairing n⋅zn\cdot z.

4. Let m=(p+z)/2m=(p+z)/2 be the midpoint of the segment from pp to zz. Write the midplane {x:n⋅x=n⋅m}\{x:n\cdot x=n\cdot m\} and evaluate n⋅mn\cdot m. Prove that this midplane strictly separates CC from {z}\{z\}.

5. Audit both sentences: (i) “because CC is centered at the origin, the projection of zz is 00”; (ii) “the support of CC in the direction nn is the pairing n⋅zn\cdot z.”

Do not replace the square by a second-order cone or a semidefinite slice, and do not introduce a conjugate calculation.

Hint

Hint

Clipping 33 and 22 to [−1,1][-1,1] produces p=(1,1)p=(1,1). Then n=(2,1)n=(2,1) and ∥n∥=5\|n\|=\sqrt{5}.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Convex Optimization sample problem: Try the free sample problem.

More Convex Optimization practice problems

Back to Convex Optimization

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.