convex optimization
Imagine a landscape shaped like a single smooth bowl — no false dips, no secret side valleys, just one lowest point. Drop a marble anywhere and it rolls to that one floor; there is nowhere else it could get stuck. Convex optimization is minimizing functions with exactly this magical property: any local minimum is automatically the global minimum, so 'good enough locally' means 'best possible'.
A set is CONVEX if the straight line between any two of its points stays inside it (a disk is convex, a crescent is not). A function f is CONVEX if its graph never bulges above the chord joining any two points — formally f(t a + (1-t) b) <= t f(a) + (1-t) f(b) for 0 <= t <= 1; equivalently, for smooth f, its Hessian is positive semidefinite everywhere (the surface curves up, never down). A convex optimization problem minimizes a convex objective over a convex feasible set. The decisive consequence is that the first-order condition becomes sufficient, not just necessary: if grad f(x*) = 0 (or the appropriate KKT conditions hold), then x* is a GLOBAL minimum — there are no bad local minima or saddles to trap you. Bowls (least squares), linear programs, quadratic programs with positive-definite cost, and many machine-learning losses (logistic regression, SVMs, LASSO) are convex.
This is one of the most important dividing lines in all of optimization: convex problems are, in a strong sense, SOLVABLE — efficient algorithms (interior-point methods, and for the unconstrained case any descent method) find the certified global optimum reliably and fast, with rigorous guarantees. Non-convex problems (most deep neural networks, many design problems) have no such guarantee; you get a local optimum and rarely know how far it is from the best. The honest caveat is that 'convex' is a strong assumption: real problems are often non-convex, and a great deal of practical work goes into either reformulating a problem to be convex (a convex relaxation), or simply accepting that for non-convex training you are hunting for a good local minimum, not the global one. The famous line, due to Rockafellar, is that the great watershed is not linear versus nonlinear, but convex versus non-convex.
Least squares min ||A x - b||_2^2 is convex: its Hessian 2 A^T A is positive semidefinite, so the surface is a single bowl and the normal equations give the unique global minimum. By contrast, a two-layer neural-network loss is non-convex — it has many local minima and saddles, and gradient descent finds one of them, not provably the best.
Convex = one bowl, local optimum is global; non-convex = many traps.
The real watershed in optimization is convex versus non-convex, not linear versus nonlinear. For convex problems a local optimum is certifiably global and solvers are reliable; for non-convex problems (most deep learning) you generally get an unverified local optimum and cannot bound its gap from the global best.