4 fix another error

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 . One can simply solve for each element of introduce a Lagrangian $x$ in turn\lambda$so that the problem becomes$min \Sigma x_i ln x_i + \lambda Ax$. Then, using one can use e.g. bisection to ensure compute$\lambda$such that the$Ax=b$constraint is satisifed. Ax=b$. If we suppose that to compute the answer to a number of bisection steps required level is independent of precision takes a constant amount the length of time for each variable, the vector $x$, then solving this kind of 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?)

3 a bit more precise

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 simply solve for each element of $x$ in turn, using e.g. bisection to ensure that the $Ax=b$ constraint is satisifed. If we suppose that to compute the answer to a required level of precision takes a constant amount of time for each variable, then solving this kind of 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 possibly 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 O(n^2more 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?)

2 oops, fixed a big mistake

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$ is diagonalhas a single row, the convexity of $x_i ln x_i$ means that this problem is very easy to solve: one can simply solve for each element of $x$ in turn, using e.g. bisection to ensure that the $Ax=b$ constraint is satisifed. If we suppose that to compute the answer to a required level of precision takes a constant amount of time for each variable, then solving this kind of 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 possibly be solved in O(n) time, since at the very least the entries of $A$ have to be read, and there are in general O(n^2) 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?)

1