I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\in\mathbb{R}^n$, $p\in\mathbb{R}$, and $f$, $g_1$, and $g_2$ are convex functions. This is not a convex optimization problem because $p$ is a variable, but if we fix $p$, then the remaining problem is convex, and if we fix $x_1$ and $x_2$, then the remaining problem is linear. At the moment, I am approximately solving this problem by simply discretizing the interval $[0,1]$ and calculating solutions for many fixed values of $p$ between $0$ and $1$. Is there any possibility that there might be a more efficient scheme?
2
-
2$\begingroup$ Trying doing alternating minimization (which exploits exactly what you wrote in the post); fix $x_1,x_2$ minimize over $p$, then fix $p$ and optimize over $x_1$, $x_2$ and iterate. $\endgroup$– SuvritCommented Mar 20, 2015 at 14:24
-
$\begingroup$ Whenever we have a more clear understanding of f(.), it is possible to re-write the problem somehow. For instance, if f is a linear form, the problem becomes a QCQP which can be approximately solved under certain conditions. $\endgroup$– mikitovCommented Mar 23, 2015 at 15:55
Add a comment
|