Question 1 [15 marks]
(a) Describe the meaning of local and global minimum using hypothetical examples and plots. Include a discussion of how convexity relates to the existence of local and global minima. [5]
(b) Consider the maximisation problem:
Starting at , perform three updates using steepest descent method with a constant step size . [7]
| g | ||
|---|---|---|
| 2 | -2 | 0.15 * -2 = -0.3 |
| 1.7 | 1.33 | 0.15 * 1.33 = 0.1995 |
| 1.9 | -0.83 | -0.1245 |
| 1.7735 | 0.54 | 0.085 |
(c) Consider the optimisation problem:
Starting at , determine if Newton’s method would converge to the minimum in a single iteration. Explain your answer. [3]
Also, our eigen values would be and , and they are both positive meaning our hessian is constant and positive definite. In addition to this, our equation is quadratic
Question 2 [15 marks]
(a) Consider the following objective function:
Find its stationary point by solving the necessary conditions. Check whether this stationary point is minimum, maximum, or a saddle point. [5]
Therefore, one of the eigenvalues will be positive and another will be negative, therefore this is a saddle point
(b) Can we use the standard Newton method to numerically find a maximum? Explain why or why not, and suggest any modifications that would make it suitable for maximization problems. [4]
The easiest way to do a maximisation problem is to multiply the objective function by -1
(c) Consider the objective function . Show that the point satisfies the necessary conditions. Calculate the condition number of the Hessian at this point and discuss the implications for optimization algorithms. [6]
At this evaluates to which correctly satisfies the necessary condition
λ₁ ≈ 1001.6 and λ₂ ≈ 0.4
Question 3 [20 marks]
(a) When an incompressible hyperelastic material is stretched in two perpendicular directions by pressures and , its total energy can be written as:
subject to an incompressibility constraint . Assume , , and .
Write the necessary condition(s) to find the minimum of by using:
- Method of reduction (eliminating )
- Method of Lagrange multiplier [10]
Neccesary conditions:
Lagrange
= = 0 = = 0 =0
(b) Consider the following constrained optimization problem: subject to
Apply both the method of Lagrange multipliers and the method of elimination to solve this problem. Show all steps and verify that both methods yield the same solution. [10]
DO LATER
Question 4 [15 marks]
(a) Explain the penalty method for solving constrained optimization problems. Specifically, describe how the following constrained problem:
can be transformed into an unconstrained problem using a quadratic penalty function. [5]
The penalty method transforms constrained optimization problems into unconstrained problems by adding penalty terms to the objective function. For the problem subject to and , we construct an unconstrained penalty function , where is the penalty parameter. As μ increases, minimizing yields solutions that progressively approach feasibility with respect to the constraints. For equality constraints , the term penalizes any deviation from zero, becoming increasingly severe as μ grows. Similarly, for inequality constraints h(x) ≤ 0, the term ensures only constraint violations are penalized. The method works iteratively: starting with a small μ, we solve the unconstrained problem, then increase μ and repeat until constraint violations become sufficiently small. While simple to implement, the method has limitations including ill-conditioning at large μ values and only approximate constraint satisfaction. Nevertheless, it provides an effective approach for solving constrained problems using unconstrained optimization techniques.
(b) Consider the problem:
Formulate this as an unconstrained problem using the quadratic penalty method. Then solve the unconstrained problem for penalty parameter . Comment on the accuracy of the solution compared to the exact solution. [6]
Solve Using the quadratic penalty method, we transform this into an unconstrained problem:
For , we need to minimize:
To find the minimum, we compute the gradient of and set it to zero:
From the second equation: , which means
From the first equation: , which means
These two equations imply . Substituting this into either equation:
Since , we have as well.
To check the accuracy against the exact solution, we note that the original constraint combined with minimizing gives the exact solution (by symmetry).
Our penalty method solution is close to but not exactly equal to the true solution. The constraint satisfaction is:
The constraint violation is small but not zero, which is expected with the penalty method. As increases, the solution would converge closer to the exact solution with better constraint satisfaction. This demonstrates how the penalty method provides an approximate solution that balances minimizing the objective function with satisfying the constraints.
(c) Describe the augmented Lagrangian method and explain how it addresses the limitations of the penalty method. What is the main advantage of the augmented Lagrangian approach over the standard penalty method? [4]
solution The augmented Lagrangian method combines elements of both penalty methods and Lagrangian methods to overcome limitations of the standard quadratic penalty approach. For a constrained problem:
The augmented Lagrangian function is defined as:
where is the Lagrange multiplier vector and is the penalty parameter.
The key difference from the standard penalty method is the inclusion of the Lagrangian term , which significantly improves convergence properties. The algorithm proceeds iteratively by:
- Minimizing with respect to while keeping and fixed
- Updating the Lagrange multipliers:
- Optionally increasing the penalty parameter to
- Repeating until convergence
The main advantage of the augmented Lagrangian method over the standard penalty method is that it can achieve exact constraint satisfaction without requiring the penalty parameter to approach infinity. This addresses the primary limitation of the penalty method, which suffers from numerical ill-conditioning as becomes very large.
With the augmented Lagrangian approach, the Lagrange multiplier estimates improve with each iteration, effectively “learning” the correct values needed at the solution. This allows the method to maintain well-conditioned subproblems even as the solution approaches the constraint boundary, resulting in better numerical stability and faster convergence.
Furthermore, while the penalty method often requires extremely large penalty parameters to achieve acceptable constraint satisfaction, the augmented Lagrangian method can obtain exact constraint satisfaction with moderate values of , leading to better-conditioned problems and more reliable solutions.
Extra
Consider the simple constrained optimization problem:
We form the augmented Lagrangian:
Let’s implement the augmented Lagrangian algorithm:
Step 1: Initialize , , and starting point .
Iteration 1: Minimize
Taking partial derivatives and setting them equal to zero:
From these equations, we get and , which gives .
Update the Lagrange multiplier:
Increase penalty parameter to .
Iteration 2: Minimize
Taking partial derivatives:
From these, we get and solving:
So .
Update the Lagrange multiplier:
Iteration 3: With and , we minimize .
Following similar calculations, we would find that approaches more closely.
After a few more iterations, we would converge to the exact solution with .
The augmented Lagrangian method successfully drives the solution to the exact constrained minimum while avoiding the need for extremely large penalty parameters. Each update of the Lagrange multiplier improves our estimate of the optimal value, accelerating convergence compared to the standard penalty method.
Question 5 [15 marks]
(a) Define the concept of Pareto optimality in multi-objective optimization. Explain what is meant by a Pareto front and provide an example of a bi-objective optimization problem with its Pareto front. [5]
Pareto optimality is a fundamental concept in multi-objective optimization where we simultaneously optimize two or more conflicting objectives. A solution is Pareto optimal (or non-dominated) if no other solution can improve one objective without worsening at least one other objective.
More formally, for a multi-objective problem minimizing objectives , a solution x^_ is Pareto optimal if there exists no other feasible solution such that f_i(x) \leq f_i(x^_) for all and for at least one .
The Pareto front is the set of all Pareto optimal solutions plotted in the objective space. It represents the fundamental trade-off between competing objectives.
Example: Consider a portfolio optimization problem with two objectives: maximize return and minimize risk. The Pareto front would show all efficient portfolios where we cannot increase return without increasing risk, or decrease risk without decreasing return. This curve illustrates the classic risk-return tradeoff in finance.
(b) Consider the following bi-objective optimization problem:
Identify the Pareto optimal solutions and sketch the Pareto front. [4]
(c) Describe the weighted sum method for solving multi-objective optimization problems. What are its advantages and limitations? Apply this method to the problem in part (b) with weights and . [6]
The weighted sum method converts a multi-objective problem into a single-objective problem by assigning weights to each objective and summing them:
where and typically .
Advantages:
- Simple to implement
- Each optimal solution to the weighted problem is Pareto optimal
- Intuitive interpretation of weights as relative importance
Limitations:
- Cannot find all Pareto optimal points for non-convex Pareto fronts
- Uniform distribution of weights doesn’t guarantee uniform distribution of solutions along the Pareto front
- Sensitivity to scaling of objectives
Applying this to our problem with and :
Taking the derivative and setting it equal to zero:
Therefore, the optimal solution using the weighted sum method with these weights is , giving objective values and . This is one point on the Pareto front, and by varying the weights, we could generate other points along the front.
End of examination paper
To find the Pareto optimal solutions, we need to find points where improving one objective necessarily worsens the other.
For this problem:
- is minimized at with value
- is minimized at with value
For any , both objectives get worse compared to , so such points are dominated. For any , both objectives get worse compared to , so such points are dominated.
For , decreasing improves but worsens , while increasing improves but worsens . Therefore, all points in the range are Pareto optimal.
The Pareto front is the curve of points for . This forms a convex curve in the objective space, starting at when and ending at when .
Question 6 [15 marks]
Consider a variational problem in mechanics to find the shape of a flexible chain hanging under its own weight (the famous catenary problem).
(a) The potential energy of the chain can be described by the functional: where is the height of the chain at horizontal position , is a positive constant related to the chain’s weight, and the chain has fixed endpoints at and .
Derive the Euler-Lagrange equation for this functional, and show that it leads to: [6]
(b) Show that a solution to this Euler-Lagrange equation has the form: where and are constants determined by boundary conditions. [6]
(c) Explain how this variational approach to the catenary problem relates to the more general principle of minimum potential energy in mechanics. How would the Euler-Lagrange formulation change if we added a constraint that the chain must have a fixed length? [3]
(a) To derive the Euler-Lagrange equation, we use the general form:
where is the integrand of our functional.
First, let’s calculate the partial derivatives:
Substituting these into the Euler-Lagrange equation:
Therefore:
(b) To solve this differential equation, let’s set:
where is a constant of integration. This is equivalent to:
So:
Integrating again:
where is another constant of integration.
This confirms that the solution has the form:
The constants and would be determined by the boundary conditions and .
(c) The variational approach to the catenary problem exemplifies the principle of minimum potential energy in mechanics, which states that a system in equilibrium adopts a configuration that minimizes its total potential energy. For the hanging chain, the energy consists of gravitational potential energy (proportional to height ) and tensile energy (proportional to length, represented by the term).
If we added a constraint that the chain must have a fixed length , we would modify our approach using the method of Lagrange multipliers. The length constraint would be:
We would then form a new functional:
where is a Lagrange multiplier. This would lead to a modified Euler-Lagrange equation:
The solution would still be a catenary, but the parameters would be adjusted to satisfy the length constraint, effectively finding the catenary that has exactly length while minimizing potential energy.