Mathematical Optimization for Data Science

Introduction

Optimization is the mathematical process of selecting the best feasible decision according to a specified objective. In data science, optimization underlies linear and logistic regression, support-vector machines, neural-network training, clustering, matrix factorization, portfolio construction, experimental design, and resource allocation. A model may be statistically appropriate yet computationally unusable if its optimization problem is poorly formulated or solved with an unsuitable algorithm.

A general optimization problem is written as

Here, x ∈ ℝⁿ is the decision vector, f is the objective function, g_i are inequality constraints, and h_j are equality constraints. Maximization can be converted to minimization by minimizing -f(x). This chapter develops the theory and algorithms needed to formulate and solve such problems.

Learning Objectives

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

• formulate data-science tasks as unconstrained or constrained optimization problems;
• distinguish convex, strictly convex, and non-convex problems;
• derive and interpret first-order and second-order optimality conditions;
• use Lagrange multipliers and Karush–Kuhn–Tucker conditions;
• explain primal–dual relationships and strong versus weak duality;
• apply gradient descent, Newton methods, and stochastic optimization;
• understand regularization as optimization and as statistical control of complexity;
• diagnose convergence, scaling, conditioning, and ethical risks in optimization systems.

1. Formulating Optimization Problems

A useful formulation identifies four elements: decision variables, objective, constraints, and data. For example, ridge regression chooses coefficients β ∈ ℝ^p by minimizing squared prediction error plus a complexity penalty:

Here, X ∈ ℝ^n×p is the feature matrix, y ∈ ℝⁿ is the response vector, n is the number of observations, and λ controls regularization. The factor 1/(2n) is conventional and simplifies derivatives. The problem is unconstrained unless additional restrictions are imposed.

A feasible point satisfies every constraint. An optimal point x^* is a feasible point whose objective is no larger than that of any other feasible point for minimization. A local optimum is best only within a neighborhood; a global optimum is best throughout the feasible set.

Important terminology

• Objective function: quantity being minimized or maximized.
• Feasible set: all points satisfying the constraints.
• Gradient: vector of first partial derivatives, denoted ∇f(x).
• Hessian: matrix of second partial derivatives, denoted ∇²f(x) when it exists.
• Stationary point: point where ∇f(x)=0 in an unconstrained problem.
• Iteration: one update made by an optimization algorithm.
• Step size or learning rate: positive scalar controlling the update magnitude.
• Conditioning: sensitivity of a problem to perturbations and numerical error.

2. Convexity and Why It Matters

A set C is convex if, for any x,y ∈ C and θ ∈ [0,1],

A differentiable function is convex on a convex domain if

for all points in the domain. Geometrically, a convex function lies below the straight line joining any two points on its graph. If twice differentiable, a sufficient and necessary condition on an open convex domain is

where ⪰ 0 means positive semidefinite. Strict positive definiteness, ∇²f(x) ≻ 0, implies strict convexity under appropriate domain conditions.

A convex optimization problem has a convex objective for minimization and a convex feasible set. Equality constraints must be affine, while inequality constraints are conventionally written g_i(x)≤0 with each g_i convex. Every local minimum of a convex problem is global. If the objective is strictly convex over a convex feasible set, the minimizer is unique.

Examples include least squares, logistic loss, linear programming, quadratic programming with positive-semidefinite quadratic term, and the soft-margin support-vector-machine primal problem. Neural-network training is generally non-convex because compositions of nonlinear layers produce non-convex objectives.

For a differentiable convex function, the first-order inequality

holds for all x,y. Thus a point with zero gradient is a global minimizer in an unconstrained convex problem. This statement is not valid for arbitrary non-convex functions.

3. Unconstrained Optimization

3.1 Gradient descent

For minimizing differentiable f(x), gradient descent uses

where α_k>0 is the step size. The negative gradient is a local direction of steepest decrease under the Euclidean norm. With a fixed sufficiently small step size, gradient descent converges for many smooth convex functions. If the gradient is L-Lipschitz, meaning

then a common theoretical choice is 0<α<2/L, with α≤1/L often used for a simple guarantee. The exact result depends on convexity and whether strong convexity holds.

For a quadratic objective,

with symmetric positive-definite Q, the unique minimizer satisfies Qx^*=b. The gradient is Qx−b, and the Hessian is Q. Poorly conditioned Q creates elongated contours and slow progress. Feature scaling can substantially improve practical convergence.

3.2 Newton and quasi-Newton methods

Newton’s method uses local curvature:

provided the Hessian is nonsingular. It is usually implemented by solving

