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?

$\endgroup$
  • $\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 Sep 22 '15 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 Sep 24 '15 at 20:55
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.

$\endgroup$
  • $\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 Sep 24 '15 at 20:50

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.