Dear Mathtalk,
I have the folowing problem.
Given hermitian matrix positive semi-definite G (eigenvalues >=0), the
question is to find the hermitian positive semi-definite "Block
Diagonal Matrix" M, which maximize:

        det(I+M*G) with tr(M)<=1.

with I identity matrix.
we can write M as:

    |M1  0 0 0 0 0|
    |0  M2 0 0 0 0|
M = |0  0  M3  0 .|
    |0  0  0 ... .|
    |0  0  ...  Mn|

with Mi hermitian positive semi-definite matrix.
I need a formulation of Mi in function of G or in function of the a
decompositon of G (EVD). I have already an iterative solution but i
need a direct formulation of each Mi.
the answer is needed in the next 3 or at max 4 days.

Thank you.

---

Clarification of Question by torrent-ga on 08 Sep 2005 08:55 PDT

Hi,

Just a small clarification.
I mean by "decomposition of G" the eigenvectors or eigenvalues of G.
the answer needs to be a direct formulation of each Mi in fucntion of G.

Thanks.

---

Clarification of Question by torrent-ga on 08 Sep 2005 18:50 PDT

Hi mathtalk,

Thank you for your comment :).
I hope that, as usual, you could solve it.

Good luck :).

---

Clarification of Question by torrent-ga on 08 Sep 2005 20:25 PDT

Hi Mathtalk,

for your simple example, it is easy to find solution, that i'm sure
you already did it :).
If M = [a 0 
        0 b] 
and G = [x1 x2
         x2 x4]
then, the solution is:

if [1+(x4-x1)/det(G)] >= 0 and [1+(x1-x4)/det(G)] >= 0 
then 
    b = 1/2*[1+(x4-x1)/det(G)] and a = 1/2*[1+(x4-x1)/det(G)].
else if [1+(x4-x1)/det(G)] < 0 then
            a = 1 and b =0
else
            a = 0 and b = 1.
end.

I hope that it will give you some ideas :) or "clues".

Thanks.

---

Clarification of Question by torrent-ga on 09 Sep 2005 14:31 PDT

Hi,

could you please inform if someone is working on my problem, because it's urgent.
I can give a good tips if i get exactly what i need :).

Thank you.

---

Clarification of Question by torrent-ga on 11 Sep 2005 17:04 PDT

Hi Mathtalk,
I hope that your argument that "the off-diagonal blocks of A = G?¹ do
not make a difference in the choice of M" is true. The example of 2*2
is really too simple to make a conlusion about that.

So, if we could show that, it will be more simple.

Could you please try to prove it. If it is true, i think that it can
be quite simple after that, to present a complete solution, including
the "perturbation argument" you said.

Thank you.

---

Clarification of Question by torrent-ga on 18 Sep 2005 20:49 PDT

Hi,

The deadline is removed.
The Price doubled.

I hope that it will provide you more time to solve it :).
seeu.

---

Clarification of Question by torrent-ga on 21 Sep 2005 16:52 PDT

Hi Mathtalk,

i've already seen the Hadamard problem, but i didn't see an easy
relation between the two problems :), i hope could you do it.

Good luck.

---

Clarification of Question by torrent-ga on 27 Sep 2005 22:05 PDT

Dear Mathtalk,
i was just wondering if the 10 left days is enough for you to find solution?
If this is the case, it is good.
If you have the solution idea but the time is not enough, i can
resubmit the question again for you.

Thank you for your efforts.

NB: In addition to the Listed price, if you find what i want, i can
give you even 50% more, as a tips. So, could you please give my
question the time it needs :).

Thanks again.

---

Clarification of Question by torrent-ga on 29 Sep 2005 21:10 PDT

Hi mathtalk,

we call such equalization, "Water-filling method". It is true that
this is the solution if there is no constraints over M, but i'm indeed
interested in the Block Diagonal case of M.

Thank you for your effort.
I'm still looking for an answer from you.

---

Clarification of Question by torrent-ga on 29 Sep 2005 21:12 PDT

Hi,

I increase again the price list (150$) hopefully getting faster answer :).

Thanks.

---

Clarification of Question by torrent-ga on 05 Oct 2005 20:39 PDT

Hi Mathtalk,

are you still working on my problem or you give up :).
please inform me abour what's going on.

Thanks.

It's an interesting question (trans: I haven't got a clue), something
like a recipe for a pre-conditioning matrix M.

