1
$\begingroup$

I'm looking for a simple method to find a linear transform that minimizes $$ \text{argmin}_T F(T): T \in \mathbb{R}^{m \times n} ,\ T \ge 0 ,\ T \mathbb{1} = c \mathbb{1} ,\ \mathbb{1}^T T = \mathbb{1} $$

i.e. over $m \times n$ matrices $\ge 0$ with row sums all the same and column sums all 1.
(If there's a standard name for this simplex or this problem, please edit.)
$F(T)$ is min${_x}\ f( T x )$ with $f()$ convex but slow; the gradient at the current minimum should be available.
$m$ ~ 20 and $n$ ~ 100, so the method should be $O( m + n )$, not $O( m\,n )$ .
Perhaps line searches that move / clip $T$ along rows / columns ?

(The problem comes from trying to optimize a filter bank a.k.a. overlapping basis; another application area with many heuristics is feature reduction in machine learning.)

$\endgroup$
1
$\begingroup$

The problem appears relatively simple: You have a few linear equality constraints and a few linear inequality constraints, together with a convex objective function. Any optimizer should not have great difficulty with this, even the one in Matlab. If you're looking for specific ones, I believe that Lancelot has ways that specifically deal with constraints like yours.

In general, it would help to know what $f(T)$ is.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.