Boyd and Vandenberghe say that a convex optimization problem is one of the form:

minimize $f_0(x)$ subject to $$f_i(x)\le 0, i=1,\ldots m$$ $$a_i^\top x=b_i, i=1,\ldots p$$

where $f_0, \ldots,f_m$ are convex functions and the equality constraint functions must be affine.

My question is, what stops me from converting the equality constraint functions into inequalities so that I am no longer restricted to affinity with those functions? (any equality $a=b$ can be expressed as $a\le b$ and $a \ge b$).

  • 6
    $\begingroup$ An equality constraint of the form $f(x) = 0$ where $f$ is nonlinear is not convex. Imagine if the constraint was that the points should lie on the surface of a sphere. Is this what you're getting at ? $\endgroup$ Apr 27, 2014 at 20:20
  • 1
    $\begingroup$ What Suresh said. The problem is that for a convex $f$, to express $f(x) = 0$ as a pair of inequalities, you need to write $f(x) \leq 0$ (which is allowed in a convex optimization problem), as well as $f(x) \geq 0$ (which is not allowed) $\endgroup$
    – Aaron Roth
    Apr 27, 2014 at 20:54
  • $\begingroup$ Thanks for the comments, this was the kind of comments that I was looking for. $\endgroup$
    – ASDF
    Apr 27, 2014 at 21:18
  • $\begingroup$ I don't think anything technically stops you from having all constraints be of the form $f_i(x) \leq 0$ for convex $f_i$: $a_i^\top x - b_i$ is both convex and concave so it is fine to write two constraints in the way you described. $\endgroup$ Apr 28, 2014 at 1:30
  • 1
    $\begingroup$ However, it is often convenient to treat the affine constraints separately. For example, by Slater's condition strong duality holds if there exists a primal feasible solution which is strictly feasible for all non-affine constraints. $\endgroup$ Apr 28, 2014 at 4:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.