What I like to do in such situations (aka: buying a clue) is tackle
the simplest possible non-trivial case, which would be G real pos.
def. symmetric 2x2 matrix, and M positive diagonal:

  max det( I + M*G ) subject to trace(M) <= 1

just to get a feel for the problem.  In fact if you could explicitly
solve the diagonal M case, then with enough commutativity assumptions,
you'd probably have a solution for the block Hermitian case.


regards, mathtalk-ga

Here are some thoughts on reformulation of the problem.  Let Hermitian
semi-definite G be expressed in the form:

  G = QDQ'

where D is the diagonal matrix of nonnegative eigenvalues of G, and Q
is special unitary, ie. det(Q) = 1.

Then det( I + MG ) = det( Q + MQD ).

If G is nonsingular (ie. pos. definite), then D is invertible, and by
factoring out a constant det(G) = det(D) we have an equivalent problem
to maximize:

  det( QD?¹ + MQ ) = det( QD?¹Q' + M )

which we could indeed have passed to immediately as:

  det( G?¹ + M )

under the assumption of G nonsingular.

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *

Setting aside the structure of G for a moment, it may be helpful to
point out that the block-structure of M defines a "partition" type of
restriction, such that requiring M to be diagonal would satisfy any
block-structure, and at the other extreme every block-structure would
be included in the broadest case that matrix M is allowed to be full.

Then clearly the maximum determinant attainable for diagonal M is a
lower bound to that attainable for any block-structure, and likewise
the maximum determinant for full matrices M is an upper bound.

You mentioned that you had worked out an iterative solution. 
Naturally I'm sure you have considered already the utility of defining
an "exact" solution simply as the algebraic solution (fixed-point) of
what the iterative scheme requires.

However I'd also suggest that short of finding an explicit solution M
for any arbitrary block-structure, it might be useful to have as an
initial value for your iterative scheme the solution for diagonal M
(in view of the fact that this solution is "admissable" for any
block-structure).

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *

This last observation ties back into our earlier reformulation, at
least for nonsingular G.  Let:

  D?¹ = diag(1/d_1,1/d_2,...,1/d_n)

and:

   M  = diag(m_1,m_2,...,m_n)

Then (QD?¹ + MQ)_i,j = (m_i + 1/d_j)q_i,j

where matrix Q has entries q_i,j.

Even when G is not necessarily nonsingular, we might be able to make use of:

  (Q + MQD)_i,j = (1 + (m_i)(d_j))q_i,j

as these expressions seem to open the way to formulating a fairly
explicit optimization problem, subject to nonnegativity of m_i's and
the trace constraint:

  SUM m_i <= 1
   i


regards, mathtalk-ga

A glimmer of hope...

I'm finding that the reformulation:

  MAX det ( G?¹ + M )

such that tr(M) <= 1 and pos. semi-definite M has the required block
structure is much easier to work with.  For example, in the above
setting it is easy to show that tr(M) = 1, ie. the inequality is
tight.

I believe this is equivalent to the original problem, which allows G
singular, by a standard perturbation argument.

One can then argue, because similarity transformations preserve trace
and pos. semi-definiteness, that only the case A = G?¹ having diagonal
blocks (within the structure imposed on M) that are real diagonal
needs to be addressed (since up to such "block" similarity
transformations the class of admissable M is invariant).

What would then polish the problem off would be a conjecture, if true,
that the off-diagonal blocks of A = G?¹ then do not make a difference
in the choice of M.

Some numerical experimentation/hand-calculations ought to quickly show
whether such a conjecture is tenable.  It is true in the simplest
(perhaps too simple) 2x2, case:

         / a   b \      /  d   0  \
  det [  |       |  +   |         |  ]  = (a+d)(c+1-d) - b²
         \ b   c /      \  0  1-d /

where the solution, equivalent to that which you posted above
involving division by det(G), is for d to be the nearest element of
[0,1] to (1/2)[1 + c - a].  So here we note that the solution doesn't
depend on the off-diagonal element b.


regards, mathtalk-ga

Alas, my conjecture turns out to be false, as one can see from the example:

      / 1 0 b \
  A = | 0 1 0 |   with M to be diagonal.
      \ b 0 1 /

Such A is positive definite provided |b| < 1.  Subject to tr(M) = 1:

  MAX det( I + M ) = 64/27  by taking M = diag(1/3,1/3,1/3)

  MAX det( A + M ) = 9/4 - b² by taking M = diag(1/2,0,1/2)

So in general we cannot ignore the effect of off-diagonal elements on
the optimal solution M.


regards, mathtalk-ga

I should clarify that only when |b| >= SQRT(3)/2 does the optimal M
get pushed to the extreme diag(1/2,0,1/2).  However any nonzero b is
sufficient to move the optimal M away from diag(1/3,1/3,1/3).  For b
between 0 and SQRT(3)/2 the optimal M is:

  diag(d,1-2d,d)

where d = (SQRT(4 + 3b²) - 1)/3, so the solutions agree if (and only if) b = 0.

regards, mathtalk-ga

Given that the off-diagonal elements do influence the solution, I'm
thinking the next step would be to get a better idea about how this
works by investigating the "block 2x2" example:

       /  I  B' \
  A =  \  B  I  /

with similar block structure for M.  Because of the symmetry between
upper and lower blocks, I'd expect the optimum M to have two equal
blocks, which cuts down on the number of unknowns.


regards, mathtalk-ga

The only case I can really nail down so far is where A is positive
diagonal and M is constrained to be diagonal (trace <= 1).  Then we
can argue that the "greedy" strategy of adding small amounts of
"trace" to the smallest entries of A (until these are equalized to the
next smallest one) is optimal and leads to the global maximum
determinant.

This leaves open for now the not-quite-as-simple case that A is
positive diagonal and M is just semi-definite (with trace <= 1).  In
fact a proof for A = I that the  best M is (1/n)I would be helpful as
it may point in the right direction.

As regards the block 2x2 situation above, I find that if M's upper and
lower diagonal blocks are constrained to be equal (pretty reasonable)
and to commute with B and thus with B' by symmetry (no idea if this
can be justified), then the optimal M is independent of B.

