Lagrange Relaxation Flashcards
(17 cards)
Why do we remove w and b in Lagrange Relaxations?
By removing w and b, we can prevent the transformation from becoming too expensive
What is the Lagrange multiplier?
A penalty to the objective when the constraint is destroyed
What is the notation for the Lagrange multiplier for a single constraint?
min x {F(x) + af(x)}
where a >= 0 subject to f(x) <= 0
What is the notation for the Lagrange multiplier for multiple constraints?
min x {F(x) + Σaifi(x)}
where ai >= 0, i ∈ {1,..,N}
where ai >= 0 subject to fi(x) <= 0
What is the Lagrange equal to when a feasible solution is found?
L(x,a) <= f(x)
What happens when the constraint is violated?
When the constraint is violated, the penalty is infinitely large. This is what the optimisation is trying to avoid
What happens when no constraint is violated?
The penalty is zero, so L(x,a) = F(x)
Why do we use the dual formation?
The dual formation moves the constrained optimisation problem outside of the unconstrained one, which may be easier to solve as dual formation can solve the unconstrained problem in closed form and reduce the number of variables.
What is weak duality?
When the dual formation is not equivalent to the primal formation
What is an example of a primal Lagrange? What is minimised and what is maximised?
minimise x, maximise a:
min x max a {F(x) + Σaifi(x)}
where ai >= 0
What is an example of a dual Lagrange? What is minimised and what is maximised?
minimise x, maximise a:
max a min x {F(x) + Σaifi(x)}
where ai >= 0
For convex optimisation problem with convex constrains, what is equivalent?
Dual maxmin is equivalent minmax
What are the Karush-Kuhn-Tucker (KKT) conditions.
- In unconstrained convex optimisation, optimality is ∇F(x) = 0
- KKT are necessary for optimality in a convex optimisation problem minxF(x) with convex inequality constraints fi(x) <= 0
- A solution x is optimal for primal and a solution a for dual iff stationarity, complementary slackness and feasibility.
What is stationarity in KKT conditions?
In max a min x, for each fixed value a we minimised an unconstrained problem w.r.t x so:
∇x L(x,a) = ∇x F(x) + Σai ∇xfi(x) = 0
What is complementary slackness for KKT conditions?
aifi(x) = 0, ∀i ∈ {1,..,N}
What is feasibility in for KKT conditions?
Primal and dual constrains must be satisfied:
- fi(x) <= 0
- ai >= 0
What does the complexity primal vs dual formulations depend upon?
Primal depends on the number of dimensions where as dual formulations depend on the number of training examples which allow for high dimensional embedding via the kernel trick
