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$ – Suresh Venkat Apr 27 '14 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 '14 at 20:54
  • $\begingroup$ Thanks for the comments, this was the kind of comments that I was looking for. $\endgroup$ – ASDF Apr 27 '14 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$ – Sasho Nikolov Apr 28 '14 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$ – Sasho Nikolov Apr 28 '14 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.