Does convex optimization belong to linear programming or nonlinear programming?

Is convex optimization an undergraduate topic or a graduate topic?

  • 1
    $\begingroup$ "The great watershed in optimization isn't between linearity and nonlinearity, but convexity and nonconvexity." -- R. Tyrrell Rockafellar, in SIAM Review, 1993 $\endgroup$ – littleO Feb 21 '15 at 8:53

To answer your first question: note there exists non linear convex shapes. So yes it is non linear programming

To answer the second, it really depends what you do. Plenty of undergraduates study it but it is also common for grad students

  • $\begingroup$ According to all sources I've come across, this answer is wrong. Convex optimization can be both linear and non-linear, however linear optimization is always a special case of convex optimization. $\endgroup$ – Digio Feb 25 at 8:43
  • $\begingroup$ I’m not sure what you disagree with, I’ve basically said exactly what you commented. If you leave a quote I can clear up any confusion. $\endgroup$ – frogeyedpeas Feb 25 at 12:02
  • $\begingroup$ Maybe I got this wrong, but I understood you were implying that convex optimization is classified under nonlinear programming (which would not be true). $\endgroup$ – Digio Feb 25 at 14:25
  • $\begingroup$ I would stand by that statement. Here’s why: $\text{linear programming } \subset \text{convex optimization} \subset \text{non linear programming}$ so if you have to describe “convex optimization” as either “linear programming” or “non-linear programming” I would confidently pick “non linear programming”. That isn’t to say they are the same; they are certainly very different; but formally speaking convex optimization lies within the domain of non linear programming. $\endgroup$ – frogeyedpeas Feb 25 at 14:40
  • $\begingroup$ I guess that makes sense. $\endgroup$ – Digio Jun 7 at 7:40

Convex optimization involves minimizing a convex objective function (or maximizing a concave objective function) over a convex set of constraints.

Linear programming is a special case of convex optimization where the objective function is linear and the constraints consist of linear equalities and inequalities.

Nonlinear programming concerns optimization where at least one of the objective function and constraints is nonlinear.

(Adapted from Mathematical optimization: Major subfields on Wikipedia.)

Therefore, convex optimization overlaps both linear and nonlinear programming, being a proper superset of the former and a proper subset of the latter. However, note that nonlinear programming, while technically including convex optimization (and excluding linear programming), can be used to refer to situations where the problem is not known to be convex (see Boyd and Vandenberghe, p. 9, below). Hence, it may be more useful in practice to think of a hierarchy: linear - convex - nonlinear. Another useful view is given by the following quote, kindly supplied by littleO: "The great watershed in optimization isn't between linearity and nonlinearity, but convexity and nonconvexity." -- R. Tyrrell Rockafellar, in SIAM Review, 1993

Whether convex optimization is an undergraduate topic or a graduate topic is not easily answered: it could be either advanced undergraduate or graduate, depending on the institution and department. For instance, Convex Optimization by Boyd and Vandenberghe has been used for a graduate course, but according to the authors, the required background is linear algebra and advanced calculus. Thus, it would appear that it could be used at the advanced undergraduate level with the proviso, mentioned in the preface, that knowledge of mathematical analysis and probability is beneficial to follow some of the details.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.