2
$\begingroup$

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?)

Improve this question
$\endgroup$
6
  • $\begingroup$ What's the application? This looks like a standard maximum entropy optimization. cf www-stat.stanford.edu/~donoho/Reports/Oldies/MENBO.pdf $\endgroup$
    – dranxo
    Commented Nov 18, 2011 at 7:44
  • $\begingroup$ I mean, you can reduce the problem subject to solving a system of equations saying that the $d f(x_i)/dx_i=(A^Tc)_i$, which you can invert, and separately $Ax=b$. Due to convexity you can invert the first equation to write $x$ as a monotone function of the $c$. Shouldn't standard equation-solving methods work here? $\endgroup$
    – Will Sawin
    Commented Nov 18, 2011 at 7:48
  • 1
    $\begingroup$ As a general statement: objective function is convex and constraints are afine---> it can be solved by either interior point methods or grandient methods. On the other hand, your statement: 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, I disagree. Indeed, in the gradient method is used as a projector and the problem it is not solved though. $\endgroup$
    – mikitov
    Commented Nov 18, 2011 at 7:52
  • $\begingroup$ @rcompton: the application that got me thinking about this indeed involved entropy optimization. There were two problems in particular. One had the simple 'probability simplex' constraint that all $x_i$ summed to 1. This was solvable very rapidly, by (more or less) bisecting on the value of each $x_i$. The other had the slightly more complex constrainto f 'nested simplices', where the $x_i$ were partitioned into (disjoint) sets. A single "primary" set was constrained to sum to 1 as before, and the remaining sets were all constrained to sum to elements $x_i$ of the primary set. $\endgroup$
    – Fumiyo Eda
    Commented Nov 18, 2011 at 8:22
  • $\begingroup$ @mikitov: absolutely, interior-point or gradient methods will work. Indeed, I am currently using a gradient method to solve the 'nested simplices' problem mentioned in my comment to rcompton. It works, but I can't help but feel there is a more computationally efficient way to solve the problem. $\endgroup$
    – Fumiyo Eda
    Commented Nov 18, 2011 at 8:23

1 Answer 1

Reset to default
1
$\begingroup$

As far as numerical solutions are concerned, your problem seems to be a good candidate for the following approaches:

  1. Bregman's algorithm (essentially a dual-coordinate ascent procedure). Closely related is the method called MART: "Multiplicative algebraic reconstruction technique"

  2. Alternatively, you could try using an Augmented Lagrangian Method to solve your problem.

For both choices above, there also exist parallel approaches that might be relevant if the problem size becomes very large.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Survit, can you say a little bit more about why you've made these suggestions? The "alternating direction method of multipliers" mentioned in your second reference seems applicable, though I am wondering if the idea is to decompose the problem above repeatedly until only one multiplier for each row of $A$ is updated at every step. Is this what you are suggesting? $\endgroup$
    – Fumiyo Eda
    Commented Nov 18, 2011 at 22:32
  • $\begingroup$ @Fumiyo: MART allows you to go thru $A$ one row at a time; the benefit being extremely simple updates. The cost of each update should be proportional to the number of nonzeros in the row of $A$ being used. The Augmented Lagrangian version will allow you to obtain a method that uses the entire matrix $A$ at one shot. MART will be by far the simplest, so one can always try it out! $\endgroup$
    – Suvrit
    Commented Nov 18, 2011 at 22:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .