Does convex optimization belong to linear programming or nonlinear programming?
Is convex optimization an undergraduate topic or a graduate topic?
$\begingroup$
$\endgroup$
1
-
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$– littleOFeb 21, 2015 at 8:53
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
5
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
answered Jun 14, 2014 at 1:20
-
$\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$– DigioFeb 25, 2019 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$ Feb 25, 2019 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$– DigioFeb 25, 2019 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$ Feb 25, 2019 at 14:40
-
$\begingroup$
$\endgroup$
For the first question, the following image will clear this up to you
For the second question, it depends on the university. However, I've noticed that convex optimization is usual a graduate topic for most universities (including mine).