∇²f(x_k)d_k = −∇f(x_k) rather than explicitly computing an inverse. Near a well-behaved solution, Newton’s method can converge quadratically, but each iteration may be expensive and an indefinite Hessian can produce a non-descent direction.

Damped Newton methods use x_k+1=x_k+α_kd_k with line search. Quasi-Newton methods, such as BFGS and limited-memory BFGS (L-BFGS), construct an approximation to the inverse Hessian using gradients. They reduce memory and computation while often retaining fast convergence on smooth problems.

3.3 Line search and stopping

A line search selects a step size that sufficiently decreases the objective. Backtracking begins with a trial value and repeatedly multiplies it by ρ∈(0,1) until an Armijo-type condition holds:

where d is a descent direction and c∈(0,1). Practical stopping criteria include small gradient norm, small step norm, small objective change, or a maximum computational budget. No single criterion is universally reliable; objective change can be misleading on flat regions, while a small gradient may occur at a saddle point in a non-convex problem.

4. Constrained Optimization and Lagrange Multipliers

Consider equality-constrained minimization:

The Lagrangian is

where ν is the vector of Lagrange multipliers. Under differentiability and a suitable constraint qualification, a local solution satisfies

The multiplier measures the first-order change in the optimal value when the constraint is relaxed, subject to sign and convention. This is called a shadow price.

Worked example: projection onto a hyperplane

Minimize the squared distance from a∈ℝⁿ to a hyperplane:

where c≠0. The Lagrangian is L=(1/2)||x−a||²₂+ν(cᵀx−d). Stationarity gives x−a+νc=0, so x=a−νc. Substitution into the constraint gives

and therefore

The solution is the orthogonal projection of a onto the hyperplane. The denominator is positive because c≠0.

5. Karush–Kuhn–Tucker Conditions

For the problem

the Lagrangian is

The KKT conditions are:

1. Stationarity: ∇f(x^*)+∑ᵢλ_i^*∇g_i(x^*)+∑ⱼν_j^*∇h_j(x^*)=0.
2. Primal feasibility: g_i(x^*)≤0 and h_j(x^*)=0.
3. Dual feasibility: λ_i^*≥0.
4. Complementary slackness: λ_i^*g_i(x^*)=0.

For a convex differentiable problem with convex inequalities, affine equalities, and a constraint qualification such as Slater’s condition—there exists a point satisfying all equalities and strictly satisfying all inequalities—KKT conditions are sufficient for global optimality and, under standard regularity, necessary. In non-convex problems they are generally necessary only under a constraint qualification, not sufficient.

Complementary slackness says that an inequality is either active (g_i=0) or has zero multiplier. A nonbinding resource constraint therefore has zero marginal value in the local sensitivity interpretation.

6. Duality

The dual function is the infimum of the Lagrangian over the primal variable:

The dual problem maximizes this lower bound:

For every primal feasible point and dual feasible point, weak duality gives

The difference between primal and dual optimal values is the duality gap. Strong duality means the gap is zero. Convexity plus an appropriate regularity condition, commonly Slater’s condition, often ensures strong duality. Dual methods are valuable when the dual has fewer variables, decomposes across observations, or provides certificates of optimality.

In machine learning, duality appears in support-vector machines, where dual variables correspond to training examples that influence the separating boundary. The primal–dual viewpoint also supports distributed optimization and robust verification.

7. Stochastic Optimization

Large data sets make full-gradient computation expensive. If the objective is an average,

an unbiased mini-batch gradient estimator is

where B_k is a randomly sampled mini-batch. Stochastic gradient descent updates x_k+1=x_k−α_kg_k. If sampling is uniform, E[g_k|x_k]=∇F(x_k), assuming finite expectations.

Noise can help escape some shallow non-convex regions, but it also causes fluctuations near a solution. Learning-rate schedules, such as diminishing rates satisfying ∑_kα_k=∞ and ∑_kα_k²<∞ under classical assumptions, support convergence in stochastic settings. Momentum, AdaGrad, RMSProp, and Adam adapt updates using historical gradients. They can be effective in deep learning, but their convergence behavior depends on assumptions, hyperparameters, gradient noise, and implementation details. Adaptive methods do not eliminate the need for validation and diagnostics.

Distributed and federated optimization introduce communication limits, heterogeneous data, privacy risks, and potentially malicious participants. Gradient clipping and differential privacy can reduce certain risks, usually at the cost of optimization accuracy.

8. Regularization and Statistical Optimization

Regularization modifies the objective to discourage undesirable solutions. A general penalized problem is

The parameter λ is selected using validation, cross-validation, information criteria, or domain constraints—not merely by choosing the value that minimizes training loss.

Common penalties include:

