How to transform two non-convex problems to convex problems?

79 Views Asked by At

I came cross two non-convex problems, and I wanted to transform them to standard form of convex problems.

However, I don't know how to do it. If anyone can provide ideas or give answers, I would like to thank you here in advance.

  1. $\min \left\{ \frac{(c^\top x + d)^2}{\|x\|_1}: \|Ax-b\|_{\infty} \leq 1 \right\}$, where $x \in \mathbb{R}^n_+ =\{x\in \mathbb{R}^n: x_i \geq 0, \forall i = 1,2,\cdots,n \}$, and $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^{m}, c \in \mathbb{R}^{n}, d \in \mathbb{R}$.

  2. \begin{equation} \begin{aligned} &\min \sum_{i=1}^m \exp\left( \frac{1}{a_i^\top x - b_i + 1}\right) \\ &{\rm s.t. } \ a_i^\top x \geq b_i, \end{aligned} \end{equation} where $a_i \in \mathbb{R}^n, b_i \in \mathbb{R}, i = 1,2,\cdots,m$.

1

There are 1 best solutions below

0
On BEST ANSWER

I guess what you really mean is that you want them modelled in conic form (as they both are convex to begin with.)

The first case is, in the special case of the positive orthant, a direct instance of quadratic-over-linear, which is SOCP-representable.

The second case can be dealt with by introducing auxiliary variables $s_i$ to replace terms in objective and adding constraints $e^{1/y_i} \leq s_i$ (where $y_i$ is short-hand for your affine expressions). These constraints can be expanded to $\frac{1}{y_i} \leq u_i,~e^{u_i} \leq s_i$. The first constraint is SOCP-representable, and the second convex exponential constraint is a simple exponential cone.

For explicit conic models, https://docs.mosek.com/modeling-cookbook/cqo.html