3
$\begingroup$

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?


What about case A?

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

The projection of a convex set of points to a subspace is also a convex set (Projection of a convex set on a subspace). But the converse is not necessarily true. Shadow of a cube with a corner pushed in (as in the difference between a big cube and small cube at one corner of the big cube) can become a square. Therefore, projection of a non-convex set can be a convex set.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 21 at 16:21
  • $\begingroup$ Thanks. I have to learn exponential cone constraint first before thinking about using it in the model. For now, to solve the model, I am thinking about or.stackexchange.com/questions/4701/… and approximate the sum of exponent constraint by secant planes. The model is a transformation of the model in the comments of or.stackexchange.com/questions/6465/… $\endgroup$ Jun 22 at 0:32
  • $\begingroup$ I am still not sure about case A. The projection from euclidean space to standard simplex is not a one-to-one mapping. So I think I can't prove that case A won't work yet. $\endgroup$ Jun 22 at 0:35
  • $\begingroup$ You can learn about exponential cone at docs.mosek.com/modeling-cookbook/expo.html . $\endgroup$ Jun 22 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.