Reformulating This Linear Program

Question

So I have the following linear program, where $\mathbf{w}_{m} \in \mathbb{R}^{K}$:

$$ \underset{\left\{ \mathbf{w}_{m} \right\}_{m=1}^{M}}{\text{minimize}} \; \; \sum_{m=1}^{M} \mathbf{d}_{m}^{T} \mathbf{w}_{m}$$ $$ \text{subject to} \; \; \mathbf{1}^{T} \mathbf{w}_{m} = 1 \quad \forall m=1,\ldots,M$$ $$ \quad \quad \quad \; \; \; \mathbf{w}_{m} \geq \mathbf{0} \quad \; \; \; \; \forall m=1,\ldots,M $$

where $\mathbf{w}_{m} = [w_{m,1}, w_{m,2}, \ldots, w_{m,K}]^{T}$ I want to reformulate it to include the constraint that $\sum_{m=1}^{M} w_{m,k} \geq \tau_{m} \forall k =1, 2, \ldots, K$ while still being in a standard form.

I was thinking of approximating this program via:

$$ \underset{ \mathbf{W}}{\text{minimize}} \; || \mathbf{D} \circ \mathbf{W} ||_{F}^{2} \; \; $$ $$ \text{subject to} \; \; \mathbf{W}^{T} \mathbf{1} = \mathbf{1} $$ $$ \quad \quad \quad \; \; \; \mathbf{W} \mathbf{1} \geq \vec{\tau} $$ $$ \quad \quad \quad \; \; \; \mathbf{W} \geq 0 $$ where $\mathbf{W} = [w_{k,m}]$ and $\mathbf{D} = [d_{k,m}]$ and $\circ$ is the hadamard product.

But, this isn't a linear program, right? Or at least it isn't in a standard form. What should I do here to get my problem into a form that is solveable?

---

I have an idea. How about this:

$$ \underset{\text{vec}(\mathbf{W})}{\text{minimize}} \; \; \mathbf{d}^{T} \text{vec}(\mathbf{W}) + \mathbf{0}^{T} \text{vec}(\mathbf{W^{T}}) $$ $$ \text{subject to} \; \; \mathbf{I} \text{vec}(\mathbf{W}) = \mathbf{1} \quad \forall m=1,\ldots,M$$ $$ \quad \quad \quad \; \; \; \mathbf{I} \text{vec}(\mathbf{W^{T}}) = \vec{\tau}$$ $$ \quad \quad \quad \; \; \; \text{vec}(\mathbf{W}), \text{vec}(\mathbf{W}^{T}) \geq 0 $$

Then I can let $\mathbf{x} = [\text{vec}(\mathbf{W})^{T} \text{vec}(\mathbf{W}^{T})^{T}]^{T}$, $\mathbf{c} = [ \mathbf{d}^{T} \mathbf{0}^{T} ]^{T}$, and $A = [ \mathbf{I}, \mathbf{0} || \mathbf{0}, \mathbf{I}]$ so that we have:

$$ \underset{\mathbf{x}}{\text{minimize}} \; \; \mathbf{c}^{T} \mathbf{x} $$ $$ \text{subject to} \; \; \mathbf{A} \mathbf{x} + [\mathbf{0}, \mathbf{0} || \mathbf{0}, \mathbf{I} ] \mathbf{s} = [\mathbf{1}^{T}, \vec{\tau}^{T}]^{T}$$ $$ \quad \quad \quad \; \; \; \mathbf{x} \geq 0 $$

where $\mathbf{s}$ are slack variables. Is that legal to do, seeing how we are reusing some of the variables between the parts of $\mathbf{x}$?

Answer 1

You can write it as follows $$ \underset{ \mathbf{W}}{\text{minimize}} \; \mathbf{d} \mathbf{W} \mathbf{1}^T\; \; $$ $$ \text{subject to} \; \; \mathbf{W}^T \mathbf{1}= \mathbf{1} $$ $$ \quad \quad \quad \; \; \; \mathbf{1} ^T\mathbf{W}\geq \vec{\tau} $$ $$ \quad \quad \quad \; \; \; \mathbf{W} \geq 0 $$.

However, for solving, you have to order the matrix $ \mathbf{W} $ as a vector.

Answer 2

If your standard form requires equality constraints and nonnegative variables, you can introduce surplus variables $s_m \ge 0$ and rewrite the inequality constraint as $\sum_{m=1}^M w_{m,k} - s_m = \tau_m$.

May solvers allow you to express the inequality constraints as is, without requiring transformations like this.