The L1 norm is non-differentiable at zero, so ordinary gradient methods require modification. Proximal gradient methods use

where the proximal operator is

For R(x)=||x||₁, the proximal operator is componentwise soft thresholding:

Regularization is not a universal cure for bias, leakage, unfairness, or distribution shift. It controls one aspect of model complexity and must be evaluated with appropriate data and metrics.

9. Worked Example: Logistic Regression

For binary labels y_i∈{0,1}, logistic regression models

The average negative log-likelihood with ridge regularization is

With X having rows x_iᵀ and p the vector of probabilities,

The Hessian is

where W is diagonal with entries p_i(1−p_i). Since W⪰0 and λI⪰0, the objective is convex; if λ>0, it is strongly convex in coefficient directions, subject to the usual parameterization. Consequently, any converged global minimizer is statistically and computationally interpretable within the model assumptions.

10. Applied Case: Predictive Maintenance

Background. An industrial firm wants to predict whether a machine will fail within 24 hours using vibration, temperature, pressure, and operating-load measurements.

Problem. False negatives are costly, but unnecessary inspections are also expensive. Sensor scales differ substantially, missing values occur, and several sensors are correlated.

Analysis. The team defines a regularized logistic-loss objective. Features are standardized using training-set statistics only. A validation set is used to select λ and the classification threshold. Because sensor correlation can make individual coefficients unstable, ridge regularization is initially preferred over pure Lasso. Class weights or a cost-sensitive objective are introduced if failures are rare and asymmetric costs are documented.

Approach. The team first checks data quality and temporal leakage. It then compares L-BFGS on the full objective with mini-batch stochastic gradient descent. Gradient norms, validation loss, calibration, recall, precision, and expected operational cost are monitored. A time-based test set evaluates performance under realistic deployment conditions. Model explanations are reviewed with maintenance engineers, and an alarm is not treated as an automatic shutdown decision.

Outcome. The optimized model improves recall while maintaining an acceptable inspection workload. Its value comes not only from the optimizer but from correct objective design, scaling, temporal validation, and explicit treatment of asymmetric consequences.

Learning points. Optimization is inseparable from measurement design and governance. A numerically converged model can still be operationally harmful if labels are delayed, costs are omitted, or deployment drift is ignored.

11. Limitations, Governance, and Best Practice

Optimization algorithms may converge to different solutions because of initialization, stochastic sampling, stopping rules, or non-convex geometry. Floating-point arithmetic can create instability when features or Hessians are poorly scaled. In high-dimensional models, training convergence does not guarantee generalization.

Responsible practice includes: defining the operational objective before tuning; separating training, validation, and test data; scaling features consistently; checking gradient and constraint residuals; reporting sensitivity to initialization and hyperparameters; using reproducible random seeds where possible; monitoring distribution shift; and documenting assumptions. Fairness constraints or group-specific performance requirements should be formulated explicitly rather than assumed to emerge from generic loss minimization. Privacy-preserving optimization must account for the accuracy–privacy trade-off, and automated decisions require human oversight where legal or safety consequences are substantial.

Contemporary research studies variance reduction, variance-reduced stochastic gradients, distributed and federated optimization, differentiable programming, bilevel optimization, meta-learning, implicit layers, and certified robustness. These methods expand capability but also increase the importance of transparent assumptions and reliable evaluation.

Chapter Summary

Optimization expresses data-science decisions through variables, objectives, and constraints. Convexity is central because local optimality becomes global optimality under convex assumptions. Gradients provide first-order directions, while Newton and quasi-Newton methods exploit curvature. Lagrange multipliers and KKT conditions characterize constrained solutions, and duality supplies bounds, sensitivity interpretations, and alternative computational formulations. Stochastic optimization makes large-scale learning feasible but introduces variance and hyperparameter sensitivity. Regularization controls complexity through penalties such as L1 and L2 norms, with proximal methods handling non-smooth objectives. Effective professional practice requires numerical diagnostics, statistically valid evaluation, explicit costs, and governance of privacy, fairness, safety, and distribution shift.

Key Terms

Convex set: A set containing every line segment between any two of its points.

Convex function: A function satisfying the line-segment inequality for convex combinations.

Objective function: The quantity optimized by a mathematical program.

Feasible set: All points satisfying the constraints.

Gradient: Vector of first partial derivatives.

Hessian: Matrix of second partial derivatives.

Stationary point: Point with zero gradient in an unconstrained differentiable problem.

Conditioning: Sensitivity of numerical results to perturbations.

Gradient descent: Iterative method moving opposite the gradient.

Newton method: Method using the Hessian to form a curvature-adjusted step.

