minimizing functions over simple matrix inequalities - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T18:04:37Z http://mathoverflow.net/feeds/question/81223 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/81223/minimizing-functions-over-simple-matrix-inequalities minimizing functions over simple matrix inequalities Fumiyo Eda 2011-11-18T06:48:38Z 2011-11-19T08:14:06Z <p>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:</p> <p>$min \Sigma x_i ln x_i$ such that $Ax=b$ </p> <p>Where $x$ is the (positive) vector variable, $b$ is a given real vector, and $A$ is a real matrix.</p> <p>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.</p> <p>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 <em>convex</em> functions subject to matrix constraints, since if the functions weren't convex, minimizing them would in general be NP-hard.)</p> <p>What I would like to ask is: what is known about cases between these two extremes?</p> <p>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:</p> <pre> |*** | |* ** | | * ** | | * **| </pre> <p>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.</p> <p>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?)</p> http://mathoverflow.net/questions/81223/minimizing-functions-over-simple-matrix-inequalities/81238#81238 Answer by S. Sra for minimizing functions over simple matrix inequalities S. Sra 2011-11-18T09:53:39Z 2011-11-18T09:53:39Z <p>As far as numerical solutions are concerned, your problem seems to be a good candidate for the following approaches:</p> <ol> <li><p>Bregman's algorithm (essentially a dual-coordinate ascent procedure). Closely related is the method called MART: "Multiplicative algebraic reconstruction technique"</p></li> <li><p>Alternatively, you could try using an <a href="http://en.wikipedia.org/wiki/Augmented_Lagrangian_method" rel="nofollow">Augmented Lagrangian Method</a> to solve your problem.</p></li> </ol> <p>For both choices above, there also exist parallel approaches that might be relevant if the problem size becomes very large.</p>