Engineering Optimisation Memorisation Sheet

Gradient Methods

1. Steepest Descent Method:

   • Example: For $f(x_1,x_2)=x_1^2+2x_2^2$, at point $[2,1]$
   • Gradient: $\nabla f=[2x_1,4x_2]=[4,4]$
   • With step size $\alpha =0.1$, next point: $[2,1]-0.1[4,4]=[1.6,0.6]$

2. Newton’s Method:

   • Example: For $f(x_1,x_2)=x_1^2+2x_2^2$
   • Gradient: $\nabla f=[2x_1,4x_2]$
   • Hessian: $H=\left[\begin{array}{cc}2& 0\\ 0& 4\end{array}\right]$
   • At point $[2,1]$: $x_{k+1}=[2,1]-\left[\begin{array}{cc}0.5& 0\\ 0& 0.25\end{array}\right][4,4]=[0,0]$ (exact solution in one step)

3. Condition Number:

   • Example: For $H=\left[\begin{array}{ccc}4& 00& 1\end{array}\right]$
   • Eigenvalues: ${\lambda }_1=4,{\lambda }_2=1$
   • Condition number: $\kappa =4/1=4$ (moderately conditioned)
   • For $H=\left[\begin{array}{ccc}100& 00& 0.1\end{array}\right]$, $\kappa =1000$ (ill-conditioned)

Constrained Optimization

4. Lagrangian Function:

   • Example: Minimize $f(x_1,x_2)=x_1^2+x_2^2$ subject to $x_1+x_2=1$
   • Lagrangian: $L(x_1,x_2,\lambda )=x_1^2+x_2^2-\lambda (x_1+x_2-1)$
   • Partial derivatives: $\frac{\partial L}{\partial x_1}=2x_1-\lambda$, $\frac{\partial L}{\partial x_2}=2x_2-\lambda$
   • Setting to zero: $x_1=x_2=\frac{\lambda }{2}$
   • From constraint: $x_1+x_2=\lambda =1$, so $x_1=x_2=0.5$

5. KKT Conditions:

   • Example: Minimize $f(x_1,x_2)=x_1^2+x_2^2$ subject to $x_1+x_2\le 1$ and $x_1,x_2\ge 0$
   • At unconstrained minimum $[0,0]$, all constraints satisfied, so that’s the solution
   • At $x_1=0.6,x_2=0.4$: $x_1+x_2=1$ (active), $x_1>0,x_2>0$ (inactive)
   • Active constraint needs multiplier $\lambda >0$
   • Inactive constraints have multipliers equal to zero Primal Feasibility:
     • $\theta \ge 0$
     • $\frac{\pi }{2}-\theta \ge 0$
     • $v\ge 0$
     • $1-v\ge 0$
     Dual feasibility:
     • ${\lambda }_1,{\lambda }_2,{\lambda }_3,{\lambda }_4\ge 0$
     Complementary Slackness
     • ${\lambda }_1\theta =0$, (either ${\lambda }_1$ or $\theta$ = 0)
     • ${\lambda }_2(\frac{\pi }{2}-\theta )=0$ (either ${\lambda }_2=0$ or $\theta =\frac{\pi }{2}$ )
     • ${\lambda }_{3}v=0$ (either ${\lambda }_3=0$ or $v=0$)
     • ${\lambda }_4(1-v)=0$ (either ${\lambda }_4=0$ or $v=1$ )

6. Active Constraints:

   • Example: Minimize $f(x_1,x_2)=(x_1-2{)}^2+(x_2-2{)}^2$ subject to $x_1+x_2\le 1$ and $x_1,x_2\ge 0$
   • Unconstrained minimum at $[2,2]$ violates $x_1+x_2\le 1$
   • At solution, $x_1+x_2=1$ is active (holds with equality)
   • Solution: $[0.5,0.5]$ with $\lambda >0$ for the active constraint

