Optimisation, Numerical Methods and Algorithmic Efficiency

Introduction

Information technology routinely requires decisions under constraints, approximate computation, and efficient use of limited resources. Examples include assigning servers to workloads, selecting a route through a network, estimating a root of an equation, and deciding whether an algorithm will finish within an acceptable time. These activities connect three areas of mathematics:

• Optimisation, which selects the best feasible solution;
• Numerical methods, which approximate solutions when exact algebra is impractical; and
• Algorithmic efficiency, which measures how computational cost grows as input size increases.

A mathematically sound computational solution must be not only correct in principle but also feasible, sufficiently accurate, efficient, and transparent about its assumptions.

Learning Objectives

By the end of this chapter, you should be able to:

1. Formulate decision problems using objective functions, variables, constraints, and feasible regions.
2. Distinguish continuous, discrete, constrained, and unconstrained optimisation problems.
3. Apply graphical and derivative-based methods to simple optimisation problems.
4. Use bisection and Newton’s method to approximate equation roots.
5. Explain absolute error, relative error, conditioning, and floating-point limitations.
6. Compare algorithms using Big-O, Big-Theta, and Big-Omega notation.
7. Evaluate computational solutions using accuracy, feasibility, robustness, and scalability.

1. Mathematical Formulation of Decision Problems

An optimisation model represents a decision situation mathematically. Its essential components are:

A general constrained optimisation problem can be written as

Here, x is the vector of decision variables, f(x) is the objective, g_i(x) are inequality constraints, h_j(x) are equality constraints, and S specifies domains such as non-negative real numbers or integers. The model is meaningful only when units, data quality, and the interpretation of every constraint are clear.

Linear programming

A linear program has a linear objective and linear constraints:

The vector x contains decision variables, c contains objective coefficients, A is the constraint-coefficient matrix, and b contains resource limits. Every term must have compatible units. For example, a money objective may combine monetary contributions, while a memory constraint must combine memory quantities.

Example: cloud-resource allocation

A small organisation can deploy two services. Let x be the number of standard instances and y the number of high-memory instances. Suppose each standard instance earns 3 units of benefit and consumes 2 units of CPU capacity; each high-memory instance earns 5 units and consumes 4 units. With at most 20 CPU units and at most 8 instances:

The integrality condition is essential: a fraction of an instance is not normally deployable. If integrality is temporarily ignored, the model is a linear programming relaxation; rounding its answer may violate constraints or fail to be optimal.

2. Feasible Regions and Optimality

For two variables, each inequality defines a half-plane. Their intersection is the feasible region. In a linear program, if a finite optimum exists, at least one optimum occurs at a vertex (corner point) of the feasible polygon. This is the geometric basis of the simplex method, although practical solvers use more sophisticated variants and interior-point methods.

For the cloud example, the boundary lines are 2x + 4y = 20 and x + y = 8. Their relevant intersections include:

• (0,0);
• (8,0);
• (0,5); and
• the intersection of the two boundaries: subtracting twice the second equation from the first gives 2y = 4, so y = 2 and x = 6.

Objective values are respectively 0, 24, 25, and 28. Thus the continuous model has optimum (6,2), which is already integral. Its benefit is 28 units. A complete solution must still check operational assumptions, such as whether instances are interchangeable and whether service demand is divisible.

Continuous and discrete optimisation

Continuous variables may take any value in an interval, such as bandwidth. Discrete variables take separate values, such as the number of servers. Integer and mixed-integer programming can express fixed charges, yes/no decisions, scheduling, and routing, but these problems may be computationally difficult. A model that is mathematically elegant may still be too slow for real-time use.

Unconstrained optimisation and derivatives

For a differentiable one-variable function f(x), an interior local optimum must satisfy

This is a necessary condition, not always a sufficient one. If f″(x*) > 0, the point is a strict local minimum; if f″(x*) < 0, it is a strict local maximum. Endpoints and constraints must also be examined.

#### Worked example

Suppose estimated processing cost is

