Convex Optimization · Problem 6.10

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · fitting-concave-nonneg-nondecreasing-quadratic

Problem

Fitting data with a concave nonnegative nondecreasing quadratic function. We are given the data x1,…,xN∈Rn,y1,…,yN∈R,x_1, \ldots, x_N \in \mathbf{R}^n, \qquad y_1, \ldots, y_N \in \mathbf{R}, and wish to fit a quadratic function of the form f(x)=(1/2)xTPx+qTx+r,f(x) = (1/2)x^T P x + q^T x + r, where P∈SnP \in \mathbf{S}^n, q∈Rnq \in \mathbf{R}^n, and r∈Rr \in \mathbf{R} are the parameters in the model (and, therefore, the variables in the fitting problem). Our model will be used only on the box B={x∈Rn∣l⪯x⪯u}\mathcal{B} = \{x \in \mathbf{R}^n \mid l \preceq x \preceq u\}. You can assume that l≺ul \prec u, and that the given data points xix_i are in this box. We will use the simple sum of squared errors objective, ∑i=1N(f(xi)−yi)2,\sum_{i=1}^N (f(x_i) - y_i)^2, as the criterion for the fit. We also impose several constraints on the function ff. First, it must be concave. Second, it must be nonnegative on B\mathcal{B}, i.e., f(z)≥0f(z) \geq 0 for all z∈Bz \in \mathcal{B}. Third, ff must be nondecreasing on B\mathcal{B}, i.e., whenever z,z~∈Bz, \tilde{z} \in \mathcal{B} satisfy z⪯z~z \preceq \tilde{z}, we have f(z)≤f(z~)f(z) \leq f(\tilde{z}). Show how to formulate this fitting problem as a convex problem. Simplify your formulation as much as you can.

Browse the problem library