# Convex quadratic program plus one non-convex term

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.

• If the non-convex term is smooth then you can sometimes get away with incorporating its gradient into another run-of-the-mill algorithm. However, the results I'm familiar with usually prefer that the gradient satisfies some sort of Lipschitz condition. The gradient of your nonconvex function goes off to $+\infty$ at $0$, so that ain't gonna fly... You could try throwing an algorithm at it and see if it gives you something reasonable, but I don't know if there are many convergence guarantees. I'd advise hard-coding some maximal step sizes to make sure it doesn't go too haywire.
– Zim
Jul 31, 2020 at 23:33
• The product $\cdot$ in $\operatorname{sign}(x) \cdot |x|^{0.4}$ is hadamard product? In other words, $(\operatorname{sign}(x) \cdot |x|^{0.4})_i = \left\{ \begin{array}{cl} x_i^{0.4} & \text{if}~x>0 \\ -x_i^{0.4} & \text{if}~x<0 \end{array}\right.$? Aug 1, 2020 at 2:02
• Yes, it`s a hadamard product. Aug 1, 2020 at 5:11
• Do you really need the $\text{sign}(x)$ term? I think it might be easier without it (but not sure). Aug 2, 2020 at 6:50

I am not sure this answer is correct.

(1) The projected gradient descent may work.

Let's start with function $$\varphi(x)$$: $$$$\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.$$$$ For convenience, we define $$$$\varphi_i(x) = c_i \operatorname{sign}(x_i) {|x_i|}^{0.4}$$$$ and thus $$\varphi(x) = \sum_{i=1}^n \varphi_i(x)$$. Now we can compute the (sub)differential of $$\varphi_i(\cdot)$$ at $$x$$: $$$$\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.$$$$ Let $$\psi(x)$$ be $$$$\psi(x) = \frac{1}{2}x^TQx+g^Tx+c^T \cdot \operatorname{sign}(x) \circ |x|^{0.4},$$$$ and we can compute its gradient: $$$$[\nabla \psi(x)]_i = [Qx]_i + g_i + c_i + \partial \varphi_i(x).$$$$ In this sense, we can apply the projected gradient descent method.

(2) We can applying the DC programming.

We can easily find that $$$$\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}.$$$$ Furthermore, we have $$$$\varphi_i(x) = \frac{c_i}{2} \left[(x_i + |x_i|^{-0.6})^2 - (x_i^2 + x_i^{-1.2})\right].$$$$ 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: $$$$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\}.$$$$ where $$\hat{\varphi}(x;x^k)$$ is the approximation of $$\varphi(x)$$ by linearizing the subtracted term at $$x^k$$, i.e., $$$$\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.$$$$ The subproblem can be solve by some convex optimization algorithm, e.g. projected gradient method, block coordinate descent, etc.

• Thank you for the comment ! You sure that f(x) is convex ? Aug 6, 2020 at 0:45
• @Kreol, yes, you can compute the second-order differential of $f(x)$ to determine the convexity. Aug 6, 2020 at 1:19
• I did, but my cvxpy keeps complainig ((x + cp.abs(x) ** -0.6) ** 2).is_convex(). Maybe you know what could be the issue here ? Aug 6, 2020 at 2:19
• @Kreol, that is an interesting finding. It seems that there exists some error in is_convex() but I am not sure. I obverse that the function $f(x) = (x+|x|^{-0.6})^2$ is symmetric, and the result of ((x + x ** -0.6) ** 2).is_convex() is true when $x > 0$. However, the result of ((x + cp.abs(x) ** -0.6) ** 2).is_convex() is False when $x < 0$. Aug 6, 2020 at 7:42
• There is a jump in 0 and the function is not symmetric Aug 6, 2020 at 23:58