where x is a tuning parameter and cost is measured in arbitrary units. Then

Setting the derivative to zero gives x = 6. Since C″(x) = 2 > 0, this is a minimum. Checking the endpoints gives C(0) = 50, C(6) = 14, and C(10) = 30. Therefore the constrained minimum is at x = 6. The derivative method assumes a differentiable model and should not be applied blindly to discontinuous or integer decisions.

3. Numerical Methods

Many equations cannot be solved conveniently in closed form. Numerical methods generate a sequence of approximations. A numerical answer should include a stopping rule, an error interpretation, and, where possible, an independent verification.

3.1 Bisection method

To solve f(x) = 0, choose a and b such that f(a)f(b) < 0. If f is continuous on [a,b], the Intermediate Value Theorem guarantees at least one root in the interval. Repeatedly compute

and retain the half-interval in which the sign change occurs. After n iterations, the interval width is

and the midpoint error is at most half that width, namely (b − a)/2ⁿ⁺¹, assuming a root remains bracketed. Bisection is reliable but converges linearly.

#### Worked example: square root by bisection

To approximate √10, solve f(x) = x² − 10 = 0 on [3,4]. Since f(3) = −1 and f(4) = 6, a root is bracketed.

After five iterations the root lies in [3.15625,3.1875]. The midpoint 3.171875 is an approximation, and the bracket width is 0.03125. Continuing the process gives increasing accuracy. The method does not require a derivative, which makes it useful when derivatives are unavailable or unreliable.

3.2 Newton’s method

Newton’s method uses a tangent-line approximation:

It requires differentiability near the root and f′(x_k) ≠ 0. Near a simple root and with a sufficiently good initial estimate, convergence is often quadratic, meaning the number of correct digits can increase rapidly. However, a poor starting value can cause divergence, cycling, or convergence to an unintended root.

For f(x) = x² − 10, f′(x) = 2x. Starting with x₀ = 3.2:

The next value is approximately x₂ = 3.16227766, close to √10 ≈ 3.16227766. This is much faster than the first few bisection steps, but it lacks bisection’s guaranteed bracket preservation.

3.3 Stopping criteria

Common stopping tests include:

and, when meaningful,

Here ε_abs is an absolute tolerance, ε_rel a relative tolerance, and ε_f a residual tolerance. A small residual does not always imply a small solution error, particularly when the problem is ill-conditioned. A robust implementation also imposes a maximum iteration count and detects division by zero or stagnation.

4. Error and Floating-Point Arithmetic

Absolute and relative error

If the exact value is x and an approximation is ẋ, absolute error is

For x ≠ 0, relative error is

Percentage error is 100E_rel%. Absolute error has the same units as the quantity; relative error is dimensionless.

For example, if the exact response time is 2.50 ms and the measured value is 2.47 ms, then E_abs = 0.03 ms and E_rel = 0.03/2.50 = 0.012, or 1.2%.

Representation, round-off, and truncation

Most computer systems represent numbers using finite binary floating-point formats. A real number may therefore be stored as a nearby representable number. Round-off error arises from arithmetic performed with finite precision. Truncation error arises when an infinite process, such as a series or iterative method, is stopped after finitely many terms. Propagation error occurs when earlier errors influence later calculations.

Floating-point arithmetic is not ordinary real arithmetic. In general,

because each operation may round. Subtracting nearly equal numbers can cause severe loss of significant digits, known as cancellation. Multiplying very large or very small values can cause overflow or underflow.

IEEE 754 floating-point systems commonly provide special values such as positive and negative infinity and NaN (not a number), but their handling is language- and application-dependent. Comparisons should therefore use tolerances when testing computed real values. A typical test is whether |a − b| ≤ ε_abs + ε_rel max(|a|,|b|), rather than requiring exact equality.

Conditioning and stability

The condition of a problem describes how sensitive the exact answer is to small changes in input. An ill-conditioned problem may amplify unavoidable input uncertainty. The stability of an algorithm concerns whether the algorithm introduces excessive additional error. A well-conditioned problem can be solved badly by an unstable algorithm, while a poorly conditioned problem cannot be made fully reliable merely by changing algorithms.