regards, mathtatlk-ga

Here's a paper that seems relevant to the Question at hand:

[Maximizing the Determinant for a Special Class of Block-partitioned Matrices]
http://winwww.rutgers.edu/~otilia/papers/max_det.pdf

I should have pointed this out before, but the topic of finding the
maximum determinant over some closed subset of matrices is known as
Hadamard's maximum determinant problem:

[Hadamard's Maximum Determinant Problem -- MathWorld]
http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html

"Hadamard (1893) proved that the determinant of any complex nxn matrix
A with entries in the closed unit disk |a_(ij)|<=1 satisfies

   |detA|<=n^(n/2) "

The modified problem considered here of maximizing det(A+M) for pos.
definite Hermitian A and pos. semi-definite Hermitian M, constrained
by trace <= 1 and by a certain block-diagonal format, fits into this
more general class of problems because the set of all such matrices
(for A fixed) is a closed set (under any of the usual equivalent
metrics on complex nxn matrices).

regards, mathtalk-ga

Just as a quick Comment, the use of Hadamard's inequality in the paper
cited above makes it clear that the solution of the "single block"
case is indeed found by reducing A to a diagonal matrix (by
similarity) and computing M as similar to the associated "rising tide"
diagonal matrix by the same similarity transformation.

So, I would put the pertubation argument (reducing to A+M formulation
instead of I+GM) and the solution of the single-block case over in
category of "on solid ground" at this point.

Looking more carefully at the 2x2 block case I proposed, I realized
the solutions of M_1 and M_2 in the respective blocks need not be
equal.  More on this soon.

regards, mathtalk-ga

Here's a sketch of the perturbation argument:

Let {G_i} be a sequence of positive semi-definite Hermitian
matrices converging to G, implying that G is also positive
semi-definite and Hermitian.

Let S be the set of all positive semi-definite Hermitian
matrices M whose trace is less than or equal to 1.  Then S
is a closed and bounded subset of nxn (complex) matrices
under any of the usual matrix norms or metrics.  Therefore
S is compact in this metric topology, and any sequence in S
contains a convergent subsequence.  [Details of proof
available upon request.]

If we define g = max det( I + G*M ) taken over all M in S,
and similarly g_i = max det( I + G_i * M ) is also taken
over all such matrices M, then we claim:

   g =  LIMIT  g_i
       i -> oo

Proof:

For convenience let M refer to a specific matrix such that:

   g = det( I + G*M )

the attainment of the maximum being a consequence of the
continuity of the determinant as a function of matrix
entries and the compactness of S.

Similarly let M_i be matrices such that:

  g_i = det( I + G_i*M_i)

are the similar maxima noted in the statement above.

Now the first thing to note is that:

  det( I + G_i*M ) <= det( I + G_i*M_i )

since the M_i are "optimal" in this respect.  Furthermore
the sequence {M_i} contains a convergent subsequence, so
that by discarding all but those entries, we would have:

  W =  LIMIT  M_i
      i -> oo

and det( I + G*W ) =  LIMIT  g_i.
                     i -> oo

Taking the limits on both sides of the inequality above,
by virtue of the continuity of deteriminant, preserves
the direction of the inequality between the limits:

  det( I + G*M ) <=  det( I + G*W )

              g  <=  LIMIT  g_i
                    i -> oo

But on the other hand, by the optimality of M, we also know:

  det( I + G*M ) >=  det( I + G*W )

Thus equality must hold, just as was claimed:

               g  =  LIMIT  g_i
                    i -> oo

QED

Now we apply this to a sequence of invertible matrices {G_i}, for example:

   G_k = G + (1/k)I

converging to G.  Then the max det( I + G*M ) is the same as the limit
of the sequence of maximum determinants:

   max det( I + G_i * M )

and any solution of the problem for invertible G (ie. positive
definite Hermitian matrices) can be then extended by continuity to
positive semi-definite Hermitian matrices.


regards, mathtalk-ga

Let G be an nxn pos. semi-definite Hermitian matrix.

The perturbation argument allows us to reduce the problem:

  maximize det( I + G*M )

over M in S = { M | M is nxn pos. semi-def. Hermitian, tr(M) <= 1 }, to:

  maximize det( A + M )

over M in the same set S.  For if G is invertible (ie. pos. definite),
then taking A = G?¹, we have:

  det( I + G*M ) = det(G)*det(A+M)

and if G is singular, then we can take a sequence of positive definite
matrices converging to G, say for the sake of concreteness:

   G_k = G + (1/k)I

and note that by the proof above, the limit of the maximum determinant
solutions for {G_k} gives us the solution for G (at least in respect
of what the maximum determinant's value is; the "solution" M also
turns out to be found by the limiting process, but we did not yet
prove that fact, which follows from the log-concavity of the
determinant function restricted to pos. semi-definite matrices).

With this restatement of the problem in hand, we turn to the "base"
case of a single block, ie. no restriction on M other than what is
imposed above by the set S.  Let A = QDQ' where Q is unitary and D
real diagonal.  Then M = QWQ' gives the maximum value of det(A + M)
where W is the nonnegative real diagonal matrix of trace 1 that
maximizes det(D + W):

  det(A + M) = det(D + W),  tr(M) = tr(W)

If D = diag(d_1,...,d_n) with nonnegative entries in descending order,
then W is characterized by having nonnegative entries in ascending
order such that as many as possible of the lowest diagonal entries of
D+W are equalized, subject to the constraint tr(W) = 1, ie. as many of
the smaller entries in D are raised up to a common plateau.

A proof of this can be given using Hadamard's inequality.


regards, mathtalk-ga

Hi, torrent-ga:

I'm inclined to think that an explicit solution for the general case
is beyond my ability to articulate.

A summary of my findings:

1. The problem has a nice existence-uniqueness theory.  If G is
nonsingular, then the maximum determinant exists and corresponds to a
unique matrix M.  I have a strong suspicion this extends to G nonzero,
the case G = 0 being trivial.

2. The constraint trace(M) <= 1 will be tight for nonzero G, ie. at
the optimum we have trace(M) = 1.

3. The water-filling method, applied as if there were but a single
block, gives an initial guess for the multi-block case by "censoring"
the resulting M to have the required zeros outside of the specified
diagonal blocks.  Such censoring leaves trace(M) unchanged and
preserves M's positive definiteness or semi-definiteness.

4. I could come close to giving an explicit solution only by imposing
pretty draconian conditions on G, or more to the point, on A the
inverse of G.

For example, suppose:

         / a   v \                / µ  0 \
   A  =  |       |    and   M  =  |      |
         \ v'  C /                \ 0  H /

where (row) vector v is a (left) eigenvector of Hermitian matrix C, a
and µ are scalars, and H is Hermitian of trace 1 - µ.  Then I think
for this very special case we can state how to choose µ and H to
maximize:

   det( A + M )

and therefore det( I + G*M ).

5.  However the difficulty of making even this small advance over the
"single block" case makes me think that a general solution in explicit
terms is not practical.  Matrix problems, including the symmetric
eigenvalue problem, often have only effective iterative methods for
solution, and in practical terms this is usually more important that a
"formula" solution.


regards, mathtalk-ga

The Hadamard inequality states that for Hermitian positive definite A:


  det(A) ? ? A(i,i)
           i

Also, equality holds if and only if A is diagonal.  Some additional facts:

(1) The set of n×n Hermitian positive semi-definite matrices M with
trace 1 is closed, bounded, and convex, the first two of these
characteristics being with respect to the usual (complete) metric
topology on complex matrices.  Any further restriction to a given
block diagonal structure yields again a convex subset.

(2) We have seen that for Hermitian positive definite G, maximizing
det(I + GM) over M in convex subsets as above is equivalent to
maximizing det(A + M), where AG = I.  Note that A is again Hermitian
positive definite.

(3) The scalar function f(A) = ln(det(A)) is concave on Hermitian
positive semi-definite matrices, and strictly concave on Hermitian
positive definite matrices.  Consequently any closed, bounded, convex
set of Hermitian positive definite matrices has a uniquely attained
maximum determinant.

(4) Distinctions between explicit formulas for a solution and implicit
characterizations that lead to an effective iterative computation can
be drawn to serve both aesthetic and practical ends.  However the
distinction, at least in a problem of this complexity, is necessarily
partly subjective and artificial.  In support of this consider the
single block case and the "water-filling" characterization of its
solution.  This leads to a fairly explicit computation of M, but
requires a unitary diagonalization of A (or G).  This diagonalization
can generally only be achieved by iterative methods.

(5) Therefore it seems relevant to me to explore various implicit
characterizations of a solution, hoping to discover one or more
methods for an effective computation even if this be of an iterative
kind.  Two such methods have come to my attention.  The first of these
begins with an initial estimate of the diagonal sublocks M_j of M and
the portion of the total trace to be allocated to each:

     M = diag(M_1,M_2,...,M_k)

     ? trace(M_j) = 1
     j

One then poses a "single block" problem for each M_j and iterates,
either Jacobi style or Gauss-Seidel style, over all the blocks until
convergence is obtained.

More specifically, let t_j be the trace allocated for diagonal block
M_j, and let the rows and columns of both A and M be "rotated" so that
we have by a consistent partitioning:

                 /  A_j + M_j      B_j   \
   A  +  M  =    |                       |
                 \     B_j'    C_j + N_j /

   det(A + M) = det(C_j + N_j)*det(A_j - B_j(C_j + N_j)?¹B_j' + M_j)

It can be shown that A_j - B_j(C_j + N_j)?¹B_j' is Hermitian positive
definite, so maximizing the above by the choice of M_j, assuming other
values fixed, is a single block problem of the type considered early,
apart from the comparatively trivial detail that now trace(M_j) = t_j
rather than 1.

When we solve a single block problem by the water-filling method, we
obtain the derivative of the determinant with respect to an increment
in trace.  Therefore we have at the end of these calculations the
"marginal cost" of increasing the determinant of A + M with respect to
increasing the trace of any M_j.  If these rates are equal, then we
are done, but if some block has a higher "margin" than another, we use
that information to rebalance the allocations of trace across the
blocks and repeat the iterations.

(6) A second approach to the problem proceeds from a diagonalization
of an initial estimate of M:

    M  =  Q D Q'

where D is nonnegative real diagonal and Q is block diagonal and unitary:

    Q  =  diag(Q_1,Q_2,...,Q_k)

Then:

   det(A + M) = det(QAQ' + D)

With respect to choosing D for fixed Q, we now have a special case of
the original problem in which the block structure imposed on M is that
of a diagonal matrix.

I believe the analysis of this important special case is nearly as
explicit as the water-filling solution, which can be viewed as the
special circumstance that A and M are both diagonal (simultaneously
diagonalizable).  However I will defer discussion of this conjecture
for now.

One then has an outer problem which consists of choosing the unitary
blocks Q_j coupled to inner problems for finding D.  Although it seems
daunting to try and find the optimal "rotations" Q_j, we may discover
a systematic way of improving them.


regards, mathtalk-ga

Case: M diagonal (G,A not diagonal)
===================================

Let's turn now to the case that the block diagonal structure of M is
simply a diagonal matrix:

  max det(A + diag(m_1,...,m_n))

where m_i >= 0 and trace(M) = SUM m_i = t for prescribed t >= 0.

As before, matrix A is n×n positive definite Hermitian.

In the diagonal-on-diagonal case, the "water-filling" solution has a
characteristic that as we continuously increase trace parameter t,
the values {m_i} which maximize det(A+M) also increase continuously.

Arguably a more precise way of stating this is a "local" strategy,
of maximizing det(A+M) by "budgeting" m_i increases according to
which afford the maximal rates of increase, attains the global
maximum det(A+M) at each value t.

This useful feature generalizes to the present case. We can write:

det(A+M) = f(m_1,...,m_n)

         = c + SUM c_i m_i + SUM c_i,j m_i m_j + ... + m_1*...*m_n
                i            i<j

where c = det(A), c_i = det(A(i|i)), c_i,j = det(A(i,j|i,j)), etc.

Here A(i,j,k,...|i,j,k,...) denotes the submatrix of A obtained by
removing the original i,j,k,... rows and columns.  In particular
note that det(A(i|i)) is the (signed) cofactor of entry A_i,i in the
expansion of det(A).  [By convention the determinant of a 0×0 matrix
is 1, so this final coefficient of the product of all m_i's fits the
pattern.]

It will prove convenient in what follows to define c_j,i = c_i,j for
the case case i < j, and so forth for the higher order coefficients,
essentially disregarding the ordering of (distinct) subscripts.

The positive definite Hermitian property of A applies to each of the
"symmetric" submatrices A(i,j,k,...|i,j,k,...) of this expansion, so
all the coefficients above are positive.

Furthermore derivatives of f with respect to the m_i's are positive:

df/dm_i = c_i + SUM c_i,j m_j + SUM c_i,j,k m_j m_k + ... + PROD m_j
                 j              j<k                          j

(where subscripts j,k,... run over all values not equal to i) and in
themselves have positive coefficients, that derivative df/dm_i will
increase with increasing m_j (i,j distinct) but be independent of
the value m_i.

As a consequence the optimal values {m_i} are obtained for all t by
starting at t = 0 and increasing the m_i's according to these rules:

  - increase those m_i with maximal derivatives df/dm_i
  
  - increase them so as to maintain equality of their derivatives

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *

One discrepancy between this case and the diagonal-on-diagonal case
that appears is that the m_i's which have "entered the solution", ie.
begun to increase with t (rather than remain zero), will not always
increase together at the same rate (as they will in diagonal A case).

A worked example may clarify this point and the theory presented.

                / 2  1  0 \
Consider    A = | 1  2  1 |
                \ 0  1  2 /

whose corresponding expansion det(A+M) is:


f(m_1,m_2,m_3) = 4 + 3*m_1 + 4*m_2 + 3*m_3

                 + 2(m_1*m2 + m_1*m_3 + m_2*m_3) + m_1*m_2*m_3

Now at t = m_1 + m_2 + m_3 = 0, the maximum derivative is df/dm_2,
and it continues to be maximal until m_2 rises to 1/2:

                     / 0  0  0 \
   A + M(1/2) =  A + | 0  ½  0 |
                     \ 0  0  0 /

at which point det(A + M) = 4 + 4/2 = 6, and where all derivatives:

   df/dm_i  =  4

(derivative df/dm_2 having remained 4 while the other two "catch up").

Once all three m_i's enter the solution at this point, how they
increase is constrained to keep these derivatives equal, t > 1/2:

   m_1 + m_2 + m_3 = t

   df/dm_1 = df/dm_2 = df/dm_3

Setting df/dm_1 - df/dm_3 = 0 implies:

   (m_3 - m_1)*(2 + m_2) = 0

so necessarily m_1 = m_3.  Taking x to be their common value:

   m_1 = x, m_2 = t - 2x, m_3 = x

and we get from df/dm_1 = df/dm_2 an equation relating x to t:

   3x² + (t+6)x - 2t + 1 = 0

in which the desired root x is the positive one, the constant term
being negative for t > 1/2:

          SQRT((t+6)² + 12(2t - 1)) - (t+6)
 x(t)  = -----------------------------------
                         6

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *

As this example shows, although many qualitative features of solving
for the optimal values {m_i} remain similar to the "water-filling"
circumstance, the actual calculation of the values will involve the
solution of polynomial systems, and the degree of these effectively
rises as more m_i's enter the solution (take on positive values).

Despite this complication, computing the optimal {m_i} numerically
should not be very difficult.


regards, mathtalk-ga