How do you call a linear programming problem when the solution should be "constrained" to a norm?

Question

(apologies for the n00b question)

Let's say we have a vector of length $n$, with to-be-determined values: $a_1, a_2, ...,a_n$.

And we have information that partial sums of these elements are equal to something, say: $$ a_1 + a_2 + ... + a_{k_1} = A_{1} \\ a_{k_1+1} + a_{k_1+2} + ... + a_n = B_1 \\ a_1 + a_2 + ... + a_{k_2} = A_2 \\ a_{k_2+1} + a_{k_2+2} + ... + a_n = B_2 \\ ...\\ a_1 + a_2 + ... + a_{k_m} = A_m \\ a_{k_m+1} + a_{k_m+2} + ... + a_n = B_m \\ $$

Where $m<<n$: so we have much fewer such $m$ equations/constraints than the $n$ unknown values $a_i$.

If we want to know which combination of $a_i$ values can solve these equations, there are probably infinite many such combinations (or 0). So I'd like to add two constraints to this:

1. $a_i>0$ for any i.
2. I want the solution with $a_i$ values that are as "similar" to each other as possible. For example, keeping $\sum_{i=1}^n (a_i - \bar a)^2$ as small as possible (L2 norm). Where $\bar a = \sum \frac{a_i}{n}$.

How is such optimization problem called? (would also love to know how to solve it, but I assume that once I have the name, I can find solvers).

Answer 1

If you are willing to replace $a_i > 0$ by $a_i \ge 0$, then this becomes a quadratic program. Indeed, it can be formulated as \begin{align*} \text{Minimize}\quad & \frac12 a^\top Q a + q^\top a, \\ \text{such that} \quad & C a = d, \\ & a \ge 0. \end{align*} Here, $Q$ and $C$ are matrices of appropriate size and $q$ and $d$ are vectors (these objects come from your data). Moreover, the matrix $Q$ is positive semidefinite.

[If you insist on keeping $a_i > 0$, the corresponding problem might fail to have solutions.]