# How to "convexify" a non-convex function?

In the following paper

there is a non-convex function [figure 1]. Does it mean that I can't find the optimal values of $p, q, \alpha, R$ to maximize $\sum R_k$?

And the author just change the variable $p,q$ to $m,s$ and told that the non-convex had change into convex,and they use the Lagrange multiplier to find the optimal value. So,is it use Lagrange multiplier to let the non-convex become convex? Because i don't think that he can transform this function from non-convex to convex by only change two variable. (1)This function is non-convex,and $R_k$ is the function of $p,q,\alpha$. $R$ is {$R_k$} (2) This function is convex,and $m=${$\alpha_k q_k/2$},$s=${$\alpha_0 p_0,\alpha_k q_k/2$},$15b$~$15f$ is the constraint

• It is not clear what you are asking. Aug 5, 2018 at 14:08
• @copper.hat Can you tell me your confusion so i can edit it ASAP Aug 5, 2018 at 14:44
• what is your question ? Aug 5, 2018 at 20:36
• @ShineSun, your problem statement is not clear, because you are not including the functional dependence of $R_k$ on the parameters. But looking at the paper, I think I understand the problem you are asking about. Aug 5, 2018 at 21:35

It seems that they are correct. The simplest form of the problem can be thought of as the following $$\max_{\alpha, p} \; \alpha \log(1+p) \quad \text{s.t.} \quad \alpha p \le 1,\; \quad \alpha,p \ge0$$ and they do a change of variable $m = \alpha p$ to obtain $$\max_{\alpha, m} \; \alpha \log(1+m/\alpha) \quad \text{s.t.} \quad m \le 1, \quad \alpha, m \ge 0.$$ The constraints of this problem are clearly convex (i.e., affine inequalities). It only remains to verify that $f(\alpha,m) = \alpha \log(1+m/\alpha)$ is concave jointly in its variables. This is easy to verify using the Hessian $$\nabla^2 f(\alpha,m) = \frac{1}{(\alpha + m)^2} \begin{pmatrix} -m^2/\alpha & m \\ m & - \alpha \end{pmatrix}.$$ The matrix above has nonpositive diagonals over $C = \{(\alpha,m) \mid \alpha,m \ge 0\}$ and the determinant is $0$. Hence, $\nabla^2 f(\alpha,m)$ is nonpostive definite over $C$, i.e. $f$ is concave over $C$. Since maximizing a concave function over a convex set is a convex optimization problem, the second problem is convex.

Here is a plot of function $f$: Extension. What they in fact have is more like $$\max_{\alpha, p, \beta, q} \; \min\{\alpha \log(1+p), \beta\log (1+q)\} \quad \text{s.t.} \quad \alpha p \le 1,\quad \beta q \le 1\quad \alpha,p, \beta,q \ge0$$ which they turn into $$\max_{\alpha, m, \beta, s} \; \min\{\alpha \log(1+m/\alpha), \beta\log (1+s/\beta)\} \quad \text{s.t.} \quad m \le 1,\quad s \le 1\quad \alpha,m, \beta,s \ge0.$$ The convexity of the second problem follows from the above argument and that the minimum of a bunch of concave functions is again concave.

Update. Here is another trick they are using. Suppose you want to solve the following problem, $$(P) \quad \max_x \sum_{k=1}^n \min(g_{1,k}(x),g_{2,k}(x)).$$ Let $g_k(x) =\min(g_{1,k}(x),g_{2,k}(x))$. Assuming that $g_{1,k}$ and $g_{2,k}$ are concave functions, then so is $g_k$ (check!). So the above problem is a convex problem. We can write it in epigraph form: $$(P') \quad \max_{x, t_1,\dots,t_n} \; \sum_{k=1}^n t_k \quad \text{s.t.} \quad t_k \le \min(g_{1,k}(x),g_{2,k}(x)) , \;\text{for all k=1,\dots,n}.$$ To see that this is equivalent to the original problem, first optimize over $t_1,\dots,t_k$ (and then over $x$). Optimizing over $t_k$ forces us to have $t_k = \min(g_{1,k}(x),g_{2,k}(x))$, giving back the original problem $(P)$.

Now, we can equivalently write $(P')$ as \begin{align*} (P'') \quad \quad &\max_{x, t_1,\dots,t_n} \; \sum_{k=1}^n t_k \quad \text{s.t.} \\ &\qquad t_k \le g_{1,k}(x), \quad, t_k \le g_{2,k}(x) , \;\text{for all $k=1,\dots,n$}. \end{align*} This problem is equivalent to the original problem. If $x^*,t_1^*,\dots,t_k^*$ is an optimal solution of $(P'')$, then $x^*$ is an optimal solution of $(P)$ and we have $t^*_k = \min(g_{1,k}(x^*),g_{2,k}(x^*)) = g_k(x^*)$

• so it may be possible that tranform nonconvex to convex by only changing the variable,because it can satisfy $\nabla^2f(a,m)\le 0$.So the lagrange multiplier just help me to find the optimal solution in convex case,not transform the non-convex to convex.Am i right? Aug 6, 2018 at 1:38
• @ShineSun, yes, here the problem becomes convex after the change of variables. You can use Lagrange multipliers (i.e. KKT) conditions for the convex problem and nonconvex one as well, but for the convex problem, they would be necessary and sufficient (under mild constraint qualification conditions), while for the nonconvex one, they would just be necessary. Aug 6, 2018 at 1:53
• while for the nonconvex one, they would just be "unnecessary" ? Aug 6, 2018 at 2:04
• $∇^2f(a,m)≤0$ is the definition of deciding whether the function is convex or nonconvex Aug 6, 2018 at 2:05
• I was talking about the KKT conditions: en.wikipedia.org/wiki/…. Whether the problem is convex or not has nothing to do with the Largrange multipliers or the KKT conditions. You can ignore my previous comment if it is confusing... Yes, $\nabla^2 f(\alpha,m) \le 0$ is equivalent to the function being concave in this case. Aug 6, 2018 at 2:14