Home / MLF / Week 9

Week 9 · Optimising with rules: Lagrange and KKT

Official syllabus line: Constrained Optimisation and Lagrange Multipliers. Logistic regression as an optimization problem

About 100 minEnd Term material (see exam radar)BSCS2004 · Harish Guruprasad Ramaswamy, Arun Rajkumar, Prashanth LA

Before you start: Week 2 (gradient), week 7 (critical points), week 8 (convexity). Comfort with solving two or three linear equations.

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine you're a hiker wanting the lowest point. But real life has rules! A shop owner seeks profit with limited labour. A farmer wants the biggest field with only so much fence. Or you want the shortest walk to a river, but must stay on the road. These rules are called constraints.
With constraints, the best spot isn't just where the ground is flat. It's where you cannot improve your goal without breaking a rule. The 'downhill arrow' of your objective and the 'wall' of the rule are in a perfect tug-of-war balance. This balance helps us find optimal solutions.
Let's find the point closest to the origin on a line. We minimise x squared plus y squared, subject to the line equation x plus two y equals five. We find the best point is where x is one and y is two. The minimum value, or squared distance, is five.
This topic is huge in exams! Linear programming questions about profit or diet, finding closest points, and KKT true/false problems appear often. Remember, constrained optimization is all about finding that perfect balance point, where you reach your goal without breaking any important rules. Keep practicing!

The one-minute story

Think of it like this

In week 7 you were a hiker free to roam anywhere. Real life has rules. A shop owner wants the most profit, but only has 80 hours of labour. A farmer wants the biggest field, but only owns 120 metres of fence. You want the shortest walk to a river, but you must stay on the road.

Rules like these are constraints. The best point is no longer where the ground is flat, but where you can't improve without breaking a rule. There the downhill arrow and the wall of the rule are in a tug-of-war that exactly balances. This week gives you three tools:

Lagrange multipliers: for rules that are exact equations ("stay on this road").
KKT conditions: for rules that are limits ("stay at most this far").
Linear programming: the everyday case where everything is a straight line (shops, farms, diets).

And at the end, a surprise: logistic regression, the classifier behind spam filters, is just an optimisation problem you can now read.

By the end of this week you can:

turn a word problem into "maximise or minimise ... subject to ...";
solve equality-constrained problems with Lagrange multipliers;
state the four KKT conditions and use complementary slackness;
solve a small linear programme by checking corner points;
write "closest point to the origin" problems as optimisation problems;
explain logistic regression as minimising a loss.

Words you need

Objective - the quantity to minimise or maximise.
Constraint - a rule the answer must obey: an equation $g(\mathbf x)=0$ or an inequality $g(\mathbf x)\le0$ .
Feasible point - a point that obeys all the rules. The set of all of them is the feasible region.
Lagrange multiplier $\lambda$ (or $\mu$ ) - a number attached to a constraint that tells how strongly the rule is pulling.
Active constraint - an inequality that is exactly tight at the solution ( $g=0$ ).
Primal problem - the original problem you want to solve.
Linear programme (LP) - linear objective, linear constraints.

Idea 1: Word problem $\to$ optimisation problem

Almost every question in this chapter starts with a story. Translate it in three moves:

What can I change? Name those numbers $x,y,\dots$ (the decision variables).
What do I want? Write the objective in terms of them.
What are the rules? Write each as an equation or inequality, and don't forget " $x,y\ge0$ ".

Solved example: 1. A shop's LP, set up and solved

Question. A workshop makes products $P_1$ and $P_2$ . Each $P_1$ takes 1 labour hour and 3 machine hours; each $P_2$ takes 2 labour hours and 2 machine hours. There are 80 labour hours and 120 machine hours. Profit is Rs 20 per $P_1$ and Rs 30 per $P_2$ . Find the best production plan.

Solution.

Variables: $x$ = number of $P_1$ , $y$ = number of $P_2$ .
Objective: maximise $20x+30y$ .
Constraints: labour $x+2y\le80$ ; machine $3x+2y\le120$ ; and $x,y\ge0$ .
Key fact: for a linear objective the best point of the feasible region is at a corner. List the corners:
- $(0,0)$ : profit $0$ .
- $(40,0)$ (machine limit with $y=0$ ): profit $800$ .
- $(0,40)$ (labour limit with $x=0$ ): profit $1200$ .
- Where the two limits cross: from $x+2y=80$ and $3x+2y=120$ , subtract: $2x=40$ , so $x=20$ , $y=30$ . Profit $400+900=\mathbf{1300}$ .
The best plan is 20 of $P_1$ and 30 of $P_2$ , profit Rs 1300. Check both limits are tight there: $20+60=80$ ✓ and $60+60=120$ ✓.

Comprehension questions in the papers usually ask in three parts: (a) the objective function (MCQ), (b) the constraints (MSQ), (c) the optimal value (numeric). Part (a) and (b) are pure translation; practise them a lot.

Idea 2: Equality constraints and Lagrange multipliers

Problem: minimise $f(\mathbf x)$ subject to $g(\mathbf x)=c$ .

Think of it like this

You are walking along a curved road (the constraint) and want the point where the altitude is lowest. At the lowest point on the road, if the ground still sloped downhill along the road you could keep walking and go lower. So at the best spot the downhill direction must point straight off the road, perpendicular to the road. And a road's perpendicular direction is exactly the gradient of its equation $g$ . So: $\nabla f$ and $\nabla g$ must point the same (or opposite) way.

\nabla f(\mathbf x)=\lambda\,\nabla g(\mathbf x),\qquad g(\mathbf x)=c

The number $\lambda$ is the Lagrange multiplier. Equivalent form: build the Lagrangian $L(\mathbf x,\lambda)=f(\mathbf x)-\lambda\big(g(\mathbf x)-c\big)$ and set all its partial derivatives to zero.

The exam recipe

Write $\nabla f=\lambda\nabla g$ : one equation per variable.
Add the constraint $g=c$ as the last equation.
Solve the system (it nearly always simplifies, often to a symmetry like $x=y$ or $y=2x$ ).
Put the point back into $f$ .

Solved example: 2. Closest point to the origin on a line

Question. Minimise $f(x,y)=x^2+y^2$ subject to $x+2y=5$ .

Solution.

$\nabla f=(2x,\,2y)$ , and $g=x+2y$ has $\nabla g=(1,\,2)$ . Recompute $\nabla g$ every time; it is where marks are lost.
$2x=\lambda\cdot1$ and $2y=\lambda\cdot2$ . So $y=2x$ .
Constraint: $x+2(2x)=5\Rightarrow x=1,\;y=2$ .
$f(1,2)=1+4=\mathbf5$ (and $\lambda=2$ ).

Geometric check: the squared distance from the origin to the line $x+2y=5$ is $\frac{25}{1^2+2^2}=5$ . ✓

Watch out - real exam trap

Do not carry a relation from one problem into the next. In $x+y=4$ you get $x=y$ because $\nabla g=(1,1)$ ; in $x+2y=5$ you get $y=2x$ because $\nabla g=(1,2)$ .

"Closest point" problems as optimisation problems

A very common question: "Choose the correct primal optimisation problem for finding the point of $S$ closest to the origin." The answer always has the same shape:

\min_{\mathbf x}\;\|\mathbf x\|^2\quad\text{subject to}\quad\mathbf x\in S

For a plane $\mathbf a^T\mathbf x=b$ the constraint is $\mathbf a^T\mathbf x=b$ ; for a disc of radius $r$ it is $\|\mathbf x\|^2\le r^2$ ; for a half-plane it is $\mathbf a^T\mathbf x\ge b$ . Closest point to some other point $\mathbf p$ : minimise $\|\mathbf x-\mathbf p\|^2$ .

Sometimes geometry beats algebra: the point of a circle of radius 2 (centre at the origin) closest to $(6,8)$ is on the ray from the origin to $(6,8)$ , at distance $\|(6,8)\|-2=10-2=\mathbf8$ . No calculus at all.

Idea 3: Inequality constraints and the KKT conditions

Now the rule is a limit: minimise $f(\mathbf x)$ subject to $g(\mathbf x)\le0$ . Two situations:

The unconstrained minimum is inside the allowed region: the rule does not bite. Solve as in week 7. The constraint is inactive.
The unconstrained minimum is outside: the best allowed point sits on the boundary, where $g=0$ . The constraint is active.

The KKT conditions (Karush-Kuhn-Tucker) cover both cases with one list. For $\min f(\mathbf x)$ s.t. $g(\mathbf x)\le0$ with multiplier $\mu$ :

The idea

Stationarity: $\nabla f(\mathbf x)+\mu\,\nabla g(\mathbf x)=\mathbf0$
Primal feasibility: $g(\mathbf x)\le0$ (the rule is obeyed)
Dual feasibility: $\mu\ge0$ (the rule can only push back, never pull)
Complementary slackness: $\mu\,g(\mathbf x)=0$ (either the rule is tight, or its multiplier is zero)

Complementary slackness is the part to love. It says: a rule that is not touching you has no influence ( $\mu=0$ ); a rule that does influence you ( $\mu>0$ ) must be exactly tight ( $g=0$ ). This is exactly why, in the support vector machine (MLT week 10), only the points on the margin carry any weight: those are the active constraints.

Solved example: 3. KKT in action, with two cases

Question. Minimise $f(x)=(x-2)^2$ subject to $x\le1$ . Then repeat with $x\le3$ .

Solution, $x\le1$ ( $g=x-1\le0$ ).

Try inactive ( $\mu=0$ ): stationarity gives $2(x-2)=0$ , $x=2$ . But $2\not\le1$ : violates primal feasibility. Reject.
Try active ( $g=0$ ): $x=1$ . Stationarity: $2(1-2)+\mu\cdot1=0\Rightarrow\mu=2$ . Dual feasibility: $\mu=2\ge0$ ✓. Complementary slackness: $\mu g=2\cdot0=0$ ✓.
Answer: $x^*=1$ , $\mu=2$ , $f=1$ . The wall at $x=1$ is pushing back with strength 2.

Solution, $x\le3$ ( $g=x-3\le0$ ). Try inactive: $x=2$ ; feasible ( $2\le3$ ), $\mu=0$ ✓. The wall at 3 is irrelevant; the answer is $x^*=2$ .

Two-case reasoning ("active or inactive?") is the standard way to solve a KKT problem by hand.

Solved example: 4. Which KKT statements are true?

Question. At the optimum of a minimisation problem with inequality constraint $g_1\le0$ and $g_2\le0$ , you find $\mu_1=3$ and $\mu_2=0$ . Which of the following must be true? (a) $g_1(\mathbf x^*)=0$ (b) $g_2(\mathbf x^*)=0$ (c) $g_2(\mathbf x^*)\le0$ (d) multipliers must be non-negative.

Solution. $\mu_1=3>0$ , so by complementary slackness constraint 1 is active: (a) true. $\mu_2=0$ says nothing about whether $g_2$ is tight: (b) not forced, it might be strictly negative. (c) true by primal feasibility. (d) true by dual feasibility for $\le$ constraints. Answer: (a), (c), (d).

Idea 4: Logistic regression as an optimisation problem

A spam filter wants to output a probability $p$ that an email is spam. For a feature vector $\mathbf x$ and weights $\mathbf w$ , take the score $z=\mathbf w^T\mathbf x$ and squash it into $(0,1)$ with the sigmoid

\sigma(z)=\frac1{1+e^{-z}},\qquad p=\sigma(\mathbf w^T\mathbf x)

So $z=0\Rightarrow p=0.5$ ; large positive $z\Rightarrow p\approx1$ ; large negative $z\Rightarrow p\approx0$ .

How do we choose $\mathbf w$ ? Pick the weights that make the observed labels most probable. For labels $y_i\in\{0,1\}$ the likelihood of the data is $\prod p_i^{y_i}(1-p_i)^{1-y_i}$ . Taking $-\log$ and averaging gives the cross-entropy (log-loss):

\mathcal L(\mathbf w)=-\frac1n\sum_{i=1}^n\Big[y_i\log\sigma(\mathbf w^T\mathbf x_i)+(1-y_i)\log\big(1-\sigma(\mathbf w^T\mathbf x_i)\big)\Big]

Training = minimise $\mathcal L$ : an unconstrained optimisation problem, and convex (week 8), so any minimum is the global one. Its gradient has a lovely form:

