0
$\begingroup$

Let's say I have a convex objective function. The boilerplate example is $z=x^2+y^2$. Now, I also have some constraint, $f(x,y)=0$. Is it true that the constrained optimization problem must be convex as well? I suspect this is the case, but have only rough intuition to back it up and was wondering if there is a proof.

My intuitive argument is that if the objective function is convex, it is always "curved downwards" (where "down" is in the direction of the objective function). Now, since the constraint can only add a condition in the x-y plane, it can't introduce any curvature in the z-direction (the direction of the objective function). So, the convexity of the objective function in that direction must be preserved.

$\endgroup$
10
  • $\begingroup$ It is not clear what you are asking. The problem is only convex if the constraints are convex as well. $\endgroup$
    – copper.hat
    Mar 13, 2019 at 4:55
  • $\begingroup$ Prove that if a objective function is convex, then regardless of any constraints, the optimization problem will remain convex. Does that make it clearer? $\endgroup$
    – Rohit Pandey
    Mar 13, 2019 at 4:56
  • $\begingroup$ @copper.hat, can you provide an example where we have a convex objective function and then we add a constraint (whatever constraint you want) and this makes the curve of intersection non-convex? $\endgroup$
    – Rohit Pandey
    Mar 13, 2019 at 4:58
  • $\begingroup$ The intersection could be a discrete set of points. For example, $|x|=1$ will only allow two points $\pm 1$. $\endgroup$
    – copper.hat
    Mar 13, 2019 at 5:03
  • $\begingroup$ Let's restrict ourselves to at least 2 variables (so including the objective function, we have three dimensions). $\endgroup$
    – Rohit Pandey
    Mar 13, 2019 at 5:05

1 Answer 1

Reset to default
1
$\begingroup$

The concept that delivers results in convex optimization is that the objective function have a convex epigraph, that is, the set of points $\{(x,f(x)):x\in\text{ constraint set}\}$ be convex. This will fail if the constraint set is non-convex.

Indeed, Rockafellar's 1970 book Convex Analysis defines the term convex function (on p.23) as follows

Let $f$ be a function whose values are real or $\pm\infty$ and whose domain is a subset $S$ of $R^n$. The set $$\{(x,\mu)|x\in S,\mu\in R,\mu\ge f(x)\}$$ is called the epigraph of $f$ and is denoted by $\text{epi } f$. We define $f$ to be a convex function on $S$ if $\text{epi }f$ is convex as a subset of $R^{n+1}$.

$\endgroup$
2
  • $\begingroup$ Can you provide an example. Let's take $z=x^2+y^2$ as the objective function. What is a constraint that will make the locus of intersection with the objective function non-convex? $\endgroup$
    – Rohit Pandey
    Mar 13, 2019 at 17:04
  • $\begingroup$ Suppose, in your case, the constraint is $|x|+|y|=1$. The set of constraint-obeying $(x,y)$ is not convex, and questions of optimizing your $z$ might be important, or might be interesting, but will not be answerable by the techniques of convex optimization. Most or all of the comments on this question seem to think this is not a convex optimization problem, but I gather you do. Your question, I think, is about a terminological quibble, without mathematical content. $\endgroup$
    – kimchi lover
    Mar 13, 2019 at 17:29

You must log in to answer this question.

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