Skip to main content

Convex Optimization · Conic, second-order cone, and semidefinite optimization

Let a ∈ ℝⁿ and P ∈ ℝ^(n×n)

Problem

Convex Optimization practice problem

Let a∈Rna\in\mathbb R^n and P∈Rn×nP\in\mathbb R^{n\times n}. For a decision x∈Rnx\in\mathbb R^n consider the worst-case linear form under Euclidean-ball uncertaintysup⁡∥u∥2≤1 (a+Pu)⊤x.\sup_{\|u\|_2\le 1}\ (a+Pu)^\top x.Take the concrete dataa=(1,0),P=diag⁡(2,1),x=(1,2).a=(1,0),\qquad P=\operatorname{diag}(2,1),\qquad x=(1,2).1. Prove that the worst-case value equals a⊤x+∥P⊤x∥2a^\top x+\|P^\top x\|_2, and that a maximizing uu (when P⊤x≠0P^\top x\ne 0) is the unit vector u=P⊤x/∥P⊤x∥2u=P^\top x/\|P^\top x\|_2.

2. Evaluate a⊤xa^\top x, P⊤xP^\top x, the maximizing uu, and the robust value exactly at the given xx.

3. Write the robust inequalitya⊤x+∥P⊤x∥2 ≤ 4a^\top x+\|P^\top x\|_2\ \le\ 4as a second-order-cone constraint whose right-hand side is required to be nonnegative. State the nonnegativity condition explicitly.

4. Substitute the given xx and compute the SOC slack 4−a⊤x−∥P⊤x∥24-a^\top x-\|P^\top x\|_2. Confirm that the right-hand side 4−a⊤x4-a^\top x is positive and that the inequality holds.

5. Audit both sentences: (i) “∥P⊤x∥2\|P^\top x\|_2 may be replaced by the operator-norm bound ∥P∥2∥x∥2\|P\|_2\|x\|_2, so the robust value is 1+251+2\sqrt{5}”; (ii) “the SOC form ∥P⊤x∥2≤4−a⊤x\|P^\top x\|_2\le 4-a^\top x is valid even when 4−a⊤x4-a^\top x is negative, so nonnegativity of the right-hand side can be omitted.”

Do not replace the Euclidean uncertainty set by an ℓ∞\ell_\infty box, and do not introduce a semidefinite lift.

Hint

Hint

a⊤x=1a^\top x=1 and P⊤x=(2,2)P^\top x=(2,2), whose Euclidean norm is 222\sqrt{2}.

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.