Full search page →

OPT 05 · Approximation, Statistical Estimation and Experiment Design

OptimizationAdvanced19 minUpdated Nov 5, 2026

Needs: OPT 04 · Duality, KKT Conditions and Certificates, ML 01B · Probability and Information Theory

Navigate: this page and this track: Navigate: this page and this track
Explore this chapter 1 interactive experiment

Move one observation and compare squared, absolute and Huber losses for fitting a constant.

What you’ll learn

  • Select a residual norm by the errors that matter, rather than habit.
  • Distinguish parameter regularization, robust residual losses and uncertain measurement models.
  • Impose monotonicity and convexity on fitted functions using linear inequalities.
  • Recognize convex likelihood and probability-estimation formulations.
  • Design randomized detectors and understand moment-based risk bounds.
  • Allocate measurement effort using information matrices and explicit design criteria.

The big picture

An optimization model can fit a curve to observations, estimate a distribution or decide which observations to collect next. These tasks share a common pattern: choose a representation, state how disagreement is measured, and specify which choices are allowed.

Boyd and Vandenberghe’s Chapters 6–7 [1] connect approximation and statistical estimation. Read them together: the same squared residual can mean a geometric approximation error, a likelihood under a noise model, or one component of a constrained design objective. Those interpretations impose different assumptions even when the numerical formula is identical.

A successful solver answers the stated optimization problem. It does not prove that the measurement assumptions are true, that a fitted curve predicts new data, or that a sensor allocation is physically achievable. This chapter keeps those questions visible alongside the mathematics.

The examples use synthetic observations and tiny measurement models. They show how the pieces work without hiding downloads, pretrained systems or application-specific assumptions inside the code.

Residual norms express priorities

Plain version. A residual is the difference between a prediction and an observation. Choosing a norm determines which patterns of error are expensive.

For a linear model,

r=Ax−b,min⁡x∥Ax−b∥.r=Ax-b,\qquad \min_x\|Ax-b\|.

A∈Rm×nA\in\mathbb R^{m\times n} is a fixed design matrix, b∈Rmb\in\mathbb R^m the observations, x∈Rnx\in\mathbb R^n the parameters and r∈Rmr\in\mathbb R^m the residual vector. The chosen norm acts on residuals, not directly on parameters.

The Euclidean norm or its square emphasizes large residuals through their squared contribution. The absolute-value norm adds residual magnitudes. The maximum norm minimizes the largest absolute residual and can be appropriate when every measured error must remain below a uniform tolerance [1, Section 6.1].

∥r∥22=∑iri2,∥r∥1=∑i∣ri∣,∥r∥∞=max⁡i∣ri∣.\|r\|_2^2=\sum_i r_i^2,\qquad \|r\|_1=\sum_i|r_i|,\qquad \|r\|_\infty=\max_i|r_i|.

rir_i is residual coordinate ii. All three objectives are convex when rr is affine in xx. Squaring a nonnegative Euclidean norm preserves its minimizers, but changes objective values, derivatives and the tradeoff with any additional penalty.

For absolute residuals, introduce ti≥rit_i\geq r_i and ti≥−rit_i\geq-r_i, then minimize ∑iti\sum_i t_i. For a uniform tolerance introduce one scalar tt and impose −t≤ri≤t-t\leq r_i\leq t. These are LP representations when there are only affine additional restrictions.

Three meanings of the best constant

A single fitted number exposes the difference between residual objectives. Take the synthetic observations b=(0,1,8)b=(0,1,8) and predict the same scalar cc for all three. The resulting design matrix is a column of ones.

For squared loss, differentiating c2+(c−1)2+(c−8)2c^2+(c-1)^2+(c-8)^2 gives 6c−18=06c-18=0, hence c=3c=3. For absolute loss, the slope is the number of observations below cc minus the number above it, away from the data points. The slope changes from negative to positive at the median, so c=1c=1 minimizes the sum. For maximum absolute loss, balance the two extreme errors: c=8−cc=8-c, hence c=4c=4.

Here cc is the fitted constant and bb the fixed observations. At their respective optima, squared residual sum is 3838, absolute residual sum is 88, and maximum residual is 44. These are different quantities with different units; comparing their raw numerical sizes would be meaningless. The important comparison is the returned prediction: average fit chooses three, median fit chooses one, and uniform-error fit chooses four. The observation eight pulls the mean strongly but does not move the median beyond the middle observation [1].

