Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 38 Ā· Projects and Practice

Practice Set: Duality, KKT and Solvers

Six worked practice problems on dual functions, LP duality, shadow prices, KKT points and proximal operators, each with a code check you can run to verify your answer.

The best way to learn convex optimization is to solve problems by hand and then check them with a computer. This practice set has six problems covering the chapter on duality, linear and quadratic programs, and proximal methods. For each one:

  1. Try it on paper first.
  2. Open the matching code check and run it. It prints the answer computed numerically.
  3. If your result differs, find out why. The mismatch is where the learning happens.

The hints are below each problem, and the full numeric checks come after the list.

The problems

Problem 1: dual function. Minimize x₁² + x₂² subject to x₁ + 2xā‚‚ ≄ 4. Write the Lagrangian with Ī» ≄ 0, find the dual function d(Ī»), maximize it and compare with the primal optimum.

Hint: write the constraint as 4 āˆ’ x₁ āˆ’ 2xā‚‚ ≤ 0. Minimizing the Lagrangian over x gives x = (Ī»/2, Ī»).

Problem 2: LP and its dual. Minimize 2x₁ + 3xā‚‚ subject to x₁ + xā‚‚ ≄ 4, x₁ + 3xā‚‚ ≄ 6, x ≄ 0. List the vertices, find the best one, then write the dual (maximize 4y₁ + 6yā‚‚ subject to y₁ + yā‚‚ ≤ 2, y₁ + 3yā‚‚ ≤ 3, y ≄ 0) and verify the dual has the same value.

Hint: the optimum has both main constraints tight.

Problem 3: shadow price. For Problem 1, replace the right-hand side 4 by u. Find p*(u) in closed form and verify that dp*/du at u = 4 equals the multiplier from Problem 1.

Hint: the optimal point lies along (1, 2); write it as t(1, 2).

Problem 4: a KKT point. Minimize (x₁ āˆ’ 1)² + (xā‚‚ āˆ’ 2)² subject to x₁ + xā‚‚ ≤ 2. Find the point and the multiplier, and state which KKT conditions you used.

Hint: the unconstrained minimizer (1, 2) breaks the constraint, so assume it is active.

Problem 5: proximal operator. Compute prox_{t f}(v) for f(x) = 2|x| with step t = 0.5, at v = 3, v = 0.8 and v = āˆ’2.5.

Hint: the threshold is tĪ» = 0.5 Ā· 2 = 1.

Problem 6: one ISTA step. For the lasso ½(aĀ·w āˆ’ b)² + Ī»|w| with a single weight a = 2, b = 5, Ī» = 1, start at w = 0 and run two ISTA steps with step size 1/L, where L = a² = 4.

Hint: the gradient of the smooth part is a(aĀ·w āˆ’ b), and the threshold is Ī»/L.

Checking the answers

The first block verifies Problems 1 to 3 with an independent method each (a grid search for the primal, a linear-program solver for the LP, and finite differences for the shadow price).

Python Checks for problems 1 to 3

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second block checks Problems 4 to 6. For Problem 6 it computes each ISTA step explicitly.

Python Checks for problems 4 to 6

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For Problem 6, you can check by hand that the exact minimizer is w* = (ab āˆ’ Ī»)/a² = 9/4 = 2.25. Because the problem has a single weight and L = a², ISTA lands on it in one step.

Answers in brief

Problem Answer
1 d(Ī») = 4Ī» āˆ’ 1.25λ², best Ī» = 1.6, d* = p* = 3.2, at x = (0.8, 1.6)
2 Best vertex (3, 1), value 9; dual y = (1.5, 0.5), value 9
3 p*(u) = u²/5, slope at u = 4 is 1.6 = Ī» (sign: for a ≄ constraint, raising u raises the cost)
4 x* = (0.5, 1.5), f* = 0.5, Ī» = 1
5 2, 0, āˆ’1.5
6 w = 2.25 after one step, and it stays there

If you could not solve a problem, re-read the matching lesson: dual function (lesson), KKT (lesson), shadow prices (lesson), LP (lesson), prox (lesson) and ISTA (lesson).

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. In Problem 1, why must the dual optimum equal the primal optimum?

    A convex QP with a feasible affine constraint satisfies Slater's condition (even in weak form), so there is no duality gap.
  2. 2. In Problem 2, which constraints are active at the optimal vertex (3, 1)?

    3 + 1 = 4 and 3 + 3Ā·1 = 6, so both main constraints hold with equality, matching the positive dual prices (1.5 and 0.5).
  3. 3. In Problem 5, what is prox at v = 0.8?

    Soft thresholding sets any value with magnitude at most tĪ» = 1 to zero.
  4. 4. For Problem 4, what would the multiplier be if the constraint were x₁ + xā‚‚ ≤ 5?

    The constraint is inactive, so complementary slackness forces Ī» = 0.

Summary

  • Solve by hand, then verify numerically: duality gives a built-in checker (primal and dual values must match).
  • Active constraints have positive multipliers; inactive ones have zero.
  • A multiplier is a derivative of the optimal value with respect to the constraint's right-hand side.
  • Prox of an L1 term is a soft threshold, and one ISTA step is a gradient step followed by that threshold.

Next: Project: Recovering a Sparse Signal