# Problems involve exponential equality constraints

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?

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$$.

 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.

• 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. Nov 25, 2022 at 5:22
• 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? Nov 25, 2022 at 5:26
• Thanks for the extra information. I updated my answer Nov 25, 2022 at 15:10