2

I have a convex function $f(x,y)$, with the equality constraint $x+y=1$. Is this still a convex optimization problem, despite the equality constraint? or is it a nonlinear optimization problem?

Ron
  • 143
  • Why nonlinear? The constraint seems linear to me at least. You can always turn an equality constraint into two inequality constraints. – Jesús Ros Jan 03 '17 at 09:33
  • It's possible for an optimization problem to be both nonlinear and convex. Your problem is convex, and depending on $f$ it might also be nonlinear. – littleO Jan 03 '17 at 11:49

2 Answers2

2

The standard definition of a convex optimization problem is:

Minimize $f(x)$ subject to $x\in S$
where (1) $S$ is a convex set and (2) $f$ is a convex function on set $S$

  • The set $(x,y)\in R^2$ with $x+y=1$ is clearly convex; hence (1) holds.

  • And $f$ is convex by your statement; hence (2) holds.

Gamow
  • 451
  • Practically, $S$ needs to be represented by convex functions, and $f$ needs to be convex outside $S$ too: http://math.stackexchange.com/questions/2038759/why-is-it-necessary-to-have-convexity-outside-the-feasible-region – LinAlg Jan 03 '17 at 12:54
  • @LinAlg But can't we always just redefine $f$ to be infinity outside of $S$? I don't see that it's necessarily important for $f$ to be convex outside of $S$. – littleO Jan 03 '17 at 15:05
  • What if you want to use an infeasible method? – Michael Grant Jan 03 '17 at 22:03
0

Linear equality constraints are OK in a convex optimization problem because the set of solutions to a linear system of equality constraints is convex. When you have equality constraints involving a nonlinear function of the variables, then you're out of luck.

Brian Borchers
  • 10,563