The course classifies its models as LP, QP or NLP. Which class has a quadratic objective function and only linear constraints?
LP
NLP with conic constraints
QP
Stochastic LP
Explanation. QP (*Quadratic Programming*): quadratic objective, linear constraints. In an LP everything is linear; in an NLP the objective or the constraints are general nonlinear functions.
In the course notes an optimization problem is called *convex* when:
every local minimum is also a global minimum
all its constraints are linear functions
its optimal solution is unique
its objective is differentiable everywhere
Explanation. This is the working definition of the notes: for LPs it always holds, for QPs and NLPs it depends on the functions. Linearity, uniqueness and differentiability are different properties.
The course classifies models as LP (everything linear), QP (quadratic objective, linear constraints) and NLP (general nonlinear objective or constraints). A model with a linear objective and the constraint $x_1^2 + x_2^2 \le d^2$ is:
an LP, because the objective is linear
a QP, because it contains quadratic terms
an NLP, because a constraint is nonlinear
not classifiable in these three classes
Explanation. A QP requires linear constraints; a quadratic constraint makes the model an NLP (here a convex one, like the conic constraints of the location chapter).
The course turns managerial problems into continuous optimization models and solves them with Gurobi. According to the notes, what is the right question at the end of every lab session?
What is the optimal value of the model?
Which solver finds the optimum fastest?
Which decision do we recommend, and how robust is it?
How many variables and constraints does the model have?
Explanation. The value of a model lies in the quality of the recommendation it supports: the optimum is the starting point, not the answer.
In the course a solved model is not only read but *interrogated*. Which of these is an example of interrogating a production plan?
How much is one more hour of capacity worth?
How many simplex iterations did Gurobi need?
Which Python version ran the script?
How many decimal digits does the solver print?
Explanation. Interrogating means asking economic questions of the solution: the value of a resource (shadow prices), the robustness to data changes, the trade-offs to recommend.
The course uses mathematical programming as a *decision* tool. According to the notes, where does the value of a model lie?
In the precision of the optimal value it computes
In the speed of the solver that solves it
In the quality of the recommendation it makes possible
In the number of variables and constraints it handles
Explanation. The notes say it explicitly: the value of a model lies in the quality of the recommendation it allows us to formulate; the optimal value is only the starting point.
After solving a course model we *interrogate* it with three kinds of questions: marginal value, robustness, compromise. Which question is about **robustness**?
Does the solution hold if the data change by 5%?
How much is one more hour of capacity worth?
Which compromise would we advise the decision maker?
What is the optimal value of the objective?
Explanation. Robustness asks whether the recommendation survives a perturbation of the data. One more hour of capacity is a marginal value (a shadow price), the compromise is a trade-off, the optimal value is not an interrogation at all.
The course classifies its models as LP (all linear), QP (quadratic objective, linear constraints) and NLP (general nonlinear functions). For which class do the notes say that convexity (every local minimum is global) **always** holds?
QP
NLP
None: it must always be checked
LP
Explanation. For an LP convexity always holds; for QPs and NLPs it depends on the functions (for a QP, on the matrix $\mathbf Q$), and the notes point it out chapter by chapter.
Three chapters of NLP Modelling (production, EV charging, least squares) are variants of cases covered in LP Modelling. What changes with respect to the linear case?
The data, which are generated anew
The variables, which become integer
The constraints, which become quadratic
The objective, with a quadratic term
Explanation. Data, variables and constraints stay those of the linear case: the objective changes, with a convex quadratic term added (or substituted).
In the map of the models of NLP Modelling, which application is a non-convex NLP?
Pricing with price-dependent demand
The Markowitz portfolio with caps on the weights
Weber's location with conic constraints
The soft-margin SVM with a linear kernel
Explanation. In pricing the revenue $p \cdot q$ is bilinear and the model is not convex; Markowitz and the SVM are convex QPs, Weber is a convex NLP with conic constraints.
The essential path of NLP Modelling has four sessions. What does the first one cover?
Production with quadratic smoothing
Pricing or the advertising budget
The Markowitz portfolio
A project of your choice
Explanation. The first session is Markowitz (convex QP and frontier), the second production with smoothing, the third pricing or budget, the fourth a project.
In the second session of NLP Modelling (production with smoothing), which learning objective is central?
Formulating a multi-period LP from scratch
Reading and verifying the multipliers of a QP
Estimating a quantile regression
Using binary variables for the changes of pace
Explanation. The session adds a quadratic term to a known linear model and teaches how to read the multipliers of the QP and verify them by perturbation.
NLP Modelling assumes another course of the series for notation, general solver commands and the sensitivity protocol. Which one?
LP Modelling
MIP Modelling
Heuristic Algorithms
Dynamic Programming
Explanation. The course follows LP Modelling, from which it takes the notation, the general Gurobi commands and the sensitivity protocol; Convex Optimization provides the notions of convexity.
A model has a linear objective and the constraint $x_1^2 + x_2^2 \le d^2$. Under which assumption on $d$ is the problem convex?
Only for integer $d$, like count data
Only for $d > 1$, so that the disc does not degenerate
For every $d$: $x_1^2 + x_2^2 \le d^2$ is a disc
Never: a quadratic constraint is never convex
Explanation. The constraint describes a disc (a point for $d = 0$), which is convex; with a linear objective the problem is convex: a convex NLP, not a QP.
A QP has objective $\tfrac12 \mathbf x'\mathbf Q\mathbf x + \mathbf c'\mathbf x$ with $\mathbf Q \succeq 0$ and linear constraints. What can be said of a point satisfying the KKT conditions?
It is only a stationary point, perhaps a saddle
It is a global optimum
It is a local optimum but not necessarily global
It is feasible but not optimal
Explanation. With $\mathbf Q \succeq 0$ the QP is convex: the KKT conditions are also sufficient and every KKT point is a global optimum.
An equality constraint $h(\mathbf x) = 0$ appears in a model. Under which assumption on $h$ is the set it defines surely convex?
$h$ convex in all the variables
$h$ continuously differentiable
$h$ quadratic with a matrix $\succeq 0$
$h$ affine (linear plus a constant)
Explanation. An equality with a nonlinear function, for instance $x_1 x_2 = 1$, defines in general a non-convex set; with $h$ affine the set is a hyperplane.
Problem $\min f(x)$ subject to $g_i(x) \le 0$ and $h_k(x) = 0$, with differentiable functions. Which statement about the KKT conditions is correct?
Every point satisfying them is a global optimum, whatever $f$, $g_i$ and $h_k$
They hold at every regular local optimum, and under convexity they are also sufficient
They are necessary and sufficient as soon as all the constraints are linear
They guarantee global optimality whenever all the multipliers are strictly positive
Explanation. The KKT conditions are necessary at regular optima and become sufficient when the problem is convex. Linear constraints do not make a non-convex $f$ harmless. For an LP they reduce to complementary slackness.
A QP has objective $\tfrac12 \sum_{i}\sum_{j} q_{ij} x_i x_j + \sum_j c_j x_j$ (to be minimized) and linear constraints. It is convex:
if and only if the matrix $Q = (q_{ij})$ is positive semidefinite
always, because its constraints are linear
if and only if all the entries $q_{ij}$ are non-negative
if and only if $Q$ is diagonal with positive entries
Explanation. The feasible set is a polyhedron (convex); the quadratic objective is convex exactly when $Q \succeq 0$. Non-negative entries are neither necessary nor sufficient, and diagonal is only a special case.
A point satisfies the KKT conditions of $\min f(x)$ subject to $g_i(x) \le 0$, $h_k(x) = 0$ (multipliers $\lambda_i \ge 0$ for the $g_i$). What is needed to conclude that it is a **global** optimum?
The problem must be convex: $f$ and the $g_i$ convex, the $h_k$ affine
All the inequality constraints $g_i$ must be active at the point
All the multipliers $\lambda_i$ must be strictly positive
It suffices that $f$ be differentiable at the point
Explanation. Convexity makes the KKT conditions sufficient. Active constraints or positive multipliers do not guarantee globality in a non-convex problem.
Convex QP: $\min x_1^2 + 2x_2^2$ subject to $x_1 + x_2 \ge 6$, $x_1, x_2 \ge 0$. At the optimum the constraint is active and the partial derivatives equal its multiplier $\lambda$: $2x_1 = 4x_2 = \lambda$. What are $\tilde x$, the optimal value and $\lambda$?
$\tilde x = (3, 3)$, value $27$, $\lambda = 6$
$\tilde x = (4, 2)$, value $24$, $\lambda = 8$
$\tilde x = (2, 4)$, value $36$, $\lambda = 16$
$\tilde x = (6, 0)$, value $36$, $\lambda = 12$
Explanation. $x_1 = 2x_2$ and $x_1 + x_2 = 6$ give $(4, 2)$, value $16 + 8 = 24$, $\lambda = 8$. By perturbation, with right-hand side 7 the value becomes $32.67 \approx 24 + 8$.
For which values of the parameter $\gamma$ is $f(x_1, x_2) = x_1^2 + \gamma x_1x_2 + x_2^2$ convex? (A quadratic function $\tfrac12\mathbf x'\mathbf Q\mathbf x$ is convex if and only if $\mathbf Q \succeq 0$.)
For every $\gamma \ge 0$
For $|\gamma| \le 1$
For $|\gamma| \le 2$
For every real $\gamma$
Explanation. Here $\mathbf Q = \begin{pmatrix} 2 & \gamma \\ \gamma & 2 \end{pmatrix}$: diagonal entries positive and $\det\mathbf Q = 4 - \gamma^2 \ge 0$, i.e. $|\gamma| \le 2$. Forgetting the factor $\tfrac12$ gives $|\gamma| \le 1$.
Convex QP $\min\ x_1^2 + 2x_2^2$ subject to $x_1 + x_2 \ge d$, $x \ge 0$: with $d = 6$ the optimal value is $24$ and the multiplier $\lambda = 8$. With $d = 7$ the optimal value is $32.67$, not $24 + 8 = 32$. Why?
The multiplier is exact only at the margin (curvature)
The solver uses too loose a feasibility tolerance
With $d = 7$ the constraint is no longer active
The multiplier of a QP is never a marginal value
Explanation. Here $\tilde f(d) = \tfrac23 d^2$, so $\tilde f(6 + \varepsilon) = 24 + 8\varepsilon + \tfrac23\varepsilon^2$: the multiplier gives the first-order term, and the quadratic term of the curvature adds $0.67$ for $\varepsilon = 1$.
KKT conditions for $\min f(\mathbf x)$ subject to $g_i(\mathbf x) \le 0$ ($i = 1, \dots, m$) and $h_j(\mathbf x) = 0$ ($j = 1, \dots, q$). How is the Lagrangian written in the course notes?
$f - \sum_i\lambda_ig_i - \sum_j\nu_jh_j$, with $\lambda_i \le 0$
$f + \sum_i\lambda_ig_i + \sum_j\nu_jh_j$, with $\nu_j \ge 0$ and $\lambda_i$ free
$\sum_i\lambda_ig_i + \sum_j\nu_jh_j$, with $\lambda_i \ge 0$
$f + \sum_i\lambda_ig_i + \sum_j\nu_jh_j$, with $\lambda_i \ge 0$
Explanation. $L = f + \sum_i\lambda_ig_i + \sum_j\nu_jh_j$: the multipliers of the inequalities $g_i \le 0$ are nonnegative, those of the equalities free. Stationarity asks $\partial L/\partial x_k = 0$, complementarity $\lambda_ig_i = 0$.
What do the KKT conditions become when applied to an LP (written as $\min$ with constraints $g_i \le 0$)?
They lose meaning, because an LP has no derivatives
Exactly complementary slackness, with dual feasibility
Only the primal feasibility conditions of the LP
Weaker conditions, necessary but never sufficient
Explanation. For an LP the multipliers $\lambda_i$ are the duals $\pi_i$, those of the sign constraints are the reduced costs; stationarity is dual feasibility and complementarity is complementary slackness. And since an LP is convex, they are also sufficient.
Solve with the KKT conditions $\min\ (x - 3)^2 + (y - 1)^2$ subject to $x + 2y \le 2$, $x, y \ge 0$. Which is the optimum, with its active constraints?
$(2; 0)$: active $x + 2y \le 2$ and $y \ge 0$, both multipliers $= 2$
$(3; 1)$: no active constraint, all multipliers zero
$(0; 1)$: active $x + 2y \le 2$ and $x \ge 0$, multiplier $0$
Explanation. The free minimum $(3, 1)$ violates $x + 2y \le 2$; projecting on the line gives $(2.4, -0.2)$, which violates $y \ge 0$. With $y = 0$ and $x = 2$: $2(x - 3) + \lambda = 0$ gives $\lambda = 2$, and $2(y - 1) + 2\lambda - \mu = 0$ gives $\mu = 2 \ge 0$. The problem is convex, so the KKT point is the global optimum (value $2$).
The KKT theorem of the notes holds «at a **regular** optimal point». What can happen at an optimum where the regularity hypothesis fails?
The point cannot be a local minimum at all
The multipliers exist but are all equal to zero
KKT multipliers may fail to exist
The conditions become sufficient without convexity
Explanation. Regularity (a constraint qualification) is what guarantees the existence of the multipliers: without it an optimum may fail to satisfy stationarity for any choice of $\lambda_i \ge 0$, $\nu_j$.
For the problem $\min f(x)$ with constraints $g_i(x) \le 0$, under which assumption are the KKT conditions also *sufficient* for the global optimum?
That the constraints are all equalities
That the problem is convex: $f$ and the $g_i$ convex
That the multipliers are all positive
That the point lies in the interior of the region
Explanation. In a convex problem a point satisfying the KKT conditions is a global optimum; without convexity the KKT conditions are only necessary (at a regular point).
In the Lagrangian $L = f + \sum_i \lambda_i g_i$ for constraints $g_i(x) \le 0$ of a minimization problem, which sign must the multipliers $\lambda_i$ have?
Any sign
$\lambda_i \le 0$
$\lambda_i = 0$ for every active constraint
$\lambda_i \ge 0$
Explanation. For inequality constraints in the form $g_i \le 0$ the multipliers are non-negative; only those of equality constraints $h_j = 0$ are free.
KKT complementarity says $\lambda_i\, g_i(\tilde x) = 0$. What does it imply for a constraint that is *not active* at the optimum ($g_i(\tilde x) < 0$)?
That its multiplier is zero
That its multiplier is positive
That the point is not optimal
That the constraint must be removed from the model
Explanation. If $g_i(\tilde x) < 0$ the product can vanish only with $\lambda_i = 0$: a constraint with slack has no marginal value.
QP with objective $\tfrac12 \mathbf x'\mathbf Q\mathbf x + \mathbf c'\mathbf x$ and linear constraints. Which assumption on $\mathbf Q$ makes the QP convex?
Any sign, depending on the type of constraint
$\lambda_i \le 0$ for every constraint
$\lambda_i = 0$ for every active constraint
$\lambda_i \ge 0$
Explanation. The QP is convex if and only if $\mathbf Q \succeq 0$; non-negative entries or invertibility are not enough (for instance a large $q_{12}$ breaks convexity).
To a condition on the gradient of the objective only
To primal feasibility only
To nothing: the KKT conditions do not hold for LPs
To dual feasibility and complementary slackness
Explanation. For an LP stationarity of the Lagrangian is dual feasibility and complementarity is complementary slackness: the KKT conditions generalize LP theory.
The function $f(x_1, x_2) = x_1^2 + \gamma x_1 x_2 + x_2^2$ has matrix $\mathbf Q = \begin{pmatrix} 2 & \gamma \\ \gamma & 2 \end{pmatrix}$. For which $\gamma$ is it convex?
For $|\gamma| \le 2$
For $\gamma \ge 0$
For every $\gamma$
For $|\gamma| \le 1$
Explanation. $\mathbf Q \succeq 0$ if and only if the principal minors are non-negative: $2 \ge 0$ and $4 - \gamma^2 \ge 0$, that is $|\gamma| \le 2$.
QP $\min\ x_1^2 + 2x_2^2$ with $x_1 + x_2 \ge 6$, $x_1, x_2 \ge 0$. What are the optimal solution and the optimal value?
$(3, 3)$, value $27$
$(6, 0)$, value $36$
$(4, 2)$, value $24$
$(2, 4)$, value $36$
Explanation. The constraint is active and the partial derivatives coincide at the optimum: $2x_1 = 4x_2$, with $x_1 + x_2 = 6$ one gets $(4, 2)$ and $16 + 8 = 24$.
In the same QP ($\min\ x_1^2 + 2x_2^2$, $x_1 + x_2 \ge 6$) why are the partial derivatives $2x_1$ and $4x_2$ equal at the optimum?
Because the feasible region is symmetric about the bisector
Otherwise it would pay to shift quantity between the variables
Because the two coefficients of the objective are equal
Because the threshold constraint is not active at the optimum
Explanation. If one derivative were smaller, shifting some quantity to the variable that is cheaper at the margin would reduce the objective while staying on the constraint; the common derivative is the multiplier, $8$.
With the KKT conditions one solves $\min\ (x-3)^2 + (y-1)^2$ with $x + 2y \le 2$, $x, y \ge 0$. Which point is optimal?
$(3, 1)$, the centre of the level curves
$(0, 1)$, on the constraint $x + 2y = 2$
$(1.6;\ 0.2)$, projection without the bounds
$(2, 0)$, with $x + 2y \le 2$ and $y \ge 0$ active
Explanation. The centre $(3, 1)$ is not feasible; with only $x + 2y \le 2$ active one would get $y < 0$. With $y \ge 0$ active too: $(2, 0)$, multipliers $\lambda = 2$ and $\mu = 2$, both non-negative.
In the QP $\min\ x_1^2 + 2x_2^2$ with $x_1 + x_2 \ge d$ the optimal value is $\tilde f(d) = \tfrac23 d^2$. What is the multiplier of the constraint at $d = 6$?
$24$
$4$
$8$
$\tfrac23$
Explanation. The multiplier is the derivative of the optimal value with respect to the right-hand side: $\tilde f'(d) = \tfrac43 d = 8$ at $d = 6$, as $\lambda = 2\tilde x_1 = 4\tilde x_2$.
A multiplier is estimated by perturbation: $\tilde f(d + \varepsilon) \approx \tilde f(d) + \lambda\,\varepsilon$. Under which assumption is the approximation good in a QP?
$\varepsilon$ small: the curvature is negligible
$\varepsilon$ large: numerical errors weigh less
The perturbed constraint is not active at the optimum
The QP is not convex, so the estimate is linear
Explanation. In the example QP $\tilde f(6 + \varepsilon) = 24 + 8\varepsilon + \tfrac23\varepsilon^2$: the quadratic term is negligible only for small $\varepsilon$.
A gurobipy model contains the product $p \cdot q$ of two decision variables (price times quantity, a bilinear term). Which parameter must be set for Gurobi to solve it?
`m.Params.NonConvex = 2`
`m.Params.FuncNonlinear = 1`
`m.Params.QCPDual = 1`
None: bilinear terms are convex
Explanation. Bilinear (non-convex) terms require `NonConvex = 2`; `FuncNonlinear = 1` is for the general functions introduced with `addGenConstrLog/Exp/Pow`.
The objective of a gurobipy model must contain $\log(1 + k x)$, with $x$ a decision variable and $k > 0$ a datum. How is this term introduced?
Directly in `setObjective`, writing `gp.log(1 + k*x)`
With a piecewise-linear approximation of the log written by hand
With auxiliary variables $g = 1 + kx$, $z$ and the constraint `m.addGenConstrLog(g, z)`
It cannot: Gurobi accepts only linear and quadratic expressions
Explanation. Nonlinear functions enter as function constraints on auxiliary variables; with `FuncNonlinear = 1` they are handled exactly and the optimum is certified global.
The course uses a single solver, Gurobi, for all its models, including the non-convex ones (pricing). Why?
Because local solvers are slower on convex problems, the most common ones
Because it certifies a global optimum also for non-convex models, with one syntax
Because Gurobi reformulates every model as an equivalent LP
Because Gurobi returns the duals for every class of model
Explanation. With a local solver every result would carry the doubt “is it only a local optimum?”. Duals are not available with function or bilinear constraints.
A convex QP (e.g. Markowitz) is solved with gurobipy, and the attribute `Pi` of its linear constraints is not available. What does the course suggest?
Declare the model with `NonConvex = 2`
Read `SARHSLow`/`SARHSUp` instead of `Pi`
Set `m.Params.QCPDual = 1`, or check the multiplier by perturbation
Assume all multipliers are zero
Explanation. For QPs the LP duals are not returned by default: `QCPDual = 1` asks for them, and perturbing the right-hand side by $\varepsilon$ checks them.
Gurobi handles nonlinear models through special parameters: `NonConvex = 2` for bilinear terms, `FuncNonlinear = 1` for functions such as $\log$. Which course model needs neither, being purely conic?
Pricing, with the term $p \cdot q$
The advertising budget, with $\log(1 + k_ix_i)$
The M/M/1 queue, with the constraint $w(\mu - \lambda) = 1$
Weber location, with $d_x^2 + d_y^2 \le d_i^2$
Explanation. Convex quadratic or conic structures (a convex QCP) need nothing special; bilinear terms need `NonConvex = 2`, function constraints `FuncNonlinear = 1`.
A course model contains the mean time in an M/M/1 queue, $w = 1/(\mu - \lambda)$, with capacity $\mu$ a decision variable. How is it written for Gurobi?
Directly as `w == 1/(mu - lam)` in `addConstr`
With `addGenConstrLog` applied to $\mu - \lambda$
With the bilinear constraint $w(\mu - \lambda) = 1$
By fixing $\mu$ and solving one LP per value of $\mu$
Explanation. Ratios are reformulated with an auxiliary variable and a bilinear constraint, `m.addQConstr(w * (mu - lam) == 1)`, which requires `NonConvex = 2`; gurobipy does not accept a division by a variable.
A course script estimates differences between two close optimal values (a marginal analysis). Which Gurobi parameters do the notes tighten to $10^{-9}$?
`TimeLimit` and `OutputFlag`
`FeasibilityTol` and `OptimalityTol`
`NonConvex` and `FuncNonlinear`
`Threads` and `Seed` of the solver
Explanation. For accurate marginal analyses the tolerances are tightened: `MIPGap`, `FeasibilityTol` and `OptimalityTol` at $10^{-9}$. The other parameters control time, log and nonlinear features.
A pricing model with constant-elasticity demand needs the constraint $q \le A\,p^{-\varepsilon}$ ($p$ price, $q$ quantity, $\varepsilon > 1$), where $p^{-\varepsilon}$ is tiny. How do the notes rewrite it?
As $q\cdot r \le A$ with an auxiliary $r = p^{\varepsilon}$
As $\log q \le \log A + \varepsilon\log p$
As $q \le A$, dropping the price term
As $q\,p \le A$, a bilinear constraint
Explanation. Scaling: with $r = p^{\varepsilon}$ (a power constraint) the condition becomes $q\,r \le A$, which keeps the numbers in a healthy range. The logarithmic form has the wrong sign of the exponent.
A multiplier is estimated by perturbation: the right-hand side is raised by $\varepsilon$, the model is solved again and the difference of the two optimal values is divided by $\varepsilon$. Why do the course scripts tighten the solver tolerances to $10^{-9}$ for this?
Because otherwise Gurobi refuses to solve twice
Because the multiplier must be an integer
To make the two solves faster
Otherwise numerical error dominates the difference
Explanation. The incremental ratio divides a small difference by a small $\varepsilon$: with default tolerances (around $10^{-6}$) the numerical noise of each optimum can be comparable to the difference itself.
A model with a functional constraint (`addGenConstrLog`) gives no duals. The budget constraint is raised from $100$ to $100.1$ and the optimal value goes from $500$ to $501.2$. What is the perturbation estimate of its multiplier?
$1.2$
$12$
$0.12$
$120$
Explanation. Incremental ratio: $(501.2 - 500)/0.1 = 12$ per unit of right-hand side. Forgetting to divide by $\varepsilon = 0.1$ gives $1.2$.
In a convex QP with linear constraints solved with gurobipy, where is the KKT multiplier of a linear constraint read?
In the `RC` attribute of the variable
It is not read: it must always be estimated by perturbation
In the `Pi` attribute of the constraint
In the `SARHSUp` attribute of the constraint
Explanation. In convex QPs with linear constraints Gurobi returns the multipliers as in LPs: the `Pi` attribute of each constraint is the KKT multiplier.
QP $\min\ x_1^2 + 2x_2^2$ with $x_1 + x_2 \ge d$: the optimal value is $\tilde f(d) = \tfrac{2}{3}d^2$ and the multiplier at $d = 6$ is $8$. Re-optimizing with $d = 7$ the value rises from $24$ to $32.67$, not to $32$. Why?
Because the multiplier of a QP holds only if the constraint is not active
Because Gurobi returns QP multipliers with a numerical error
Because with $d = 7$ the constraint stops being active
Because the optimal value has curvature: the multiplier is exact only at the margin
Explanation. $\tilde f(6 + \varepsilon) = 24 + 8\varepsilon + \tfrac{2}{3}\varepsilon^2$: the multiplier gives the linear term, the curvature adds $\tfrac23$ for $\varepsilon = 1$. This is why the check uses a small $\varepsilon$.
A gurobipy model has a bilinear term $p \cdot q$ (price times quantity). What is needed for Gurobi to solve it to global optimality?
Nothing: every quadratic term is convex
`m.Params.QCPDual = 1`
`m.Params.NonConvex = 2`
`m.Params.FuncNonlinear = 1` and a functional constraint
Explanation. A bilinear term is not convex; with `NonConvex = 2` Gurobi solves it with global techniques. `QCPDual` concerns duals, `FuncNonlinear` functions such as log and exp.
A model contains the functional constraint $z = \log(1 + k x)$ written with `addGenConstrLog`. One wants the multiplier of the bound $x \le b$: how is it obtained?
By perturbation: $b$ slightly higher, then the difference quotient
From the `Pi` attribute of the bound $x \le b$ at the optimum
From the `RC` attribute of the auxiliary variable $z$
From the `QCPi` attribute of the functional constraint
Explanation. With functional constraints the solver provides no duals: the multiplier is estimated by perturbation.
One wants to compare two very close optima of a nonlinear model (to estimate a multiplier by difference). Which device does the course recommend?
Reducing the number of auxiliary variables of the model
Using a local solver faster than Gurobi
Rounding all the data to the second decimal digit
Tightening Gurobi's tolerances to $10^{-9}$
Explanation. Differences between two close optima are small: with the default tolerances the numerical error may exceed them, so they are tightened to $10^{-9}$.
Why does the course use a single solver (Gurobi) also for non-convex problems, instead of a local solver?
Because local solvers do not accept linear constraints
Because Gurobi certifies the global optimum also in non-convex problems
Because the non-convex problems of the course are actually linear
Because a local solver does not compute multipliers
Explanation. With a local solver every result would come with the question ``is it only a local optimum?''; Gurobi gives a certified global optimum with the same syntax.
In a convex QP with linear constraints `Pi` is the KKT multiplier of the constraint. For which increments of the right-hand side is the estimate $\Delta f \approx \pi\,\Delta$ exact?
Only at the margin, for small increments
For every increment, as happens in LPs
Within the `SARHSLow`–`SARHSUp` range
For none: in QPs `Pi` has no meaning
Explanation. Unlike LPs, where the optimal value is piecewise linear, in QPs it is curved: the multiplier is exact only at the margin.
One wants the multiplier of a *quadratic* constraint (for instance $d_x^2 + d_y^2 \le d^2$). What is needed for Gurobi to return it?
Nothing: reading the `Pi` attribute is enough
Setting `NonConvex = 2` before optimizing
`QCPDual = 1`, then the `QCPi` attribute
Rewriting it as a functional constraint `addGenConstrPow`
Explanation. For quadratic constraints the duals are requested with `QCPDual = 1` and read in `QCPi`; otherwise the multiplier is estimated by perturbation.
A parameter estimated from data (e.g. an expected return) changes at the second decimal digit when the sample changes slightly. How many digits should a lab report show?
Six, to be as precise as possible
Few: six decimals of an estimate wobbling at the second mislead
None: estimates should not be reported
As many as the solver prints
Explanation. Spurious precision is in the checklist of mistakes: the digits shown must reflect the reliability of the estimate.
In the essential path of NLP Modelling, what is done in the fourth session?
A multi-period LP is formulated from scratch
A quantile regression is estimated on the data
A MIP with binary variables is solved
A project of your choice, presented to managers
Explanation. The fourth session is a project of your choice (supply chain, location, EV charging, queues, SVM or least squares) with a presentation of the results.
In the third session of NLP Modelling (pricing or budget) what are the learning objectives?
Nonlinear functions, concavity and checking the KKT conditions
Read the shadow prices and reduced costs of an LP
Trace the efficient frontier of Markowitz
Estimate the parameters of an SVM with a kernel
Explanation. Pricing and budget have nonlinear functions (bilinear revenue, concave responses): concavity is studied and the KKT conditions are verified numerically.
An item of the checklist of mistakes is ``believing a problem convex when it is not''. Why is it serious?
Because Gurobi always rejects non-convex problems
Because the multipliers all become zero
Because the model becomes infeasible
Because a local optimum is mistaken for a global one
Explanation. Without convexity a stationary point may be only a local optimum; declaring non-convexity (`NonConvex = 2`) makes the solver search for the global one.
In gurobipy the constraint `x + 5 <= 10` is stored as $x \le 5$. Under which condition is the value assigned to `c.RHS` exactly the number on the right of the constraint as it was written?
Always: `RHS` is the number written on the right of the constraint
Only if the model is convex and has no bilinear terms
Only after calling `m.update()` on the model
Only if the constraint has all the constants on the right
Explanation. Constants on the left are moved into the right-hand side: here `RHS` equals 5, not 10, and setting it to 12 gives $x \le 12$. It is mistake 5 of the checklist.
Minimum-cost production-inventory LP (products $i$, months $t$; $x_{it}$ = units produced, $s_{it}$ = inventory at the end of month $t$, $d_{it}$ = demand). The term $\gamma \sum_{t=2}^{m} (v_t - v_{t-1})^2$, with $\gamma > 0$ and $v_t = \sum_i x_{it}$ the total production of month $t$, is added to the minimized cost. What is it for?
To penalize the inventory held at the end of each month
To keep the problem an LP while adding a cost
To smooth the plan, penalizing changes of pace between months
To reduce the demand to be served in the peak months
Explanation. It is the QP variant: in the case study, with $\gamma = 0.5$ the profile becomes almost flat at a cost of only $0.35\%$.
Minimum-cost production-inventory LP (products $i$, months $t$; $x_{it}$ = units produced, $s_{it}$ = inventory at the end of month $t$, $d_{it}$ = demand). The smoothing variant adds $\gamma\sum_{t=2}^m (v_t - v_{t-1})^2$, with $v_t = \sum_i x_{it}$ and $\gamma > 0$, to the linear cost. To which class does the resulting model belong?
A non-convex QP, because of the squares
An LP, because the constraints are linear
A non-convex NLP that needs `NonConvex = 2`
A convex QP: a sum of squares with $\gamma > 0$ plus linear terms
Explanation. Each $(v_t - v_{t-1})^2$ is the square of a linear function, hence convex; with $\gamma > 0$ and linear constraints the model is a convex QP and its optimum is global.
In the production and inventory case the minimum-cost linear plan has a total production going from 219.5 to 389.0 units per month. Why is a quadratic penalty on the jumps added?
Because every change of pace has costs the linear model does not see
Because the linear model is infeasible in the peak months
Because the penalty reduces the demand to serve
Because without the penalty Gurobi does not find the global optimum
Explanation. Overtime, shifts to reorganize and suppliers to realign make changes of pace costly; the linear model ignores them, the penalty prices them.
Quadratic penalty $\gamma \sum_t (v_t - v_{t-1})^2$ on the jumps of total production. Compared with a jump of 10 units, how much does a jump of 20 units cost?
The same, because the penalty only counts sign changes
Twice as much
Four times as much
Eight times as much
Explanation. The cost is proportional to the square of the jump: $20^2 / 10^2 = 4$. This is why the model prefers many small adjustments to a few large jumps.
In the production model with smoothing, what stays the same as in the linear model of LP Modelling?
Only the objective
Data, variables and constraints
Only the capacity constraints
Nothing: the case is new
Explanation. A single datum is added, the weight $\gamma$; data, variables $x_{it}$, $s_{it}$ and balance and capacity constraints stay those of the linear case.
Production with smoothing: $\gamma \sum_{t=2}^{m} (\sum_i x_{it} - \sum_i x_{i,t-1})^2$ with $\gamma \ge 0$ is added to the linear objective; the constraints are linear. Which property guarantees that every local minimum is global?
The balance constraints are equalities, not inequalities
The production and stock variables are non-negative
The number of months of the horizon is finite and small
The square of a linear function is convex, so is the weighted sum
Explanation. Every jump is linear in the variables, its square is convex and a non-negatively weighted sum of convex functions is convex: with linear constraints the QP is convex.
In the production QP with smoothing the term is $\gamma \sum_t (v_t - v_{t-1})^2$. For which values of $\gamma$ does the model stay a convex QP?
Only for $\gamma > 1$
For every $\gamma \ge 0$
Only for $\gamma \le 1/160$
For every real value of $\gamma$
Explanation. With $\gamma \ge 0$ a convex function is added; with $\gamma < 0$ a square would be subtracted and the problem would become non-convex (it would reward jumps).
In the same example (one product, two months, $h = 1$, jump $40 - 2s_1$) the derivative at $s_1 = 0$ is $f'(0) = 1 - 160\gamma$. For which values of $\gamma$ does it pay to keep stock?
For every $\gamma > 0$
Only for $\gamma \ge 1$
Only for $\gamma > 1/160$
Never: holding always costs
Explanation. If $f'(0) \ge 0$ (that is $\gamma \le 1/160$) increasing $s_1$ does not pay and the optimum is $s_1 = 0$; with $\gamma = 0.004$ the solver indeed gives zero stock.
Two-month example with smoothing ($h = 1$): at the optimum with positive stock the multipliers of the two balances are $\tilde\pi_1 = 9.5$ and $\tilde\pi_2 = 10.5$. What do the KKT conditions say about their difference?
That it equals $\gamma$
That it equals the holding cost $h$
That it is zero, because the stock is free
That it equals the optimal jump
Explanation. Stationarity with respect to $s_1 > 0$ gives $h + \tilde\pi_1 - \tilde\pi_2 = 0$: one more unit of demand in month 2 costs one holding period more than one in month 1.
In the production script with smoothing `tot[t]` is the total production of month $t$ and `costo` the linear cost. How is the objective written in gurobipy?
`m.addConstr(costo + gamma * salti <= 0)` with `salti` the sum of the squared jumps
`m.setObjective(costo, GRB.MINIMIZE)` and then `m.Params.NonConvex = 2` for the jumps
`m.addGenConstrPow(salti, costo, 2)` and then `m.setObjective(costo, GRB.MINIMIZE)`
`m.setObjective(costo + gamma * salti, GRB.MINIMIZE)` with `salti` the sum of the squared jumps
Explanation. The quadratic term is written as a product of linear expressions and added to the cost in the objective; the QP is convex and no special parameter is needed.
The production script with smoothing does not read the data from a file: it writes them in the code with the same values as the linear case. Why?
Because it also runs in Colab; the CSVs live in the LP Modelling repository
Because Gurobi cannot read the CSV files of the case studies
Because the data of the quadratic case differ from the linear ones
Because Colab notebooks cannot import pandas
Explanation. The data live in a single repository (LP Modelling); the NLP script writes them again with the same values, so it is self-contained also in Colab.
Production case study: the linear plan costs €32,889.33; with $\gamma = 0.5$ the production and holding cost is €33,000.96 and the largest jump falls from 81.4 to 1.2 units. How much does smoothness cost, in percent?
About 3.4%
About 0.34%
About 34%
Nothing: the cost does not change
Explanation. $33{,}000.96 - 32{,}889.33 = 111.63$ €, that is $0.34\%$ of the linear cost: an almost flat plan costs very little.
With smoothing ($\gamma = 0.5$) mostly product 1 goes to stock ($a_1 = 0.9$ hours per unit), while in the linear plan the stock built in advance was that of product 3 ($a_3 = 2.1$). Why?
Because product 1 has the highest holding cost of the three
Because the penalty reduces the demand to serve of product 3
Because in the QP product 3 can never be held in stock
Because the penalty counts units: product 1 gives more per hour
Explanation. The quadratic term levels total production in *units*; to raise the units of the first months for the same hours the product using fewer hours per unit pays, product 1.
Production QP with $\gamma = 0.5$: the multiplier of the capacity of month 6 is $-3.134$ €/hour. With one more hour the optimal value falls by $3.060$; with $0.01$ hours the difference quotient is $-3.133$. What can be concluded?
That Gurobi computes the multipliers of convex QPs wrongly
That the capacity constraint of month 6 is not active
That the multiplier holds at the margin: check it with a small $\varepsilon$
That the multiplier must be multiplied by the weight $\gamma$
Explanation. The optimal value of a QP has curvature: for finite increments the change departs from the multiplier, which is the derivative. With $\varepsilon = 0.01$ the quotient goes back to the multiplier.
With smoothing ($\gamma = 0.5$) the capacity multipliers of months 1–3 are zero, while in the linear model those of months 2 and 3 were negative. Why?
Because in the QP the multipliers of the first months are not computed
Because the levelled plan does not saturate the hours in the first months
Because the capacity of the first months was increased in the QP
Because the demand of the first three months is zero
Explanation. The smooth plan produces about 325 units every month and in the first months it does not use all the hours: the capacity constraints are not active and, by complementarity, their multiplier is zero.
Cost-smoothness frontier of production: with $\gamma = 0.01$ the sum of the squared jumps falls from 13,699 to 2,075 and the cost rises by €48. What shape does the frontier have?
Linear: every reduction of the jumps always costs the same
Flat: smoothness costs nothing at any level
Increasing at first and then decreasing to the right
Steep at first: the first steps towards smoothness cost little
Explanation. The first reductions of the jumps cost very little; reaching an almost flat plan costs about €112 in all out of 33,000.
5. Supply chain with congestion and sustainability (27)
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. In the flow conservation constraint $\sum_{j:(i,j)\in A} x_{ij} - \sum_{j:(j,i)\in A} x_{ji} = b_i$ (outgoing minus incoming flow), a market, i.e. a demand node, has:
$b_i > 0$
$b_i < 0$
$b_i = 0$
$b_i = \sum_{j:(j,i)\in A} u_{ji}$
Explanation. Out minus in equals the balance: positive at plants (supply), negative at markets (demand), zero at hubs (transit).
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. The congestion term $\alpha\,c_{ij}\,x_{ij}^2/u_{ij}$, with $\alpha > 0$, is added to the cost of every arc. What is its effect on the optimal flows?
It saturates the cheapest routes even more
It makes the model non-convex and harder to solve
It spreads the flow over several routes instead of saturating one
It reduces the total demand that must be served
Explanation. The term is convex and grows with the utilization $x_{ij}/u_{ij}$: in the case study no arc stays saturated, as a prudent planner would choose.
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. An internal CO$_2$ price $\tau$ (€/kg) is added to the arc costs, $c_{ij} + \tau e_{ij}$ ($e_{ij}$ = emissions per unit). As $\tau$ grows, the cost-emissions frontier of the LP proceeds by jumps. Why?
LP optima lie at vertices: the optimum stays on a vertex, then jumps to another
The emissions data $e_{ij}$ are rounded to whole kilograms
The solver stops before the optimum for some values of $\tau$
The capacities $u_{ij}$ change with $\tau$ in steps
Explanation. In the case study nothing changes up to $\tau = 1$ €/kg and the main jump happens at $\tau = 1.25$. A strictly convex model (with congestion) would move continuously.
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. At the optimum an arc with cost $c_{ij} = 7$ €/unit carries no flow and has reduced cost $+2$ (Gurobi attribute `RC`). Below which cost would it start carrying flow?
Above $9$ €/unit
Below $7$ €/unit
It never would: positive `RC` means useless
Below $5$ €/unit
Explanation. In a minimization the reduced cost of a variable at zero is the improvement it needs: threshold $7 - 2 = 5$ €/unit (`SAObjLow`); above it the arc stays unused.
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. $e_{ij}$ are the kg of CO$_2$ emitted per unit sent on arc $(i,j)$. How is an internal CO$_2$ price $\tau$ (€/kg) introduced in the model?
With a binary variable for each polluting arc
Replacing $c_{ij}$ with $c_{ij} + \tau\,e_{ij}$ in the objective
Adding the constraint $\sum e_{ij}x_{ij} = \tau$
Multiplying every capacity $u_{ij}$ by $\tau$
Explanation. This is the “weight” approach, with no new constraints; the alternative imposes $\sum e_{ij}x_{ij} \le \bar e$ and reads the dual of that constraint.
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. The “pure” minimax utilization model minimizes $z$ subject to $x_{ij}/u_{ij} \le z$ on every arc and the flow constraints. Why is it not used alone?
Any routing with utilization at most $\tilde z$ is optimal, even a very expensive one
It is non-convex because of the ratios $x_{ij}/u_{ij}$
It is always infeasible when some arc is saturated
Gurobi cannot solve problems with a minimax objective
Explanation. The pure minimax is degenerate in the cost; in practice one minimizes cost $+\,\rho\, z$ or bounds $z$ and minimizes the cost.
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. The demand of each market is a flow conservation constraint. In the case study the shadow prices of these constraints range between $8$ and $10.50$ €/unit. What do they represent?
The selling prices charged in the markets
The residual capacities of the arcs entering the markets
The marginal cost of serving one more unit in each market
The CO$_2$ emitted per unit delivered to each market
Explanation. They are the marginal costs of service: the number to compare with the commercial margin before accepting new orders.
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. With the congestion term $\alpha c_{ij}x_{ij}^2/u_{ij}$ ($\alpha > 0$) the optimal flows move continuously as the data change, while in the LP they can jump. Which property is responsible?
The linearity of the flow conservation constraints
The strict convexity of the objective, which gives a unique optimum
The non-negativity of the flows $x_{ij}$
The integrality of the capacities $u_{ij}$
Explanation. With a strictly convex objective the optimum is unique and varies continuously with the data; an LP can have its optimum jump between vertices.
Supply chain with congestion: 100 units go on two routes; route 1 costs $2x_1 + x_1^2/40$ (cost $c_1 = 2$, capacity $u_1 = 80$, $\alpha = 1$), route 2 costs $5$ €/unit with ample capacity. At the optimum the marginal costs are equal. What is the split $(x_1, x_2)$?
$(80, 20)$
$(100, 0)$
$(60, 40)$
$(50, 50)$
Explanation. Marginal cost of route 1: $2 + x_1/20$; setting it equal to $5$ gives $x_1 = 60$, $x_2 = 40$. The LP without congestion would fill route 1 up to its capacity, $(80, 20)$.
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. Node balances $b_i$ are positive at plants (supply), negative at markets (demand), zero at hubs. Which condition on the balances is necessary for the model to be feasible?
$\sum_{i \in N} b_i \ge 0$: total supply covers total demand
$b_i \le u_{ij}$ for every arc leaving $i$
$\sum_{i \in N} b_i < 0$: demand exceeds supply
All $b_i$ must be integers
Explanation. If total demand exceeds total supply no flow can satisfy all conservation constraints; capacities can make the model infeasible even when the balance condition holds.
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. $e_{ij}$ = kg of CO$_2$ per unit on arc $(i,j)$. Instead of an internal price, the company imposes a cap $\sum e_{ij}x_{ij} \le \bar e$ on total emissions. What does the shadow price of this constraint represent?
The emissions saved per euro spent
The total cost of the network divided by $\bar e$
The emissions of the cheapest route
The implicit CO$_2$ price: cost change per kg of extra allowance
Explanation. The dual of the cap is the marginal cost of abatement: it is the internal price $\tau$ that would produce the same routing with the “weight” approach.
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. Congestion version: each arc costs $c_{ij}x_{ij} + \alpha c_{ij}x_{ij}^2/u_{ij}$. Which facts make this model convex?
The flows are integers and the capacities are positive
Explanation. $x_{ij}^2$ is convex and is multiplied by the non-negative coefficient $\alpha c_{ij}/u_{ij}$; the conservation and capacity constraints are linear, so the feasible set is a polyhedron.
The supply-chain chapter of the course asks three managerial questions about a network with costs, capacities and CO$_2$ footprints. Which one concerns CO$_2$?
How many plants should be opened or closed?
Which market should be dropped first?
How much should each arc be taxed by the state?
Which CO$_2$ price makes clean routes pay?
Explanation. The three questions: how to route flows at minimum cost, what changes when congestion is penalized, and how high an internal CO$_2$ price must be for the «clean» routes to become convenient.
According to the course notes, why is the network-flow structure of the supply-chain model worth learning well?
It is the only structure Gurobi can solve
It is among the most reusable OR structures
It always has integer optimal solutions
It needs no capacities on the arcs
Explanation. Routes, loads per arc, capacity investments and carbon accounting all share the same structure; flow models reappear across logistics, energy and telecommunications.
In the supply-chain chapter, the effective cost of a route «grows rapidly as it approaches saturation». What does this represent in practice?
Overtime, queues, insurance premiums
Taxes on CO$_2$ emissions
The fixed cost of opening a new route
Discounts granted for large volumes
Explanation. Congestion costs grow more than linearly with the use of an arc; the chapter models them with a convex quadratic term $\alpha c_{ij}x_{ij}^2/u_{ij}$.
Which daily decisions of a logistics manager does the supply-chain chapter of the course address?
Hiring and firing the truck drivers
Setting the selling prices of the products
Routes, arc loads, capacity, carbon
Scheduling the maintenance of trucks
Explanation. Routing, deciding how much to load each arc, evaluating capacity investments and reporting the carbon footprint: all readable from the flow model and its duals.
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). One market demands $100$ units; route 1 costs $2$ €/unit with capacity $80$, route 2 costs $5$ €/unit with ample capacity. What does the pure LP do, and at what cost?
Splits 50–50, cost $350$ €
Fills route 1, overflows: $260$ €
Uses only route 2, cost $500$ €
Uses only route 1, cost $200$ €
Explanation. The cheap route is saturated ($x_1 = 80$) and the rest goes on route 2 ($x_2 = 20$): $2\cdot 80 + 5\cdot 20 = 260$ €. Route 1 alone cannot carry 100 units.
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). One market demands $100$; route 1 ($2$ €/unit, capacity $80$) is saturated, route 2 ($5$ €/unit) carries 20. What are the shadow prices of the demand and of the capacity of route 1?
Demand $2$, capacity $5$
Demand $3$, capacity $-2$
Demand $0$, capacity $0$
Demand $5$, capacity $-3$
Explanation. The 101st unit would travel on route 2, costing 5; one more unit of capacity on route 1 moves a unit from route 2 to route 1, saving $5 - 2 = 3$ (dual $-3$ for a $\le$ capacity in a minimum).
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Two routes for 100 units; with congestion ($\alpha = 1$) the cheap route carries $60$ units instead of $80$ although its capacity is 80. Why does the model leave it unsaturated?
Marginal costs of the routes equalize
A hidden capacity constraint at 60 units
The solver stops before the optimum
Because congestion makes route 1 more expensive on average than route 2
Explanation. With the quadratic term the marginal cost of route 1, $2 + x_1/20$, grows with the flow; at $x_1 = 60$ it equals the 5 € of route 2, and moving more flow would cost more: a safety margin, as a prudent planner would keep.
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). In the gurobipy code the plants are written `x.sum(s, '*') <= offerta[s]`. Why an inequality?
Because plants can also receive flow
Because Gurobi does not accept equalities on sums
Total supply 500 exceeds demand 450
Because supply is uncertain
Explanation. With supply larger than demand, forcing every plant to ship all its supply would make the model infeasible; the hubs instead are written as equalities (in = out).
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). In the code the arc capacities are given as variable bounds, `x = m.addVars(A, ub=U)`, not as constraints. Where is the value of one more unit of capacity on a saturated arc then read?
In the reduced cost `RC` of the arc variable
In the `Pi` of a capacity constraint
In the `Slack` of the hub constraint
Nowhere: bounds have no dual
Explanation. For a variable at its upper bound, `RC` is the shadow price of the bound: a saturated arc in a minimum has $\texttt{RC} < 0$, the saving per extra unit of capacity.
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). How are costs and emissions of the arcs chosen in the case study, and why?
Proportional, to keep the LP simple
All equal, to isolate the effect of capacity
Random, to test robustness
Not proportional: road cheap, rail clean
Explanation. If emissions were proportional to costs, minimizing cost would also minimize emissions and there would be no trade-off; the case is built so that cost and CO$_2$ conflict.
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). In the code the hubs are written `x.sum('*', h) == x.sum(h, '*')`. What does it express?
Each hub ships its full capacity
Hubs hold no stock: what enters leaves
Each hub receives from one plant only
Hubs have a positive balance
Explanation. It is the conservation constraint of a transit node, balance $b_h = 0$: inflow equals outflow.
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). The shadow prices of the four market demands are $8.00$, $9.50$, $10.00$ and $10.50$ €/unit. What is the managerial use of these numbers?
They are the selling prices to charge
They are the average transport costs
Marginal costs of serving each market
They measure the CO$_2$ of each market
Explanation. Each is the cost of serving one more unit of that market; M4 costs $31\%$ more than M1. They are also the right basis for an internal transfer price.
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). Case results: pure LP cost $3385$ €, max utilization $100\%$; with congestion ($\alpha = 1$) cost $3702.81$ €, max utilization $90\%$; minimax: $58.4\%$. What is the $58.4\%$?
The lowest achievable maximum utilization
The share of arcs used by the plan
The utilization of the cheapest arc
The cost increase of the minimax plan
Explanation. The minimax model $\min z$ with $x_{ij}/u_{ij} \le z$ finds the routing that keeps the most loaded arc as empty as possible: no plan can load every arc below $58.4\%$.
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). Internal CO$_2$ price $\tau$ (€/kg) added to the arc costs: up to $\tau = 1$ nothing changes; the main jump happens at $\tau = 1.25$ €/kg. What does this mean for the manager?
Emissions fall linearly with $\tau$
Any positive $\tau$ changes the routes
$\tau$ has no effect at all on an LP
Below it nothing changes; above, a jump
Explanation. LP optima sit at vertices: the solution stays on one vertex and then jumps. A CO$_2$ price below the threshold changes nothing; above it, the whole network moves toward rail.
Minimum-cost flow LP with costs $c_{ij} + \tau e_{ij}$ ($\tau$ = internal CO$_2$ price, $e_{ij}$ = kg per unit): as $\tau$ grows, emissions stay constant on intervals and then drop in jumps. Which LP property explains it?
The LP has a unique solution for every $\tau$
An optimal vertex always exists
The objective is convex in the flows
The flows are always integer numbers
Explanation. For each $\tau$ an optimal vertex exists; it stays optimal on an interval of $\tau$ and is then replaced by an adjacent vertex. A strictly convex model (congestion) would move continuously instead.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. Where does diversification come from?
From the covariances $q_{ij}$ in the variance, which reward weakly correlated assets
From the return constraint, which forces several assets into the portfolio
From the caps $x_i \le u_i$, which forbid investing everything in one asset
From the budget constraint $\sum_i x_i = 1$, which spreads the capital
Explanation. The variance contains the covariances: combining weakly correlated assets lowers the risk below that of each component, even without caps.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. Without the return constraint, the minimum-variance portfolio already has expected return $11.06\%$. What is the multiplier of the constraint “expected return at least $\bar r = 8\%$”?
Positive, because every point of return costs variance
Negative, because the constraint is a lower bound
Zero, because the constraint is not active
Undefined, because the model is a QP
Explanation. The constraint does not bite up to $11.06\%$, so by complementarity its multiplier is zero; only beyond that threshold every extra point of return is paid in variance.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. The inputs $\mu_i$ and $q_{ij}$ are estimated from 60 months of returns. What is the main practical lesson of the case study about these estimates?
Covariances are much harder to estimate than expected returns
Expected returns are far less stable than covariances, and the optimum chases their errors
Sixty months of data give estimates accurate enough to trust the optimum
The caps $x_i \le u_i$ remove the estimation errors from the inputs
Explanation. An asset with a true expected return of $11\%$ shows an estimated $1.6\%$ over 60 months. Remedies: caps, shrinkage, or the minimum-variance portfolio only.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. The efficient frontier collects the portfolios of minimum variance for each $\bar r$. In the case study, how does the equally weighted portfolio $x_i = 1/n$ compare with it?
It lies exactly on the efficient frontier
It coincides with the minimum-variance portfolio
It lies above the frontier, dominating it
It is dominated: similar return, almost twice the volatility
Explanation. The “I know nothing” strategy is clearly dominated; the minimum-variance portfolio has volatility $6\%$ and return $11\%$.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. Varying $\bar r$ traces the efficient frontier. Which formulation does **not** trace the same frontier?
$\max \sum_i \mu_i x_i$, with no risk term and no bound on the variance
$\max \sum_i\mu_ix_i$ with variance at most $\bar\sigma^2$, varying $\bar\sigma$
$\min$ variance with expected return exactly $\bar r$ on the upper branch
Explanation. Threshold on the return, mean-variance and bound on the variance trace the same frontier; maximizing the return alone gives only one extreme point.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. A mandate adds the cap $x_i \le 30\%$ for every asset. What is the effect on the efficient frontier?
It cuts the upper part: the highest returns become unreachable
It shifts the whole frontier upwards, improving every portfolio
It has no effect, since optimal portfolios are already diversified
It lowers the minimum attainable variance
Explanation. Mandate constraints restrict the feasible set, so they can only worsen the frontier; their cost is the distance between the two frontiers, largest at high returns.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. Which statement about this QP is correct?
It is convex only if short selling is forbidden ($x_i \ge 0$)
It is convex only if the assets are uncorrelated ($q_{ij} = 0$ for $i \ne j$)
Every covariance matrix is positive semidefinite, so the QP is convex and its optimum global
Every covariance matrix is positive definite, so the optimal portfolio is unique
Explanation. Covariance matrices are $\succeq 0$, not necessarily $\succ 0$: convexity holds with any linear constraints, uniqueness is not guaranteed.
Markowitz model with two uncorrelated assets of variances $\sigma_1^2$, $\sigma_2^2$, no return constraint: minimize $\sigma_1^2x_1^2 + \sigma_2^2x_2^2$ with $x_1 + x_2 = 1$. Which steps prove that $x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$ is optimal?
The return constraint must be active at the optimum
Strong LP duality between the QP and its dual
The caps $x_i \le u_i$ must be inactive at the optimum
Substitute $x_2 = 1 - x_1$: a convex parabola, whose stationary point is the minimum
Explanation. $f(x_1) = \sigma_1^2x_1^2 + \sigma_2^2(1-x_1)^2$ is convex, so $f'(x_1) = 0$ gives the global minimum; here it falls in $[0, 1]$.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. The lower bounds $x_i \ge \ell_i$ close the model. What does the choice $\ell_i = 0$ for every asset express?
That every asset must be in the portfolio
That the expected returns are non-negative
That the covariances are non-negative
That short selling is forbidden
Explanation. A negative share would be a short sale; with $\ell_i = 0$ only non-negative shares are allowed, while $\ell_i > 0$ would force a minimum holding.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. In the case study (eight sector ETFs) the least risky single asset has volatility $7.53\%$, while the minimum-variance portfolio has volatility $6.03\%$. What does this show?
An estimation error: no portfolio can beat its best asset
Diversification: combining assets lowers risk below the safest one
That the safest asset should get $100\%$ of the capital
That the covariances were set to zero
Explanation. With imperfectly correlated assets the portfolio variance is below that of every component; the minimum-variance portfolio still returns $11\%$.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. In the case study the minimum-variance portfolio puts $58.3\%$ in the utilities ETF (UTL), the asset with the lowest volatility ($7.53\%$). Why not $100\%$?
Because a mandate caps every asset at $58.3\%$
Because UTL has the lowest expected return
Because adding weakly correlated assets lowers the variance further
Because the return constraint is active
Explanation. Moving away from the single safest asset towards weakly correlated ones reduces the variance, until the marginal variance contributions are balanced.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. In the case study, at $\bar r = 12\%$ the multiplier of the return constraint is about $0.022$. How is it read?
The portfolio volatility is $2.2\%$
The expected return grows by $0.022$ per unit of variance
$2.2\%$ of the capital is in the riskiest asset
Raising $\bar r$ by one unit raises the minimum variance by about $0.022$
Explanation. The multiplier is $d(\text{variance})/d\bar r$: beyond $11.06\%$ every extra point of required return is paid in variance, and the price grows along the frontier.
Beyond finance, where does the structure of the Markowitz model reappear, according to the course notes?
In R&D project mixes and similar choices
Only in the management of pension funds
In the routing of vehicles on a network
In the scheduling of jobs on machines
Explanation. The structure is «allocate a budget among risky, correlated alternatives»: R&D portfolios, client portfolios, even production capacity across volatile markets.
The course calls Markowitz «the natural bridge between optimization and statistics». Why?
Because it uses integer variables
Because it has no constraints at all
Because it is solved by regression
Its data are estimates
Explanation. Expected returns and covariances are estimated from historical data; the optimizer takes them as true, so estimation errors flow into the portfolio.
What is the decision of an investor in the Markowitz model of the course?
Which single asset to buy
The share invested in each asset
The number of shares to sell short
The moment at which to sell the assets
Explanation. The variables are the shares $x_i$ (they sum to 1); the objective is the variance of the portfolio return, with a minimum expected return and per-asset bounds.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. Two uncorrelated assets with volatilities $\sigma_1 = 20\%$, $\sigma_2 = 30\%$, no return constraint. What is the minimum-variance share $x_1$?
$x_1 = 2/5 = 40\%$
$x_1 = 9/13 \approx 69.2\%$
$x_1 = 1/2$
$x_1 = 3/5 = 60\%$
Explanation. Minimizing $0.04x_1^2 + 0.09(1 - x_1)^2$: $x_1 = 0.09/(0.04 + 0.09) = 9/13$. Weights are inversely proportional to the variances (not to the volatilities, which would give $60\%$).
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. Two uncorrelated assets, $\sigma_1 = 20\%$, $\sigma_2 = 30\%$: the minimum-variance portfolio has variance $0.0277$. What is its volatility, compared with the two assets?
$25\%$, between the two
$20\%$, as the safer asset
$30\%$, as the riskier asset
$16.6\%$, below both
Explanation. $\sqrt{0.0277} \approx 16.6\% < 20\%$: the portfolio is less risky than either asset, diversification in its purest form.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. In the two-asset example ($\sigma_1 = 20\%$, $\sigma_2 = 30\%$, uncorrelated, $x_2 = 1 - x_1$), how is the optimal share found by hand?
Zero derivative of the variance in $x_1$
Taking the asset with the higher return
Splitting the capital in equal parts
Solving an LP on the two shares
Explanation. After substituting the budget, the variance is a convex parabola in $x_1$: $0.08x_1 - 0.18(1 - x_1) = 0$ gives $x_1 = 9/13$.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. Case study: eight sector ETFs (Exchange Traded Funds, quoted funds that track a sector basket), 60 simulated monthly returns. How are $\mu_i$ and $q_{ij}$ obtained?
They are given exactly by the fund managers
They are set equal for all assets
They are estimated from the 60 monthly returns
They come from the solver
Explanation. As in practice, the inputs are estimated from data (then annualized): this is why the chapter ends with a warning on the fragility of the estimates.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. In the gurobipy code the shares are created with `x = m.addVars(n, ub=u)`. Which constraint of the model does `ub=u` implement?
The per-asset caps $x_i \le u_i$
The budget $\sum_ix_i = 1$
The minimum return $\sum_i\mu_ix_i \ge \bar r$
The ban on short selling only
Explanation. The caps are given as upper bounds of the variables; the default lower bound $0$ is the ban on short selling ($\ell_i = 0$). Budget and return are explicit constraints.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. Case-study statistics (annualized): TEC has $\mu = 1.58\%$ and volatility $29.27\%$, UTL $\mu = 11.99\%$ and volatility $7.53\%$. Which asset is the least risky on its own?
TEC, the most volatile
MAT, with the highest return
ENE, with a high return
UTL, with volatility $7.53\%$
Explanation. UTL has the lowest volatility of the eight ETFs; the minimum-variance portfolio puts $58.3\%$ in it and still goes below its risk (6.03%) by diversifying.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. In the gurobipy code the objective is `quicksum(Q[i, j]*x[i]*x[j] for i in range(n) for j in range(n))`. What kind of model does Gurobi receive?
An LP, since the constraints are linear
A convex QP
A nonconvex QP needing `NonConvex = 2`
An NLP with functional constraints only
Explanation. A covariance matrix is positive semidefinite, so the quadratic objective is convex and Gurobi certifies a global optimum without special parameters.
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. Case study: up to $\bar r = 11\%$ the volatility stays $6.03\%$; at $\bar r = 12\%$ it becomes $6.10\%$ with multiplier about $0.022$. What does the multiplier measure?
The return gained per unit of variance
The share invested in the best asset
Variance paid per point of return
The volatility of the min-variance portfolio
Explanation. It is $\partial(\text{variance})/\partial\bar r$ for the active return constraint; below $11.06\%$ the constraint is inactive and the multiplier is zero.
Markowitz with two uncorrelated assets of variances $\sigma_1^2$ and $\sigma_2^2$, budget $x_1 + x_2 = 1$, no return constraint. Which statement about the minimum-variance shares is correct?
$x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$
$x_i$ is proportional to $\sigma_i^2$
$x_i$ is inversely proportional to $\sigma_i$
$x_1 = x_2 = 1/2$, whatever the variances
Explanation. Setting the derivative of $\sigma_1^2x_1^2 + \sigma_2^2(1 - x_1)^2$ to zero gives $x_1\sigma_1^2 = x_2\sigma_2^2$: weights inversely proportional to the variances, and portfolio variance below both.
The Markowitz QP minimizes $\sum_i\sum_jq_{ij}x_ix_j$; the notes call it convex because $\mathbf Q = (q_{ij})$ is a covariance matrix. If $\mathbf Q$ were patched together from estimates on different samples and lost positive semidefiniteness, what would fail?
Nothing: any symmetric matrix gives a convex QP
Only the budget constraint of the model
Convexity of the QP
The linearity of the return constraint
Explanation. The QP is convex if and only if $\mathbf Q \succeq 0$; a genuine covariance matrix always is, but an inconsistent patchwork may not, and then the objective can be nonconvex (even unbounded below along some direction).
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Where does the non-convexity of this model come from?
From the capacity constraint $q \le k$
From the bilinear term $p \cdot q$ in the objective
From the non-negativity of the price $p$
From the demand constraint, even when $d$ is linear
Explanation. The product of two variables is non-convex. With linear demand, substituting $q = a - bp$, the reduced problem is a concave parabola in $p$.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). With linear demand $d(p) = a - b\,p$ and no capacity limit, what is the optimal price $p^\circ$?
$p^\circ = (a/b + c)/2$
$p^\circ = a/b$
$p^\circ = c$
$p^\circ = (a - c)/b$
Explanation. The profit $(p - c)(a - bp)$ is a concave parabola: setting its derivative to zero gives $p^\circ = (a/b + c)/2$, halfway between $c$ and the choke price $a/b$.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Concert example: $d(p) = 1200 - 5p$, $c = 20$ €, $k = 400$ seats, optimal price $\tilde p = 160$ €. The value of one more seat, $d\Pi/dk$ with $\Pi(k)$ the optimal profit, is $60$ €, not the margin $\tilde p - c = 140$ €. Why?
Because the marginal cost $c$ grows with the capacity $k$
Because the extra seat would stay empty at the price $\tilde p$
Because the capacity constraint becomes inactive at $k = 401$
Because the price falls for everybody: $d\Pi/dk = (\tilde p - c) + k\,d\tilde p/dk = 140 - 80$
Explanation. With $\tilde p = (a - k)/b$ the price falls by $1/b$ per extra seat, on all $k$ tickets. Ignoring it is a classic mistake in evaluating capacity investments.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). With constant-elasticity demand $d(p) = \theta p^{-\varepsilon}$ ($\varepsilon > 1$) and binding capacity, the optimum is $\tilde p = (\theta/k)^{1/\varepsilon}$, where $d(\tilde p) = k$. What kind of optimum is it?
A stationary point of the profit $(p - c)\,d(p)$
A local minimum of the profit
A corner point, where no derivative of the profit vanishes
An unbounded solution cut off by the capacity
Explanation. Below $\tilde p$ the capacity sells out anyway (better raise the price), above it the profit falls: with constraints the optimum must not be sought among stationary points only.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Concert example $d(p) = 1200 - 5p$, $c = 20$ €: without capacity the optimal quantity is $q^\circ = 550$ seats. What happens to the value of capacity $d\Pi/dk$ for $k > 550$?
It keeps growing linearly with $k$
It is zero: capacity is no longer binding
It becomes negative: empty seats cost money
It equals the full margin $p^\circ - c$
Explanation. Beyond the unconstrained optimal quantity the optimal profit curve $\Pi(k)$ is flat: additional capacity is worth nothing.
Pricing model with two seat categories (stalls and balcony) and substitution: the demand of each category depends on both prices $p_1, p_2$. Why must the two prices be decided jointly?
Because each demand depends on both prices: one at a time loses profit
Because the two categories have the same marginal cost
Because the two categories have the same capacity
Because with two products the model becomes an LP
Explanation. Raising the stalls price pushes part of the demand towards the balcony: the joint model keeps the stalls expensive to exploit the substitution.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). With a general demand function $d(p)$ (e.g. logistic) the profit may not be concave. What does the course recommend before trusting the solver's answer?
Replacing $d(p)$ with a linear demand fitted to the data
Removing the capacity constraint, a source of corner points
Setting the price equal to the marginal cost $c$
Studying domain and derivatives and plotting the profit
Explanation. Gurobi certifies the global optimum, but understanding the shape of the profit (domain, derivatives, plot over the relevant interval, several starting points) remains part of the work.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). The model writes $q \le d(p)$ rather than $q = d(p)$. Which assumption guarantees that, at the optimum, $\tilde q = \min\{d(\tilde p), k\}$?
$k > d(p)$ for every price $p$
The demand $d(p)$ is linear in $p$
$\tilde p > c$: every extra unit sold adds profit
$\tilde p = c$: the margin is zero
Explanation. With a positive unit margin each extra unit sold increases the profit, so $q$ is pushed up to the smaller of demand and capacity.
Two-category pricing (stalls 1, balcony 2) with demands $d_1 = 500 - 2p_1 + 0.6\,p_2$ and $d_2 = 900 + 0.8\,p_1 - 4p_2$. What does the positive coefficient $0.6$ of $p_2$ in $d_1$ express?
That the stalls are 60% full
That stalls demand falls when the balcony price rises
That the two categories are complements
Substitution: a dearer balcony moves demand to the stalls
Explanation. A positive cross coefficient means substitute products; this is why the two prices must be chosen jointly.
Two-category pricing: maximize $\sum_i (p_i - c_i)q_i$ with $q_i \le d_i(p_1, p_2)$ (linear demands) and $q_i \le k_i$. Which Gurobi setting does this model need?
None: with linear demands it is an LP
`NonConvex = 2`, because of the bilinear terms $p_i q_i$
`FuncNonlinear = 1`, because of the demand functions
`QCPDual = 1`, to make it convex
Explanation. The objective contains the products of two variables $p_iq_i$, as in the single-product case: bilinear, non-convex, solved globally with `NonConvex = 2`.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Constant-elasticity demand $d(p) = \theta p^{-\varepsilon}$ with $\varepsilon = 2.2$ and $c = 20$ €: without capacity the optimal price would be $c\,\varepsilon/(\varepsilon - 1) = 36.67$ €. Why is the optimum with capacity $k$ instead $\tilde p = 79.11$ €?
At $36.67$ € demand far exceeds $k$: the price rises until $d(p) = k$
Because the formula $c\varepsilon/(\varepsilon - 1)$ holds only for $\varepsilon < 1$
Because the solver stops at a local optimum
Because at $36.67$ € the margin $p - c$ is negative
Explanation. Selling $k$ anyway at a higher price increases profit: the optimum is the corner point where demand equals capacity, $\tilde p = (\theta/k)^{1/\varepsilon}$.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). With linear demand $d(p) = a - bp$ ($b > 0$) and no capacity, which facts make $p^\circ = (a/b + c)/2$ the global optimum?
With $q = a - bp$ the profit $(p - c)(a - bp)$ is concave in $p$: stationary means global
The bilinear term $p\,q$ is convex, so every stationary point is a global optimum
The demand constraint is inactive at the optimum, so the model reduces to an LP
Strong duality between the pricing model and its dual, with equal optimal values
Explanation. The coefficient of $p^2$ is $-b < 0$: the reduced profit is concave in $p$ and $\Pi'(p) = 0$ gives its global maximum.
What is new in the pricing chapter of the course compared with the previous models?
The demand is a fixed datum of the model
The price is a decision variable
The model has integer variables
The capacity is assumed unlimited
Explanation. With the price as a decision, the quantity sold depends on it and the profit $p\cdot q$ contains a bilinear term: the course meets nonconvexity for the first time.
Why do the course notes call the price «perhaps the business decision with the highest impact on margin»?
Price moves the margin of every unit
Because prices never change
Because costs do not depend on volume
Because demand is insensitive to price
Explanation. A price change hits the margin of every unit sold, while a volume change affects only the extra units; hence the attention to pricing models.
One learning goal of the pricing chapter is to recognize «corner optima». What are they?
Optima of linear programs only
Optima found by rounding a solution
Optima where no derivative vanishes
Local optima of nonconvex functions
Explanation. With capacity binding, the optimum can sit where $d(p) = k$: the profit has no stationary point there, so searching only among stationary points would miss it.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Linear demand $d(p) = a - bp$. Substituting $q = a - bp$, what does the profit $(p - c)(a - bp)$ become as a function of $p$?
A convex parabola: the problem is hard
A linear function: the optimum is at a bound
A concave parabola: the reduced problem is easy
A cubic with two local maxima
Explanation. The reduced profit is a concave quadratic in $p$, maximized at $p^\circ = (a/b + c)/2$ without capacity; the bilinear version is still solved globally by Gurobi with `NonConvex = 2`.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). How do the notes treat the general demand functions (constant elasticity $\theta p^{-\varepsilon}$, logistic) in Gurobi?
With functional constraints
By linearizing them around the optimum
With a local NLP solver from a guess
By replacing them with linear demand
Explanation. Gurobi's functional constraints (`addGenConstrPow`, `addGenConstrExp`) handle them in the same solver, still with a global optimum.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Concert case ($d(p) = 1200 - 5p$, $c = 20$, $k = 400$): Gurobi gives $p^* = 160$, profit $56{,}000$ €; resolving with $k = 401$ estimates the value of one more seat at $59.80$ € (theory: $60$). Why is the value estimated by re-solving?
Because the LP duals are too slow to read
Because the capacity constraint is inactive
Because the result must be an integer
Nonconvex QPs give no duals: perturbation is used
Explanation. With the bilinear objective (`NonConvex = 2`) Gurobi returns no `Pi`; the script sets `v_cap.RHS = K + 1`, re-optimizes and takes the difference.
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Logistic demand $d(p) = m/(1 + e^{-\alpha + \beta p})$ with $m = 900$, $\alpha = 6$, $\beta = 0.045$, $c = 20$, $k = 400$: the solver gives $p^* = 138.29$ €. What do the notes recommend before trusting such a result?
Nothing: Gurobi is always right
Study and plot the profit curve
Round the price to the nearest euro first
Replace the logistic with a linear demand
Explanation. With general demand functions the profit may not be concave: study domain and derivatives, plot the profit on the relevant interval, and with local solvers try several starting points.
Pricing with linear demand $d(p) = a - bp$, cost $c$, capacity $k$ binding: $p^* = (a - k)/b$ and profit $\Pi(k) = (p^* - c)k$. Why is one more seat worth less than the full margin $p^* - c$?
Because the cost $c$ grows with $k$
Because demand becomes infinite
Because the capacity constraint becomes inactive
Filling it lowers the price for all
Explanation. $dp^*/dk = -1/b$, so $d\Pi/dk = (p^* - c) + k\,dp^*/dk$; in the concert ($a = 1200$, $b = 5$, $c = 20$, $k = 400$) it is $140 - 80 = 60$ €, not 140.
Pricing with constant-elasticity demand $d(p) = \theta p^{-\varepsilon}$ ($\varepsilon > 1$), cost $c$, capacity $k$; the unconstrained optimum $c\varepsilon/(\varepsilon - 1)$ would exceed capacity. Why is the optimum at $p^* = (\theta/k)^{1/\varepsilon}$, where $d(p) = k$?
It is the only stationary point of the profit
Below it profit rises, above it falls
Because the profit is linear in $p$
Because the elasticity equals 1 there
Explanation. For $p < p^*$ demand exceeds $k$, sales stay at $k$ and $(p - c)k$ grows; for $p > p^*$ the profit $(p - c)\theta p^{-\varepsilon}$ decreases (we are past its unconstrained peak). The optimum is a corner where no derivative vanishes.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). A channel is left at zero in the optimal allocation, $\tilde x_i = 0$. What can be said about it?
Its marginal return $r_i'(0)$ equals $\lambda$
Its cap $u_i$ is too small to be useful
Its initial marginal return $r_i'(0)$ is at most $\lambda$
The budget constraint is not active
Explanation. A channel at zero is not worth even the first euro: $r_i'(0) \le \lambda$. Channels at the cap may instead have marginal return $\ge \lambda$.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the case study the caps are $u = (60, 80, 120, 35)$ thousand € and $\lambda$ drops to zero when the budget reaches $b = 300$. Why?
Because the responses $r_i$ become linear for large spends
Because the solver fails for large budgets
Because the budget constraint becomes an equality
Because all channels are at their caps: $60 + 80 + 120 + 35 = 295 < 300$
Explanation. With every channel at its cap the budget constraint is no longer active, so its multiplier is zero. The budget value curve is concave: $\lambda$ falls as $b$ grows.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). The responses are $r_i(x) = a_i\log(1 + k_ix)$. In the case study TV gets less than social media although its cap $u_i$ is higher. What explains it?
The cap of TV is active at the optimum
The saturation speed $k_i$ of each channel, not its size
A numerical error of the solver
The scale coefficient $a_i$ alone
Explanation. What matters is how fast the marginal return $a_ik_i/(1 + k_ix)$ decreases, governed by $k_i$: a large channel that saturates quickly gets less.
By replacing each logarithm with its tangent line at $x_i = 0$
By setting `NonConvex = 2` and writing the logarithms directly
By solving the KKT conditions by hand and fixing the $x_i$
Explanation. The function constraints make the objective linear in the $z_i$; the optimum is certified global and the KKT conditions are then checked on the numbers.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). What does the multiplier $\lambda$ of the budget constraint tell a CFO?
The total response of the campaign at the optimum
The cap of the channel with the best response
The extra response bought by one more euro of budget
The average response per euro spent
Explanation. $\lambda$ is the marginal value of the budget: it is worth adding budget as long as $\lambda$ exceeds the value of a euro invested elsewhere, and $\lambda$ falls as the budget grows.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Which statement justifies that this model has a certifiable global optimum?
Every NLP with linear constraints has a unique optimum
A sum of concave functions is maximized over a polyhedron: local maxima are global
Every separable function is linear on a polyhedron
The objective is increasing, so the budget is active
Explanation. The objective is separable and a sum of concave functions, the constraints are linear: the problem is convex and every local maximum is global.
Explanation. For channels on a bound, the multipliers of $x_i \ge 0$ or $x_i \le u_i$ enter the stationarity condition and the equality with $\lambda$ no longer holds.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). The responses $r_i$ are increasing. What would happen without the budget constraint $\sum_i x_i \le b$?
The model would become infeasible
Every channel would get the same spend
The model would become non-convex
Every channel would go to its cap $u_i$
Explanation. The budget is the only constraint linking the channels: with increasing responses and no budget, each channel is pushed independently to its cap.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the case study, with $b = 100$ thousand €, all four channels lie strictly between $0$ and their caps and their marginal returns $r_i'(\tilde x_i)$ all equal $8.2693$. What does this confirm?
That the solver stopped too early
That the budget constraint is not active
The KKT condition $r_i'(\tilde x_i) = \lambda$, with $\lambda = 8.2693$
That the four responses are identical
Explanation. For interior channels stationarity gives $r_i'(\tilde x_i) = \lambda$: the last euro yields the same everywhere, and the common value is the multiplier of the budget.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the case study $\lambda = 8.2693$; adding $1$ (thousand €) to the budget and re-solving, the response grows by $8.244$. Why slightly less than $\lambda$?
A numerical error of the function constraints
Because one channel reaches its cap
Because the multiplier is wrong by about $0.3\%$
Concavity: the marginal value falls as the budget grows
Explanation. The optimal response $V(b)$ is concave: the finite increment over $[b, b + 1]$ is below the slope $\lambda$ at $b$. The check still confirms the reading of the multiplier.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Let $V(b)$ be the optimal total response as a function of the budget $b$. Which statement is correct?
$V(b)$ is concave, with slope $\lambda(b)$ non-increasing in $b$
$V(b)$ is convex, so $\lambda(b)$ grows with the budget
$V(b)$ is linear, so $\lambda$ is the same for every budget
$V(b)$ is decreasing once all channels are active
Explanation. Maximizing a concave function with the budget as right-hand side gives a concave value function: in the case study $\lambda$ falls from $19$ ($b = 20$) to $4$ ($b = 260$).
The budget chapter calls the allocation among uses with diminishing returns a «universal scheme». Which example fits it?
Routing trucks on a road network
Funds among projects, time among activities
Choosing one supplier out of three
Sequencing jobs on a machine
Explanation. Marketing channels, funds among projects, time among activities, fertilizer among fields: the same model and the same optimality rule apply.
What «strong and verifiable» statement does the theory make about the optimal budget allocation, according to the course notes?
Marginal returns are equal at the optimum
All channels get the same spend
The largest channel gets everything
The spend is proportional to the caps
Explanation. At the optimum the marginal returns of the active channels coincide, and the solver returns exactly that, digit by digit (the case study shows $8.2693$ for all four channels).
How will the multiplier $\lambda$ of the budget constraint be used, according to the goals of the budget chapter?
To set the caps of the channels
To choose the response functions
To negotiate the size of the budget
To round the spends
Explanation. $\lambda$ is the extra response per extra euro of budget; the curve of $\lambda$ against the budget is the quantitative argument for deciding how much to give to marketing.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Two channels, $r_1(x) = 100\log(1 + 0.2x)$, $r_2(x) = 60\log(1 + 0.1x)$, $b = 50$: the optimum is $x_1 = 35.6$, $x_2 = 14.4$. What is the shadow price of the budget?
$\lambda = 20.0$
$\lambda = 6.0$
$\lambda = 0.0$
$\lambda = 2.46$
Explanation. $\lambda = r_1'(35.6) = 20/(1 + 0.2\cdot 35.6) = 2.46$, the same as $r_2'(14.4) = 6/2.44$: one more euro of budget yields about $2.46$ units, whichever channel it enters.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Two-channel example with no caps and $b = 50$. Why can the budget constraint be used as an equality, $x_2 = 50 - x_1$?
Unspent budget would be wasted
Because the caps force it here
Because $\lambda = 0$ at the optimum
Because the two channels are identical
Explanation. With increasing responses an unspent euro could always add response somewhere, so the budget is active at the optimum (and $\lambda > 0$).
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Two channels with $r_1'(0) = 20$ and $r_2'(0) = 6$ (marginal response of the first euro). What does the optimal rule imply for channel 2 when the budget is very small?
It always gets half of the budget
It gets everything, being the cheaper one
It stays at zero until $r_1'$ falls to 6
It gets the same spend as channel 1
Explanation. Money goes first where the marginal return is highest; channel 2 enters only when channel 1's marginal, decreasing with spend, has dropped to its initial marginal of 6.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the gurobipy code, with $r_i(x) = a_i\log(1 + k_ix)$, the script creates `g = m.addVars(4, lb=1.0)` and `z = m.addVars(4, lb=-GRB.INFINITY)`, with `g[i] == 1 + k[i]*x[i]` and `addGenConstrLog(g[i], z[i])`. Why is `z` free?
Because $z_i$ must be negative
Because Gurobi requires free variables in objectives
Because a logarithm can be negative in general
Because $z_i$ is a binary variable
Explanation. `addGenConstrLog` imposes $z = \log g$; the default bound $z \ge 0$ would cut values where $g < 1$. Here $g \ge 1$ so $z \ge 0$ anyway, but declaring it free avoids a hidden restriction.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the gurobipy code of the budget case the script sets `m.Params.FuncNonlinear = 1`. What does it do?
Treats the logarithm exactly
Turns the model into an LP
Allows integer spends on channels
Prints the log of the solver
Explanation. With `FuncNonlinear = 1` the functional constraints are handled exactly (not by a fixed piecewise approximation), so the optimum is certified global.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the budget code the objective is `quicksum(a[i] * z[i] for i in range(4))`, with $z_i = \log(1 + k_ix_i)$ imposed by functional constraints. Why does this work?
Because $\log$ is linear in $x_i$
Because Gurobi approximates $\log$ by a line
Because the caps make $z_i$ constant
It is linear in the auxiliary $z_i$
Explanation. All the nonlinearity is moved into the constraints $z_i = \log g_i$, $g_i = 1 + k_ix_i$; the objective is then a linear combination of the $z_i$.
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Case study: total response $1449.8$, four channels with marginals all equal to $8.2693$; adding 1000 € of budget raises the response by $8.244$. What does this check?
That the caps of the channels are active
That $\lambda$ is the value of budget
That the responses are linear
That one channel should be dropped
Explanation. The KKT condition $r_i'(x_i) = \lambda$ appears in the numbers, and the actual gain of one more unit of budget, $8.244$, confirms the reading of the multiplier (slightly less, by concavity).
Advertising budget model: maximize $\sum_ir_i(x_i)$ (concave) with $\sum_ix_i \le b$ (multiplier $\lambda$) and $0 \le x_i \le u_i$. The rule $r_i'(\tilde x_i) = \lambda$ holds for channels strictly inside $(0, u_i)$. What happens for a channel at its cap $u_i$?
$r_i'(u_i) \ge \lambda$
$r_i'(u_i) = \lambda$ in any case
$r_i'(u_i) \le \lambda$
$r_i'(u_i) = 0$ at the cap
Explanation. Stationarity reads $r_i'(\tilde x_i) = \lambda + \mu_i$ with $\mu_i \ge 0$ the multiplier of $x_i \le u_i$: a capped channel would deserve more money but cannot take it. Dropping the hypothesis «interior» changes the condition.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Which objective has a closed-form optimum?
Weber: weighted sum of the distances
Minimax: maximum distance
Weighted sum of the squared distances
None of the three objectives
Explanation. Setting the gradient of $\sum_i w_i[(x - a_i)^2 + (y - b_i)^2]$ to zero gives the weighted centroid $\tilde x = \sum_i w_ia_i/\sum_i w_i$ (and similarly for $y$).
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Which property characterizes the optimum of the minimax model (minimize the distance of the farthest district)?
It is the centre of the smallest circle containing all the districts
It is the weighted centroid of the districts
It is the weighted median of the districts, coordinate by coordinate
It always coincides with the Weber point
Explanation. It depends only on the extreme districts and ignores the weights: this is why the minimax protects the outskirts, regardless of their population.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Weber model: minimize $\sum_i w_i\,d_i$, with $d_i$ the Euclidean distance from district $i$. Which condition holds at the optimum, when it is not a district point?
The facility is equidistant from all the districts
The gradient of the squared distances vanishes
The maximum distance $\max_i d_i$ is minimal
$\sum_i w_i\,\mathbf u_i = \mathbf 0$, with $\mathbf u_i$ the unit vector towards district $i$
Explanation. The weighted unit “pulls” balance; the function is not differentiable at the district points and has no closed form.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). How are the Euclidean distances written in the Gurobi model of the case study?
With a piecewise-linear approximation of the square root
With a variable $d_i$ and the convex conic constraint $(x - a_i)^2 + (y - b_i)^2 \le d_i^2$
With `NonConvex = 2` and the squared distances in the objective
With binary variables that select the nearest district
Explanation. Weber minimizes $\sum_i w_id_i$, the minimax a variable $z$ with $d_i \le z$: purely conic (convex) structures need no special parameter in Gurobi.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). The efficiency-equity frontier plots the weighted mean distance against the maximum distance. In the case study it is almost flat. What does it mean?
Efficiency and equity are in strong conflict
The model with both objectives is infeasible
Lowering the maximum distance costs very little mean distance
The Weber and minimax points coincide
Explanation. Guaranteeing $0.63$ km less to the farthest district costs only $47$ metres of mean distance: a strong argument in a public discussion.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). How is the efficiency-equity frontier (mean distance versus maximum distance) built with the $\varepsilon$-constraint method?
Minimize the mean distance with a cap $D$ on every distance, varying $D$
Minimize the sum of the mean distance and of the maximum distance
Solve Weber and minimax separately and average the two locations
Vary the weights $w_i$ of the districts and re-solve Weber
Explanation. Each value of $D$ gives one point of the frontier; the extremes are the minimax solution (smallest feasible $D$) and the Weber point (large $D$).
Location on a line: customers at positions $a_i$ with weights $w_i \ge 0$. Which statement about $\min_x \sum_i w_i|x - a_i|$ (Weber in one dimension) is correct?
The optimum is the weighted mean $\sum_i w_ia_i/\sum_i w_i$
An optimum is the weighted median: at least half of the weight on each side
The optimum is the midpoint of the two extreme customers
The optimum is the unweighted median of the positions
Explanation. Moving away from the weighted median increases the cost on the heavier side faster than it decreases on the other. The weighted mean solves the squared distances, the midpoint the minimax.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Which facts make the Weber objective $\sum_i w_i\sqrt{(x - a_i)^2 + (y - b_i)^2}$ convex in $(x, y)$?
It is differentiable everywhere in the plane
The squared distance is convex and the square root is increasing
The districts are finitely many and numbered
Norm of an affine map is convex, $w_i \ge 0$, sums of convex functions are convex
Explanation. Each term is the Euclidean norm of an affine function of $(x, y)$; the weights are non-negative. Differentiability fails at the district points, but convexity holds. Note: increasing $\circ$ convex is convex only if the outer function is also convex, and the square root is concave.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). The facility must lie within distance $r$ of an electrical substation at $(a_0, b_0)$. How is this constraint written, and is it convex?
$|x - a_0| + |y - b_0| \ge r$, non-convex
$(x - a_0)^2 + (y - b_0)^2 \le r^2$, convex
$(x - a_0)^2 + (y - b_0)^2 \ge r^2$, convex
$x \le a_0 + r$ only, linear
Explanation. A disc is a convex set; adding it to any convex location objective keeps the problem convex. The $\ge$ version would describe the outside of a disc, which is not convex.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). In the case study the facility must be within 2 km of a substation; the constrained Weber optimum lies on the boundary of that disc and costs only $+0.2\%$. What is the managerial lesson?
The constraint is inactive and could be removed
The Weber model is not suited to constrained problems
Equity and efficiency are in strong conflict
A feared constraint may turn out almost free: measure it
Explanation. The constraint is active (optimum on the boundary) but its cost is tiny: discovering it is a result as important as the optimum itself.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). In the case study (12 districts) the Weber point $(4.886, 5.310)$ almost coincides with the weighted centroid $(4.897, 5.397)$, while the minimax point moves half a kilometre away. Why are Weber and centroid so close?
Because the weights are fairly evenly distributed around the centre
Because Weber and centroid always coincide
Because the minimax ignores the weights
Because the substation constraint is active
Explanation. Weber (sum of distances) and centroid (sum of squared distances) differ when a few heavy or far districts pull differently; with balanced weights they are close, while the minimax follows the extreme districts.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). The efficiency-equity frontier plots the minimum mean distance against a cap $D$ on the maximum distance. What would a **steep** frontier mean?
That equity is almost free
That the model is badly scaled
That Weber and minimax coincide
A real conflict: each km less for the farthest costs much mean distance
Explanation. In the case study the frontier is almost flat (equity almost free); a steep one would signal that protecting the outskirts has a high efficiency cost.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). The chapter compares three meanings of «close to the demand». Which objective expresses **equity** toward the worst-off user?
The weighted mean distance (Weber)
The weighted squared distance
The maximum distance (minimax)
The number of districts served
Explanation. Mean distance measures efficiency, the squared distance leads to the barycenter, and the maximum distance protects the farthest district.
Which facilities does the course cite as examples for the continuous location model?
Warehouses chosen from a fixed list
Machines on a production line
Bank branches to close down
A charging station or a micro-hub
Explanation. In the continuous version the coordinates are free on the plane: a charging station, a logistic micro-hub or a health post placed «close» to the demand.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Three customers on a road at km $0$, $4$ and $10$, weights $1$, $1$ and $3$. What is the barycenter (weighted squared distance)?
$x = 4.67$, the plain mean
$x = 6.8$
$x = 10$
$x = 5$
Explanation. $(1\cdot 0 + 1\cdot 4 + 3\cdot 10)/5 = 34/5 = 6.8$: unlike the median it depends on how far the points are, not only on which side.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Three customers on a road at km $0$, $4$ and $10$, weights $1$, $1$ and $3$. Where is the minimax location (smallest maximum distance)?
$x = 10$
$x = 6.8$
$x = 4$
$x = 5$
Explanation. The midpoint of the extreme customers, $(0 + 10)/2 = 5$, whatever the weights: three reasonable objectives give $10$, $6.8$ and $5$.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Three customers on a road at km $0$, $4$, $10$, weights $1$, $1$, $3$: Weber (sum of weighted distances) gives $x = 10$. Why does moving left from $10$ by $\delta$ make things worse?
The first two save $2\delta$, the third pays $3\delta$
All three customers pay more
The cost function is constant there
The road ends at km 10
Explanation. Moving left lowers the distances of the two customers on the left (weight 2 in all) and raises that of the customer with weight 3: net $+\delta$. The optimum is the weighted median.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Case study: in the gurobipy code each distance is a variable $d_k$ with `dx[k]**2 + dy[k]**2 <= d[k]*d[k]`. What kind of constraint is it?
A linear constraint in $d_k$
A nonconvex bilinear constraint
A convex conic constraint
A functional constraint on a logarithm
Explanation. $\sqrt{d_x^2 + d_y^2} \le d_k$ is a second-order cone: convex, handled by Gurobi without `NonConvex`; minimizing $\sum_kw_kd_k$ pushes each $d_k$ down to the true distance.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Case study: twelve districts, and the station must stay within $r = 2$ km of the electrical substation at $(7, 6)$. How is this written?
$(x - 7)^2 + (y - 6)^2 \le 4$
$|x - 7| + |y - 6| = 2$
$x \le 7$ and $y \le 6$, a box
As a penalty in the objective
Explanation. A disc around the substation is a convex region, so the constrained Weber problem stays convex; the constraint is a quadratic inequality.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Case study: how does the minimax model use the distance variables $d_k$?
It minimizes $\sum_kw_kd_k$
It minimizes $\sum_kd_k^2$
It fixes every $d_k$ to the same value
It minimizes $z$, with $d_k \le z$
Explanation. Same conic distances as Weber, but the objective is an auxiliary $z$ bounded below by every distance: the largest distance is minimized.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Case results: Weber $(4.886, 5.310)$ with mean $3.344$ km and max $6.314$ km; minimax $(5.496, 5.029)$ with mean $3.391$ km and max $5.680$ km. How is the move of the minimax point read?
An error: the two should coincide
It moves toward the peripheral districts
It moves toward the most populated district
It moves to the substation
Explanation. The minimax point shifts over half a km south-east to protect the outlying districts, cutting the maximum distance by $0.63$ km at a small cost in mean distance.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Case results: Weber constrained to stay within 2 km of the substation lies on the boundary of the disc and costs $+0.2\%$ of total distance. What is the managerial lesson?
The constraint should be removed
The substation is badly placed
The constrained model is infeasible
A feared constraint may be cheap
Explanation. The constraint is active (optimum on the boundary) but costs very little: discovering that is a result as important as the optimum itself.
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Efficiency–equity frontier of the case: cap $D = 5.680$ km gives mean $3.391$, $D = 5.997$ gives $3.351$, $D = 6.314$ gives $3.344$. What does a frontier this flat mean?
Equity costs very little in efficiency
Efficiency and equity are in strong conflict
The minimax solution is infeasible
The mean distance is independent of the cap
Explanation. Guaranteeing $0.63$ km less to the farthest district costs only $47$ m of mean distance: the fair solution is «almost free»; a steep frontier would signal a real conflict.
Continuous location with the weighted squared distance $\sum_iw_i[(x - a_i)^2 + (y - b_i)^2]$ ($w_i > 0$ weights, $(a_i, b_i)$ district coordinates). Which statement is correct?
The optimum is the weighted median
The optimum has no closed form
The weighted barycenter
The optimum is the center of the smallest enclosing circle
Explanation. The objective is a strictly convex quadratic; setting its gradient to zero, $\sum_iw_i(x - a_i) = 0$, gives the barycenter (and similarly for $y$): the only one of the three objectives with a closed form.
10. Electric vehicle charging with a smooth profile (18)
In minimum-cost overnight charging the total draw rises to 103.4 kW and changes by up to 54.9 kW from one hour to the next. What does the QP variant add?
A constraint on the maximum peak of the draw
A quadratic penalty on the hourly jumps of the total draw
Binary variables switching the chargers on
A fixed cost for every plugged-in vehicle
Explanation. The QP variant adds $\gamma \sum_t (z_t - z_{t-1})^2$ to the objective: it penalizes every change of the draw, not only the peak.
In the charging model with a smooth profile, which datum is added to those of the linear model?
The weight $\gamma$ of the jumps of the total draw
The hourly price of energy in every hour of the night
The maximum power of the charger of each vehicle
The charging efficiency $\eta$ of the vehicles
Explanation. Prices, powers, availability, energy, base load, meter and efficiency are those of the linear case; only $\gamma$ (€ per kW$^2$) is added.
The charging QP penalizes the jumps of the *total* draw $z_t = b_t + \sum_v x_{vt}$, base load included. What consequence does this have on the charging profile?
Charging ignores the ramps of the building and follows the prices
Charging can also soften the ramps of the base load
The base load becomes a decision variable
The problem becomes non-convex and needs `NonConvex = 2`
Explanation. Since $b_t$ enters the jumps, shifting charging to the hours in which the base load rises or falls reduces the penalty: charging offsets the ramps of the building.
The charging QP has objective $\sum_{v,t} \pi_t x_{vt} + \gamma \sum_t (z_t - z_{t-1})^2$ and linear constraints. Which assumption is needed for it to be a convex QP?
That the prices $\pi_t$ are all positive
That the meter $k$ exceeds the base load
That the availability windows are contiguous
That the weight $\gamma$ is non-negative
Explanation. With $\gamma \ge 0$ a convex function (a sum of squares of linear functions) is added to a linear objective; prices and windows do not affect convexity.
One vehicle, two hours: $e = 10$ kWh, $\eta = 1$, prices $0.10$ and $0.20$ €/kWh, $\bar p = 12$ kW, zero base load, $\gamma = 0.01$. With $x_1 = 5 + d$ the objective is $1.5 - 0.1 d + 4\gamma d^2$. What is $x_1$ at the optimum?
$6.25$
$10.00$
$5.00$
$7.50$
Explanation. The minimum is at $d = 0.1/(8\gamma) = 1/(80\gamma) = 1.25$, hence $x_1 = 6.25$ and $x_2 = 3.75$.
Same example (prices $0.10$ and $0.20$, active energy constraint, both hours used). Stationarity gives $0.10 - 2\gamma(x_2 - x_1) = \lambda = 0.20 + 2\gamma(x_2 - x_1)$. What is the multiplier $\lambda$ of the requirement?
$0.10$, the price of the cheap hour, for every $\gamma$
$0.20$, the price of the expensive hour, for every $\gamma$
$0.15$, the average price, for every $\gamma \ge 1/400$
$2\gamma$, twice the weight of the penalty
Explanation. Adding the two equalities gives $2\lambda = 0.30$: $\lambda = 0.15$, independent of $\gamma$ as long as both hours are used ($\gamma \ge 1/400$).
In the two-hour example the interior optimum is $x_1 = 5 + 1/(80\gamma)$. What happens for $\gamma < 1/400$?
The optimum still stays $x_1 = 5 + 1/(80\gamma)$
All in the cheap hour: $x_1 = 10$, $x_2 = 0$
Everything is charged in the expensive hour, the second
The problem becomes infeasible because of the energy constraint
Explanation. For $\gamma < 1/400$ the formula would give $x_1 > 10$ and hence $x_2 < 0$: the bound $x_2 \ge 0$ becomes active and everything is charged in hour 1, as in the linear model.
The charging script with a smooth profile writes the objective `spesa + gamma * salti`. What kind of model does Gurobi solve?
An LP, because the constraints are linear
A convex QP
A non-convex NLP with `NonConvex = 2`
A MIQP with integer variables
Explanation. The spend is linear, `salti` is a sum of squares of linear expressions, the constraints are linear: a convex QP, solved with no special parameter.
The linear compromise cost $+\,\rho\,$peak of LP Modelling reaches the 68 kW peak spending less than the QP with $\gamma = 0.01$. Why does the QP spend more?
Because the QP uses a smaller meter than the linear model
Because the QP cannot use the cheapest night hours
Because the QP softens every ramp, not only the maximum
Because the QP has a worse charging efficiency
Explanation. The linear compromise only looks at the maximum of the draw; the QP penalizes every hourly jump and moves charging also where it does not reduce the peak.
In the linear model the requirement multipliers of the six vehicles are 0.0842 or 0.0947 €/kWh; in the QP with $\gamma = 0.01$ they are all 0.0916. Why do they coincide in the QP?
Because in the QP the vehicles have the same availability window
Because the QP ignores the charging efficiency
Because in the QP the energy constraint is not active
Because the penalty links the vehicles through the total draw
Explanation. The quadratic term depends only on the sum of the powers: one more kWh for any vehicle is obtained by redistributing the charging of all, at the same marginal cost.
Spend-jitter frontier of charging: with $\gamma = 0.0005$ the spend rises by €1.15 and the sum of the squared jumps falls from 7,268 to 1,563. What does this stretch of the frontier say?
That the first smoothing steps cost little
That smoothness costs more and more at every equal step
That the QP does not improve the profile
That the spend falls as $\gamma$ grows
Explanation. The frontier is steep at first: with little more than one euro per night the sum of the squared jumps falls by almost five times.
Charging with $\gamma = 0.5$: the spend reaches €43.80 per night, more than twice the linear model. Why does smoothing cost so much beyond a certain threshold?
Because the meter becomes too small for the fleet
Because with large $\gamma$ the problem becomes non-convex
Because to follow the ramps of the building it charges in costly hours
Because the vehicles charge more energy than needed
Explanation. The morning and evening ramps come from the building; to offset them charging must move to hours with high prices.
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. What is the optimal utilization $\rho = \lambda/\tilde\mu$?
$100\%$, because unused capacity is waste
Below $100\%$: spare capacity keeps the queue short
Exactly $50\%$, whatever the data
Undefined, because the cost diverges
Explanation. In the worked example $\lambda = 8$, $c = 2$, $h = 4$: $\tilde\mu = 12$, $\rho = 66.7\%$; with $\mu = 9$ ($\rho = 89\%$) the cost rises from $32$ to $50$ €/h.
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. The optimum has safety margin $\tilde\mu - \lambda = \sqrt{h\lambda/c}$. How does it grow with the demand $\lambda$?
Like $\sqrt{\lambda}$: large systems need proportionally less buffer
Linearly in $\lambda$: the buffer is a fixed share of demand
Like $\lambda^2$: queues explode with demand
It does not depend on $\lambda$
Explanation. Capacity = demand + safety margin, and the margin grows less than proportionally to demand: economies of scale in the buffer (pooling).
M/M/1 queue (Poisson arrivals at rate $\lambda$, exponential service at rate $\mu > \lambda$, one server). Which formulas give the mean time in the system $w$ and the mean number of customers in the system $l$?
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Marketing promises a mean time in the system $w = 1/(\mu - \lambda)$ of at most $w_{\max}$. Which constraint on the capacity follows?
$\mu \le \lambda + 1/w_{\max}$
$\mu \ge \lambda\,w_{\max}$
$\mu \ge 1/w_{\max}$
$\mu \ge \lambda + 1/w_{\max}$
Explanation. From $1/(\mu - \lambda) \le w_{\max}$; the constraint matters only when it is tighter than the economic optimum $\tilde\mu$.
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. In the case study $\lambda$ is uncertain in $[36, 48]$ and the optimum computed for the nominal demand is $\tilde\mu = 46.58$. Why is sizing the system on it dangerous?
Because $C(\mu)$ is not convex for uncertain $\lambda$
Because with $\lambda = 48 > \tilde\mu$ the queue is unstable
Because $\tilde\mu$ is larger than any likely demand
Because the formula of $\tilde\mu$ holds only for $\lambda < 36$
Explanation. With $\mu \le \lambda$ the queue grows without bound and the cost diverges. Minimizing the worst-case cost gives $\mu = 52.90$: an insurance premium of about $13\%$.
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. When the promise $w \le w_{\max}$ is active, $\mu = \lambda + 1/w_{\max}$ and the cost is $C(w_{\max}) = c\lambda + c/w_{\max} + h\lambda\,w_{\max}$. With $c = 3$, $h = 1.5$, $\lambda = 42$ and $w_{\max} = 0.1$ h, what is $dC/dw_{\max}$?
$-237$ €/h per hour of promise
$+63$ €/h per hour of promise
$-300$ €/h per hour of promise
$-30$ €/h per hour of promise
Explanation. $dC/dw_{\max} = -c/w_{\max}^2 + h\lambda = -3/0.01 + 63 = -237$: relaxing the promise saves money, the number to give marketing before signing the SLA.
M/M/1 queue with utilization $\rho = \lambda/\mu$ and mean time in the system $w = 1/(\mu - \lambda)$. The “utilization wall” plot shows $w$ as $\rho$ grows, for a fixed $\mu$. What does it show?
The total cost decreases as $\rho$ grows
The waiting time does not depend on $\rho$
From $\rho = 90\%$ to $\rho = 99\%$ the time $w$ is multiplied by ten
The optimal utilization is $99\%$
Explanation. $w = 1/(\mu(1 - \rho))$ explodes like a hyperbola as $\rho \to 1$: saturating resources and giving good service are in mathematical conflict.
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Which statement about $C(\mu)$ on $\mu > \lambda$ is correct?
It is concave, so its stationary point is a maximum
It is linear in $\mu$, so the optimum is at a bound
It has no minimum on $(\lambda, +\infty)$
It is convex there, so $\tilde\mu = \lambda + \sqrt{h\lambda/c}$ is the global minimum
Explanation. $C''(\mu) = 2h\lambda/(\mu - \lambda)^3 > 0$; the cost tends to $+\infty$ both as $\mu \to \lambda^+$ and as $\mu \to +\infty$.
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. To claim that $\tilde\mu = \lambda + \sqrt{h\lambda/c}$ is the optimal capacity, which facts are used?
Strong LP duality
$C'(\tilde\mu) = 0$, convexity of $C$ on $(\lambda, +\infty)$ and $\tilde\mu > \lambda$
That the arrival rate $\lambda$ is an integer
That the utilization at the optimum is $100\%$
Explanation. The derivative vanishes at $\tilde\mu$, which satisfies the stability requirement; convexity turns the stationary point into the global minimum.
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Case study: $\lambda = 42$ per hour, $c = 3$, $h = 1.5$: $\tilde\mu = 46.58$, utilization $90.2\%$, mean time in the system $13.1$ minutes. Marketing proposes to promise a mean time of at most $15$ minutes. What does this promise cost?
Nothing: $13.1 < 15$, the promise is not binding
It forces $\mu \ge \lambda + 15 = 57$ per hour
It forces $\mu = \lambda + 4 = 46$, saving money
It is infeasible at this demand
Explanation. The constraint $\mu \ge \lambda + 1/w_{\max}$ is already satisfied by the economic optimum: a promise looser than $13.1$ minutes is free.
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. In the Gurobi model of the case study the mean time $w$ is a variable linked to $\mu$ by the constraint $w(\mu - \lambda) = 1$. Which parameter does this require?
`FuncNonlinear = 1`, for the function $1/x$
`QCPDual = 1`, to get the multipliers
No parameter: the constraint is linear
`NonConvex = 2`, because $w\mu$ is a bilinear term
Explanation. The product $w\mu$ of two variables is bilinear (non-convex as an equality); Gurobi solves it to global optimality with `NonConvex = 2` and matches the analytical $\tilde\mu$.
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. In the case study, tightening the promise on the mean time in the system from 12 to 9 minutes costs $1.85$ €/h, while going from 3 to 2 minutes costs $28.95$ €/h. What does this show?
That short promises are cheaper to keep
That the cost of the promise is linear in $w_{\max}$
That the price of the promise grows explosively as $w_{\max}$ shrinks
That the promise is never binding
Explanation. With the promise active, $C(w_{\max}) = c\lambda + c/w_{\max} + h\lambda w_{\max}$: the term $c/w_{\max}$ makes the marginal cost explode for short promises.
In the queues chapter, what is new compared with classical queueing theory?
New formulas for the M/M/1 queue
Simulation instead of formulas
Several servers instead of one
Capacity $\mu$ becomes a variable
Explanation. The M/M/1 formulas are standard; the chapter treats the service rate as a decision and chooses it by minimizing capacity cost plus waiting cost.
What does the notation M/M/1 mean in the queues chapter of the course?
Mean arrivals, mean service, one hour of work
Poisson arrivals, exponential service, 1 server
Multiple queues, multiple servers, one line
A Markov chain with a single state only
Explanation. Markovian arrivals (Poisson process), Markovian (exponential) service times and a single server: the simplest queue, with closed-form formulas.
M/M/1 capacity model (Poisson arrivals, exponential service, one server): arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, whose optimum is $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Desk with $\lambda = 8$ customers/h, $c = 2$ €, $h = 4$ €/h. What are $\tilde\mu$ and the optimal cost?
M/M/1 capacity model (Poisson arrivals, exponential service, one server): arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, whose optimum is $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Desk with $\lambda = 8$/h, $c = 2$ €, $h = 4$ €/h, optimum $\tilde\mu = 12$. What is the mean time in the system $w = 1/(\mu - \lambda)$?
$7.5$ minutes
$4$ minutes
$12$ minutes
$15$ minutes
Explanation. $w = 1/(12 - 8) = 0.25$ h $= 15$ minutes; with $\mu = 9$ it would be a full hour.
M/M/1 capacity model (Poisson arrivals, exponential service, one server): arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, whose optimum is $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Desk with $\lambda = 8$/h, $c = 2$ €, $h = 4$ €/h: the optimum $\tilde\mu = 12$ costs $32$ €/h. What does the «more efficient» $\mu = 9$ (utilization $89\%$) cost?
$50$ €/h: far worse
$18$ €/h: cheaper
$32$ €/h: the same
$26$ €/h: slightly cheaper
Explanation. $C(9) = 2\cdot 9 + 4\cdot 8/1 = 18 + 32 = 50$ €/h: the apparent waste of the optimum (a third of the capacity idle) is what keeps the queue short.
M/M/1 capacity model (Poisson arrivals, exponential service, one server): arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, whose optimum is $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Desk with $\lambda = 8$/h, $c = 2$ €, $h = 4$ €/h. What is the utilization $\rho = \lambda/\tilde\mu$ at the optimum?
$100\%$
$89\%$
$66.7\%$
$50\%$
Explanation. $\tilde\mu = 12$, so $\rho = 8/12 = 66.7\%$: one third of the capacity stays idle on average, by design.
M/M/1 capacity model (Poisson arrivals, exponential service, one server): arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, whose optimum is $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Case study ($\lambda = 42$/h, $c = 3$, $h = 1.5$): the «utilization wall» plots $w$ against $\rho$. Between $\rho = 90\%$ and $\rho = 99\%$ the waiting time is multiplied by about:
$1.1$
$10$
$2$
$100$
Explanation. $w = 1/(\mu - \lambda) = \rho/(\lambda(1 - \rho))$: $1 - \rho$ goes from $0.10$ to $0.01$, so $w$ grows about tenfold. Saturating resources and serving well conflict mathematically.
M/M/1 capacity model $\min\ c\mu + h\lambda/(\mu - \lambda)$, $\mu > \lambda$, with the promise $1/(\mu - \lambda) \le w_{\max}$. In the case study the economic optimum has $w = 13.1$ minutes. For which promises is $\tilde\mu = \lambda + 1/w_{\max}$ the optimum?
For every $w_{\max}$
Only for $w_{\max} > 13.1$ minutes
Only when the promise binds
Only when $c = h$ in the model
Explanation. If $w_{\max} \ge 13.1$ min the economic optimum already keeps the promise and $\tilde\mu = \lambda + \sqrt{h\lambda/c}$ is unchanged; the formula $\lambda + 1/w_{\max}$ needs the hypothesis that the constraint is active.
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Hard margin: $\min\tfrac12\sum_j w_j^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$. Why does this maximize the margin?
The distance between the hyperplanes $\mathbf w'\mathbf x + b = \pm 1$ is $2/\|\mathbf w\|$
The distance between the hyperplanes $\mathbf w'\mathbf x + b = \pm 1$ is $\|\mathbf w\|$
Because the intercept $b$ is a free variable
Because the labels are $\pm 1$ and cancel out
Explanation. A smaller $\|\mathbf w\|$ means a wider margin; the constraints keep each point on its side, at least one unit away in the scale of $\mathbf w$.
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. What does $\tilde\xi_i > 1$ mean for observation $i$?
It lies exactly on the margin
It is a support vector with $\alpha_i = 0$
It is on the wrong side of the hyperplane
It is correctly classified beyond the margin
Explanation. $0 < \xi_i \le 1$ is a margin violation on the correct side; $\xi_i > 1$ puts the point on the wrong side of the hyperplane (misclassified).
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. What is the effect of a small $C$?
A narrow margin and zero training errors
A wide margin, accepting many points inside it
An infeasible model
No effect on the width of the margin
Explanation. $C$ is the price of violations: a small $C$ buys a wide margin, a large $C$ chases every training point. It must be chosen on validation data.
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual has multipliers $0 \le \alpha_i \le C$. Which feature of the dual opens the door to kernels $K(\mathbf x_i, \mathbf x_j)$?
It depends on the data only through the inner products $\mathbf x_i'\mathbf x_j$
It has the bound constraints $\alpha_i \le C$
It is a maximization problem
It has a single equality constraint
Explanation. Replacing $\mathbf x_i'\mathbf x_j$ with $K(\mathbf x_i, \mathbf x_j)$ classifies in a transformed space without building it.
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual has multipliers $0 \le \alpha_i \le C$. With the RBF kernel $K(\mathbf x_i, \mathbf x_j) = e^{-\gamma\|\mathbf x_i - \mathbf x_j\|^2}$ and $\gamma = 5$, the boundary breaks into islands and 61 of the 90 points are support vectors. What is happening?
The training QP has become non-convex
The model is too simple (underfitting)
Overfitting: the model memorizes the training set
The kernel is not a valid kernel
Explanation. Training remains a convex QP: convexity and ability to generalize are different properties. $C$ and $\gamma$ are chosen together by cross-validation.
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. With unbalanced classes (few defaulters among loan applicants) the slacks of the two classes get different costs $C_-$ and $C_+$. How should they be chosen?
Proportional to the class frequencies
To reflect the costs of the two wrong decisions
Always equal to each other
By maximizing the accuracy on the test set
Explanation. The costs should mirror the decisions (a loan to a defaulter versus a good customer turned down): with a $10\times$ cost on defaulters none escapes, at the price of a few more false alarms.
Explanation. Only the points with $\tilde\alpha_i > 0$ (support vectors) enter $\tilde{\mathbf w}$. The points with $\tilde\alpha_i = 0$ could disappear without changing anything: in the case study 7 support vectors out of 90.
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual has multipliers $0 \le \alpha_i \le C$. The inner products $\mathbf x_i'\mathbf x_j$ of the dual are replaced by a kernel $K(\mathbf x_i, \mathbf x_j)$. Under which condition does training remain a convex QP?
$\gamma < 1$ in the RBF kernel
The two classes are balanced
$C$ is small
The kernel matrix $(K(\mathbf x_i, \mathbf x_j))$ is positive semidefinite
Explanation. With a positive semidefinite kernel matrix the dual objective is concave; the boundary in the original space can be arbitrarily curved.
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual has multipliers $0 \le \alpha_i \le C$. From which condition does the dual constraint $\sum_i \alpha_i y_i = 0$ come?
From the bound $\alpha_i \le C$
From stationarity of the Lagrangian in the free intercept $b$
From the non-negativity of the slacks $\xi_i$
From the classes being balanced
Explanation. $\partial L/\partial b = -\sum_i\alpha_iy_i = 0$; stationarity in $\mathbf w$ gives $\mathbf w = \sum_i\alpha_iy_i\mathbf x_i$ and in $\xi_i$ the bound $\alpha_i \le C$.
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Hard margin: $\min\tfrac12\|\mathbf w\|^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$ for every $i$. What happens when the two classes overlap (no line separates them)?
The optimum has $\mathbf w = \mathbf 0$
The model becomes unbounded
The model is infeasible: slacks are needed (soft margin)
Gurobi returns the best separating line anyway
Explanation. No hyperplane satisfies all the constraints, so the QP has no feasible solution; the soft margin adds slacks $\xi_i \ge 0$ paid in the objective.
Support Vector Regression: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i(\xi_i + \xi_i^*)$ with $|y_i - (\mathbf w'\mathbf x_i + b)| \le \varepsilon + \xi_i^{(*)}$, i.e. errors within a tube of width $\varepsilon$ are free. Which observations determine the fitted line?
Only those on or outside the tube
All the observations equally
Only those strictly inside the tube
Only the observation with the largest $y_i$
Explanation. Points strictly inside the tube have null multipliers, like the points beyond the margin in the SVM; in the case study 14 points out of 40 lie outside the tube.
In the course chapter on Support Vector Machines, the labels $y_i \in \{-1, +1\}$ of the training observations (e.g. reliable / defaulting client) are:
binary decision variables of the QP
continuous variables between $-1$ and $+1$
observed data, not variables
multipliers of the classification constraints
Explanation. The labels are observed data; the variables (coefficients $w_j$, intercept $b$, slacks $\xi_i$, multipliers $\alpha_i$) are all continuous, so the SVM stays within the continuous models of the course.
The course trains its Support Vector Machines without any machine-learning library: every classifier is a QP written and solved with Gurobi. Why?
To understand what a classifier actually optimizes
Because libraries cannot handle the kernel
Because Gurobi is faster than any ML library
Because libraries give only local optima
Explanation. The point of the chapter is to see the SVM as an optimization problem (a convex QP with its dual and multipliers), not as a black box; speed or library limits are not the reason.
A Support Vector Machine is a binary classifier obtained by solving a QP. Which managerial question is a classification problem suited to it?
How many loaves will be sold tomorrow?
Which price maximizes the profit of a concert?
How much should be produced in each month?
Will this client repay the loan or default?
Explanation. Credit risk, churn, predictive maintenance, quality control and fraud are the applications of the notes: each observation gets one of two labels. Predicting a quantity is regression, choosing prices or production plans is optimization.
The course chapter on Support Vector Machines says it «closes the circle» of the course. In what sense?
It introduces integer variables for the first time
Convex QPs and duality drive a classifier
It replaces Gurobi with a machine-learning library
It shows that optimization is not needed in machine learning
Explanation. Convex QPs, duality and multipliers, used for production, logistics and finance, are the engine of the SVM: the support vectors are read through complementary slackness, as shadow prices were.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Hard margin: $\min\ \tfrac12\|\mathbf w\|^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$. Two observations: $\mathbf x_1 = (0; 0)$ with $y_1 = -1$ and $\mathbf x_2 = (4; 0)$ with $y_2 = +1$. What are $\tilde{\mathbf w}$, $\tilde b$ and the margin $2/\|\tilde{\mathbf w}\|$?
$\mathbf w = (1; 0)$, $b = -1$, margin $2$
$\mathbf w = (0.5; 0)$, $b = -1$, margin $4$
$\mathbf w = (0.25; 0)$, $b = -0.5$, margin $8$
$\mathbf w = (0.5; 0.5)$, $b = -1$, margin $2.83$
Explanation. Constraints: $-b \ge 1$ and $4w_1 + b \ge 1$; minimizing $w_1^2 + w_2^2$ gives $w_2 = 0$ and both constraints active: $b = -1$, $w_1 = 0.5$. The hyperplane $x_1 = 2$ is the bisector of the segment, and the margin $2/0.5 = 4$ equals the distance between the two points.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Hard margin with $n$ observations and $p$ features: $\min\ \tfrac12\sum_j w_j^2$ subject to $y_i(\sum_j w_jx_{ij} + b) \ge 1$. How many variables and constraints does the QP have?
$n$ variables and $p + 1$ constraints
$p$ variables and $n + 1$ constraints
$n + p$ variables and $n$ constraints
$p + 1$ variables and $n$ constraints
Explanation. The variables are the $p$ coefficients $w_j$ and the intercept $b$, all free; there is one classification constraint per observation. The slacks $\xi_i$ (another $n$ variables) appear only in the soft margin.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Hard margin: $\min\ \tfrac12\|\mathbf w\|^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$ for every $i$. Under which hypothesis on the data does this QP have an optimal solution?
The two classes are linearly separable
The two classes have the same number of points
The features are standardized
There are more observations than features
Explanation. If some hyperplane separates the classes, scaling it gives a feasible $(\mathbf w, b)$; the objective is convex and bounded below by $0$, so an optimum exists. Without separability the feasible set is empty: this is why the soft margin is needed.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. At the optimum an observation has $0 < \tilde\xi_i < 1$. Where is it?
Exactly on its margin line
On the wrong side of the hyperplane
On the right side, but inside the margin
Far beyond its margin line
Explanation. $y_i(\mathbf w'\mathbf x_i + b) = 1 - \tilde\xi_i$ lies strictly between $0$ and $1$: the point is correctly classified but violates the margin. With $\tilde\xi_i > 1$ it would be misclassified, with $\tilde\xi_i = 0$ on or beyond the margin.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. For fixed $(\mathbf w, b)$, what is the optimal value of each slack $\xi_i$?
$\xi_i = \max\{0,\ y_i(\mathbf w'\mathbf x_i + b) - 1\}$
Explanation. $\xi_i$ must satisfy $\xi_i \ge 1 - y_i(\mathbf w'\mathbf x_i + b)$ and $\xi_i \ge 0$, and costs $C > 0$: it takes the smallest admissible value, the hinge loss. So the soft margin minimizes $\tfrac12\|\mathbf w\|^2$ plus $C$ times the total hinge loss.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Credit-risk case (90 clients, 2 indicators): $C = 0.05$ gives margin $2.42$ with 2 errors and 22 points inside the margin; $C = 20$ gives margin $0.36$, 0 errors, 3 points inside. Is $C = 20$ the best choice?
Yes: it makes no error on the training set
Yes: a larger $C$ always generalizes better
No: the smallest $C$ is always the best
Not necessarily: $C$ is chosen on validation data
Explanation. A large $C$ chases every training point (zero errors, very narrow margin); a small one buys a wide margin. It is the regularization–fit trade-off: $C$ is chosen on validation data, never on the training errors or on the test set.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. When does the soft margin, for $C$ large enough, return the hard-margin solution ($\min\ \tfrac12\|\mathbf w\|^2$ with $y_i(\mathbf w'\mathbf x_i + b) \ge 1$)?
Always, whatever the data
Never: the two models differ for every $C$
When the classes are linearly separable
Only when there is a single feature, $p = 1$
Explanation. If the classes are separable the hard margin is feasible, and for a large enough $C$ paying any slack costs more than shrinking the margin: all $\xi_i = 0$. With overlapping classes the hard margin is infeasible and the slacks stay positive for every $C$.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ subject to $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. At the optimum an observation has $\tilde\alpha_i = C$. What does complementary slackness say about it?
$\tilde\xi_i > 0$: inside the margin or misclassified
It lies exactly on the margin line
It lies beyond the margin and does not affect the solution
It must be removed from the training set
Explanation. The KKT conditions organize the points: $\alpha_i = 0$ beyond the margin, $0 < \alpha_i < C$ exactly on it, $\alpha_i = C$ when the constraint pays a slack $\xi_i > 0$ (inside the margin, or on the wrong side if $\xi_i > 1$).
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ subject to $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. Credit-risk case with $C = 1$: 83 of the 90 clients have $\tilde\alpha_i = 0$. What happens to the classifier if those 83 points are removed and the QP is solved again?
It changes completely, both $\mathbf w$ and $b$
It becomes infeasible for the remaining points
It stays the same
Only the intercept $b$ changes
Explanation. $\tilde{\mathbf w} = \sum_i\tilde\alpha_iy_i\mathbf x_i$ uses only the 7 points with $\tilde\alpha_i > 0$, the support vectors; the other 83 are beyond the margin and could disappear without changing the solution.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ subject to $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. In the credit-risk case the solver reports dual value $4.7868$ = primal value $4.7868$. Which result guarantees this equality?
Weak duality, which holds for every QP
The kernel trick
The uniqueness of the support vectors
Strong duality for convex QPs
Explanation. The soft margin is a convex QP with linear constraints: the KKT conditions are necessary and sufficient and the dual optimum has the same value as the primal. Weak duality would only give an inequality.
Explanation. The transformed space is never built: the classifier uses only kernel values between the new point and the support vectors ($\tilde\alpha_i > 0$), weighted by $\tilde\alpha_iy_i$, plus the intercept.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. With the RBF kernel $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$ the SVM has two hyperparameters, $C$ and $\gamma$. How do the notes choose them?
$\gamma$ first on the training errors, then $C$
The largest values that give zero training errors
$C$ by duality, $\gamma$ by a rule of thumb
Together, by cross-validation
Explanation. $C$ and $\gamma$ interact (both control how closely the frontier follows the training points), so they are chosen together by cross-validation; zero training errors is the overfitting signal, not a goal.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. «Ring» case with the RBF kernel: with $\gamma = 5$ the frontier breaks into islands and 61 of 90 points are support vectors, yet the training problem is still a convex QP. What does this show?
Convexity and generalization are different things
The QP is no longer convex for large $\gamma$
The solver has stopped at a local optimum
The RBF kernel is not a valid kernel for $\gamma > 1$
Explanation. The QP is convex for every valid kernel and its optimum is global, but a global optimum of the training problem can still memorize the data: generalization is judged on validation data.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. The rare class (e.g. defaulting clients, $y_i = +1$) costs more when misclassified. How do the notes change the objective?
They duplicate the rare observations in the data
They raise the margin requirement of the rare class to 2
Explanation. It is enough to weigh the slacks of the two classes differently, with $C_+ > C_-$ for the class whose errors cost more; the model stays a convex QP.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Credit-risk case: with equal costs, precision $1.00$ and recall of the defaulters $0.94$; with a cost 10 times higher on the defaulters' slacks, precision $0.97$ and recall $1.00$. How is the change read?
The frontier moves toward the healthy class
The classifier got worse on every measure
The frontier moves toward the defaulters: fewer false alarms
Nothing changed: the differences are numerical noise
Explanation. Raising the cost of missing a defaulter pushes the frontier into the healthy region: recall reaches 100% and precision drops slightly because some good clients are flagged.
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. In the credit-risk case, the recall of the defaulters is $1.00$. What does it mean?
Every client flagged as defaulter really defaults
The training error is zero
All slacks $\xi_i$ are zero
No actual defaulter is classified as reliable
Explanation. Recall = share of the actual defaulters that the classifier detects; precision = share of the flagged clients that really default. Recall 1 means no defaulter escapes, possibly at the price of false alarms.
Support Vector Regression: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i(\xi_i + \xi_i^*)$ with $|y_i - (\mathbf w'\mathbf x_i + b)| \le \varepsilon + \xi_i^{(*)}$, where $\xi_i, \xi_i^* \ge 0$. What is the role of $\varepsilon$?
The weight of the errors in the objective
The half-width of a tube of free errors
The largest admissible slope of the line
The share of points allowed outside the tube
Explanation. Errors within $\pm\varepsilon$ of the estimate are ignored; only the points outside the tube pay, through $\xi_i$ (above) or $\xi_i^*$ (below), with weight $C$.
Support Vector Regression on price–demand data (40 observations): with tube $\varepsilon = 8$, 14 points fall outside the tube. What happens to the number of points outside if $\varepsilon$ is enlarged?
It grows, because the tube is stricter
It stays 14, since it does not depend on $\varepsilon$
It decreases: fewer points pay
It becomes zero for every $\varepsilon > 0$
Explanation. A wider tube contains more points, which are then ignored; the estimate rests on the fewer points left outside (with $\varepsilon = 8$ the line was $-10.86p + 220.32$, against the true $-11p + 220$).
Support Vector Regression: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i(\xi_i + \xi_i^*)$ subject to $y_i - (\mathbf w'\mathbf x_i + b) \le \varepsilon + \xi_i$, $(\mathbf w'\mathbf x_i + b) - y_i \le \varepsilon + \xi_i^*$, $\xi_i, \xi_i^* \ge 0$. Which class of problem is it, and what follows?
A convex QP: every local optimum is global
An LP: its optimum is at a vertex
A nonconvex QP: it needs `NonConvex = 2`
An NLP with functional constraints
Explanation. Convex quadratic objective ($\tfrac12\|\mathbf w\|^2$ plus a linear term) and linear constraints: a convex QP, like the soft-margin SVM, with a certifiable global optimum.
The dual of the soft-margin SVM has objective $\sum_i \alpha_i - \tfrac12 \sum_i\sum_j \alpha_i\alpha_j y_i y_j\, \mathbf x_i'\mathbf x_j$. How does it depend on the data $\mathbf x_i$?
On each coordinate $x_{ij}$ taken separately
Only on the mean of all the observations
Only on the observations labelled $y_i = +1$
Only through the inner products $\mathbf x_i'\mathbf x_j$
Explanation. The dual depends on the data only through the inner products: replacing them with a kernel gives nonlinear boundaries with the same QP.
A bakery fits sales against temperature in two ways: least absolute deviations (an LP) and least squares (a QP). The history contains five strike days with very low sales. Which fitted line moves more because of them?
The absolute-deviation (LP) line
The least-squares (QP) line, which pays deviations squared
Neither line moves noticeably
Both lines move by the same amount
Explanation. A deviation of $100$ weighs, squared, as much as ten thousand deviations of one: least squares is dragged down, the LP stays with the normal data.
Bakery history with five strike days. On the 55 normal days the least-absolute-deviation (LP) line has mean error $13.08$ pieces, the least-squares (QP) line $14.81$; the QP refitted *without* the strikes has intercept $213.58$, from which the LP intercept differs by $3.81$ and the QP one by $11.24$. What is the lesson?
The QP is better because it uses all the data
Both methods need the strikes removed by hand
The strikes do not affect either estimate
The LP finds by itself the line the QP finds only after cleaning
Explanation. Paying each deviation once makes the LP robust to outliers: no one has to recognize and remove the strike days first.
Bakery history (60 days, 5 strike days with about 20 loaves sold): the least-squares line is pulled down by the strikes, the least-absolute-deviations line is not. Why does one anomalous datum in ten move least squares so much?
Because least squares has more variables
Because the LP removes the outliers before estimating
Because the QP is solved with a looser tolerance
Because it pays each deviation squared
Explanation. The squared objective lets a large deviation dominate; the LP pays each deviation once, so the line stays where the normal data are, without anyone cleaning the history by hand.
In the bakery case study, least squares is written as a QP to compare it with the LP of absolute deviations. How?
$\min\sum_i(u_i + v_i)^2$ with $u_i, v_i \ge 0$ and no constraints
$\min\sum_ir_i^2$, $r_i$ free, same equalities as the LP
$\min\sum_i|r_i|$ with $r_i \ge 0$ and the same equalities
$\max\sum_ir_i^2$ with $r_i$ free and no constraints
Explanation. One free residual per observation, defined by the same equality as in the LP, and a quadratic objective: a convex QP solved with the same solver.
The robust regression of LP Modelling minimizes the sum of the absolute deviations (an LP). What does least squares minimize?
The maximum of the absolute deviations
The sum of the squared deviations
The weighted sum of the deviations with weights $\tau$ and $1-\tau$
The number of badly predicted observations
Explanation. Least squares minimizes $\sum_i r_i^2$: a convex QP; the maximum of the deviations would be a minimax LP, the weighted sum quantile regression.
Which advantage of least squares over absolute deviations does the chapter highlight?
Closed-form normal equations and the estimate of the mean
Robustness to the outliers in the history
The possibility of estimating any quantile
Automatic selection of the useful features
Explanation. On clean data least squares has the normal equations and estimates the mean; robustness, quantiles and selection are strengths of the linear models.
In the least-squares QP $\min \sum_i r_i^2$ with $\sum_j w_j x_{ij} + b + r_i = y_i$, how are the residuals $r_i$ declared?
Non-negative, like the deviations of the linear model
Binary, to count the errors
As two non-negative variables $u_i$ and $v_i$ per residual
Free: the square does not distinguish the sign
Explanation. The square of a residual does not depend on its sign: one free variable per residual is enough, without the two positive parts of the linear model.
Least squares without features ($p = 0$) on seven sales: 88, 96, 104, 112, 120, 132, 148. What is the optimal intercept $\tilde b$?
$800/7 \approx 114.29$, the mean
$112$, the median
$120$, the $9/13$ quantile
$118$, the midpoint between minimum and maximum
Explanation. Stationarity with respect to $b$ gives $\sum_i r_i = 0$: $\tilde b$ is the mean $800/7$. The median 112 is the optimum of absolute deviations.
In the same seven sales the last value goes from 148 to 248. How do the least-squares estimate (mean) and the absolute-deviation estimate (median) change?
They both stay unchanged, because the data are few
The mean rises by 14.29, the median stays at 112
The median rises by 100, the mean stays the same
They both rise by 100/7, that is by about 14.29
Explanation. The mean depends on every value: it rises by $100/7 = 14.29$. The median depends only on the order of the values and stays at 112.
In the least-squares QP the multiplier of the constraint of observation $i$ is $\tilde\pi_i = 2\tilde r_i$. What does it measure?
How much the sum of squares grows if $y_i$ rises by one
The probability that observation $i$ is an outlier
The number of observations lying above the line
The weight of feature $i$ in the forecast
Explanation. The multiplier is the derivative of the optimal value with respect to the right-hand side $y_i$: twice the residual. A distant datum weighs as much as it is distant.
In absolute-deviation regression (LP) the duals are $\pm 1/2$ or an interior value; in least squares they are $2 r_i$. What consequence does this have on outliers?
None: the two models weigh outliers in the same way
Least squares ignores outliers altogether
The LP gives outliers a weight proportional to the deviation
In least squares an outlier weighs in proportion to the deviation
Explanation. In the LP only the sign of the residual matters (bounded weight); in least squares the weight grows with the residual, and a distant outlier pulls the line.
The newsvendor needs the $9/13$ quantile of demand. Starting from least squares (forecast mean $128.7$, standard deviation of the residuals $9.40$, $z = 0.5024$), which quantity is obtained assuming normal residuals?
$128.7$ items
$138.1$ items
$133.5$ items
$124.0$ items
Explanation. $128.7 + 0.5024 \cdot 9.40 = 133.5$ items; quantile regression, with no assumption on the shape of the errors, gives $132.1$.
To reach the newsvendor quantile a stock $z\sigma$ is added to the least-squares mean. Which assumption does this road require, and quantile regression does not?
That the features are standardized
That the strike days are included
That the quantile is the median
That the residuals are normal
Explanation. The formula mean $+\,z\sigma$ uses the quantile of the standard normal: it holds if the residuals are normal. Quantile regression estimates the quantile directly.
On the typical day of the bakery (28 degrees, price 3.00, weekend) the mean forecast by least squares is 128.7 items. Why is producing 128.7 items not enough?
Because with $c_u = 9$ and $c_o = 4$ the $9/13$ quantile is needed, above the mean
Because the least-squares mean is underestimated by ten items
Because the weekend must be excluded from the demand estimate
Because the mean must always be rounded down
Explanation. With shortage cost 9 and excess cost 4 the critical fractile is $9/13 > 1/2$: it pays to produce more than the mean, that is a high quantile of demand.
The demand of the hottest normal day (33.7 degrees) is moved down. How do the least-squares line and the absolute-deviation line react?
They both stay still, whatever the shift
They both move in proportion to the shift
The LP line moves in proportion, the QP line only once
The QP line moves in proportion, the LP line only once
Explanation. In least squares the slope changes by about 0.004 per item; in the LP only the sign of the residual matters and the estimate stays 211.63 $-$ 3.689 temperature.
Ridge regression: $\lambda \sum_j w_j^2$ is added to the least-squares objective. As $\lambda$ grows the coefficients shrink but none becomes exactly zero. Why?
Because Gurobi rounds the small coefficients
Because $2\lambda w_j$ vanishes at $w_j = 0$: no fixed push
Because the features have been standardized
Because the problem becomes non-convex for large $\lambda$
Explanation. Near zero the quadratic penalty no longer pushes: the coefficient approaches zero without reaching it. The budget on absolute values has a constant push instead and sets coefficients to zero.
Least-squares QP without features: $\min \sum_i r_i^2$ with $b + r_i = y_i$. What does stationarity with respect to $b$ give?
$\sum_i |r_i| = 0$: the estimate is the median
$r_i = 0$ for every observation $i$
$\sum_i r_i = 0$: the estimate is the mean
$b = \max_i y_i$, the largest value
Explanation. With $\pi_i = 2r_i$ stationarity with respect to $b$ gives $\sum_i r_i = 0$: the estimate $\tilde b$ is the mean of the data (114.29 for the seven sales).
In the least-squares QP the residuals $r_i$ are free variables. What happens if they keep the default gurobipy lower bound ($r_i \ge 0$)?
The line must lie below all the data: biased estimate
Nothing changes, because the square ignores the sign
The model becomes non-convex and needs `NonConvex = 2`
Gurobi stops and reports a syntax error
Explanation. With $r_i \ge 0$ every prediction must be at most the observed value: the model changes and the estimate is no longer the least-squares one.
Generated questions (29)
Each generator builds a new instance, with different numbers, at every start: a few examples here.
Convex QP: $\min\ 6x_1^2 + x_2^2$ subject to $x_1 + x_2 \ge 20$, $x_1, x_2 \ge 0$. At the optimum the constraint is active, the bounds are not, and stationarity of the Lagrangian $L = f + \lambda(20 - x_1 - x_2)$ holds. What are $\tilde x_1$ and the multiplier $\lambda$?
$\tilde x_1 = 2.86$, $\lambda = 34.29$
$\tilde x_1 = 10$, $\lambda = 120$
$\tilde x_1 = 17.14$, $\lambda = 34.29$
$\tilde x_1 = 2.86$, $\lambda = 17.14$
Explanation. Stationarity: $12x_1 = \lambda$ and $2x_2 = \lambda$, so $x_1 = \lambda/12$, $x_2 = \lambda/2$; the active constraint gives $\lambda = 34.29$, hence $\tilde x_1 = 2.86$, $\tilde x_2 = 17.14$. The variable with the smaller quadratic coefficient takes the larger share; $\lambda$ is the marginal cost of one more unit of $d$.
Convex QP: $\min\ 3x_1^2 + 6x_2^2$ subject to $x_1 + x_2 \ge 9$, $x_1, x_2 \ge 0$. At the optimum the constraint is active, the bounds are not, and stationarity of the Lagrangian $L = f + \lambda(9 - x_1 - x_2)$ holds. What are $\tilde x_1$ and the multiplier $\lambda$?
$\tilde x_1 = 4.5$, $\lambda = 27$
$\tilde x_1 = 6$, $\lambda = 18$
$\tilde x_1 = 3$, $\lambda = 36$
$\tilde x_1 = 6$, $\lambda = 36$
Explanation. Stationarity: $6x_1 = \lambda$ and $12x_2 = \lambda$, so $x_1 = \lambda/6$, $x_2 = \lambda/12$; the active constraint gives $\lambda = 36$, hence $\tilde x_1 = 6$, $\tilde x_2 = 3$. The variable with the smaller quadratic coefficient takes the larger share; $\lambda$ is the marginal cost of one more unit of $d$.
Example 1 · nlpm-g-kkt-proiezione · level media · notes
Convex QP: $\min\ (x - 4)^2 + (y - 4)^2$ subject to $x + y \le 7$, $x, y \ge 0$; $\lambda \ge 0$ is the KKT multiplier of $x + y \le 7$ (Lagrangian $L = f + \lambda(x + y - 7)$). What are the optimum and $\lambda$?
$(4; 4)$, $\lambda = 0$
$(3.5; 3.5)$, $\lambda = 0.5$
$(3.5; 3.5)$, $\lambda = 1$
$(3.5; 3.5)$, $\lambda = 2$
Explanation. The free minimum $(4, 4)$ violates $x + y \le 7$, so the constraint is active. Stationarity: $2(x - 4) + \lambda = 0$, $2(y - 4) + \lambda = 0$, so $x = 4 - \lambda/2$, $y = 4 - \lambda/2$; with $x + y = 7$: $\lambda = 1$, optimum $(3.5; 3.5)$, both positive (bounds inactive). Convex problem: the KKT point is the global optimum.
Example 2 · nlpm-g-kkt-proiezione · level media · notes
Convex QP: $\min\ (x - 3)^2 + (y - 6)^2$ subject to $x + y \le 4$, $x, y \ge 0$; $\lambda \ge 0$ is the KKT multiplier of $x + y \le 4$ (Lagrangian $L = f + \lambda(x + y - 4)$). What are the optimum and $\lambda$?
$(3.5; 0.5)$, $\lambda = 5$
$(3; 6)$, $\lambda = 0$
$(0.5; 3.5)$, $\lambda = 2.5$
$(0.5; 3.5)$, $\lambda = 5$
Explanation. The free minimum $(3, 6)$ violates $x + y \le 4$, so the constraint is active. Stationarity: $2(x - 3) + \lambda = 0$, $2(y - 6) + \lambda = 0$, so $x = 3 - \lambda/2$, $y = 6 - \lambda/2$; with $x + y = 4$: $\lambda = 5$, optimum $(0.5; 3.5)$, both positive (bounds inactive). Convex problem: the KKT point is the global optimum.
3. The solver for nonlinear models (1)
Example 1 · nlpm-g-sv-perturbazione-nl · level facile · notes
A gurobipy model maximizes $20\log(1 + 1x)$ subject to $0 \le x \le b$, with the logarithm written through `addGenConstrLog`, so the solver returns no dual for the bound $x \le b$. Solving with $b = 5$ gives $35.8352$; with $b = 5.1$ it gives $36.1658$. What is the perturbation estimate of the multiplier of $x \le b$?
$\approx 33.06$
$\approx 7.17$
$\approx 3.31$
$\approx 0.33$
Explanation. Incremental ratio: $(36.1658 - 35.8352)/0.1 = 3.31$, close to the exact derivative $20\cdot 1/(1 + 1\cdot 5) = 3.33$ (the difference is the curvature). Forgetting to divide by $0.1$ is the typical slip.
Example 2 · nlpm-g-sv-perturbazione-nl · level facile · notes
A gurobipy model maximizes $50\log(1 + 1x)$ subject to $0 \le x \le b$, with the logarithm written through `addGenConstrLog`, so the solver returns no dual for the bound $x \le b$. Solving with $b = 7$ gives $103.9721$; with $b = 7.1$ it gives $104.5932$. What is the perturbation estimate of the multiplier of $x \le b$?
$\approx 62.11$
$\approx 14.85$
$\approx 0.62$
$\approx 6.21$
Explanation. Incremental ratio: $(104.5932 - 103.9721)/0.1 = 6.21$, close to the exact derivative $50\cdot 1/(1 + 1\cdot 7) = 6.25$ (the difference is the curvature). Forgetting to divide by $0.1$ is the typical slip.
4. Production with quadratic smoothing (1)
Example 1 · nlpm-g-prodq-scorta · level facile · notes
Production with quadratic smoothing, one product and two months: demand $d_1 = 60$ and $d_2 = 100$, holding cost $h = 2$ per unit, ample capacity, zero initial stock and weight $\gamma = 1$ on the squared jump $(x_2 - x_1)^2$. With $x_1 = d_1 + s_1$ and $x_2 = d_2 - s_1$, what is the optimal stock $\tilde s_1$?
$\tilde s_1 = 19$
$\tilde s_1 = 20$
$\tilde s_1 = 19.5$
$\tilde s_1 = 19.75$
Explanation. The jump is $40 - 2s_1$ and the objective (up to constants) is $h s_1 + \gamma(40 - 2s_1)^2$. Stationarity: $h - 4\gamma(40 - 2s_1) = 0$, so $\tilde s_1 = 40/2 - h/(8\gamma) = 19.75$: stock is built until the marginal saving on the penalty equals the holding cost.
Example 2 · nlpm-g-prodq-scorta · level facile · notes
Production with quadratic smoothing, one product and two months: demand $d_1 = 50$ and $d_2 = 110$, holding cost $h = 1$ per unit, ample capacity, zero initial stock and weight $\gamma = 0.05$ on the squared jump $(x_2 - x_1)^2$. With $x_1 = d_1 + s_1$ and $x_2 = d_2 - s_1$, what is the optimal stock $\tilde s_1$?
$\tilde s_1 = 27.5$
$\tilde s_1 = 20$
$\tilde s_1 = 25$
$\tilde s_1 = 30$
Explanation. The jump is $60 - 2s_1$ and the objective (up to constants) is $h s_1 + \gamma(60 - 2s_1)^2$. Stationarity: $h - 4\gamma(60 - 2s_1) = 0$, so $\tilde s_1 = 60/2 - h/(8\gamma) = 27.5$: stock is built until the marginal saving on the penalty equals the holding cost.
5. Supply chain with congestion and sustainability (2)
Example 1 · nlpm-g-sc-due-rotte · level facile · notes
Minimum-cost flow LP of a supply chain: a market demands $D = 140$ units, sent on two routes with flows $x_1, x_2 \ge 0$ and demand constraint $x_1 + x_2 \ge D$. Route 1 costs $c_1 = 4$ €/unit with capacity $x_1 \le 110$; route 2 costs $c_2 = 10$ €/unit with unlimited capacity. What are the optimal cost and the shadow price of the demand constraint (cost of serving one more unit)?
cost 740 €, marginal cost 6 €/unit
cost 740 €, marginal cost 4 €/unit
cost 560 €, marginal cost 4 €/unit
cost 740 €, marginal cost 10 €/unit
Explanation. The cheap route is saturated ($x_1 = 110$) and the rest goes on route 2: $4\cdot 110 + 10\cdot 30 = 740$ €. The next unit can only travel on route 2: the shadow price of the demand is $10$.
Example 2 · nlpm-g-sc-due-rotte · level facile · notes
Minimum-cost flow LP of a supply chain: a market demands $D = 110$ units, sent on two routes with flows $x_1, x_2 \ge 0$ and demand constraint $x_1 + x_2 \ge D$. Route 1 costs $c_1 = 2$ €/unit with capacity $x_1 \le 60$; route 2 costs $c_2 = 3$ €/unit with unlimited capacity. What are the optimal cost and the shadow price of the demand constraint (cost of serving one more unit)?
cost 270 €, marginal cost 3 €/unit
cost 270 €, marginal cost 1 €/unit
cost 220 €, marginal cost 2 €/unit
cost 270 €, marginal cost 2 €/unit
Explanation. The cheap route is saturated ($x_1 = 60$) and the rest goes on route 2: $2\cdot 60 + 3\cdot 50 = 270$ €. The next unit can only travel on route 2: the shadow price of the demand is $3$.
Example 1 · nlpm-g-sc-congestione · level media · notes
Supply chain with congestion: $D = 235$ units are split between two routes, $x_1 + x_2 = D$, $x_1, x_2 \ge 0$. Route 1 (unit cost $c_1 = 1$, nominal capacity $u_1 = 140$, congestion parameter $\alpha = 2$) costs $c_1x_1 + \alpha c_1x_1^2/u_1$ €; route 2 costs $c_2 = 6$ €/unit with ample capacity. Minimizing the total cost, what is the optimal split $(\tilde x_1; \tilde x_2)$?
$(\tilde x_1; \tilde x_2) = (140; 95)$
$(\tilde x_1; \tilde x_2) = (117.5; 117.5)$
$(\tilde x_1; \tilde x_2) = (235; 0)$
$(\tilde x_1; \tilde x_2) = (175; 60)$
Explanation. At the optimum the marginal costs are equal: $1 + 2\alpha\,1\,x_1/140 = 6$, so $x_1 = 175$ and $x_2 = 60$. The pure LP would saturate route 1; forgetting the factor 2 of the derivative doubles $x_1$.
Example 2 · nlpm-g-sc-congestione · level media · notes
Supply chain with congestion: $D = 370$ units are split between two routes, $x_1 + x_2 = D$, $x_1, x_2 \ge 0$. Route 1 (unit cost $c_1 = 5$, nominal capacity $u_1 = 200$, congestion parameter $\alpha = 0.5$) costs $c_1x_1 + \alpha c_1x_1^2/u_1$ €; route 2 costs $c_2 = 13$ €/unit with ample capacity. Minimizing the total cost, what is the optimal split $(\tilde x_1; \tilde x_2)$?
$(\tilde x_1; \tilde x_2) = (185; 185)$
$(\tilde x_1; \tilde x_2) = (200; 170)$
$(\tilde x_1; \tilde x_2) = (320; 50)$
$(\tilde x_1; \tilde x_2) = (370; 0)$
Explanation. At the optimum the marginal costs are equal: $5 + 2\alpha\,5\,x_1/200 = 13$, so $x_1 = 320$ and $x_2 = 50$. The pure LP would saturate route 1; forgetting the factor 2 of the derivative doubles $x_1$.
6. The Markowitz portfolio (4)
Example 1 · nlpm-g-mk-minvar · level facile · notes
Markowitz model with two uncorrelated assets of volatilities (standard deviations of the return) $\sigma_1 = 30\%$ and $\sigma_2 = 40\%$. The shares $x_1, x_2$ of capital, with $x_1 + x_2 = 1$, minimize the portfolio variance (no return constraint). What are the optimal share $\tilde x_1$ and the portfolio volatility $\sigma_p$ (square root of the variance)?
$\tilde x_1 = 50\%$, $\sigma_p = 25\%$
$\tilde x_1 = 57.1\%$, $\sigma_p = 24.2\%$
$\tilde x_1 = 36\%$, $\sigma_p = 27.8\%$
$\tilde x_1 = 64\%$, $\sigma_p = 24\%$
Explanation. Setting the derivative of $\sigma_1^2 x_1^2 + \sigma_2^2 (1 - x_1)^2$ to zero gives $x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$: the weights are inversely proportional to the variances (not to the volatilities). The volatility is below that of both assets.
Example 2 · nlpm-g-mk-minvar · level facile · notes
Markowitz model with two uncorrelated assets of volatilities (standard deviations of the return) $\sigma_1 = 20\%$ and $\sigma_2 = 40\%$. The shares $x_1, x_2$ of capital, with $x_1 + x_2 = 1$, minimize the portfolio variance (no return constraint). What are the optimal share $\tilde x_1$ and the portfolio volatility $\sigma_p$ (square root of the variance)?
$\tilde x_1 = 50\%$, $\sigma_p = 22.4\%$
$\tilde x_1 = 20\%$, $\sigma_p = 32.2\%$
$\tilde x_1 = 80\%$, $\sigma_p = 17.9\%$
$\tilde x_1 = 66.7\%$, $\sigma_p = 18.9\%$
Explanation. Setting the derivative of $\sigma_1^2 x_1^2 + \sigma_2^2 (1 - x_1)^2$ to zero gives $x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$: the weights are inversely proportional to the variances (not to the volatilities). The volatility is below that of both assets.
Example 1 · nlpm-g-mk-portafoglio · level facile · notes
Markowitz model, portfolio of two assets with shares of capital $x_1 = 0.5$, $x_2 = 0.5$; expected returns $\mu_1 = 5\%$, $\mu_2 = 12\%$; volatilities $\sigma_1 = 0.2$, $\sigma_2 = 0.25$; correlation $\rho = 0.75$, so $q_{ii} = \sigma_i^2$ and $q_{12} = q_{21} = \rho\sigma_1\sigma_2$. What are its expected return and its variance $\sum_{i}\sum_{j} q_{ij} x_i x_j$?
expected return 8.5%, variance 0.0444
expected return 8.5%, variance 0.0513
expected return 8.5%, variance 0.0256
expected return 8.5%, variance 0.035
Explanation. The return is linear, $\mu_1 x_1 + \mu_2 x_2$. The variance has three terms: $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$; the covariance appears twice ($q_{12}$ and $q_{21}$).
Example 2 · nlpm-g-mk-portafoglio · level facile · notes
Markowitz model, portfolio of two assets with shares of capital $x_1 = 0.4$, $x_2 = 0.6$; expected returns $\mu_1 = 8\%$, $\mu_2 = 13\%$; volatilities $\sigma_1 = 0.3$, $\sigma_2 = 0.15$; correlation $\rho = -0.5$, so $q_{ii} = \sigma_i^2$ and $q_{12} = q_{21} = \rho\sigma_1\sigma_2$. What are its expected return and its variance $\sum_{i}\sum_{j} q_{ij} x_i x_j$?
expected return 11%, variance 0.0117
expected return 11%, variance 0.0171
expected return 11%, variance 0.0225
expected return 11%, variance 0.0495
Explanation. The return is linear, $\mu_1 x_1 + \mu_2 x_2$. The variance has three terms: $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$; the covariance appears twice ($q_{12}$ and $q_{21}$).
Example 1 · nlpm-g-mk-correlati · level media · notes
Markowitz model with two assets of volatilities (standard deviations of the return) $\sigma_1 = 0.3$, $\sigma_2 = 0.4$ and correlation $\rho = -0.5$. The shares $x_1 + x_2 = 1$ minimize the portfolio variance $\sum_i\sum_j q_{ij}x_ix_j$, with covariance $q_{12} = \rho\sigma_1\sigma_2$ (no return constraint; the optimum has $x_1, x_2 > 0$). What are $\tilde x_1$ and the minimum variance $\sigma_p^2$?
$\tilde x_1 = 59.5\%$, $\sigma_p^2 = 0.0292$
$\tilde x_1 = 76.9\%$, $\sigma_p^2 = 0.0405$
$\tilde x_1 = 64\%$, $\sigma_p^2 = 0.03$
$\tilde x_1 = 40.5\%$, $\sigma_p^2 = 0.0424$
Explanation. With correlation $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 0.5946$; the variance is $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ at that weight. Ignoring $\rho$ or flipping its sign gives the wrong weight.
Example 2 · nlpm-g-mk-correlati · level media · notes
Markowitz model with two assets of volatilities (standard deviations of the return) $\sigma_1 = 0.2$, $\sigma_2 = 0.4$ and correlation $\rho = -0.25$. The shares $x_1 + x_2 = 1$ minimize the portfolio variance $\sum_i\sum_j q_{ij}x_ix_j$, with covariance $q_{12} = \rho\sigma_1\sigma_2$ (no return constraint; the optimum has $x_1, x_2 > 0$). What are $\tilde x_1$ and the minimum variance $\sigma_p^2$?
$\tilde x_1 = 25\%$, $\sigma_p^2 = 0.085$
$\tilde x_1 = 87.5\%$, $\sigma_p^2 = 0.0288$
$\tilde x_1 = 80\%$, $\sigma_p^2 = 0.0256$
$\tilde x_1 = 75\%$, $\sigma_p^2 = 0.025$
Explanation. With correlation $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 0.75$; the variance is $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ at that weight. Ignoring $\rho$ or flipping its sign gives the wrong weight.
Example 1 · nlpm-g-mk-due-titoli-r · level complessa · notes
Markowitz with two assets: expected returns $\mu_1 = 16\%$, $\mu_2 = 6\%$; volatilities $\sigma_1 = 27\%$, $\sigma_2 = 14\%$; correlation $\rho = -0.2$. Minimize the portfolio variance $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ with $x_1 + x_2 = 1$, $x \ge 0$ and expected return at least $\bar r = 12\%$. What are the optimal share $x_1$ and the portfolio volatility?
$x_1 = 60\%$, volatility $16.05\%$
$x_1 = 60\%$, volatility $21.8\%$
$x_1 = 25.2\%$, volatility $11.29\%$
$x_1 = 60\%$, volatility $17.14\%$
Explanation. Minimum-variance share without the return constraint: $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 25.2\%$, with return $8.52\%$. It is below $\bar r$, so the constraint binds: $x_1\mu_1 + (1 - x_1)\mu_2 = \bar r$ gives $x_1 = 60\%$. Volatility $16.05\%$.
Example 2 · nlpm-g-mk-due-titoli-r · level complessa · notes
Markowitz with two assets: expected returns $\mu_1 = 14\%$, $\mu_2 = 8\%$; volatilities $\sigma_1 = 19\%$, $\sigma_2 = 8\%$; correlation $\rho = 0$. Minimize the portfolio variance $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ with $x_1 + x_2 = 1$, $x \ge 0$ and expected return at least $\bar r = 12\%$. What are the optimal share $x_1$ and the portfolio volatility?
$x_1 = 66.7\%$, volatility $12.94\%$
$x_1 = 66.7\%$, volatility $15.33\%$
$x_1 = 15.1\%$, volatility $7.37\%$
$x_1 = 33.3\%$, volatility $8.28\%$
Explanation. Minimum-variance share without the return constraint: $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 15.1\%$, with return $8.9\%$. It is below $\bar r$, so the constraint binds: $x_1\mu_1 + (1 - x_1)\mu_2 = \bar r$ gives $x_1 = 66.7\%$. Volatility $12.94\%$.
7. Pricing and revenue management (2)
Example 1 · nlpm-g-pricing-ottimo · level facile · notes
Pricing model: choose the price $p$ and the quantity sold $q$ to maximize the profit $(p - c)\,q$ subject to $q \le d(p) = 1100 - 5p$ (demand) and $q \le k$ (capacity), with marginal cost $c = 66$ € and $k = 405$. What are the optimal price $p^*$ and the optimal profit?
$p^* = 143$ €, profit 29645 €
$p^* = 110$ €, profit 17820 €
$p^* = 139$ €, profit 29565 €
$p^* = 187$ €, profit 19965 €
Explanation. Without capacity $p^\circ = (a/b + c)/2 = 143$ with $q^\circ = 385 \le k$: the capacity constraint is inactive and $p^* = p^\circ$.
Example 2 · nlpm-g-pricing-ottimo · level facile · notes
Pricing model: choose the price $p$ and the quantity sold $q$ to maximize the profit $(p - c)\,q$ subject to $q \le d(p) = 1080 - 4p$ (demand) and $q \le k$ (capacity), with marginal cost $c = 32$ € and $k = 416$. What are the optimal price $p^*$ and the optimal profit?
$p^* = 166$ €, profit 55744 €
$p^* = 151$ €, profit 49504 €
$p^* = 135$ €, profit 42848 €
$p^* = 150$ €, profit 49088 €
Explanation. Without capacity $p^\circ = (a/b + c)/2 = 151$ with $q^\circ = 476 > k$: capacity bites, and the price that sells exactly $k$ is $p^* = (a - k)/b = 166$.
Example 1 · nlpm-g-pricing-posto · level media · notes
Pricing model: choose the price $p$ and the quantity sold $q$ to maximize $(p - c)\,q$ subject to $q \le d(p) = 1100 - 5p$ and $q \le k$, with $c = 66$ € and $k = 235$; the capacity constraint is active at the optimum. Let $\Pi(k)$ be the optimal profit as a function of the capacity. What is $d\Pi/dk$, the value of one more unit of capacity?
126 €
107 €
13 €
60 €
Explanation. With $p^* = (a - k)/b = 173$ the profit is $(p^* - c)\,k$, and $dp^*/dk = -1/b$: $d\Pi/dk = (p^* - c) - k/b = 60$. The full margin $p^* - c$ forgets that, to fill the extra seat, the price falls for everybody.
Example 2 · nlpm-g-pricing-posto · level media · notes
Pricing model: choose the price $p$ and the quantity sold $q$ to maximize $(p - c)\,q$ subject to $q \le d(p) = 1080 - 4p$ and $q \le k$, with $c = 32$ € and $k = 456$; the capacity constraint is active at the optimum. Let $\Pi(k)$ be the optimal profit as a function of the capacity. What is $d\Pi/dk$, the value of one more unit of capacity?
10 €
42 €
-104 €
124 €
Explanation. With $p^* = (a - k)/b = 156$ the profit is $(p^* - c)\,k$, and $dp^*/dk = -1/b$: $d\Pi/dk = (p^* - c) - k/b = 10$. The full margin $p^* - c$ forgets that, to fill the extra seat, the price falls for everybody.
8. Advertising budget allocation (2)
Example 1 · nlpm-g-budget-due-canali · level media · notes
Advertising budget: the spends $x_1, x_2 \ge 0$ (thousands of €) on two channels maximize $r_1(x_1) + r_2(x_2)$ with $r_1(x) = 160\log(1 + 0.25x)$, $r_2(x) = 180\log(1 + 0.25x)$ (natural logarithm), subject to $x_1 + x_2 \le b = 20$, no caps. What are the optimal allocation and the multiplier $\lambda$ of the budget constraint (extra response per extra thousand €)?
Explanation. At the optimum the marginal returns are equal: $40/(1 + 0.25x_1) = 45/(1 + 0.25x_2)$ with $x_1 + x_2 = 20$, so $x_1 = 9.2$; $\lambda$ is the common marginal return, $12.14$. Splitting in proportion to $a_i k_i$ ignores the saturation.
Example 2 · nlpm-g-budget-due-canali · level media · notes
Advertising budget: the spends $x_1, x_2 \ge 0$ (thousands of €) on two channels maximize $r_1(x_1) + r_2(x_2)$ with $r_1(x) = 70\log(1 + 0.2x)$, $r_2(x) = 30\log(1 + 0.5x)$ (natural logarithm), subject to $x_1 + x_2 \le b = 50$, no caps. What are the optimal allocation and the multiplier $\lambda$ of the budget constraint (extra response per extra thousand €)?
Explanation. At the optimum the marginal returns are equal: $14/(1 + 0.2x_1) = 15/(1 + 0.5x_2)$ with $x_1 + x_2 = 50$, so $x_1 = 34.9$; $\lambda$ is the common marginal return, $1.75$. Splitting in proportion to $a_i k_i$ ignores the saturation.
Example 1 · nlpm-g-budget-tetto · level complessa · notes
Advertising budget: the spends $x_1, x_2 \ge 0$ (thousands of €) maximize $r_1(x_1) + r_2(x_2)$, with $r_1(x) = 160\log(1 + 0.25x)$ and $r_2(x) = 180\log(1 + 0.25x)$ (natural logarithm), subject to $x_1 + x_2 \le b = 30$ (multiplier $\lambda$) and the cap $x_1 \le u_1 = 10$ (multiplier $\mu_1$). KKT: $r_i'(\tilde x_i) = \lambda + \mu_i$, with $\mu_2 = 0$. What are the optimal allocation, $\lambda$ and $\mu_1$?
Explanation. Without the cap the marginal returns would be equal at $x_1 = 13.88 > u_1$: the cap binds, $\tilde x_1 = 10$ and $\tilde x_2 = 20$. Channel 2 is interior, so $\lambda = r_2'(20) = 45/(1 + 0.25\cdot 20) = 7.5$; channel 1 gives $\mu_1 = r_1'(10) - \lambda = 11.43 - 7.5 = 3.93$, the value of one more thousand € of cap.
Example 2 · nlpm-g-budget-tetto · level complessa · notes
Advertising budget: the spends $x_1, x_2 \ge 0$ (thousands of €) maximize $r_1(x_1) + r_2(x_2)$, with $r_1(x) = 70\log(1 + 0.2x)$ and $r_2(x) = 30\log(1 + 0.5x)$ (natural logarithm), subject to $x_1 + x_2 \le b = 60$ (multiplier $\lambda$) and the cap $x_1 \le u_1 = 34$ (multiplier $\mu_1$). KKT: $r_i'(\tilde x_i) = \lambda + \mu_i$, with $\mu_2 = 0$. What are the optimal allocation, $\lambda$ and $\mu_1$?
Explanation. Without the cap the marginal returns would be equal at $x_1 = 41.9 > u_1$: the cap binds, $\tilde x_1 = 34$ and $\tilde x_2 = 26$. Channel 2 is interior, so $\lambda = r_2'(26) = 15/(1 + 0.5\cdot 26) = 1.07$; channel 1 gives $\mu_1 = r_1'(34) - \lambda = 1.79 - 1.07 = 0.72$, the value of one more thousand € of cap.
9. Continuous location of a service (2)
Example 1 · nlpm-g-loc-weber-1d · level facile · notes
Location on a straight road: customers at positions $a_i$ with weights $w_i$: km 2 (weight 4), km 12 (weight 5), km 13 (weight 1), km 16 (weight 5), km 18 (weight 1). A facility at position $x$ (km) minimizes the weighted total distance $\sum_i w_i |x - a_i|$ (Weber model on a line). Where is the optimal position $x^*$?
$x^* = 13$ km
$x^* = 10$ km
$x^* = 12$ km
$x^* = 11.2$ km
Explanation. In one dimension Weber is the weighted median: the point that leaves at least half of the total weight ($16/2$) on each side, here km $12$. The centroid ($11.2$) is the optimum of the squared distances, the midpoint of the extremes ($10$) that of the minimax.
Example 2 · nlpm-g-loc-weber-1d · level facile · notes
Location on a straight road: customers at positions $a_i$ with weights $w_i$: km 4 (weight 1), km 9 (weight 3), km 12 (weight 5). A facility at position $x$ (km) minimizes the weighted total distance $\sum_i w_i |x - a_i|$ (Weber model on a line). Where is the optimal position $x^*$?
$x^* = 10.1$ km
$x^* = 9$ km
$x^* = 12$ km
$x^* = 8$ km
Explanation. In one dimension Weber is the weighted median: the point that leaves at least half of the total weight ($9/2$) on each side, here km $12$. The centroid ($10.1$) is the optimum of the squared distances, the midpoint of the extremes ($8$) that of the minimax.
Example 1 · nlpm-g-loc-minimax-2d · level media · notes
Minimax location in the plane: three districts at $(6; 6)$, $(8; 9)$, $(1; 8)$ (km). The facility at $(x, y)$ minimizes $z$, the largest Euclidean distance from it to a district (no weights). What are the optimal point $(x^*; y^*)$ and the optimal value $z^*$?
$(x^*; y^*) = (4.5; 8.5)$, $z^* = 3.54$
$(x^*; y^*) = (4.5; 7.5)$, $z^* = 3.81$
$(x^*; y^*) = (5; 7.67)$, $z^* = 4.01$
$(x^*; y^*) = (4.39; 9.24)$, $z^* = 3.61$
Explanation. The optimum is the centre of the smallest circle containing the three points. The triangle is obtuse: the circle having the longest side as diameter already contains the third point, so the centre is the midpoint of that side and $z^*$ is half its length, $3.54$. The circle through all three points would be larger.
Example 2 · nlpm-g-loc-minimax-2d · level media · notes
Minimax location in the plane: three districts at $(4; 9)$, $(3; 1)$, $(8; 7)$ (km). The facility at $(x, y)$ minimizes $z$, the largest Euclidean distance from it to a district (no weights). What are the optimal point $(x^*; y^*)$ and the optimal value $z^*$?
$(x^*; y^*) = (4.44; 4.88)$, $z^* = 4.14$
$(x^*; y^*) = (5; 5.67)$, $z^* = 5.08$
$(x^*; y^*) = (3.5; 5)$, $z^* = 4.03$
$(x^*; y^*) = (5.5; 5)$, $z^* = 4.72$
Explanation. The optimum is the centre of the smallest circle containing the three points. The triangle is acute: no circle built on one side contains the third point, so the optimum is the circumcentre, equidistant from the three districts, with $z^* = 4.14$. The centroid ignores the extreme districts.
10. Electric vehicle charging with a smooth profile (1)
Example 1 · nlpm-g-evq-due-ore · level media · notes
EV charging with a smooth profile, one vehicle and two hours: it needs $e = 20$ kWh ($\eta = 1$), prices $0.1$ and $0.2$ €/kWh, power limit large enough, zero base load, objective $\pi_1 x_1 + \pi_2 x_2 + \gamma (x_2 - x_1)^2$ with $\gamma = 0.05$ and constraint $x_1 + x_2 \ge 20$. Both hours are used at the optimum. What are $\tilde x_1$ and the multiplier $\lambda$ of the energy constraint?
$\tilde x_1 = 10.5$, $\lambda = 0.15$
$\tilde x_1 = 10.25$, $\lambda = 0.1$
$\tilde x_1 = 20$, $\lambda = 0.1$
$\tilde x_1 = 10.25$, $\lambda = 0.15$
Explanation. With $x_1 = 10 + d$ the objective is linear in $d$ with slope $-0.1$ plus $4\gamma d^2$: $d = (\pi_2 - \pi_1)/(8\gamma)$, so $\tilde x_1 = 10.25$. Stationarity gives $\pi_1 - 2\gamma(x_2 - x_1) = \lambda = \pi_2 + 2\gamma(x_2 - x_1)$, hence $\lambda = (\pi_1 + \pi_2)/2 = 0.15$: the marginal kWh costs the average price.
Example 2 · nlpm-g-evq-due-ore · level media · notes
EV charging with a smooth profile, one vehicle and two hours: it needs $e = 16$ kWh ($\eta = 1$), prices $0.12$ and $0.18$ €/kWh, power limit large enough, zero base load, objective $\pi_1 x_1 + \pi_2 x_2 + \gamma (x_2 - x_1)^2$ with $\gamma = 0.005$ and constraint $x_1 + x_2 \ge 16$. Both hours are used at the optimum. What are $\tilde x_1$ and the multiplier $\lambda$ of the energy constraint?
$\tilde x_1 = 9.5$, $\lambda = 0.15$
$\tilde x_1 = 11$, $\lambda = 0.15$
$\tilde x_1 = 16$, $\lambda = 0.12$
$\tilde x_1 = 9.5$, $\lambda = 0.12$
Explanation. With $x_1 = 8 + d$ the objective is linear in $d$ with slope $-0.06$ plus $4\gamma d^2$: $d = (\pi_2 - \pi_1)/(8\gamma)$, so $\tilde x_1 = 9.5$. Stationarity gives $\pi_1 - 2\gamma(x_2 - x_1) = \lambda = \pi_2 + 2\gamma(x_2 - x_1)$, hence $\lambda = (\pi_1 + \pi_2)/2 = 0.15$: the marginal kWh costs the average price.
11. Service capacity and waiting times (4)
Example 1 · nlpm-g-code-ottimo · level facile · notes
Capacity of an M/M/1 queue: arrival rate $\lambda = 25$ customers/hour; the service rate $\mu > \lambda$ (capacity) minimizes $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$, where $c = 4$ €/h per unit of $\mu$, $h = 4$ € per hour a customer spends in the system and $\lambda/(\mu - \lambda)$ is the mean number of customers in the system. What are $\mu^*$ and $C(\mu^*)$?
Example 2 · nlpm-g-code-ottimo · level facile · notes
Capacity of an M/M/1 queue: arrival rate $\lambda = 27$ customers/hour; the service rate $\mu > \lambda$ (capacity) minimizes $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$, where $c = 3$ €/h per unit of $\mu$, $h = 1$ € per hour a customer spends in the system and $\lambda/(\mu - \lambda)$ is the mean number of customers in the system. What are $\mu^*$ and $C(\mu^*)$?
Example 1 · nlpm-g-code-misure · level facile · notes
M/M/1 queue (Poisson arrivals, exponential service, one server) with arrival rate $\lambda = 18$ per hour and service rate $\mu = 24$ per hour. What are the utilization $\rho$, the mean time in the system $w$ and the mean number of customers in the system $l$?
$\rho = 75\%$, $w = 2.5$ min, $l = 0.75$
$\rho = 75\%$, $w = 10$ min, $l = 3$
$\rho = 75\%$, $w = 180$ min, $l = 0.17$
$\rho = 75\%$, $w = 10$ min, $l = 4$
Explanation. $\rho = \lambda/\mu$, $w = 1/(\mu - \lambda)$ hours $= 10$ minutes and, by Little's law, $l = \lambda\, w = \lambda/(\mu - \lambda) = 3$. $1/\mu$ is only the mean service time.
Example 2 · nlpm-g-code-misure · level facile · notes
M/M/1 queue (Poisson arrivals, exponential service, one server) with arrival rate $\lambda = 13$ per hour and service rate $\mu = 22$ per hour. What are the utilization $\rho$, the mean time in the system $w$ and the mean number of customers in the system $l$?
$\rho = 59.1\%$, $w = 6.7$ min, $l = 2.44$
$\rho = 59.1\%$, $w = 86.7$ min, $l = 0.11$
$\rho = 59.1\%$, $w = 6.7$ min, $l = 1.44$
$\rho = 59.1\%$, $w = 2.7$ min, $l = 0.59$
Explanation. $\rho = \lambda/\mu$, $w = 1/(\mu - \lambda)$ hours $= 6.7$ minutes and, by Little's law, $l = \lambda\, w = \lambda/(\mu - \lambda) = 1.44$. $1/\mu$ is only the mean service time.
Example 1 · nlpm-g-code-promessa · level media · notes
Capacity of an M/M/1 queue: arrival rate $\lambda = 16$ customers/hour; the service rate $\mu > \lambda$ minimizes $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$ €/h, with $c = 2$ and $h = 8$; the mean time in the system is $w = 1/(\mu - \lambda)$ hours. Marketing promises $w \le w_{\max} = 6$ minutes. What are the optimal capacity under the promise and its cost $C$?
$\mu = 26$, $C = 64.8$ €/h
$\mu = 26$, $C = 52.8$ €/h
$\mu = 24$, $C = 64$ €/h
$\mu = 22$, $C = 65.33$ €/h
Explanation. Without the promise $\tilde\mu = \lambda + \sqrt{h\lambda/c} = 24$. The promise requires $\mu \ge \lambda + 1/w_{\max} = 16 + 60/6 = 26$ (with $w_{\max}$ in hours), tighter than $\tilde\mu$: since $C$ is convex, the optimum is on the constraint, with $C = 2\cdot 26 + 8\cdot 16\cdot 6/60 = 64.8$ €/h.
Example 2 · nlpm-g-code-promessa · level media · notes
Capacity of an M/M/1 queue: arrival rate $\lambda = 27$ customers/hour; the service rate $\mu > \lambda$ minimizes $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$ €/h, with $c = 3$ and $h = 1$; the mean time in the system is $w = 1/(\mu - \lambda)$ hours. Marketing promises $w \le w_{\max} = 2$ minutes. What are the optimal capacity under the promise and its cost $C$?
$\mu = 30$, $C = 99$ €/h
$\mu = 29$, $C = 100.5$ €/h
$\mu = 57$, $C = 171.03$ €/h
$\mu = 57$, $C = 171.9$ €/h
Explanation. Without the promise $\tilde\mu = \lambda + \sqrt{h\lambda/c} = 30$. The promise requires $\mu \ge \lambda + 1/w_{\max} = 27 + 60/2 = 57$ (with $w_{\max}$ in hours), tighter than $\tilde\mu$: since $C$ is convex, the optimum is on the constraint, with $C = 3\cdot 57 + 1\cdot 27\cdot 2/60 = 171.9$ €/h.
Example 1 · nlpm-g-code-robusto · level complessa · notes
M/M/1 capacity model: choose the capacity $\mu$ to minimize $C(\mu, \lambda) = c\mu + h\lambda/(\mu - \lambda)$, with $c = 4$ € per unit of capacity and $h = 3$ €/h per customer in the system. The arrival rate is uncertain, $\lambda \in [31, 42]$ per hour, nominal value $36.5$. One sizes $\mu$ to minimize the worst-case cost over the interval. What are the robust $\mu$, its worst-case cost and its premium over the nominal optimal cost $C(\tilde\mu(36.5), 36.5)$?
Explanation. For fixed $\mu$ the cost grows with $\lambda$, so the worst case is $\lambda = 42$: $\mu_{\rm rob} = 42 + \sqrt{h\cdot 42/c} = 47.61$, worst-case cost $212.9$. The nominal optimum costs $187.86$: the insurance premium is $13.3\%$. Sizing on the nominal $\tilde\mu = 41.73 < 42$ would make the queue unstable at the top of the interval.
Example 2 · nlpm-g-code-robusto · level complessa · notes
M/M/1 capacity model: choose the capacity $\mu$ to minimize $C(\mu, \lambda) = c\mu + h\lambda/(\mu - \lambda)$, with $c = 2$ € per unit of capacity and $h = 1$ €/h per customer in the system. The arrival rate is uncertain, $\lambda \in [28, 42]$ per hour, nominal value $35$. One sizes $\mu$ to minimize the worst-case cost over the interval. What are the robust $\mu$, its worst-case cost and its premium over the nominal optimal cost $C(\tilde\mu(35), 35)$?
Explanation. For fixed $\mu$ the cost grows with $\lambda$, so the worst case is $\lambda = 42$: $\mu_{\rm rob} = 42 + \sqrt{h\cdot 42/c} = 46.58$, worst-case cost $102.33$. The nominal optimum costs $86.73$: the insurance premium is $18\%$. Sizing on the nominal $\tilde\mu = 39.18 < 42$ would make the queue unstable at the top of the interval.
12. Support Vector Machine (7)
Example 1 · nlpm-g-svm-due-punti · level facile · notes
Hard-margin SVM: $\min \tfrac12\|\mathbf w\|^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$, with $\mathbf w \in \mathbb R^2$ and $b$ free. Two observations: $\mathbf x_1 = (0; 0)$ with label $y_1 = -1$ and $\mathbf x_2 = (2; 2)$ with label $y_2 = +1$. What are the optimal $\tilde{\mathbf w}$ and the margin $2/\|\tilde{\mathbf w}\|$?
$\mathbf w = (0.25; 0.25)$, margin $5.657$
$\mathbf w = (0.5; 0.5)$, margin $2.828$
$\mathbf w = (2; 2)$, margin $0.707$
$\mathbf w = (0.5; 0.5)$, margin $1.414$
Explanation. Both constraints are active: $b = -1$ and $\mathbf w'\mathbf x_2 + b = 1$; the minimum-norm $\mathbf w$ is parallel to $\mathbf x_2$, $\mathbf w = 2\mathbf x_2/\|\mathbf x_2\|^2$. The margin $2/\|\mathbf w\| = \|\mathbf x_2\| = 2.828$ is the distance between the two points.
Example 2 · nlpm-g-svm-due-punti · level facile · notes
Hard-margin SVM: $\min \tfrac12\|\mathbf w\|^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$, with $\mathbf w \in \mathbb R^2$ and $b$ free. Two observations: $\mathbf x_1 = (0; 0)$ with label $y_1 = -1$ and $\mathbf x_2 = (1; 4)$ with label $y_2 = +1$. What are the optimal $\tilde{\mathbf w}$ and the margin $2/\|\tilde{\mathbf w}\|$?
$\mathbf w = (0.118; 0.471)$, margin $2.062$
$\mathbf w = (1; 4)$, margin $0.485$
$\mathbf w = (0.118; 0.471)$, margin $4.123$
$\mathbf w = (0.059; 0.235)$, margin $8.246$
Explanation. Both constraints are active: $b = -1$ and $\mathbf w'\mathbf x_2 + b = 1$; the minimum-norm $\mathbf w$ is parallel to $\mathbf x_2$, $\mathbf w = 2\mathbf x_2/\|\mathbf x_2\|^2$. The margin $2/\|\mathbf w\| = \|\mathbf x_2\| = 4.123$ is the distance between the two points.
Soft-margin SVM: objective $\tfrac12\|\mathbf w\|^2 + C\sum_i \xi_i$, where for given $\mathbf w, b$ the optimal slacks are $\xi_i = \max\{0,\ 1 - y_i(\mathbf w'\mathbf x_i + b)\}$. Candidate classifier $\mathbf w = (0; -2)$, $b = 0$, with $C = 1$; observations $\mathbf x_1 = (1; -2)$, $y_1 = +1$; $\mathbf x_2 = (-1; 2)$, $y_2 = -1$; $\mathbf x_3 = (-1; -2)$, $y_3 = -1$; $\mathbf x_4 = (0; 1)$, $y_4 = +1$. What are $\sum_i \xi_i$ and the objective value?
$\sum_i \xi_i = 6$, objective $8$
$\sum_i \xi_i = 8$, objective $12$
$\sum_i \xi_i = 8$, objective $10$
$\sum_i \xi_i = 2$, objective $4$
Explanation. Compute $y_i(\mathbf w'\mathbf x_i + b)$ for each observation: the points with value $\ge 1$ are beyond the margin and pay nothing, the others pay $1 - y_i(\mathbf w'\mathbf x_i + b)$. The slacks sum to $8$ and the objective is $\tfrac12\cdot 4 + 1\cdot 8 = 10$. Dropping the $\max$ lets well-classified points subtract.
Soft-margin SVM: objective $\tfrac12\|\mathbf w\|^2 + C\sum_i \xi_i$, where for given $\mathbf w, b$ the optimal slacks are $\xi_i = \max\{0,\ 1 - y_i(\mathbf w'\mathbf x_i + b)\}$. Candidate classifier $\mathbf w = (-1; 0)$, $b = 2$, with $C = 2$; observations $\mathbf x_1 = (-2; 1)$, $y_1 = -1$; $\mathbf x_2 = (-2; -2)$, $y_2 = +1$; $\mathbf x_3 = (2; 1)$, $y_3 = -1$; $\mathbf x_4 = (2; -1)$, $y_4 = -1$. What are $\sum_i \xi_i$ and the objective value?
$\sum_i \xi_i = 7$, objective $14.5$
$\sum_i \xi_i = 4$, objective $8.5$
$\sum_i \xi_i = 7$, objective $15$
$\sum_i \xi_i = 5$, objective $10.5$
Explanation. Compute $y_i(\mathbf w'\mathbf x_i + b)$ for each observation: the points with value $\ge 1$ are beyond the margin and pay nothing, the others pay $1 - y_i(\mathbf w'\mathbf x_i + b)$. The slacks sum to $7$ and the objective is $\tfrac12\cdot 1 + 2\cdot 7 = 14.5$. Dropping the $\max$ lets well-classified points subtract.
Example 1 · nlpm-g-svm-margine · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. A trained SVM has $\mathbf w = (1; 1)$ and $b = 5$; its margin lines are $\mathbf w'\mathbf x + b = \pm 1$. What are the margin (the distance between the two margin lines) and the distance of the point $\mathbf x_0 = (3; -4)$ from the hyperplane?
margin $1.414$, distance $2.828$
margin $1.414$, distance $4$
margin $0.707$, distance $2.828$
margin $1$, distance $2.828$
Explanation. $\|\mathbf w\| = \sqrt{2} = 1.414$: the margin is $2/\|\mathbf w\| = 1.414$; the distance of $\mathbf x_0$ is $|\mathbf w'\mathbf x_0 + b|/\|\mathbf w\| = 4/1.414 = 2.828$. Forgetting to divide by $\|\mathbf w\|$ is the typical mistake.
Example 2 · nlpm-g-svm-margine · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. A trained SVM has $\mathbf w = (-2; 4)$ and $b = -3$; its margin lines are $\mathbf w'\mathbf x + b = \pm 1$. What are the margin (the distance between the two margin lines) and the distance of the point $\mathbf x_0 = (-4; -1)$ from the hyperplane?
margin $0.447$, distance $0.224$
margin $0.224$, distance $0.224$
margin $0.447$, distance $1$
margin $0.1$, distance $0.224$
Explanation. $\|\mathbf w\| = \sqrt{20} = 4.472$: the margin is $2/\|\mathbf w\| = 0.447$; the distance of $\mathbf x_0$ is $|\mathbf w'\mathbf x_0 + b|/\|\mathbf w\| = 1/4.472 = 0.224$. Forgetting to divide by $\|\mathbf w\|$ is the typical mistake.
Example 1 · nlpm-g-svm-duale-w · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. In the dual of the soft margin ($\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$, $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$) only three points have $\tilde\alpha_i > 0$: $\mathbf x_1 = (1; 1)$, $y_1 = +1$, $\tilde\alpha_1 = 1.5$; $\mathbf x_2 = (3; 3)$, $y_2 = +1$, $\tilde\alpha_2 = 1.5$; $\mathbf x_3 = (-3; 3)$, $y_3 = -1$, $\tilde\alpha_3 = 3$. What is the optimal $\tilde{\mathbf w}$ of the primal?
$\tilde{\mathbf w} = (-15; 3)$
$\tilde{\mathbf w} = (-3; 15)$
$\tilde{\mathbf w} = (15; -3)$
$\tilde{\mathbf w} = (6; 6)$
Explanation. Primal–dual relation: $\tilde{\mathbf w} = \sum_i\tilde\alpha_iy_i\mathbf x_i$, a sum over the support vectors only, with the sign of the labels: $1.5\,\mathbf x_1 + 1.5\,\mathbf x_2 - 3\,\mathbf x_3 = (15; -3)$. Forgetting the labels $y_i$ is the typical mistake.
Example 2 · nlpm-g-svm-duale-w · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. In the dual of the soft margin ($\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$, $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$) only three points have $\tilde\alpha_i > 0$: $\mathbf x_1 = (4; 3)$, $y_1 = +1$, $\tilde\alpha_1 = 2$; $\mathbf x_2 = (2; 3)$, $y_2 = +1$, $\tilde\alpha_2 = 2$; $\mathbf x_3 = (3; -2)$, $y_3 = -1$, $\tilde\alpha_3 = 4$. What is the optimal $\tilde{\mathbf w}$ of the primal?
$\tilde{\mathbf w} = (24; 4)$
$\tilde{\mathbf w} = (0; 20)$
$\tilde{\mathbf w} = (12; 12)$
$\tilde{\mathbf w} = (0; -20)$
Explanation. Primal–dual relation: $\tilde{\mathbf w} = \sum_i\tilde\alpha_iy_i\mathbf x_i$, a sum over the support vectors only, with the sign of the labels: $2\,\mathbf x_1 + 2\,\mathbf x_2 - 4\,\mathbf x_3 = (0; 20)$. Forgetting the labels $y_i$ is the typical mistake.
Example 1 · nlpm-g-svm-rbf-valore · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. With the RBF (Gaussian) kernel $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$ and $\gamma = 0.5$, what is $K(\mathbf x, \mathbf z)$ for $\mathbf x = (4; 2)$ and $\mathbf z = (3; 1)$?
$K = 0.018$
$K = 0.607$
$K = 0.368$
$K = 0.493$
Explanation. $\|\mathbf x - \mathbf z\|^2 = 2$ (the squared distance, not the distance), so $K = e^{-0.5\cdot 2} = 0.368$. Points far apart give $K$ close to 0, coincident points $K = 1$; a larger $\gamma$ makes the kernel more local.
Example 2 · nlpm-g-svm-rbf-valore · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. With the RBF (Gaussian) kernel $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$ and $\gamma = 0.5$, what is $K(\mathbf x, \mathbf z)$ for $\mathbf x = (4; 3)$ and $\mathbf z = (3; 4)$?
$K = 0.368$
$K = 0.493$
$K = 0.607$
$K = 0.018$
Explanation. $\|\mathbf x - \mathbf z\|^2 = 2$ (the squared distance, not the distance), so $K = e^{-0.5\cdot 2} = 0.368$. Points far apart give $K$ close to 0, coincident points $K = 1$; a larger $\gamma$ makes the kernel more local.
Example 1 · nlpm-g-svr-tubo · level facile · notes
Support Vector Regression: errors within a tube $|y_i - \hat y_i| \le \varepsilon$ cost nothing, those outside pay $|y_i - \hat y_i| - \varepsilon$ (the slacks $\xi_i$, $\xi_i^*$). The estimated line is $\hat y = -8x + 210$, with $\varepsilon = 7$; the observations $(x_i; y_i)$ are (2; 205), (9; 124), (10; 141), (11; 113), (13; 99). How many points fall outside the tube, and what is their total penalty $\sum_i(\xi_i + \xi_i^*)$?
$4$ points outside, penalty $45$
$1$ points outside, penalty $17$
$1$ points outside, penalty $45$
$4$ points outside, penalty $17$
Explanation. Residuals $y_i - \hat y_i$: $11$, $-14$, $11$, $-9$, $-7$. Those with $|r_i| > 7$ are 4; each pays only the part beyond the tube, $|r_i| - 7$, for a total of $17$. Paying the whole residual gives $45$.
Example 2 · nlpm-g-svr-tubo · level facile · notes
Support Vector Regression: errors within a tube $|y_i - \hat y_i| \le \varepsilon$ cost nothing, those outside pay $|y_i - \hat y_i| - \varepsilon$ (the slacks $\xi_i$, $\xi_i^*$). The estimated line is $\hat y = -6x + 240$, with $\varepsilon = 4$; the observations $(x_i; y_i)$ are (1; 241), (7; 202), (10; 183), (13; 168), (14; 161). How many points fall outside the tube, and what is their total penalty $\sum_i(\xi_i + \xi_i^*)$?
$2$ points outside, penalty $18$
$3$ points outside, penalty $18$
$2$ points outside, penalty $6$
$3$ points outside, penalty $6$
Explanation. Residuals $y_i - \hat y_i$: $7$, $4$, $3$, $6$, $5$. Those with $|r_i| > 4$ are 3; each pays only the part beyond the tube, $|r_i| - 4$, for a total of $6$. Paying the whole residual gives $18$.
Example 1 · nlpm-g-svm-duale-b · level media · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. A soft-margin SVM (dual multipliers $0 \le \alpha_i \le C$) gives $\tilde{\mathbf w} = (0; 1)$. The point $\mathbf x_k = (2; 3)$ with label $y_k = -1$ has $0 < \tilde\alpha_k < C$. What are the intercept $\tilde b$ and the score $f(\mathbf x_0) = \tilde{\mathbf w}'\mathbf x_0 + \tilde b$ of $\mathbf x_0 = (2; 1)$?
$\tilde b = -3$, $f(\mathbf x_0) = -2$
$\tilde b = -4$, $f(\mathbf x_0) = -3$
$\tilde b = 4$, $f(\mathbf x_0) = 5$
$\tilde b = -2$, $f(\mathbf x_0) = -1$
Explanation. $0 < \tilde\alpha_k < C$ means $\mathbf x_k$ lies exactly on its margin line: $y_k(\tilde{\mathbf w}'\mathbf x_k + b) = 1$, so $\tilde b = y_k - \tilde{\mathbf w}'\mathbf x_k = -4$ (since $1/y_k = y_k$). Then $f(\mathbf x_0) = -3$: $\mathbf x_0$ is assigned to class $-1$.
Example 2 · nlpm-g-svm-duale-b · level media · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. A soft-margin SVM (dual multipliers $0 \le \alpha_i \le C$) gives $\tilde{\mathbf w} = (-1; 2)$. The point $\mathbf x_k = (-1; -3)$ with label $y_k = -1$ has $0 < \tilde\alpha_k < C$. What are the intercept $\tilde b$ and the score $f(\mathbf x_0) = \tilde{\mathbf w}'\mathbf x_0 + \tilde b$ of $\mathbf x_0 = (3; 2)$?
$\tilde b = 4$, $f(\mathbf x_0) = 5$
$\tilde b = 5$, $f(\mathbf x_0) = 6$
$\tilde b = -4$, $f(\mathbf x_0) = -3$
$\tilde b = 6$, $f(\mathbf x_0) = 7$
Explanation. $0 < \tilde\alpha_k < C$ means $\mathbf x_k$ lies exactly on its margin line: $y_k(\tilde{\mathbf w}'\mathbf x_k + b) = 1$, so $\tilde b = y_k - \tilde{\mathbf w}'\mathbf x_k = 4$ (since $1/y_k = y_k$). Then $f(\mathbf x_0) = 5$: $\mathbf x_0$ is assigned to class $+1$.
13. Least-squares regression (1)
Example 1 · nlpm-g-ls-media · level facile · notes
Least squares without features: $\min \sum_i r_i^2$ subject to $b + r_i = y_i$, with $b$ and $r_i$ free, on the five observations $y = (145, 130, 130, 151, 81)$. What are the optimal intercept $\tilde b$ and the multiplier $\tilde\pi$ of the constraint of the largest observation ($y = 151$)?
$\tilde b = 130$, $\tilde\pi = 42$
$\tilde b = 127.4$, $\tilde\pi = 23.6$
$\tilde b = 127.4$, $\tilde\pi = 47.2$
$\tilde b = 130$, $\tilde\pi = 47.2$
Explanation. Stationarity in $b$ gives $\sum_i r_i = 0$: $\tilde b$ is the mean, $127.4$. Stationarity in $r_i$ gives $\pi_i = 2 r_i$: for $y = 151$ the residual is $23.6$ and $\tilde\pi = 47.2$. The median $130$ would be the optimum of absolute deviations.
Example 2 · nlpm-g-ls-media · level facile · notes
Least squares without features: $\min \sum_i r_i^2$ subject to $b + r_i = y_i$, with $b$ and $r_i$ free, on the five observations $y = (110, 148, 105, 87, 112)$. What are the optimal intercept $\tilde b$ and the multiplier $\tilde\pi$ of the constraint of the largest observation ($y = 148$)?
$\tilde b = 112.4$, $\tilde\pi = 71.2$
$\tilde b = 110$, $\tilde\pi = 76$
$\tilde b = 112.4$, $\tilde\pi = 35.6$
$\tilde b = 110$, $\tilde\pi = 71.2$
Explanation. Stationarity in $b$ gives $\sum_i r_i = 0$: $\tilde b$ is the mean, $112.4$. Stationarity in $r_i$ gives $\pi_i = 2 r_i$: for $y = 148$ the residual is $35.6$ and $\tilde\pi = 71.2$. The median $110$ would be the optimum of absolute deviations.