Line search: Procedure for selecting a suitable step length.

Lagrangian: Objective augmented by weighted constraints.

Lagrange multiplier: Variable associated with a constraint and its marginal value.

KKT conditions: Stationarity, feasibility, dual feasibility, and complementary slackness conditions.

Dual function: Infimum of the Lagrangian over primal variables.

Strong duality: Equality of optimal primal and dual values.

Stochastic gradient: Random gradient estimator based on sampled observations.

Regularization: Penalty used to control model complexity.

Proximal operator: Minimizer combining a quadratic proximity term with a penalty.

Constraint qualification: Regularity condition supporting valid optimality conditions.

Review Questions

Short Answer Questions

1. What distinguishes a local optimum from a global optimum?
2. State the KKT complementary-slackness condition and interpret it.
3. Why does feature scaling often improve gradient-based optimization?
4. What is the role of the learning rate in stochastic gradient descent?
5. Why can L1 regularization produce exact zero coefficients?

Long Answer Questions

1. Explain convexity, positive-semidefinite Hessians, and the significance of convexity for data-science optimization.
2. Derive the Lagrange multiplier solution for projection onto a hyperplane and explain its geometric meaning.
3. Compare gradient descent, Newton’s method, and L-BFGS in terms of curvature, memory, computational cost, and convergence.
4. Explain weak and strong duality, including the role of Slater’s condition.
5. Discuss how regularization affects optimization, statistical bias, variance, and model interpretability.

Analytical / Application Questions

1. Formulate a cost-sensitive, regularized logistic-regression problem for rare-event prediction. Identify the variables, objective, penalty, and evaluation criteria.
2. A quadratic objective has a very large condition number. Predict the effect on gradient descent and recommend two remedies, explaining why they help.
3. Design an optimization and governance plan for a predictive-maintenance model in which false negatives are safety-critical. Include data splitting, optimization diagnostics, threshold selection, and deployment monitoring.

Multiple Choice Questions with Answers

Question 1

Which statement is guaranteed for a differentiable convex unconstrained objective?

A. Every stationary point is a global minimizer.

B. Every point is a global minimizer.

C. The Hessian must be negative definite.

D. Gradient descent always converges with any step size.

Correct Answer: A. Every stationary point is a global minimizer.

Question 2

For the inequality convention g_i(x)≤0, KKT dual feasibility requires:

A. λ_i≤0

B. λ_i≥0

C. λ_i=1

D. λ_i=0 for every i

Correct Answer: B. λ_i≥0

Question 3

What does complementary slackness state?

A. λ_i + g_i(x)=0

B. λ_i g_i(x)=0

C. λ_i g_i(x)=1

D. g_i(x)>0 whenever λ_i>0

Correct Answer: B. λ_i g_i(x)=0

Question 4

For f(x)=(1/2)xᵀQx−bᵀx+c with positive-definite Q, the minimizer satisfies:

A. Qx^*=−b

B. Qx^*=b

C. x^*=Qb

D. Q^{-1}x^*=b

Correct Answer: B. Qx^*=b

Question 5

Which method explicitly uses second-order curvature information?

A. Newton’s method

B. Basic stochastic gradient descent

C. Random search only

D. Coordinate labeling

Correct Answer: A. Newton’s method

Question 6

Under uniform mini-batch sampling, the standard mini-batch gradient is typically:

A. A biased estimator unrelated to the full gradient

B. An unbiased estimator of the full gradient, under standard finite-expectation assumptions

C. Always equal to the full gradient

D. Always smaller in every coordinate

Correct Answer: B. An unbiased estimator of the full gradient, under standard finite-expectation assumptions

Question 7

Which penalty is most directly associated with sparse coefficients?

A. L1 norm

B. L2 norm only

C. Constant penalty

D. Negative entropy in every model

Correct Answer: A. L1 norm

Question 8

What does strong duality mean?

A. The dual objective is always convex in every problem

B. The primal and dual optimal values are equal

C. The primal problem has no constraints

D. All multipliers are strictly positive

Correct Answer: B. The primal and dual optimal values are equal

Question 9

For the hyperplane projection problem, why is cᵀc nonzero when c≠0?

A. Because it equals the number of observations

B. Because it is the squared Euclidean norm of c

C. Because d must be positive

D. Because the objective is linear

Correct Answer: B. Because it is the squared Euclidean norm of c

Question 10

Which practice best addresses temporal leakage in predictive maintenance?

A. Randomly mixing future records into training data

B. Using training-set statistics and time-based evaluation

C. Selecting the test set after viewing its labels repeatedly

D. Removing all validation data

Correct Answer: B. Using training-set statistics and time-based evaluation