7. Penalty Method:

   • Example: Minimize $f(x)=x^2$ subject to $x-2=0$
   • Penalty function: $P(x,\mu )=x^2+\mu (x-2{)}^2$
   • For $\mu =1$: Minimum at $x=1$ (compromise between $f$ and constraint)
   • For $\mu =10$: Minimum at $x\approx 1.82$ (closer to feasible solution)
   • For $\mu =100$: Minimum at $x\approx 1.98$ (very close to feasible solution)

Least Squares and Curve Fitting

8. Linear Least Squares:

   • Example: Fit $y={\theta }_{1}x+{\theta }_0$ to points $(1,2)$ and $(2,3)$
   • Residuals: $r_1=2-({\theta }_1\cdot 1+{\theta }_0)$, $r_2=3-({\theta }_1\cdot 2+{\theta }_0)$
   • Jacobian: $J=\left[\begin{array}{cc}-1& -1\\ -1& -2\end{array}\right]$
   • Normal equations: $\left[\begin{array}{cc}2& 3\\ 3& 5\end{array}\right]\left[\begin{array}{c}{\theta }_0\\ {\theta }_1\end{array}\right]=\left[\begin{array}{c}58\end{array}\right]$
   • Solution: ${\theta }_0=1,{\theta }_1=1$

9. Gauss-Newton Method:

   • Example: For model $y={\theta }_1{e}^{{\theta }_{2}x}$ with data $(0,1)$ and $(1,0.5)$
   • Residuals: $r_1=1-{\theta }_1$, $r_2=0.5-{\theta }_1{e}^{{\theta }_2}$
   • Initial guess: ${\theta }_0=[2,-0.5]$
   • Jacobian at ${\theta }_0$: $J_0=\left[\begin{array}{cc}-1& 0\\ -0.607& -1.214\end{array}\right]$
   • $J_0^T{J}_0=\left[\begin{array}{cc}1.368& 0.736\\ 0.736& 1.474\end{array}\right]$, $J_0^T{r}_0=\left[\begin{array}{c}-0.696-0.598\end{array}\right]$
   • Update: $\Delta \theta \approx [0.68,0.2]$ z

Mathematical Foundations

10. Local vs. Global Minima:

    • Example: $f(x)=x^4-4x^2+2$
    • Local minima at $x=-1$ and $x=1$ with value $f(-1)=f(1)=-1$
    • Local maximum at $x=0$ with value $f(0)=2$
    • This function has two global minima

11. Positive Definite Test (2×2 matrix):

    • Example 1: $A=\left[\begin{array}{cc}2& 1\\ 1& 3\end{array}\right]$
      • First principal minor: $|2|=2>0$
      • Second principal minor (determinant): $|A|=2\cdot 3-1\cdot 1=5>0$
      • Therefore $A$ is positive definite
    • Example 2: $A=\left[\begin{array}{ccc}2& 33& 2\end{array}\right]$
      • First principal minor: $|2|=2>0$
      • Second principal minor: $|A|=2\cdot 2-3\cdot 3=4-9=-5<0$
      • Therefore $A$ is not positive definite (it’s indefinite)
    • Example 3: $A=\left[\begin{array}{ccc}2& 00& -1\end{array}\right]$
      • First principal minor: $|2|=2>0$
      • Second principal minor: $|A|=2\cdot (-1)-0\cdot 0=-2<0$
      • Therefore $A$ is not positive definite (it’s indefinite)

12. Convexity Test:

    • Example 1: $f(x_1,x_2)=x_1^2+x_2^2$
      • Hessian: $H=\left[\begin{array}{cc}2& 0\\ 0& 2\end{array}\right]$ is positive definite
      • Therefore $f$ is strictly convex
    • Example 2: $f(x_1,x_2)=x_1^2-x_2^2$
      • Hessian: $H=\left[\begin{array}{cc}2& 0\\ 0& -2\end{array}\right]$ has both positive and negative eigenvalues
      • Therefore $f$ is not convex (it’s a saddle)

These examples provide concrete illustrations of the key concepts, using small 2×2 matrices and simple functions for clarity and ease of calculation.