\nabla\mathcal L=\frac1n\sum_i\big(\sigma(\mathbf w^T\mathbf x_i)-y_i\big)\,\mathbf x_i

"prediction minus truth, times the features". There is no closed-form solution, so we use gradient descent (week 7). MLT week 9 and MLP week 5 build on exactly this.

Solved example: 5. A probability from a trained model

Question. A trained model has $\mathbf w=(1,-2)$ and bias $b=0.5$ . For $\mathbf x=(2,1)$ , what is the probability of class 1, and which class does it predict?

Solution. $z=1\cdot2-2\cdot1+0.5=0.5$ . $p=\sigma(0.5)=\frac1{1+e^{-0.5}}=\frac1{1+0.6065}\approx\mathbf{0.622}$ . Since $p>0.5$ it predicts class 1. The decision boundary is where $z=0$ , a straight line.

Your turn

Your turn: 1. Lagrange

Minimise $x^2+y^2$ subject to $2x+y=10$ .

Need a hint?

$\nabla g=(2,1)$ .

Show the full solution

$2x=2\lambda$ , $2y=\lambda$ , so $x=\lambda$ and $y=\lambda/2$ , hence $x=2y$ . Constraint: $4y+y=10$ , $y=2$ , $x=4$ . Minimum value $16+4=\mathbf{20}$ . (Check: distance $^2$ from the origin to the line $=\frac{100}{4+1}=20$ ✓.)

Your turn: 2. A different shape

Maximise $f(x,y)=xy$ subject to $x+y=10$ .

Need a hint?

$\nabla f=(y,x)$ and $\nabla g=(1,1)$ .

Show the full solution

$y=\lambda$ and $x=\lambda$ , so $x=y$ . Constraint: $x=y=5$ . Maximum value $\mathbf{25}$ . (A rectangle of fixed perimeter has the biggest area when it is a square.)

Your turn: 3. KKT with two cases

Minimise $f(x)=x^2$ subject to $x\ge1$ (write it as $1-x\le0$ ). Find $x^*$ and $\mu$ .

Need a hint?

Try "inactive" first and see whether you obey the rule.

Show the full solution

Inactive: $\mu=0\Rightarrow x=0$ , but $0\ge1$ is false. So the constraint is active: $x=1$ . Stationarity $2x+\mu(-1)=0\Rightarrow\mu=2\ge0$ ✓. So $x^*=1$ , $\mu=2$ , $f=1$ .

Your turn: 4. Set up an LP

A diet needs at least 60 units of vitamin A and 80 of vitamin B. Food 1 costs Rs 3 and gives (3 A, 2 B) per pack; Food 2 costs Rs 4 and gives (1 A, 4 B). Write the LP. Then find the minimum cost.

Need a hint?

Minimise cost; the constraints are "at least".

Show the full solution

Minimise $3x+4y$ s.t. $3x+y\ge60$ , $2x+4y\ge80$ , $x,y\ge0$ . Corners: $(0,60)$ : cost 240. $(40,0)$ : constraint 1 gives $120\ge60$ ✓ and $80\ge80$ ✓: cost 120. Intersection of the two limits: $3x+y=60$ , $2x+4y=80$ : from the first $y=60-3x$ , then $2x+240-12x=80$ , $x=16$ , $y=12$ : cost $48+48=96$ . Minimum cost Rs 96 at $(16,12)$ .

Your turn: 5. Which is the primal problem?

Write the problem of finding the point of the plane $x+2y+3z=6$ closest to the origin.

Need a hint?

Closest to the origin means minimise the squared length.

Show the full solution

$\min_{x,y,z}\;x^2+y^2+z^2$ subject to $x+2y+3z=6$ . (Lagrange gives $(x,y,z)=\lambda'(1,2,3)$ with $14\lambda'=6$ : the point $\frac37(1,2,3)$ and minimum value $\frac{36}{14}=\frac{18}7$ .)

Exam radar

This is the single biggest block of the End Term, and it repeats the same shapes:

