# Existence of a transformation to convex optimization

### Question

Does a transformation of the following problem to convex optimization exist?

\begin{aligned} \label{1} \min_{\vec{x}, \vec{y}} \quad & F(\vec{x}, \vec{y}) \\ \textrm{s.t.} \quad &F(\vec{x}, \vec{y}) \le 0 \\ &G(\vec{x}) = 0 \\ &H(\vec{x}, \vec{y}) \le 0 \\ & \forall n: x_n > 0 \\ & \forall n: y_n > 0 \end{aligned}

where $$F(\vec{x}, \vec{y}) = \left[ \sum_{n=1}^{N} f_n(x_n, y_n) \right ] - A\\ G(\vec{x}) = \left[ \sum_{n=1}^{N} x_n \right] - 1 \\ H(\vec{x}, \vec{y}) = \left[ \sum_{n=1}^{N} h_n(x_n, y_n) \right] - C$$ where $$A$$ and $$C$$ are positive constants and \begin{align} f_n(x_n, y_n) &= a_n x_n + b_n y_n \\ h_n(x_n, y_n) &= c_n e^{x_n / y_n} \end{align}

where $$a_n$$, $$b_n$$, and $$c_n$$ are positive constants.

### Simplification

There are two cases. I will try case B first.

Case A. Rewrite $$x_1 = 1 - \sum_{n=2}^{N} x_{n}$$ and get rid of the equality constraint. After that, we can transform both $$x_n$$ and $$y_n$$. However, the Hessians are not block diagonal.

Case B. Keep the equality constraint. The model is a convex optimization when $$F$$ and $$H$$ are convex functions and $$G$$ remains affine. The constraint containing $$G$$ has to remain an affine equation because it is an equality constraint. That means we can only apply an affine transform to the equality constraint, which means applying the transform to $$\vec{x}$$. Since an affine transform doesn't change the convexity of the $$F$$ and $$G$$ functions, it makes sense to not transform $$x_n$$.

The good news is that the Hessians of $$F$$ and $$H$$ are block diagonal. A function is convex if its Hessian is positive semi-definite. A block diagonal matrix is positive semi-definite if all of its blocks are positive semi-definite. Therefore, $$F$$ and $$H$$ are convex functions if the $$f_n$$ and $$h_n$$ are all convex functions.

Therefore, in case B, finding a transformation $$y(x, z)$$ for $$f(x, y) = ax + y$$ and $$h(x, y) = e^{x/y}$$ is sufficient.

### Hessian for transformed $$f$$

Let $$y = q(x, z)$$

$$\tag{1} f(x, z) = ax + q$$

$$f_{x} = a + q_{x}$$ $$f_{xx} = q_{xx}$$ $$f_{xz} = q_{xz}$$ $$f_{zz} = q_{zz}$$ where $$f_x = \frac{\partial f}{\partial x}$$

Therefore, the Hessian of the transformed $$f$$ is:

$$\tag{2} H_f = H_q = \begin{bmatrix} q_{xx} & q_{xz} \\ q_{zx} & q_{zz} \end{bmatrix}$$

A symmetric matrix is positive definite if all determinants of the upper-left sub-matrices are positive (Sylvester's criterion). Therefore, we have:

$$\tag{3}\label{3}q_{xx} > 0$$ $$\tag{4}\label{4}\det(H_{q}) = q_{xx} q_{zz} - q_{xz}^{2} > 0$$

### Hessian for transformed $$h$$

$$\tag{5} h(x, z) = e^{x/q}$$

\begin{align} h_x &= e^{x/q}q^{-1} \\ h_z &= e^{x/q}\cdot x \cdot -q^{-2} \cdot q_{z} = -e^{x/q}xq^{-2}q_{z} \\ h_{xx} &= e^{x/q}q^{-2} \\ h_{xz} &= h_{z} q^{-1} + e^{x/q} \cdot -q^{-2} \cdot q_{z}\\ &= -e^{x/q}xq^{-2}q_{z}q^{-1} - e^{x/q} q^{-2} q_{z} \\ &= -e^{x/q}xq^{-3}q_{z} - e^{x/q} q^{-2} q_{z} \\ &= -e^{x/q}q^{-3} \left( xq_{z} + qq_{z} \right) \\ &= -e^{x/q}q^{-3} q_{z} \left( x + q \right) \\ h_{zz} &= -h_{z}xq^{-2}q_{z} -e^{x/q}x\cdot -2q^{-3}q_{z} \cdot q_{z} - e^{x/q}xq^{-2}q_{zz} \\ &= e^{x/q}xq^{-2}q_{z}xq^{-2}q_{z} + e^{x/q}q^{-3} \left( 2x q_{z}^{2} - xq q_{zz} \right) \\ &= e^{x/q}q^{-3}\left( 2xq_{z}^{2} - xq q_{zz} - x^{2}q^{-1} q_{z}^{2} \right) \end{align}

$$\tag{7} H_h = q^{-3}e^{x/q} \begin{bmatrix} q & - \left(x + q \right)q_{z} \\ - \left(x + q \right)q_{z} & 2xq_{z}^{2} - xq q_{zz} - x^{2}q^{-1} q_{z}^{2} \end{bmatrix}$$

Recall that we constraint $$q = y > 0$$ and $$1 \ge x > 0$$ in the optimization problem. Therefore, $$q^{-3}e^{x/q} > 0$$. By Sylvester's criterion, we have:

$$\tag{8}q > 0$$ $$\tag{9}\label{9} \det(H_{h}) = 2xqq_{z}^{2} - xq^{2} q_{zz} - x^{2}q_{z}^{2} - \left(x + q\right)^{2}q_{z}^{2} > 0 \\ \iff 2xqq_{z}^{2} - xq^{2} q_{zz} - x^{2}q_{z}^{2} - \left(x^{2} + 2qx + q^{2}\right)q_{z}^{2} > 0 \\ \iff - xq^{2} q_{zz} - 2x^{2}q_{z}^{2} - q^{2}q_{z}^{2} > 0 \\ \iff - xq^{2} q_{zz} > (2x^{2} + q^{2}) q_{z}^{2}$$

But \eqref{9} implies $$q_{zz} < 0$$. \eqref{4} and $$q_{zz} < 0$$ together imply $$q_{xx} < 0$$, which contradicts \eqref{3}.

Therefore, case B doesn't work.

Is there an easier way to prove that case B won't work?

I am not sure if case A can work. Rewriting $$x_{1}$$ to $$1 - \sum_{n=2}^{N} x_{n}$$ is a projection from $$\mathbb{R}^{n}$$ to the standard simplex, which is within a subspace of $$\mathbb{R}^{n}$$.
• Everything except for the non-convex constraint $H$ is linear (affine), and therefore convex. If $h_n(x_n, y_n) = c_n e^{x_n / y_n}$, were instead $h_n(x_n, y_n) = c_n y_n e^{x_n / y_n}$, the constraint on $H$ would be convex, because each $h$ term could be replaced by a new variable and (convex) exponential cone constraint. Of course, that corresponds to a different problem than the one you presented. Jun 21 at 16:21