Convex Optimization · Problem 6.9

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · minimax-rational-function-fitting

Problem

Minimax rational function fitting. Show that the following problem is quasiconvex: minimizemax⁡i=1,…,k∣p(ti)q(ti)−yi∣\text{minimize} \quad \max_{i=1,\ldots,k} \left| \frac{p(t_i)}{q(t_i)} - y_i \right| where p(t)=a0+a1t+a2t2+⋯+amtm,q(t)=1+b1t+⋯+bntn,p(t) = a_0 + a_1 t + a_2 t^2 + \cdots + a_m t^m, \qquad q(t) = 1 + b_1 t + \cdots + b_n t^n, and the domain of the objective function is defined as D={(a,b)∈Rm+1×Rn∣q(t)>0,  α≤t≤β}.D = \{(a, b) \in \mathbf{R}^{m+1} \times \mathbf{R}^n \mid q(t) > 0,\; \alpha \leq t \leq \beta\}. In this problem we fit a rational function p(t)/q(t)p(t)/q(t) to given data, while constraining the denominator polynomial to be positive on the interval [α,β][\alpha, \beta]. The optimization variables are the numerator and denominator coefficients aia_i, bib_i. The interpolation points ti∈[α,β]t_i \in [\alpha, \beta], and desired function values yiy_i, i=1,…,ki = 1, \ldots, k, are given.

Browse the problem library