For a real task, ask which error pattern is costly. Uniform instrument tolerances suggest maximum error. A specified Gaussian measurement model suggests squared error. Contaminated responses can motivate bounded-influence residual losses. None of these choices follows solely from the convenience of a solver.

Units and weighted errors

Measurements with different units cannot be added sensibly without a stated scaling convention. A residual of one pixel and a residual of one second are not automatically comparable.

A weighted least-squares objective can be written

(Ax−b)⊤W(Ax−b),W⪰0.(Ax-b)^\top W(Ax-b),\qquad W\succeq0.

WW is a fixed positive-semidefinite weighting matrix. If WW is the inverse of a known positive-definite noise covariance, the objective has a statistical interpretation. If weights encode priorities, explain that interpretation instead.

Off-diagonal entries can describe correlated measurement errors. Replacing a full covariance by diagonal weights is a modeling approximation, not just an implementation detail. Whitening with a matrix factor transforms the residual before fitting and should preserve the intended quadratic form.

A large residual is not automatically an outlier. It could reveal a wrong model, a poorly scaled feature, genuine rare behavior or a corrupted observation. Inspect the generating process before deciding which errors should lose influence.

Least-norm solutions and regularization

Plain version. Matching the observations may leave many parameter choices. A norm on parameters chooses among them or trades fit against complexity.

A least-norm problem has the form

min⁡x∥x∥subject toAx=b.\min_x\|x\|\quad\text{subject to}\quad Ax=b.

xx is the parameter vector, and A,bA,b are fixed. This differs from a residual-norm problem: here exact consistency is required, and the objective selects a small parameter vector [1, Section 6.2].

If the equality is inconsistent, the problem is infeasible. Replacing it with a soft residual term changes the question. In an underdetermined consistent system, the Euclidean least-norm solution can be expressed through a suitable pseudoinverse, but numerical rank and singular values still matter.

Regularized approximation instead balances two goals:

min⁡x12∥Ax−b∥22+λR(x),λ≥0.\min_x\frac12\|Ax-b\|_2^2+\lambda R(x),\qquad \lambda\geq0.

RR is a convex penalty and λ\lambda its nonnegative weight. The factor one-half simplifies derivatives. Changing that factor while keeping λ\lambda fixed changes the tradeoff.

For R(x)=12∥x∥22R(x)=\frac12\|x\|_2^2, the objective is a ridge or quadratic regularization model [1, Section 6.3]. Positive λ\lambda makes the Hessian A⊤A+λIA^\top A+\lambda I positive definite. For R(x)=∥x∥1R(x)=\|x\|_1, the penalty encourages exact zero coordinates through its nonsmooth geometry.

An intercept is often treated separately because penalizing it has a different meaning from penalizing feature effects. Feature units also change a parameter norm. Standardizing columns or using an explicitly scaled penalty makes this choice visible.

Derive quadratic shrinkage direction by direction

Quadratic regularization reduces the instability caused by weakly observed parameter directions. For the ridge objective already defined, setting its gradient to zero gives

(A⊤A+λI)x∗=A⊤b.(A^\top A+\lambda I)x^*=A^\top b.

Here x∗x^* is the optimizer, A,bA,b are the fixed design and observations, II is the identity, and λ>0\lambda>0 is the penalty weight. Let A=UΣV⊤A=U\Sigma V^\top be a singular-value decomposition, with orthonormal singular vectors in U,VU,V and singular values σi\sigma_i in Σ\Sigma. In direction viv_i, the coefficient is

vi⊤x∗=σiσi2+λ ui⊤b.v_i^\top x^*=\frac{\sigma_i}{\sigma_i^2+\lambda}\,u_i^\top b.

Here ui,viu_i,v_i are paired singular vectors. Without regularization, a nonzero singular value divides the observation coefficient by σi\sigma_i; a tiny value can amplify measurement error. With regularization, the denominator never falls below λ\lambda. A nullspace direction receives zero in this fully penalized model.

For A=diag⁡(1,0.1)A=\operatorname{diag}(1,0.1) and b=(1,0.1)b=(1,0.1), the unregularized solution is (1,1)(1,1). With λ=0.1\lambda=0.1, the solution becomes (10/11,1/11)(10/11,1/11). The weakly observed second direction is shrunk much more strongly. This explains both the numerical stability and the introduced bias: regularization does not learn that the second true coefficient is small. It imposes a preference when the observations constrain that direction weakly [1, Section 6.3].

