I'm wondering if anything is known about minimizing convex, not necessarily linear functions subject to "simple" matrix equalities. To be precise, consider the following example:

$min \Sigma x_i ln x_i$ such that $Ax=b$

Where $x$ is the (positive) vector variable, $b$ is a given real vector, and $A$ is a real matrix.

At one extreme, if $A$ has a single row, the convexity of $x_i ln x_i$ means that this problem is very easy to solve. One can introduce a Lagrangian $\lambda$ so that the problem becomes $min \Sigma x_i ln x_i + \lambda Ax$. Then, one can use e.g. bisection to compute $\lambda$ such that $Ax=b$. If we suppose that the number of bisection steps required is independent of the length of the vector $x$, then solving this minimization problem takes O(n) time for vectors of length n.

At the other extreme, if $A$ is an arbitrary real matrix, the minimization problem above is at least as difficult as solving the matrix equation itself, since it contains that problem. Solving the matrix equation is doable in polynomial time (e.g. via the Ellipsoid algorithm) but in the absence of any additional structure, cannot be expected to be solved in O(n) time, since at the very least the entries of $A$ have to be read, and there are in general more than O(n) of these. (And I guess I should mention that this is why I'm interested in minimizing *convex* functions subject to matrix constraints, since if the functions weren't convex, minimizing them would in general be NP-hard.)

What I would like to ask is: what is known about cases between these two extremes?

As a motivating example, consider minimizing $\Sigma x_i ln x_i$ such that $Ax=b$, where $A$ has O(n) nonzero entries, in the following pattern:

|*** | |* ** | | * ** | | * **|

This matrix has n non-zeros in the first row, plus 3 non-zeros in the subsequent n rows, i.e. 4n non-zeros in total.

Is there an efficient way to minimize functions subject to simple matrix constraints like these? (I'm well and truly hand-waving now, but maybe something like the ellipsoid method can be applied O(n) times to smaller sub-problems of O(1) size?)