For a differentiable scalar function, a local relative condition estimate for evaluating y = f(x) is

when x ≠ 0 and f(x) ≠ 0. This expression is a sensitivity indicator, not a universal error bound. High κ means relative input errors may be amplified substantially.

5. Algorithmic Efficiency and Growth Rates

Efficiency considers how resource requirements grow with input size n. Time complexity measures operations or execution time; space complexity measures additional memory. Exact running time depends on hardware, implementation, compiler, and input distribution, so asymptotic notation focuses on growth.

• O(g(n)) is an asymptotic upper bound: growth is no faster than a constant multiple of g(n) beyond some point.
• Ω(g(n)) is an asymptotic lower bound.
• Θ(g(n)) is a tight bound: both upper and lower bounds hold.

Typical growth rates, from generally more scalable to less scalable, are

Constants and lower-order terms are ignored asymptotically. Thus 3n² + 5n + 2 = Θ(n²). This does not mean constants are irrelevant in practice; a large constant or memory-access pattern may dominate for realistic input sizes.

Examples of common complexities

• Accessing an array element by index: Θ(1).
• Scanning an unsorted list: Θ(n).
• Binary search in a sorted array: Θ(log n).
• Comparison sorting using a suitable divide-and-conquer method: typically Θ(n log n).
• Comparing every pair of records: Θ(n²).

Binary search halves the search interval at each step. After k steps, the remaining size is approximately n/2ᵏ. To reduce it to one item requires k ≈ log₂ n steps. This assumes sorted data, random access or an equivalent structure, and a correct implementation.

Worst, average, and best cases

Worst-case complexity provides a guarantee over all valid inputs. Average-case complexity requires a probability model for inputs. Best-case complexity may be useful diagnostically but can be misleading as a performance guarantee. For safety-critical or service-level applications, worst-case behaviour may matter more than average performance.

6. Integrated Case Study: Capacity Planning for an API Service

This is an illustrative case, not a report of a specific company.

Background

An IT team must select the number of ordinary and memory-optimised virtual machines for an API service. Ordinary machines provide 100 request-capacity units and use 4 GB of memory. Memory-optimised machines provide 160 capacity units and use 8 GB. The service requires at least 1,000 capacity units, while the platform permits at most 80 GB of memory. The costs are 6 and 10 cost units per machine, respectively.

Problem formulation

Let x be ordinary machines and y memory-optimised machines. The objective is to minimise cost:

The constraints represent capacity, memory, non-negativity, and deployability. If reliability requires redundancy, an additional constraint would be needed; the current model does not automatically guarantee fault tolerance.

Analysis and solution

The memory constraint simplifies to x + 2y ≤ 20. Testing low-cost feasible combinations:

• With y = 0, at least 10 ordinary machines are required, costing 60; memory use is 40 GB.
• With y = 1, capacity requires x ≥ 8.4, so x = 9; cost is 64.
• With y = 2, 100x + 320 ≥ 1000, so x ≥ 6.8, hence x = 7; cost is 62.
• With y = 3, x ≥ 5.2, hence x = 6; cost is 66.

The combination (10,0) is cheaper than the tested alternatives and satisfies all constraints. Its capacity is 1,000 units and memory use is 40 GB. However, if memory-optimised machines have operational advantages or if workload uncertainty is significant, cost alone is not a sufficient decision criterion.

Numerical and efficiency considerations

Suppose capacity demand is forecast by solving an equation numerically, such as a nonlinear demand model. The team should report the tolerance and residual, not just a rounded forecast. A bisection solver provides a safe bracket when continuity and a sign change are known; Newton’s method may be faster but should be protected by a maximum iteration count and fallback logic.

For incoming requests, a linear scan through all service records costs Θ(n), while indexed lookup may approach Θ(log n) for a balanced search structure. At large scale, this algorithmic difference may exceed the cost difference between two hardware configurations.

