3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Zim
    Jul 31, 2020 at 23:33
  • $\begingroup$ 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.$? $\endgroup$
    – Zenan Li
    Aug 1, 2020 at 2:02
  • $\begingroup$ Yes, it`s a hadamard product. $\endgroup$
    – Kreol
    Aug 1, 2020 at 5:11
  • $\begingroup$ Do you really need the $\text{sign}(x)$ term? I think it might be easier without it (but not sure). $\endgroup$
    – littleO
    Aug 2, 2020 at 6:50

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thank you for the comment ! You sure that f(x) is convex ? $\endgroup$
    – Kreol
    Aug 6, 2020 at 0:45
  • $\begingroup$ @Kreol, yes, you can compute the second-order differential of $f(x)$ to determine the convexity. $\endgroup$
    – Zenan Li
    Aug 6, 2020 at 1:19
  • $\begingroup$ 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 ? $\endgroup$
    – Kreol
    Aug 6, 2020 at 2:19
  • $\begingroup$ @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$. $\endgroup$
    – Zenan Li
    Aug 6, 2020 at 7:42
  • $\begingroup$ There is a jump in 0 and the function is not symmetric $\endgroup$
    – Kreol
    Aug 6, 2020 at 23:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .