1
$\begingroup$

My teacher in the course Mat-2.3139 presented the same definition as in Wikipedia for the nonlinear programming problem here

enter image description here

but he did not specify what the nonlinearity actually means or what it actually infers. It is a bit hard to make a linear problem into nonlinear without a clear definition for it. So

I. Does the nonlinearity mean nonlinear objective function?

II. For one variable $\bf x$, does the nonlinearity mean that the function is not a linear map? Definition here.

III. or does the NLO mean a problem with nonlinear constraints?

IV. or does the NLO mean a problem with nonlinear constraints and nonlinear objective function?

V. or instead of linear mapping is a NLO problem with an objective function with certain smoothness?

VI. and what kind of requirements a NLO problem require: what kind of convexity assumptions for domain and codomain? Does the function itself need to be convex or concave? More detailed question related to convex optimisation here.

$\endgroup$
  • 1
    $\begingroup$ "Nonlinear" here doesn't refer to a requirement that things not be linear -- it just means you're not restricting yourself to linear things; linear is a special case of nonlinear, though it sounds a bit funny. The real question then is, "What needs to be linear for the problem to be considered linear?" $\endgroup$ – Harry Altman Oct 29 '13 at 23:16
  • $\begingroup$ @HarryAltman Great question! Moved the new question now here. $\endgroup$ – hhh Oct 29 '13 at 23:36
  • $\begingroup$ @hhh: I don't agree that needs a new question; from my answer we can see that to be linear we must have that all of $f$, $g_j$, and $h_i$ are linear. $\endgroup$ – Eric Stucky Oct 29 '13 at 23:39
2
$\begingroup$

Any of I, III or IV would make a problem non-linear.

The answers to VI will probably covered during your course and different convexity conditions may lead to different algorithms.

$\endgroup$
  • $\begingroup$ It would be useful that people say why they are upvoting or downvoting, I think this answer is most helpful even though lacking examples -- answering just "possibly" feels so open. Anyway I am not qualified yet to judge whether something is good or bad, yet. $\endgroup$ – hhh Oct 29 '13 at 23:39
  • $\begingroup$ @hhh: Just fyi: It is polite to give comments for downvotes, especially if you send the overall score to the negatives. But upvotes are cheap, and at least personally when I don't find anything I can answer I often just read the first ten questions and give upvotes to answers pseudo-randomly. $\endgroup$ – Eric Stucky Oct 29 '13 at 23:43
  • $\begingroup$ +1 first line makes sense -- even though I am not expert here, it just makes sense and keeps things simple enough. (I cannot invent now a counter-example where it could not, thinking...) $\endgroup$ – hhh Oct 29 '13 at 23:58
2
$\begingroup$

I. Possibly

II. Possibly.

III. Possibly.

IV. Possibly.

V. Possibly.

VI. None, in general.

If this answer feels vague, that's because it is. There is a wonderful quote about non-linearity. “Classification of mathematical problems as linear and nonlinear is like classification of the Universe as bananas and non-bananas.”

We can see that at play here: non-linearity can creep in at literally any stage of the process. The only thing "non-linear" means is that at least one of the functions $f$, $h_i$, and $g_j$ are non-linear.

$\endgroup$
  • $\begingroup$ So you mean that it is impossible to convert a nonlinear problem into a linear problem? Suppose an objective function let say $x^4-10x^3-2x^2-5$ such that $x>0$ where the goal is to find the minimum. Now its minimum is at the point $\frac 1 8 (3+\sqrt{ 73})$. Now according to the course material, an equivalent problem is a problem with the same minimum: $\min x-\frac 1 8 (3+\sqrt{ 73})$ such that $x-\frac 1 8 (3+\sqrt{ 73})\geq0$ where the minimum is again at $\frac 1 8 (3+\sqrt{ 73})$. So did I change the nonlinear problem into a linear problem or just to totally different linear problem? $\endgroup$ – hhh Oct 29 '13 at 23:47
  • 1
    $\begingroup$ @hhh: In general, we don't consider a problem "the same" as another one just because it has the same answer, which seems to be what happened there. If you had some compelling reason why any situation that could be modeled by the first could be equally well modeled by the second, then we would call them "the same". But if the answers are the same, all you know is that the optimum for the two situations is identical; in particular a near-optimum solution for the two problems might look quite different (even qualitatively). $\endgroup$ – Eric Stucky Oct 29 '13 at 23:51
  • $\begingroup$ Yes I agree but I would really love to know what is the sense behind the questions such as 2 here. (P.s. My teacher said that anyone in the course can ask questions in any place such as Math.Stackexchange and even share answers so this is not cheating but open discussion so what is the pedagogy or the goal behind such questions?) $\endgroup$ – hhh Oct 29 '13 at 23:54

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.