I want to maximize a composite function over a convex set \begin{equation} \begin{aligned} & \underset{\mathbf{p}}{\text{maximize}} & & f(\mathbf{p})-g(\mathbf{p})\\ & \text{subject to} & & \mathbf{p}^T\mathbf{C}_{m}\mathbf{p}\leq\beta_{m}, \; \forall m. \end{aligned} \end{equation} where \begin{align} f(\mathbf{p})=\log\sum_{k=1}^{N}\exp\Big[-\sum_{i}\log\Big(1+a_{i}\mathbf{p}^{T}\mathbf{A}_{k}\mathbf{p}\Big)\Big]\\ g(\mathbf{p})=\log\sum_{k=1}^{N}\exp\Big[-\sum_{i}\log\Big(1+a_{i}\mathbf{p}^{T}\mathbf{B}_{k}\mathbf{p}\Big)\Big]. \end{align} All $\mathbf{A}_k, \mathbf{B}_k$ and $\mathbf{C}_m$ are positive semi-definite matrices; $a_i>0,b_i>0$ for all $i$. The main challenge of this problem is that $\mathbf{p}^{T}\mathbf{A}_{k}\mathbf{p}$ is a convex function, $\log(1+x)$ is a concave function and $\log\sum_{k=1}^{N}\exp(x_k)$ is a convex function. Clearly, both $f(\mathbf{p})$ and $g(\mathbf{p})$ are non-convex. How to maximize an objective function like this? Any suggestions will be highly appreciated, thank you.
12
-
$\begingroup$ have you already tried projected gradient and d.c. programming (the latter will require some work because your functions are purely nonconvex, but may be broken up in a way that enables d.c.).. $\endgroup$– SuvritOct 1, 2015 at 1:06
-
$\begingroup$ Hi, Survit. I had tried a lot of method to solve it. The first is something like SDP, by introducing a matrix $Q=pp^T$ the objective function can be transformed into a d.c. function, and then I relaxed the rank one constraint and solve it using CCCP. This method works well in practice but in theory it is not a global optimization method. I also tried to reformulate the objective function as (f(p)+kp'*p)-(g(p)+kp'*p). I can find a relative small k such that the objective function is a d.c. function, However, this method works really bad because k is still too large. $\endgroup$– mycalOct 1, 2015 at 3:11
-
$\begingroup$ "not a global optimization method..." --- in general it'll be NP-Hard to get a global optimization here, and anything that'll be practical will be not global, so I don't see why you would not use the SDP based formulation (neglecting the rank constraint, or if you wish you can add a trace-norm constraint to encourage the system to have low rank solution)... $\endgroup$– SuvritOct 1, 2015 at 14:22
-
$\begingroup$ Yeah, this is in general a NP-hard problem, so I hope I can find a branch-and-bound based algorithm. The general QCQP can be solved globally by using the reformulation-and-linearization technique (RLT) and maximizing a d.c. function over a convex set can also be solved globally. However, it seems very difficult to combine them together.... $\endgroup$– mycalOct 1, 2015 at 15:08
-
$\begingroup$ I guess your use of the word "solve" is different from mine (by "solve" I mean: guaranteed polynomial time solve, not just a heuristic). $$\phantom{a}$$ However, I don't have expertise in branch-and-bound style global optimization, so I'll leave it to someone else to answer. For approximate solutions you could still try SQP. $\endgroup$– SuvritOct 1, 2015 at 15:35
|
Show 7 more comments