Constrained Optimization
Prithwijit Guha
Dept. of EEE, IIT Guwahati
Overview
• The Constrained Optimization Problem
• Contour Plot and Gradients
• Objective Function and Gradients
• The KKT Conditions
• Necessary Conditions
• Sufficient Conditions
• The Primal-Dual Formulation
Constrained Optimization: Definition & Formulation
Constrained Optimization is the Process of Maximizing or Minimizing
a Desired Objective Function while Satisfying a Set of Prevailing
Constraints
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑓 𝑋
Subject To
𝑔 𝑋 ≤ 0; 𝑖 = 1, … 𝑚 ℎ 𝑋 = 0; 𝑗 = 1, … 𝑙
𝑦
Contour Plot & Gradient
𝑧=6 1
𝛻𝑧 =
1
𝑧 = 𝑓 𝑥, 𝑦 = 𝑥 + 𝑦 − 1
𝑧=2
𝑧=0 𝑧=4 𝑧=8 𝑥
Objective Functions & Gradients: Linear Case
Objective Function
Increases/Decreases
along Gradient
Best Feasible
Solution
Feasible Region
Containing
Regular
Interior Points
Points
Objective Functions & Gradients (Contd.)
𝑀𝑖𝑛𝑚𝑖𝑧𝑒 𝑓(𝑋)
𝛻𝑓(𝑋)
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑔 𝑋 ≤0
𝛻ℎ(𝑋) 𝛻𝑔(𝑋) ℎ 𝑋 =0
Observation:
𝛻𝑓 𝑋 , 𝛻𝑔 𝑋 𝑎𝑛𝑑 𝛻ℎ 𝑋
𝑔(𝑋)
ℎ(𝑋) pass through the same point
𝑓(𝑋) Thus, we can write
𝛻𝑓 𝑋 + 𝜇𝛻𝑔 𝑋 + 𝜆𝛻ℎ 𝑋 = 0
Karush-Kuhn-Tucker (KKT) Conditions
Minimize 𝑓 𝑋 subject to 𝑔 𝑋 ≤ 0; 𝑖 = 1 … 𝑚 and ℎ 𝑋 = 0; 𝑗 = 1 … 𝑙
Construct Lagrangian Function L
𝐿 𝑋; 𝝁, 𝝀 = 𝑓 𝑋 + 𝜇𝑔 𝑋 + 𝜆ℎ 𝑋
Where, 𝝁 = { 𝜇 … 𝜇 … 𝜇 } and 𝝀 = {𝜆 … 𝜆 … 𝜆 }
KKT Conditions (Contd.)
𝐎𝐩𝐭𝐢𝐦𝐚𝐥𝐢𝐭𝐲: 𝛻 𝐿 𝑋; 𝝁, 𝝀 = 𝛻 𝑓 𝑋 + 𝜇𝛻 𝑔 𝑋 + 𝜆𝛻 ℎ 𝑋 =0
𝐍𝐨𝐧 − 𝐧𝐞𝐠𝐚𝐭𝐢𝐯𝐢𝐭𝐲: 𝜇 ≥ 0 ; 𝑖 = 1 … 𝑚
𝐂𝐨𝐦𝐩𝐥𝐞𝐦𝐞𝐧𝐭𝐚𝐫𝐢𝐭𝐲: 𝜇 𝑔 𝑋 = 0; 𝑖 = 1, … 𝑚
𝐅𝐞𝐚𝐬𝐢𝐛𝐢𝐥𝐢𝐭𝐲: 𝑔 𝑋 ≤ 0; 𝑖 = 1, … 𝑚 and ℎ 𝑋 = 0; 𝑗 = 1, … 𝑙
Necessary Conditions
KKT Conditions (Contd.)
𝑋 ∗ : Optimal Solution of 𝛻 𝐿 𝑋; 𝝁, 𝝀 = 0
Hessian Matrix 𝛻 𝐿 𝑋 ∗ ; 𝜇, 𝜆 𝑖𝑠 𝑃𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝐷𝑒𝑓𝑖𝑛𝑖𝑡𝑒 𝑖𝑛 𝑻 ⊂ ℝ
𝑻 = 𝑦: 𝛻𝑔 𝑋 ∗ 𝑦 = 0; 𝑖 = 1 … 𝑚 ∧ 𝛻ℎ 𝑋 ∗ y = 0; j = 1 … 𝑙
𝐒𝐮𝐟𝐟𝐢𝐜𝐢𝐞𝐧𝐭 𝐂𝐨𝐧𝐝𝐢𝐭𝐢𝐨𝐧: 𝒚𝑻 𝛻 𝐿 𝑋 ∗ ; 𝜇, 𝜆 y > 0; 𝑦 ≠ 0; 𝑦 ∈ 𝑻
𝐒𝐭𝐫𝐨𝐧𝐠𝐞𝐫 𝐂𝐨𝐧𝐝𝐢𝐭𝐢𝐨𝐧: 𝒚𝑻 𝛻 𝐿 𝑋 ∗ ; 𝜇, 𝜆 y > 0; 𝑦 ≠ 0; 𝑦 ∈ ℝ𝒏
Problem
Minimize 𝑓 𝑥 , 𝑥 = 2𝑥 + 𝑥
Subject To
ℎ 𝑥 ,𝑥 = 𝑥 +𝑥 −1 =0
Solution
𝐿 𝑥 , 𝑥 ; 𝜆 = 2𝑥 + 𝑥 + 𝜆(𝑥 + 𝑥 − 1)
𝜕𝐿 1 𝜕𝐿 1
=0→𝑥 =− =0→𝑥 =−
𝜕𝑥 𝜆 𝜕𝑥 2𝜆
√5
𝜆= ±
2
ℎ(𝑥 , 𝑥 ) B A= 𝑥 =−
2
,𝑥 = −
1
5 5
𝑓(𝑥 , 𝑥 ) 2 1
A B= 𝑥 =
5
,𝑥 =
5
𝑓(𝑥 , 𝑥 )
Primal-Dual Formulation
Minimize 𝑓 𝑋 subject to 𝑔 𝑋 ≤ 0; 𝑖 = 1 … 𝑚 and ℎ 𝑋 = 0; 𝑗 = 1 … 𝑙
𝑋 ∗ , 𝝁∗ , 𝝀∗ : Optimal Solution of the 𝐏𝐫𝐢𝐦𝐚𝐥 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝛻 𝐿 𝑋; 𝝁, 𝝀 = 0
(𝑋 ∗ , 𝝁∗ , 𝝀∗ ) is a 𝐒𝐚𝐝𝐝𝐥𝐞 𝐏𝐨𝐢𝐧𝐭 of 𝐿 𝑋; 𝝁, 𝝀 i.e.
𝐿(𝑋 ∗ , 𝝁, 𝝀) ≤ 𝐿(𝑋 ∗ , 𝝁∗ , 𝝀∗ ) ≤ 𝐿(𝑋, 𝝁∗ , 𝝀∗ )
(𝑋 ∗ , 𝝁∗ , 𝝀∗ ) 𝐬𝐨𝐥𝐯𝐞𝐬 𝐭𝐡𝐞 𝐟𝐨𝐥𝐥𝐨𝐰𝐢𝐧𝐠 𝐝𝐮𝐚𝐥 𝐩𝐫𝐨𝐛𝐥𝐞𝐦
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝐿 = 𝑓 + 𝝁 𝒈 + 𝝀 𝒉
𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑇𝑜 𝛁𝐿 = 0 ∧ [𝝁 ≥ 0]
Problem
Minimize 𝑓 𝑥 , 𝑥 = 𝑥 −3 + 𝑥 −3
𝐒𝐮𝐛𝐣𝐞𝐜𝐭 𝐓𝐨
g 𝑥 ,𝑥 = 2𝑥 + 𝑥 − 2 ≤ 0
g 𝑥 ,𝑥 = −𝑥 ≤ 0
g 𝑥 ,𝑥 = −𝑥 ≤ 0
Solution
𝐿 𝑥 ,𝑥 ;𝝁 = 𝑥 − 3 + 𝑥 −3 + 𝜇 2𝑥 + 𝑥 − 2 − 𝜇 𝑥 − 𝜇 𝑥
𝜕𝐿 𝜇 𝜕𝐿 𝜇 𝜇
=0→𝑥 = −𝜇 +3 =0→𝑥 = − +3
𝜕𝑥 2 𝜕𝑥 2 2
5𝜇 𝜇 𝜇 𝜇 𝜇
𝑄 𝝁 =− − − + + 𝜇 𝜇 + 7𝜇 − 3𝜇 − 3𝜇
4 4 4 2
Dual Function to be Maximized w. r. t. 𝝁
Applications
• Principal Component Analysis
• Linear Discriminant Analysis
• Factor Analysis
• Regularization
• Neural Network Learning
• Support Vector Machines
• Parameter Estimation And Many Others…
Summary
• Constrained Minimization
• Visualizations
• Contour Plots & Gradients
• Objective Functions & Gradients
• Feasible Regions and Best Solutions
• Karush-Kuhn-Tucker Conditions
• Necessary Conditions
• Sufficient Conditions
• Primal-Dual Formulations
• Applications
