Katkat
Back

Solve a constrained problem using KKT conditions

ImcData Scientist · Onsite
MediumData ScientistOnsiteMachine Learning

Last updated

This question tests the ability to solve a convex optimization problem under inequality constraints using KKT conditions and the identification of active versus inactive constraints.

Constrained Optimization Problem

Consider a function f(x, y) = (x - 2)^2 + (y - 3)^2 representing the squared distance from a point (x, y) to the target point (2, 3). We want to minimize f(x, y) subject to the following inequality constraint:

g(x, y) = x + y - 1 <= 0

Task

  1. Write down the Lagrangian function L(x, y, lambda) for this problem, where lambda is the KKT multiplier.
  2. State the KKT conditions (Stationarity, Primal Feasibility, Dual Feasibility, and Complementary Slackness).
  3. Determine the optimal point (x*, y*) and the value of lambda by testing whether the constraint is active or inactive.

Constraints

  • x, y are real numbers.
  • lambda >= 0.

Example

If we were minimizing f(x) = x^2 subject to x >= 1, the optimal solution would be x = 1 because the unconstrained minimum x = 0 violates the constraint.

Edge Cases

  • What happens if the unconstrained global minimum of f satisfies g(x, y) <= 0?
  • Consider the case where the optimal solution lies exactly on the boundary x + y = 1.

Hints

Hint 1

Check if the unconstrained minimum of f(x, y) = (2, 3) satisfies the constraint x + y - 1 <= 0.

Hint 2

If the unconstrained minimum violates the constraint, the optimal solution must lie on the boundary where x + y = 1 (the active constraint).

Hint 3

Use the stationarity condition (gradient of L = 0) and the boundary equation to solve for x, y, and lambda.

Follow-up questions

  • How would the solution change if the constraint were instead an equality constraint (x + y = 1)?
  • What does the value of lambda represent in terms of the sensitivity of the objective function to changes in the constraint?
  • If we added a second constraint x <= 0, how would you determine which constraints are active at the optimum?