Linear-programming comprehension sets appear in nearly every paper: TV sets at Rs 510/Rs 675 profit (7 times), products with labour and machine hours (8 times), hens and eggs, trucks vs vans, brownies vs cheesecake, and the consumer utility problem (7 times). Each has an objective (MCQ), constraints (MSQ) and an optimal value (SA).
"Choose the correct primal optimisation problem" (closest point to the origin) about 14 times; KKT true/false about 12; Lagrange closest-point problems about 4; complementary slackness once in 2026.
The summaries mention KKT conditions in 14 papers, Lagrange multipliers in 10, stationarity/dual feasibility/primal feasibility in 10 each, complementary slackness in 11, constrained optimisation in 8.

Watch out - real exam trap

Recompute $\nabla g$ for each new constraint; do not reuse a relation.
KKT dual feasibility is $\mu\ge0$ for a $\le$ constraint. If the problem is written with $\ge$ , rewrite it as $\le$ first.
Zero multiplier does not mean the constraint is slack, only that it may be.
In an LP, don't forget $x,y\ge0$ when listing the corners.
Answer what is asked: sometimes the value of the objective, sometimes a variable, sometimes a multiplier.

Quick quiz

At a constrained minimum with an equality constraint, the gradient of f and the gradient of g are...

perpendicular to each other
parallel (one is a multiple of the other)
both zero
equal in length

That is the Lagrange condition: grad f = lambda times grad g.

Complementary slackness says...

mu is always positive
mu times g(x) equals zero
g(x) is always zero
f(x) equals zero

Either the constraint is tight (g = 0) or its multiplier is zero.

The maximum of a linear function over a polygon is always attained...

in the exact middle
at a corner
on the longest edge only
nowhere

For a linear objective, an optimum is at a vertex (corner) of the feasible region.

Select all TRUE statements about logistic regression. (select all that apply)

The model outputs a probability between 0 and 1.
Training minimises a convex loss.
It has a simple closed-form solution like least squares.
Its predicted probability can be negative.

The sigmoid keeps probabilities in (0,1); training is done with gradient descent because there is no closed form.

Recap

Remember this

Translate stories into: variables, objective, constraints (and $x,y\ge0$ ).
Lagrange: $\nabla f=\lambda\nabla g$ plus $g=c$ . Recompute $\nabla g$ each time.
KKT for $g\le0$ : stationarity, primal feasibility, dual feasibility ( $\mu\ge0$ ), complementary slackness ( $\mu g=0$ ). Solve by "active or inactive?".
LP: optimum at a corner. Check each corner.
Closest point to the origin: $\min\|\mathbf x\|^2$ s.t. the set. Logistic regression: minimise convex log-loss with gradient descent.

Formulas to keep

Lagrange: $\nabla f=\lambda\nabla g$ , $g=c$ ; Lagrangian $L=f-\lambda(g-c)$
KKT ( $g\le0$ ): $\nabla f+\mu\nabla g=0$ ; $g\le0$ ; $\mu\ge0$ ; $\mu g=0$
Distance $^2$ from origin to $\mathbf a^T\mathbf x=b$ : $b^2/\|\mathbf a\|^2$ ; closest point $=\frac{b}{\|\mathbf a\|^2}\mathbf a$
LP: optimum at a vertex of the feasible region
Sigmoid: $\sigma(z)=\frac1{1+e^{-z}}$ ; log-loss $-\frac1n\sum[y\log p+(1-y)\log(1-p)]$ ; gradient $\frac1n\sum(p_i-y_i)\mathbf x_i$

Connected weeks (learn them together)

MLT week 10 - Support vector machines: The SVM dual comes straight out of Lagrange multipliers and the KKT conditions.
MLT week 9 - Perceptron and logistic regression: Logistic regression written as an optimisation problem.
MLP week 5 - Logistic regression in sklearn: Logistic regression in sklearn.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 23 real questions on this week All End Term papers

Week 9 · Optimising with rules: Lagrange and KKT

The one-minute story

Words you need

Idea 1: Word problem →\to→ optimisation problem

Idea 2: Equality constraints and Lagrange multipliers

"Closest point" problems as optimisation problems

Idea 3: Inequality constraints and the KKT conditions

Idea 4: Logistic regression as an optimisation problem

Your turn

Exam radar

Quick quiz

Recap

Practise with real exam questions

Idea 1: Word problem $\to$ optimisation problem