Convex quadratic program plus one non-convex term

Question

How would you approach a standard convex quadratic program with convex constraints but one non-convex term? Say $|x|^{0.4}$.

$$\begin{array}{ll} \underset{x}{\text{minimize}} & \frac12 x^{T} Q x + g^T x + c^T \cdot \mbox{sign}(x) \cdot |x|^{0.4}\\ \text{subject to} & A x \leq b\end{array}$$

where $|\cdot|$ and $\mbox{sign}(\cdot)$ are applied element-wise. Is there any other way to solve the problem within convex framework? What's the best way to approximate if the dimensions are large?

This is similar to this question, but here there is a power term.

Answer 1

I am not sure this answer is correct.

(1) The projected gradient descent may work.

Let's start with function $\varphi(x)$: \begin{equation} \varphi(x) = c^T \cdot \operatorname{sign}(x) \circ |x|^{0.4} = \sum_{i=1}^n c_i \operatorname{sign}(x_i) {|x_i|}^{0.4}, \quad \forall x \in \mathbb{R}^n. \end{equation} For convenience, we define \begin{equation} \varphi_i(x) = c_i \operatorname{sign}(x_i) {|x_i|}^{0.4} \end{equation} and thus $\varphi(x) = \sum_{i=1}^n \varphi_i(x)$. Now we can compute the (sub)differential of $\varphi_i(\cdot)$ at $x$: \begin{equation} \partial \varphi_i(x) = \left\{ \begin{array}{cl} 0.4c_i x_i^{-0.6} & \text{if}~x_i > 0, \\ (-\infty, + \infty) & \text{if}~x_i = 0, \\ -0.4c_i x_i^{-0.6} & \text{if}~x_i < 0. \end{array} \right. \end{equation} Let $\psi(x)$ be \begin{equation} \psi(x) = \frac{1}{2}x^TQx+g^Tx+c^T \cdot \operatorname{sign}(x) \circ |x|^{0.4}, \end{equation} and we can compute its gradient: \begin{equation} [\nabla \psi(x)]_i = [Qx]_i + g_i + c_i + \partial \varphi_i(x). \end{equation} In this sense, we can apply the projected gradient descent method.

(2) We can applying the DC programming.

We can easily find that \begin{equation} \phi_i(x) = c_i \operatorname{sign}(x_i) |x_i|^{0.4} = c_i \frac{x_i}{|x_i|}|x_i|^{0.4} = c_i x_i |x_i|^{-0.6}. \end{equation} Furthermore, we have \begin{equation} \varphi_i(x) = \frac{c_i}{2} \left[(x_i + |x_i|^{-0.6})^2 - (x_i^2 + x_i^{-1.2})\right]. \end{equation} Let $$f_i(x) = (x_i + |x_i|^{-0.6})^2, \quad g_i(x) = (x_i^2 + x_i^{-1.2}),$$ and we can find that $f_i(x)$ and $g_i(x)$ are both convex function. Thus $$\phi_i(x) = \frac{c_i}{2}(f_i(x) - g_i(x))$$ is a DC (difference of convex) function. We can applying the DC programming to solve this problem. For details, in iteration $\textit{k}$, we try to solve the following convex optimization subproblem: \begin{equation} x^{k+1} = \mathop{\arg\min}_x \left\{\frac{1}{2}x^TQx+g^Tx + \hat{\varphi}(x;x^k), \quad \text{s.t.} Ax \leq b\right\}. \end{equation} where $\hat{\varphi}(x;x^k)$ is the approximation of $\varphi(x)$ by linearizing the subtracted term at $x^k$, i.e., \begin{equation} \hat{\varphi}(x) = \sum_{i=1}^n \hat{\varphi}_i(x), \quad \hat{\varphi}_i(x) = \left\{ \begin{array}{cl} \frac{c_i}{2}\left[f_i(x) - g_i'(x)(x_i-x_i^k) \right] & \text{if}~c_i \ge 0, \\ -\frac{c_i}{2} \left[g_i(x) - f_i'(x)(x_i-x_i^k) \right] & \text{if}~c_i < 0. \end{array} \right. \end{equation} The subproblem can be solve by some convex optimization algorithm, e.g. projected gradient method, block coordinate descent, etc.