The constrained model min⁡∥Ax−b∥22\min\|Ax-b\|_2^2 subject to R(x)≤ρR(x)\leq\rho directly specifies an allowable complexity budget. Its Lagrange multiplier can connect it to a penalty formulation under appropriate conditions.

That connection does not mean a particular numerical λ\lambda corresponds to an obvious ρ\rho in advance. Nonunique solutions and inactive restrictions can complicate the correspondence. Choose the form that expresses the actual requirement.

Regularization can improve conditioning, but that numerical advantage is distinct from predictive improvement. A well-conditioned biased model may predict poorly. Select tuning parameters with a valid evaluation split when prediction is the goal, and keep the fitting objective separate from the final evaluation metric.

Robust losses and robust measurement models

Plain version. “Robust” can mean reducing the influence of unusually large residuals, or protecting against uncertainty in the measurement operator. These are different models.

One convex residual loss is the Huber function:

ϕδ(r)={12r2,∣r∣≤δ,δ∣r∣−12δ2,∣r∣>δ.\phi_\delta(r)= \begin{cases} \frac12r^2,&|r|\leq\delta,\\ \delta|r|-\frac12\delta^2,&|r|>\delta. \end{cases}

rr is a scalar residual and δ>0\delta>0 the transition scale. The derivative equals rr near zero and saturates at magnitude δ\delta outside. Summing this loss over affine residuals gives a convex problem [1, Section 6.1].

The transition has the units of the residual. Multiplying all observations by a scale while leaving δ\delta unchanged alters which points receive reduced influence. The loss is not immune to every corruption pattern; high-leverage errors in the design matrix require separate attention.

A synthetic line with several corrupted observations, comparing a squared-loss fit with a Huber-loss fit.
Figure 1 — Original synthetic observations and fitted solutions. Some responses were deliberately shifted upward. This illustrative example compares residual losses; it is not a benchmark or a general robustness guarantee.

Code: fit a line with two losses

The data and shift are generated locally. The smooth optimization call follows the official SciPy interface [2]. We compare solutions and verify the robust objective’s gradient instead of asserting that one estimator always wins.

Code · Python · 23 lines
import numpy as np
from scipy.optimize import minimize

rng = np.random.default_rng(15)
t = np.linspace(-1, 1, 40)
A = np.column_stack([np.ones_like(t), t])
b = 0.4 + 1.5*t + rng.normal(0, 0.08, len(t))
b[[5, 12, 30]] += 2.5
least_squares = np.linalg.lstsq(A, b, rcond=None)[0]
delta = 0.2

def huber_objective(x):
    r = A @ x - b
    loss = np.where(abs(r) <= delta, 0.5*r*r,
                    delta*abs(r) - 0.5*delta**2)
    return loss.sum(), A.T @ np.clip(r, -delta, delta)

fit = minimize(huber_objective, least_squares, jac=True,
               method="BFGS", options={"gtol": 1e-9})
assert np.linalg.norm(huber_objective(fit.x)[1]) < 1e-6
print("squared-loss coefficients:", np.round(least_squares, 4))
print("Huber-loss coefficients:", np.round(fit.x, 4))
print("robust objective:", round(fit.fun, 6))

Uncertain operators

Suppose the matrix itself may vary in a specified set A\mathcal A. A worst-case approximation model is

min⁡xsup⁡A∈A∥Ax−b∥.\min_x\sup_{A\in\mathcal A}\|Ax-b\|.

xx is the decision, bb the fixed target, and A\mathcal A the allowed measurement matrices. Each fixed-matrix norm objective is convex in xx, so their pointwise supremum is convex [1, Section 6.4].

Convexity does not guarantee that evaluating this supremum is easy. A finite uncertainty set can yield finitely many epigraph restrictions. Structured ellipsoidal uncertainty can permit conic reformulations. A vaguely described “small perturbation” is not enough to select the correct counterpart.

An expected squared-error model is different. If A=Aˉ+UA=\bar A+U, with E[U]=0\mathbb E[U]=0, then

E∥Ax−b∥22=∥Aˉx−b∥22+x⊤Px,P=E[U⊤U].\mathbb E\|Ax-b\|_2^2 =\|\bar Ax-b\|_2^2+x^\top P x,\qquad P=\mathbb E[U^\top U].

Aˉ\bar A is the mean operator, UU its random variation and PP a positive-semidefinite second-moment matrix. The cross term vanishes under the zero-mean assumption. Here regularization follows from a specified uncertainty model, rather than an arbitrary complexity preference.

Worst-case and expected protection answer different questions. An uncertainty set is not a probability distribution. A covariance model does not promise control of every possible realization.

Function fitting with shape constraints

Plain version. We can ask a fitted function to be increasing or convex while keeping the optimization convex in its coefficients.

For fixed basis functions ψj(t)\psi_j(t),

f(t)=∑j=1nxjψj(t).f(t)=\sum_{j=1}^n x_j\psi_j(t).

tt is the input, ψj\psi_j are known basis functions, and xjx_j are fitted coefficients. Evaluating at fixed sample inputs makes the predictions affine in xx, even when the basis functions are nonlinear in tt.

This distinction matters: convexity in the optimization variables is not the same as convexity in the function’s input. A polynomial regression may be a convex coefficient-fitting problem while the fitted polynomial is neither increasing nor convex.

At ordered knots t1<⋯<tmt_1<\cdots<t_m, let zi=f(ti)z_i=f(t_i) be fitted values. Monotonicity can be imposed by zi+1≥ziz_{i+1}\geq z_i. Convexity of the piecewise-linear interpolant requires

zi+1−ziti+1−ti≤zi+2−zi+1ti+2−ti+1.\frac{z_{i+1}-z_i}{t_{i+1}-t_i} \leq \frac{z_{i+2}-z_{i+1}}{t_{i+2}-t_{i+1}}.

ziz_i are variables and the knot spacings are fixed positive numbers. These slope-order inequalities are linear in fitted values. Unlike sampling a derivative of an arbitrary flexible function, they guarantee the shape of this particular interpolant throughout its knot interval.

Code: monotone absolute-error fitting as an LP

We fit five ordered measurements. The auxiliary variables represent absolute residual bounds. SciPy’s LP bounds are explicitly specified [3], including unrestricted fitted values.

Code · Python · 22 lines
import numpy as np
from scipy.optimize import linprog

observed = np.array([0., 2., 1., 3., 4.])
n = len(observed)
I = np.eye(n)
order = np.zeros((n-1, n))
for i in range(n-1):
    order[i, i], order[i, i+1] = 1, -1
G = np.vstack([np.hstack([I, -I]),
               np.hstack([-I, -I]),
               np.hstack([order, np.zeros((n-1, n))])])
h = np.r_[observed, -observed, np.zeros(n-1)]
fit = linprog(np.r_[np.zeros(n), np.ones(n)], A_ub=G, b_ub=h,
              bounds=[(None, None)]*n + [(0, None)]*n,
              method="highs")
assert fit.success
z = fit.x[:n]
assert np.all(np.diff(z) >= -1e-9)
assert np.isclose(abs(z-observed).sum(), fit.fun)
print("monotone fitted values:", z)
print("total absolute residual:", fit.fun)

Absolute-error solutions may be nonunique. The code verifies the property and objective rather than requiring one particular plateau value. Adding a strictly convex secondary objective would select one solution, but would be a different stated problem.

Constraints outside the observed interval require care. Piecewise-linear interpolation supplies a clear in-range function; extrapolation is an additional rule. Shape restrictions can improve plausibility while introducing bias if the underlying process violates them.

Likelihood and convex parameterizations

Plain version. A likelihood model can generate a convex objective, but the chosen parameterization and domain determine whether that is true.

For independent observations yiy_i under a distribution with natural parameter θ\theta,

p(y∣θ)=exp⁡(θ⊤T(y)−A(θ)+c(y)).p(y\mid\theta)= \exp\bigl(\theta^\top T(y)-A(\theta)+c(y)\bigr).

T(y)T(y) is a sufficient-statistic vector, A(θ)A(\theta) the log-partition function and c(y)c(y) a parameter-independent base term. For an exponential-family model, AA is convex on its natural domain.

Ignoring terms independent of θ\theta, the negative log-likelihood is

ℓ(θ)=NA(θ)−θ⊤∑i=1NT(yi).\ell(\theta)=N A(\theta)-\theta^\top\sum_{i=1}^N T(y_i).

NN is the number of observations. This is convex in the natural parameter. An arbitrary nonlinear change of parameter does not necessarily preserve convexity [1, Section 7.1].

For Bernoulli observations with success probability p∈(0,1)p\in(0,1) and kk successes out of NN, the negative log-likelihood is −klog⁡p−(N−k)log⁡(1−p)-k\log p-(N-k)\log(1-p). Its interior optimum is p=k/Np=k/N when both outcomes are observed.

If every observation is a success or every observation a failure, the optimum over the open domain may only be approached at a boundary. Allowing boundary distributions or adding a prior changes the existence question. A program that clips probabilities should record that clipping as a domain choice.

Maximum a posteriori estimation adds the negative log prior. A convex negative log prior preserves convexity in the selected coordinates. “Bayesian” alone does not guarantee a convex optimization problem, and a point estimate does not represent the entire posterior uncertainty.

Optional: Logistic separation and finite estimates (in the Supplementary notes). A worked example distinguishes diverging coefficients from an objective unbounded below.

Nonparametric probabilities

For discrete outcomes, estimate a probability vector qq on the simplex:

qj≥0,∑jqj=1.q_j\geq0,\qquad \sum_jq_j=1.

qjq_j is the probability of outcome jj. Given counts njn_j, the negative log-likelihood is −∑jnjlog⁡qj-\sum_j n_j\log q_j, with the appropriate extended-value convention for positive counts at zero probability.

Known moments become affine restrictions, such as ∑jqjaj=μ\sum_jq_j a_j=\mu for fixed outcome features aja_j and known mean μ\mu. Maximizing entropy, equivalently minimizing ∑jqjlog⁡qj\sum_jq_j\log q_j, selects a distribution subject to such constraints [1, Section 7.2].

Moment restrictions should come from the same population and units as the data. Inconsistent empirical constraints can make the simplex model infeasible. Softening them adds a modeling decision about acceptable uncertainty, rather than repairing an algebraic nuisance.

Detector design as a linear program

Plain version. Choosing decisions after observing discrete evidence can be optimized directly. Allowing randomized decisions makes the feasible set convex.

Suppose pkjp_{kj} is the known probability of observation kk under hypothesis jj. Let TikT_{ik} be the probability of deciding hypothesis ii after seeing kk.

Tik≥0,∑iTik=1,Dij=∑kTikpkj.T_{ik}\geq0,\qquad \sum_iT_{ik}=1,\qquad D_{ij}=\sum_kT_{ik}p_{kj}.

DijD_{ij} is the probability of deciding ii when jj is true. TT is the decision variable; the conditional probabilities pkjp_{kj} are fixed. Each entry of DD is linear in TT.

Weighted error costs, lower bounds on correct detection and upper bounds on false decisions can therefore be expressed as linear objectives and restrictions [1, Section 7.3]. A prior distribution on hypotheses can weight overall expected error, but should not be silently substituted for a conditional-error guarantee.

For binary hypotheses, likelihood-ratio threshold rules emerge from suitable optimal detector formulations. A boundary observation may need randomization to meet an exact error budget. Deterministic rules are a restricted subset; forcing them introduces discrete choices.

An optimized detector is only as valid as its conditional distributions. Distribution shift, estimated likelihoods and calibration uncertainty belong in the assessment. Numerical optimality under a specified probability table does not validate that table.

Worked detector: why randomization can be useful

A false-positive budget can fall between two deterministic rules. Suppose the observation is either aa or bb. Under hypothesis H0H_0, its probabilities are (0.8,0.2)(0.8,0.2); under H1H_1, they are (0.2,0.8)(0.2,0.8). These are synthetic conditional probability tables, not measured frequencies.

Let ta,tb∈[0,1]t_a,t_b\in[0,1] be the probabilities of deciding H1H_1 after each observation. Maximizing true-positive probability with false-positive budget 0.10.1 is the LP

maximize⁡ta,tb0.2ta+0.8tbsubject to0.8ta+0.2tb≤0.1,0≤ta,tb≤1.\begin{aligned} \operatorname{maximize}_{t_a,t_b}\quad&0.2t_a+0.8t_b\\ \text{subject to}\quad&0.8t_a+0.2t_b\leq0.1,\\ &0\leq t_a,t_b\leq1. \end{aligned}

Here the objective is detection probability under H1H_1, and the first restriction is error probability under H0H_0. Spending one unit of error budget on bb yields four units of detection probability, whereas spending it on aa yields only one quarter. Allocate the budget to bb: ta=0t_a=0, tb=1/2t_b=1/2, giving true-positive probability 0.40.4.

A deterministic decision on bb would cost 0.20.2, beyond the budget. With this discrete observation alphabet, every nontrivial deterministic rule violates the stated budget, so the only allowed deterministic rule always decides H0H_0 and detects nothing. Randomization fills the convex space between deterministic rules and achieves the desired operating point [1, Section 7.3]. This is randomizing a decision after a known observation, not treating unknown probabilities as decision variables.

Moment and exponential risk bounds

Plain version. Sometimes we know moments but not the whole distribution. Bounds can control a tail event conservatively, with assumptions stated explicitly.

For a scalar random variable YY with mean μ\mu and finite variance σ2\sigma^2, Chebyshev’s inequality gives

Pr⁡(∣Y−μ∣≥a)≤σ2a2,a>0.\Pr(|Y-\mu|\geq a)\leq\frac{\sigma^2}{a^2},\qquad a>0.

aa is a deviation threshold. The bound uses only the first two moments and can be loose. An upper bound above one can be replaced by one; it is not an estimated event probability [1, Section 7.4].

For a threshold bb, an exponential or Chernoff bound uses

Pr⁡(Y≥b)≤inf⁡s>0exp⁡(−sb) E[exp⁡(sY)].\Pr(Y\geq b)\leq \inf_{s>0}\exp(-sb)\,\mathbb E[\exp(sY)].

ss is a positive auxiliary parameter, and the expectation must be finite where used. Optimizing its logarithm gives inf⁡s>0{log⁡E[exp⁡(sY)]−sb}\inf_{s>0}\{\log\mathbb E[\exp(sY)]-sb\}.

The log moment-generating function is convex in ss on its domain. This does not automatically make every joint design-and-risk problem convex in all its variables. Check how the random variable depends on decisions and which distribution assumptions are retained.

Tail bounds can support conservative design constraints. They do not replace checking whether moments were reliably estimated. Heavy tails, dependence and finite-sample uncertainty can make an assumed moment-generating function unsuitable.

Choosing the next measurements

Plain version. Estimation quality depends on what we measure, not only on how we fit. Convex experiment design allocates continuous measurement effort before any discrete rounding.

For candidate measurement vectors aj∈Rna_j\in\mathbb R^n, independent unit-variance noise and normalized weights wjw_j, define

M(w)=∑jwjajaj⊤,wj≥0,∑jwj=1.M(w)=\sum_jw_ja_ja_j^\top,\qquad w_j\geq0,\quad\sum_jw_j=1.

MM is the information matrix per normalized measurement effort. The covariance of a corresponding linear estimator scales with its inverse when the matrix is positive definite, the measurement model is correct and total effort is accounted for.

D-optimal design minimizes −log⁡det⁡M-\log\det M, which targets an uncertainty-volume criterion. A-optimal design minimizes tr⁡(M−1)\operatorname{tr}(M^{-1}), targeting total coordinate variance. E-optimal design maximizes the smallest eigenvalue of MM, targeting the weakest measured direction [1, Section 7.5].

These are different scalar summaries. Units and coordinate changes can affect their interpretation differently. A small total variance may hide one poorly measured direction; a small uncertainty volume does not promise a bound on every coordinate.

Two analytical experiment-design criteria for allocating effort between orthogonal measurements with different strengths.
Figure 2 — Original analytical two-direction design. The D-optimal and A-optimal allocations differ because volume and total coordinate variance are different goals. The curves assume independent unit-variance noise and positive effort in both directions.

Code: two design criteria with exact checks

Use candidate vectors (2,0)(2,0) and (0,1)(0,1), with first weight ww and second weight 1−w1-w. The information matrix is diagonal: M=diag⁡(4w,1−w)M=\operatorname{diag}(4w,1-w). Both criteria diverge at an unobserved direction.

Code · Python · 15 lines
import numpy as np
from scipy.optimize import minimize_scalar

def d_loss(w):
    return -np.log(4*w) - np.log(1-w)

def a_loss(w):
    return 1/(4*w) + 1/(1-w)

d = minimize_scalar(d_loss, bounds=(1e-6, 1-1e-6), method="bounded")
a = minimize_scalar(a_loss, bounds=(1e-6, 1-1e-6), method="bounded")
assert np.isclose(d.x, 0.5, atol=1e-5)
assert np.isclose(a.x, 1/3, atol=1e-5)
print("D-optimal first weight:", round(d.x, 6))
print("A-optimal first weight:", round(a.x, 6))

With a fixed number of experiments, actual counts are integers. Continuous weights are a relaxation or a randomized sampling policy. Rounding can destroy a budget or leave a direction unmeasured, so reassess the resulting matrix after converting weights into a schedule.

If candidate vectors do not span the parameter space, no weighting makes the information positive definite. Adding a prior matrix may regularize the design, but changes its interpretation to prior-plus-measurement information.

Derive why the two design criteria allocate differently

The two-direction experiment can be solved before running numerical code. With candidate vectors (2,0)(2,0) and (0,1)(0,1) and weights w,1−ww,1-w, its information matrix is M=diag⁡(4w,1−w)M=\operatorname{diag}(4w,1-w). Let 0<w<10<w<1 so both directions are measured.

The D-optimal objective and its derivative are

fD(w)=−log⁡(4w)−log⁡(1−w),fD′(w)=−1w+11−w.f_D(w)=-\log(4w)-\log(1-w),\qquad f_D'(w)=-\frac1w+\frac1{1-w}.

Here fDf_D is the negative log-determinant criterion. Stationarity gives w=1/2w=1/2. The strength factor four changes the objective by a constant and does not change this D-optimal allocation.

For A-optimal design,

fA(w)=14w+11−w,fA′(w)=−14w2+1(1−w)2.f_A(w)=\frac1{4w}+\frac1{1-w},\qquad f_A'(w)=-\frac1{4w^2}+\frac1{(1-w)^2}.

Here fAf_A is the inverse-information trace criterion. Positive denominators turn its stationary equation into 1−w=2w1-w=2w, giving w=1/3w=1/3. Each scalar objective has positive second derivative and diverges at the endpoints, so these stationary points are the unique global minima [1, Section 7.5].

The interpretation is useful: the first measurement already observes its direction more strongly, so minimizing total variance sends more effort to the weaker second direction. Minimizing uncertainty volume balances multiplicative directional information instead and gives equal effort. If measurement cost or noise variance differs, incorporate those changes in the information matrix and budget before repeating the derivation. Neither allocation is universally best; each answers its chosen uncertainty question.

A fitting and design audit

Start with the application quantity that must be accurate. Decide whether it is a prediction, parameter component, worst residual or a distributional probability. Then state the representation and units before selecting a numerical loss.

For each constraint, ask whether it is physically required, statistically estimated or introduced for numerical convenience. Those roles imply different responses to infeasibility. A physical limit may need a revised design; an empirical moment may need uncertainty; redundant algebra may need removal.

After fitting, verify domain membership, shape restrictions and solver residuals. Then assess generalization or uncertainty using an appropriate independent procedure. An optimum of a training objective and a reliable future prediction are separate claims.

For design, inspect the information spectrum, available budget, noise assumptions and schedule conversion. Report the final implementable schedule alongside the relaxed objective. This keeps the most consequential approximation visible.

What an uncertainty ellipsoid actually says

An inverse information matrix describes a covariance only under the corresponding measurement and estimator assumptions. Turning it into a region with a stated coverage probability needs a distributional argument and a correctly chosen threshold. Drawing an ellipse from that matrix alone does not establish a confidence level.

For a positive-definite covariance CC, an ellipsoid can be written as (x−x^)⊤C−1(x−x^)≤c(x-\hat x)^\top C^{-1}(x-\hat x)\leq c. Here x^\hat x is a center and c>0c>0 is a threshold. The matrix specifies shape; the threshold specifies size. Coverage additionally depends on the actual distribution of estimation error.

A prior covariance, a sampling covariance and a numerical Hessian inverse need not have the same interpretation. They can coincide under particular models, but should not be exchanged without checking those models. Likewise, an estimator’s optimization tolerance and its sampling uncertainty have different units and sources.

When measurements are repeated, independent equal-variance assumptions justify a simple additive information model. Correlated repeats can provide less new information than their count suggests. A design that ignores that correlation may confidently allocate effort to redundant measurements.

This distinction affects stopping precision. Solving far below the uncertainty in the input coefficients may offer little practical value, while violating a hard physical bound by a seemingly small amount may still be unacceptable. Set optimization tolerances against the relevant application scale, rather than choosing precision solely from the number of available floating-point digits.

Finally, uncertainty visualization should state whether it displays an analytical model, an estimated covariance or repeated synthetic experiments. The figures in this chapter show illustrative fits and objective curves. They do not display empirically calibrated coverage regions or claim a particular confidence probability.

Modern view

Plain version. Current work combines structured convex estimation with large-scale first-order computation and learned convex components. The convexity guarantee belongs to the stated variables and domains.

Pokutta’s 2024 survey [4] organizes Frank–Wolfe methods around linear minimization over a convex feasible set, convergence guarantees and useful variants. Simplex-constrained experiment design is a natural setting for this viewpoint: an extreme-point search can avoid a full projection. The objective still needs the required smoothness and positive-definite domain control.

Schaller, Bemporad and Boyd’s 2025 manuscript [5] studies learning parametric convex functions for subsequent optimization. It connects fitting with disciplined curvature rules: a learned component can preserve convexity in decision variables for valid fixed parameters. Training the component is a separate problem and need not itself be convex.

These sources cover complementary questions: how to move through a structured feasible set, and how to construct functions usable inside such a set. Neither replaces uncertainty modeling, held-out evaluation or the physical feasibility of a design.

Current challenges include reliable uncertainty under model mismatch, informative measurements under resource limits, shape restrictions that remain appropriate outside the sample interval, and scalable updates when observations arrive sequentially. Distinguish a provably convex estimator from a complete validated statistical pipeline.

Key takeaways

  • Residual norms, parameter norms and evaluation metrics answer different questions.
  • Regularization weights depend on objective normalization and feature units.
  • Robust residual losses and uncertain-operator models protect against different errors.
  • Fixed nonlinear bases can still yield convex coefficient fitting.
  • Likelihood convexity depends on parameterization and domain.
  • Randomized discrete-evidence detectors can be formulated as LPs.
  • Experiment-design criteria differ, and continuous weights require an implementation plan.

Exercises

  1. Formulate maximum absolute residual fitting as an LP, including unrestricted parameters.
Hint

Use one nonnegative residual bound.

  1. Scale observations and predictions by ten. Determine how a Huber transition and a quadratic regularization weight should change to preserve a chosen equivalent objective.
Hint

Write the scaled objective explicitly; the answer depends on whether parameters and penalty units are also scaled.

  1. Add convexity constraints to the five-knot monotone-fitting example, using unequal positive knot spacings.
Hint

Order adjacent slopes.

  1. Derive the Bernoulli maximum-likelihood estimate, and explain the open-domain boundary cases.
Hint

Set the likelihood derivative to zero, then inspect endpoints.

  1. Construct a two-hypothesis randomized detector LP with a stated false-positive budget.
Hint

Use decision probabilities per observation, and conditional error as a linear expression.

  1. Derive the two-direction D- and A-optimal weights in the code, then explain why rounding a small measurement budget needs another check.
Hint

Differentiate the scalar criteria; inspect whether each rounded direction receives a measurement.

Supplementary notes

1 supplementary note, each on a page of its own; the main text does not depend on them.

Open the notes →

References

  1. Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004. Reading: Chapter 6, Sections 6.1–6.5; Chapter 7, Sections 7.1–7.5. Official book, free PDF.

  2. SciPy developers, “scipy.optimize.minimize” and “scipy.optimize.minimize_scalar,” SciPy API documentation, accessed 2026. Multivariate interface, scalar interface.

  3. SciPy developers, “scipy.optimize.linprog,” SciPy API documentation, accessed 2026. Official documentation.

  4. Sebastian Pokutta, “The Frank-Wolfe Algorithm: A Short Introduction,” Jahresbericht der Deutschen Mathematiker-Vereinigung, 126, 2024. Open-access survey.

  5. Michael Schaller, Alberto Bemporad and Stephen Boyd, “Learning Parametric Convex Functions,” manuscript, 2025. Official manuscript page.

  6. SAS Institute, “Existence of Maximum Likelihood Estimates,” SAS/STAT 12.1 User’s Guide, accessed 2026-11-05. Official documentation.

Check your understanding

This tutorial has 6 exercises. Can you solve them without opening the hints?

Go to the exercises ↑

Next OPT 06 · Gradient Descent, Newton Steps and Numerical Reliability · 19 min