2
$\begingroup$

Suppose I'm optimizing for an unknown $x\in\mathbb{R}^k.$ I have a linear operator $A(\cdot)$ that maps $x$ to an $n\times n$ symmetric matrix, i.e., $A:\mathbb{R}^k\rightarrow\mathbb{R}^{n\times n}.$

I'd like to solve a problem of the form $$ \begin{array}{rl} \min_{x\in\mathbb{R}^k} & f(x)\\ \textrm{s.t.} & x\in\mathcal C\\ & \mathrm{exp}(A(x))\cdot v=w, \end{array} $$ where $f:\mathbb{R}^k\rightarrow\mathbb{R}$ is convex, $\mathcal C\subseteq\mathbb{R}^k$ is some convex set and $v,w\in\mathbb{R}^n$ are constant vectors.

Is there any chance this problem can be transformed into something convex? If not (or if so), what would be a good optimization technique/algorithm for problems of this form?

Improve this question
$\endgroup$
2
  • $\begingroup$ Your problem looks interesting. Could you please tell me where this problem comes from? I would like to spend some time looking into it. $\endgroup$
    – user17640
    Commented Sep 22, 2015 at 19:21
  • $\begingroup$ Any help with this problem would be much appreciated! This problem comes from some numerical challenges in differential geometry. At a high level, you can think of $A$ as defining an ODE $y'=Ay$, and the constraint links $y(1)=exp(A)v$ to $y(0)=v$. Please feel free to email me if you have ideas or thoughts about how to solve this problem. $\endgroup$
    – Justin Solomon
    Commented Sep 24, 2015 at 20:55

1 Answer 1

Reset to default
1
$\begingroup$

No, this is not possible to cast as a convex problem, as the feasible set generically is nonconvex. Consider, e.g., the case $A = \begin{bmatrix} x & 0\\0 & 2x\end{bmatrix}$, $v = \begin{bmatrix}2\\-1\end{bmatrix}$ and $w=1/2$. This data generates the constraint $2e^x-e^{2x}=1/2$ which has two distinct feasible points ($-.123$ and $.534$). This is of course to be expected, as anything but affine equalities are nonconvex.

It could be that you can escape this by some logarithmic transformation, although the likelihood is very low. Depends on the specifics of all components of this model.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Excellent counterexample --- thanks for your help. Indeed the problem is nonconvex as stated. I was hoping that there could be some log-style transformation that simplified matters, but perhaps this is too optimistic! $\endgroup$
    – Justin Solomon
    Commented Sep 24, 2015 at 20:50

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.