3
$\begingroup$

I have a question like

Let, $\mu = (\mu_1,\ldots, \mu_K),$ given $M: K \times m$ a full rank matrix

$\min_{\mu \in \mathbb R^K} \sum^n_{i=1}\sum^K_{k=1}(y_{ik} - \mu_k)^2$ subject to $\log \mu = M\beta,~\beta \in \mathbb R^m.$

The $\log$ here is an element-wise log transform of a vector.

I think this problem is a nonlinear problem due to the log constraint.

Initially, I thought a gradient descent method with a projection to the constraint set $\{\mu: \mu = \exp(M\beta), \beta \in \mathbb R^m\}$

However, this cannot guarantee a solution because it is not a convex problem.

How can I solve this problem?

$\endgroup$

1 Answer 1

4
$\begingroup$

Is $\beta$ also part of the decision variables?

Using the constraints $\log \mu = M \beta$, you can substitute out $\mu$ in the objective, which yields an unconstrained problem

\begin{align} \min_{\beta} \quad \sum_{i=1}^{N} \sum_{k=1}^{K} \left( y_{ik} - \exp(M_{k} \beta) \right)^2 \end{align} where $M_{k}$ denotes the $k$-th row of $M$.

This is indeed a non-convex function so, in that form, unless you have few variables, it's unlikely that you'll find a global minimizer efficiently. If you're OK with local minimizers, quasi-Newton methods like L-BFGS may give you better convergence than gradient descent.


[Edit: $M$ has full column rank, not row rank, so the approach below does not guarantee a feasible solution]

That being said, you mention that $M$ has full rank. Is that full row rank, i.e., does the system $M \beta = \log \mu$ always has a solution (for any choice of $\mu$)? If that's the case, then you can solve \begin{align} \min_{\mu} \quad & \sum_{i=1}^{N} \sum_{k=1}^{K} \left( y_{ik} - \mu_{k} \right)^2\\ \text{s.t.} \quad & \mu > 0 \end{align} then retrieve $\beta$ by solving $M \beta = \log \mu$. This yields a convex quadratic program, which can be solved very efficiently, followed by a linear system solve. There is one catch: optimization solvers do not like "strictly positive" constraints. You can handle this by adding a small, positive lower bound $\mu \geq \epsilon$. If none of the lower bounds are active, you have a global minimizer. Otherwise, you have a (presumably good) solution.

Note that solving the above quadratic problem with constraints $\mu \geq 0$ instead of $\mu > 0$ will give you a valid lower bound on the optimal objective value of the original problem. You can use this to gauge the quality of the solution you obtain when solving with $\mu \geq \epsilon$.

[Edit] when $M$ does not have full row rank, one can solve the above quadratic program, obtain $\mu$, then project $\log \mu$ onto the column space of $M$ and recover a feasible $\beta$. While this always yields a feasible solution, it has no guarantee on the quality of the resulting objective objective value.

$\endgroup$
3
  • $\begingroup$ Thank you. I forget $K >m$ i.e. $M\beta$ indicates a constrained feasible set of $\mu$. and all observation $y_i$ are always positive. Then $\mu > 0$ would not be a big issue. $\endgroup$
    – Sungmin Ji
    Nov 25, 2022 at 5:22
  • $\begingroup$ Do above conditions, if satisfied, allow to get a global minima of the subject function? Or can I get a solution with a projection $\log \mu$ into $M$ column space after solving the quadratic problem? $\endgroup$
    – Sungmin Ji
    Nov 25, 2022 at 5:26
  • $\begingroup$ Thanks for the extra information. I updated my answer $\endgroup$
    – mtanneau
    Nov 25, 2022 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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