Outcome and learning points

The model identifies a feasible low-cost plan, but professional deployment requires sensitivity analysis: What if demand is 10% higher? What if one machine fails? What if costs change? The case illustrates that optimisation, numerical accuracy, and algorithmic efficiency are connected. A mathematically optimal plan can be operationally poor if its data are inaccurate, its numerical computation is unstable, or its implementation does not scale.

7. Best Practices, Limitations, and Governance

1. Define the decision precisely. Separate controllable variables from assumptions and observations.
2. Validate units and bounds. Dimensional inconsistency often reveals a faulty model.
3. Check feasibility before optimality. A low-cost infeasible answer is not a solution.
4. Use suitable numerical methods. Prefer bracketing when reliability is more important than speed; use safeguarded Newton methods when derivatives and good initial estimates are available.
5. Report tolerances and residuals. A decimal expansion without an error statement can create false confidence.
6. Test edge cases. Include empty inputs, extreme magnitudes, duplicate data, overflow risks, and non-convergence.
7. Measure both asymptotic and practical performance. Benchmark representative workloads, but do not confuse a benchmark with a proof of scalability.
8. Preserve auditability. Record data sources, model versions, solver settings, rounding rules, and rejected alternatives.

Optimisation can encode organisational bias if objectives or constraints unfairly allocate resources. Automated decisions should therefore be reviewed for fairness, explainability, privacy, security, and accountability. AI systems may assist with forecasting or heuristic search, but their outputs remain estimates. Human oversight is necessary where decisions affect access to services, employment, safety, or financial outcomes. A solver’s numerical precision does not compensate for biased data or an inappropriate objective.

Chapter Summary

Optimisation expresses a decision problem through variables, an objective, constraints, and a feasible domain. Linear programming is useful when relationships are linear, while integer restrictions represent indivisible IT decisions. Derivatives identify interior candidates for smooth unconstrained problems, but constraints, endpoints, and discrete choices must also be considered.

Numerical methods approximate solutions to equations. Bisection is dependable when continuity and a sign-changing bracket are available; Newton’s method is often faster but depends on derivatives and a suitable starting point. Absolute and relative error quantify approximation quality, while conditioning describes sensitivity of the problem and stability describes error behaviour of the algorithm. Floating-point arithmetic introduces representation and round-off effects.

Algorithmic efficiency studies how time and memory grow with input size. Big-O, Big-Ω, and Big-Θ provide asymptotic descriptions, but practical decisions also require attention to constants, hardware, data structures, worst-case behaviour, and operational constraints. Reliable IT solutions combine mathematical validity, numerical accuracy, computational efficiency, and responsible governance.

Key Terms

Optimisation: Selection of the best feasible solution according to an objective.

Decision variable: A quantity whose value is chosen by a model or algorithm.

Objective function: A mathematical measure to maximise or minimise.

Constraint: A condition restricting allowed solutions.

Feasible region: The set of all solutions satisfying every constraint.

Linear programming: Optimisation with linear objective and constraint functions.

Integer programming: Optimisation in which some or all variables must be integers.

Local optimum: A solution better than nearby feasible solutions.

Bisection method: A root-finding method that repeatedly halves a sign-changing interval.

Newton’s method: An iterative root-finding method based on tangent-line estimates.

Residual: The value of an equation expression at an approximate solution.

Absolute error: The magnitude of the difference between approximate and exact values.

Relative error: Absolute error divided by the magnitude of the exact value.

Round-off error: Error caused by finite numerical representation or arithmetic precision.

Truncation error: Error caused by stopping an infinite or limiting process.

Conditioning: Sensitivity of a problem’s answer to changes in its input.

Stability: The tendency of an algorithm to control the effects of numerical error.

Big-O notation: An asymptotic upper-growth bound.

Big-Theta notation: An asymptotically tight-growth bound.

Scalability: The ability of a solution to remain effective as workload grows.

Review Questions

Short Answer Questions

