Can optimizing a convex function subject to convex constraints be written as optimizing the function subject to a convex set? Does the intersection of convex nonlinear ineualities necessarily describe a convex set? In notation, is minimize $f(x)$ subject to $g_i(x)\le0, \forall i$, where $f$ and $g_i$ are convex functions equivalent to minimizing $f$ over a convex set $\mathcal{C}$ corresponding to the constraints (if that is true)?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Do you mean "subject to $g_i(x)\geq 0$"? $\endgroup$– smccJul 17, 2016 at 10:45
-
$\begingroup$ @smcc yes, fixed $\endgroup$– UndertherainbowJul 17, 2016 at 10:46
-
$\begingroup$ Or did you mean $g_i(x)\leq 0$? (It matters here.) $\endgroup$– smccJul 17, 2016 at 10:49
-
1$\begingroup$ "the intersection of convex functions" This phrase commits a category error. It makes no sense to say "the intersection of convex functions". You can intersect sets, not functions. What you can say is "the intersections of convex nonlinear inequalities", because generally it is understood that each inequality describes a set. $\endgroup$– Michael GrantJul 22, 2016 at 0:53
-
$\begingroup$ @MichaelGrant Thanks, I fixed it. $\endgroup$– UndertherainbowJul 22, 2016 at 5:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
We know that a convex function is also quasiconvex and therefore has lower level sets that are convex sets. Thus if $g_i$ is convex then the set of $x$ such that $g_i(x)\leq 0$ is a convex set. The set $\mathcal{C}$ is the intersection of these sets over $i$. Since the intersection of convex sets is convex, $\mathcal{C}$ is convex.
See https://en.wikipedia.org/wiki/Convex_optimization#Convex_optimization_problem