Optimization

What is the gradient of f(x₁,x₂)=½x₁²+½x₂²+ax₁x₂−x₁−x₂?

∇f=[x₁+ax₂−1,\;x₂+ax₁−1]ᵀ.

What is the Hessian of f(x₁,x₂)=½x₁²+½x₂²+ax₁x₂−x₁−x₂?

H=[[1,a],[a,1]].

What are the eigenvalues of the Hessian H=[[1,a],[a,1]]?

λ₁=1+a and λ₂=1−a.

When is H=[[1,a],[a,1]] positive definite?

When |a|<1.

When is H=[[1,a],[a,1]] positive semidefinite?

When |a|≤1.

When is H=[[1,a],[a,1]] indefinite?

When |a|>1.

What happens to the optimization problem when |a|<1?

The objective is strictly convex and has a unique global minimizer.

What happens when a=1?

The Hessian is singular and the function is convex but not strictly convex.

What happens when a=-1?

The Hessian is singular and the function is convex but not strictly convex.

What happens when |a|>1?

The Hessian is indefinite and the function is nonconvex.

How does increasing a affect the contour lines?

The contours become increasingly tilted due to stronger coupling between x₁ and x₂.

What is the stationary-point equation for the function?

x₁+ax₂−1=0 and ax₁+x₂−1=0.

What is the unconstrained minimizer when |a|<1?

x₁*=x₂*=1/(1+a).

What is the unconstrained minimizer when a=1/2?

(x₁,x₂)=(2/3,2/3).

What is the unconstrained minimizer when a=1?

The stationary-point equations reduce to x₁+x₂=1, giving infinitely many minimizers.

Why does a=1 produce infinitely many minimizers?

The Hessian has a zero eigenvalue, creating a flat direction.

What are the contour lines when a=0?

Circular contours centered around the minimizer.

What are the contour lines when 0<a<1?

Tilted ellipses.

What are the contour lines when |a|>1?

Hyperbolic or saddle-shaped contours.

What does the cross term ax₁x₂ represent?

Coupling between the variables x₁ and x₂.

What is the unconstrained optimization first-order condition?

∇f(x)=0.

What is the second-order sufficient condition for a strict minimum?

∇f(x)=0 and Hessian positive definite.

What is the constrained optimization problem?

Minimize f(x) subject to gᵢ(x)≤0.

What is g₁(x₁,x₂)?

x₁²+x₂²−4x₁−2x₂+4≤0.

How can g₁ be rewritten in completed-square form?

(x₁−2)²+(x₂−1)²≤1.

What geometric region does g₁ define?

A disk centered at (2,1) with radius 1.

What is g₂(x₁,x₂)?

−x₁+2≤0.

How can g₂ be rewritten?

x₁≥2.

What geometric region does g₂ define?

The half-plane to the right of x₁=2.

What is the feasible region?

The intersection of the disk and the half-plane.

What are the boundary points where both constraints are active?

(2,0) and (2,2).

What does an active constraint mean?

A constraint satisfying gᵢ(x)=0 at the solution.

What does an inactive constraint mean?

A constraint satisfying gᵢ(x)<0 at the solution.

What is the Lagrangian for this problem?

L=f+λ₁g₁+λ₂g₂.

What is the full Lagrangian?

L=f+λ₁(x₁²+x₂²−4x₁−2x₂+4)+λ₂(−x₁+2).

What are the KKT conditions?

Stationarity, primal feasibility, dual feasibility, and complementary slackness.

What is primal feasibility?

All constraints satisfy gᵢ(x)≤0.

What is dual feasibility?

All multipliers satisfy λᵢ≥0.

What is complementary slackness?

λᵢgᵢ(x)=0 for every constraint.

What is the stationarity condition?

∇f+Σλᵢ∇gᵢ=0.

Why are KKT conditions important?

They characterize optimal solutions for constrained optimization problems.

When are KKT conditions necessary?

Under suitable constraint qualifications.

When are KKT conditions sufficient?

For convex problems with convex constraints.

What is the gradient of g₁?

∇g₁=[2x₁−4,\;2x₂−2]ᵀ.

What is the gradient of g₂?

∇g₂=[−1,\;0]ᵀ.

What is the stationarity equation for this problem?

∇f+λ₁∇g₁+λ₂∇g₂=0.

What does λ₁ measure?

The sensitivity of the optimal objective value to changes in constraint g₁.

What does λ₂ measure?

The sensitivity of the optimal objective value to changes in constraint g₂.

What is the economic interpretation of a Lagrange multiplier?

The shadow price of a constraint.

What does λᵢ=0 imply?

The constraint is inactive or not affecting the optimum.