1. What are the four essential components of a basic optimisation model?
2. Why must integer restrictions be included when modelling numbers of servers?
3. State the condition that guarantees bisection can begin on an interval.
4. Distinguish absolute error from relative error.
5. What does Θ(n log n) communicate about an algorithm?

Long Answer Questions

1. Explain how a feasible region is formed in a two-variable linear program and why vertices are important.
2. Compare bisection and Newton’s method in terms of assumptions, reliability, and convergence speed.
3. Explain how floating-point representation can make ordinary algebraic rules fail in computer programs.
4. Discuss the difference between problem conditioning and algorithmic stability, using an IT example.
5. Explain why asymptotic complexity should be combined with empirical benchmarking when selecting an implementation.

Analytical / Application Questions

1. Formulate and solve a model that minimises the cost of purchasing two types of servers subject to capacity and memory constraints. State all assumptions and verify feasibility.
2. Use two iterations of Newton’s method to approximate a positive root of x² − 7 = 0 starting from x₀ = 3. Report the recurrence and approximations.
3. An application performs one scan of n records inside a loop that executes n times. Derive its asymptotic time complexity and explain how the result changes if the inner scan is replaced by binary search on sorted data.

Multiple Choice Questions with Answers

Question 1

Which component specifies what an optimisation model seeks to maximise or minimise?

A. Objective function

B. Feasible region

C. Parameter domain

D. Iteration counter

Correct Answer: A. Objective function

Question 2

In a linear program, what does the constraint x + y ≤ 8 represent when x and y count instances?

A. A profit requirement

B. A limit on the total number of instances

C. An equality forcing eight instances

D. A requirement that x equal y

Correct Answer: B. A limit on the total number of instances

Question 3

What condition is required for the standard bisection method to bracket a root on [a,b]?

A. f′(a) = f′(b)

B. f(a) = f(b)

C. f(a)f(b) < 0 and f is continuous

D. a and b must both be positive

Correct Answer: C. f(a)f(b) < 0 and f is continuous

Question 4

Which recurrence defines Newton’s method for solving f(x) = 0?

A. x_{k+1} = x_k + f(x_k)

B. x_{k+1} = x_k − f(x_k)/f′(x_k)

C. x_{k+1} = f′(x_k)/f(x_k)

D. x_{k+1} = (a+b)/2

Correct Answer: B. x_{k+1} = x_k − f(x_k)/f′(x_k)

Question 5

An exact value is 2.50 ms and an approximation is 2.47 ms. What is the relative error?

A. 0.012, or 1.2%

B. 0.03, or 3%

C. 0.97, or 97%

D. 2.50, or 250%

Correct Answer: A. 0.012, or 1.2%

Question 6

Which issue is most directly associated with subtracting two nearly equal floating-point numbers?

A. Integer overflow

B. Cancellation and loss of significant digits

C. Guaranteed quadratic convergence

D. Improved relative accuracy

Correct Answer: B. Cancellation and loss of significant digits

Question 7

What does Θ(n²) mean?

A. The running time is bounded only below by n²

B. The running time grows exactly as a constant multiple of log n

C. The running time has matching asymptotic upper and lower bounds proportional to n²

D. The algorithm always performs exactly n² operations

Correct Answer: C. The running time has matching asymptotic upper and lower bounds proportional to n²

Question 8

Binary search on a sorted, randomly accessible array has which typical time complexity?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: B. Θ(log n)

Question 9

For C(x) = x² − 12x + 50 on 0 ≤ x ≤ 10, where is the minimum?

A. x = 0

B. x = 5

C. x = 6

D. x = 10

Correct Answer: C. x = 6

Question 10

Which statement best distinguishes conditioning from stability?

A. Conditioning concerns input sensitivity; stability concerns error introduced by an algorithm

B. Conditioning measures memory use; stability measures running time

C. Conditioning applies only to integer programs; stability applies only to sorting

D. They are exactly the same concept

Correct Answer: A. Conditioning concerns input sensitivity; stability concerns error introduced by an algorithm