Skip to content

Lesson 36: Introduction to Non-Linear Programming

36.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Classify optimisation problems and state what makes a problem non-linear.
  2. Define a convex set and a convex function, and test for each.
  3. Use the Hessian to test convexity of a twice-differentiable function.
  4. State why convexity guarantees that a local optimum is global.
  5. Define unimodality and explain why every method in Lessons 38–41 depends on it.

36.2 Where Linear Programming Stops

Units I and II solved problems in which the objective and all constraints were linear. That assumption bought an enormous amount: the feasible region was a polyhedron, the optimum was at a vertex, and the simplex method could find it by a finite search over corner points.

But linearity is often false:

Situation Why it is non-linear
Economies of scale Cost per unit falls with volume: \(C(x)=ax^{b}\), \(b<1\)
Price depends on quantity sold Revenue \(=p(x)\cdot x\) is quadratic or worse
Portfolio risk Variance \(=\mathbf{x}^{T}\Sigma\mathbf{x}\) is quadratic
Inventory total cost \(\dfrac{C_oD}{Q}+\dfrac{C_hQ}{2}\) — Lesson 31!
Queueing cost \(\dfrac{\rho}{1-\rho}\) — Lesson 24!
Engineering design Stress, drag and heat transfer are non-linear in dimensions

Note that Unit III was already non-linear optimisation: the EOQ derivation set a derivative to zero and checked a second derivative. This unit provides the general theory and the algorithms for cases where no closed-form answer exists.

The general problem

\[\begin{aligned} \text{minimise}\quad & f(\mathbf{x})\\ \text{subject to}\quad & g_i(\mathbf{x})\le 0,\quad i=1,\dots,m\\ & h_j(\mathbf{x})=0,\quad j=1,\dots,p\\ & \mathbf{x}\in\mathbb{R}^{n} \end{aligned}\]

with at least one of \(f,g_i,h_j\) non-linear. Maximising \(f\) is minimising \(-f\), so it suffices to study minimisation.

Classification

Class Objective Constraints Method
Linear programming linear linear simplex (Unit I)
Quadratic programming quadratic linear Wolfe, Beale (L45)
Convex programming convex convex set any local method finds the global optimum
General NLP arbitrary arbitrary local methods only; no global guarantee
Unconstrained any none L37–L42
Separable \(\sum f_i(x_i)\) any piecewise-linear approximation, then LP

What is lost without linearity

  • The optimum need not be at a vertex. It may lie in the interior of the feasible region or anywhere on the boundary. Vertex enumeration is useless.
  • There may be many local optima. A method that finds one has no way to know whether a better one exists elsewhere.
  • There is no finite algorithm. Methods are iterative and converge; they terminate on a tolerance, not on a proof of optimality.

Convexity is what restores the guarantees, which is why it occupies the rest of this lesson.

36.3 Convex Sets

Definition. A set \(S\subseteq\mathbb{R}^n\) is convex if for every \(\mathbf{x},\mathbf{y}\in S\) and every \(\lambda\in[0,1]\), $\(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\in S.\)$ In words: the straight segment joining any two points of the set lies entirely inside the set.

   CONVEX                      NOT CONVEX
    ______                      ______
   /      \                    /      \
  |        |                  |   __   |     the segment between the
  |        |                  |  /  \  |     two marked points leaves
   \______/                    \_/    \_/    the set
     o----o                      o------o

Properties that make convex sets useful.

  • The intersection of convex sets is convex. Hence a feasible region defined by convex constraints is convex.
  • Half-spaces \(\{\mathbf{x}: \mathbf{a}^T\mathbf{x}\le b\}\) are convex, so every LP feasible region is convex — Units I and II were a special case all along.
  • \(\{\mathbf{x}: g(\mathbf{x})\le 0\}\) is convex whenever \(g\) is a convex function.

36.4 Convex Functions

Definition. \(f\) is convex on a convex set \(S\) if for all \(\mathbf{x},\mathbf{y}\in S\) and \(\lambda\in[0,1]\), $\(f\big(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\big)\ \le\ \lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y}).\tag{3.1}\)$ Geometrically: the chord lies on or above the graph. \(f\) is concave if \(-f\) is convex, and strictly convex if the inequality is strict for \(\mathbf{x}\ne\mathbf{y}\) and \(0<\lambda<1\).

The derivative tests

First-order (differentiable \(f\)). \(f\) is convex iff $\(f(\mathbf{y})\ \ge\ f(\mathbf{x})+\nabla f(\mathbf{x})^{T}(\mathbf{y}-\mathbf{x}) \quad\text{for all }\mathbf{x},\mathbf{y}. \tag{3.2}\)$ The tangent plane lies on or below the graph everywhere — so a tangent gives a global underestimate, which is the basis of cutting-plane methods.

Second-order (twice differentiable \(f\)). $\(f \text{ convex}\iff \nabla^{2}f(\mathbf{x})\ \text{is positive semi-definite for all }\mathbf{x}.\)$ In one dimension this is simply \(f''(x)\ge0\).

Testing a 2×2 Hessian

For \(H=\begin{pmatrix}a & b\\ b& c\end{pmatrix}\) (Hessians are symmetric):

Condition Classification Meaning for \(f\)
\(a>0\) and \(\det H=ac-b^2>0\) positive definite strictly convex
\(a\ge0\), \(c\ge0\), \(\det H\ge0\) positive semi-definite convex
\(a<0\) and \(\det H>0\) negative definite strictly concave
\(\det H<0\) indefinite neither — a saddle

Equivalently, compute the eigenvalues: all positive \(\Rightarrow\) positive definite, mixed signs \(\Rightarrow\) indefinite.

Operations that preserve convexity

If \(f\) and \(g\) are convex, so are:

  • \(\alpha f\) for \(\alpha\ge0\); \(\ f+g\); \(\ \max\{f,g\}\);
  • \(f(A\mathbf{x}+\mathbf{b})\) — composition with an affine map;
  • \(h(f(\mathbf{x}))\) when \(h\) is convex and non-decreasing.

These rules let one certify convexity of a complicated expression without ever touching a Hessian — the technique used by modern convex-optimisation software.

36.5 Why Convexity Matters

Theorem (the fundamental result of convex optimisation). If \(f\) is convex and \(S\) is a convex set, then every local minimum of \(f\) over \(S\) is a global minimum. If \(f\) is strictly convex, the minimum is unique.

Proof. Let \(\mathbf{x}^{*}\) be a local minimum and suppose some \(\mathbf{y}\in S\) has \(f(\mathbf{y})<f(\mathbf{x}^{*})\). For \(\lambda\in(0,1)\) the point \(\mathbf{z}_\lambda=\lambda\mathbf{y}+(1-\lambda)\mathbf{x}^{*}\) lies in \(S\) (convex set) and by (3.1)

\[f(\mathbf{z}_\lambda)\le\lambda f(\mathbf{y})+(1-\lambda)f(\mathbf{x}^{*})<f(\mathbf{x}^{*}).\]

Taking \(\lambda\) small enough puts \(\mathbf{z}_\lambda\) inside any neighbourhood of \(\mathbf{x}^{*}\), contradicting local minimality. ∎

This is the whole reason convexity is worth checking. Without it, an algorithm that stops at a point where the gradient vanishes has proved nothing about global optimality. With it, the same computation has solved the problem.

The practical divide in optimisation is not linear versus non-linear. It is convex versus non-convex.

36.6 Unimodality

The one-dimensional methods of Lessons 38–41 need less than convexity.

Definition. \(f\) is unimodal on \([a,b]\) if there is an \(x^{*}\in[a,b]\) such that \(f\) is strictly decreasing on \([a,x^{*}]\) and strictly increasing on \([x^{*},b]\).

A unimodal function has exactly one local minimum, which is therefore global. It need not be convex, continuous or differentiable.

The elimination property — the engine of every search method in this unit. Let \(a<x_1<x_2<b\) with \(f\) unimodal. Then $\(f(x_1)<f(x_2)\Rightarrow x^{*}\in[a,x_2];\qquad f(x_1)>f(x_2)\Rightarrow x^{*}\in[x_1,b].\)$ Two function evaluations delete part of the interval and keep the minimum.

Proof of the first case. If \(x^{*}>x_2\) then \(f\) is decreasing on \([a,x^{*}]\supseteq[x_1,x_2]\), so \(f(x_1)>f(x_2)\) — a contradiction. Hence \(x^{*}\le x_2\). ∎

The warning. If \(f\) is not unimodal, the elimination step can throw away the interval containing the true minimum, and every method in Lessons 38–41 will converge confidently to the wrong answer. Verify or ensure unimodality before trusting a line search — usually by plotting.

36.7 Solved Problems

Problem 1 — Testing convexity of a set

Is \(S=\{(x_1,x_2): x_1^{2}+x_2^{2}\le 4,\ x_1+x_2\ge1\}\) convex?

Solution.

\(S=S_1\cap S_2\) with \(S_1=\{x_1^2+x_2^2\le4\}\) and \(S_2=\{x_1+x_2\ge1\}\).

\(S_1\): the constraint is \(g_1(\mathbf{x})=x_1^2+x_2^2-4\le0\). The Hessian is \(\nabla^2g_1=\begin{pmatrix}2&0\\0&2\end{pmatrix}\), which has eigenvalues \(2,2>0\): positive definite, so \(g_1\) is convex and its sublevel set \(S_1\) is a convex set (a disc).

\(S_2\): a half-space \(\{-x_1-x_2+1\le0\}\), defined by a linear function — convex.

Intersection: the intersection of convex sets is convex.

\[\boxed{S\text{ is convex}}\]

Contrast. \(\{x_1^2+x_2^2\ge4\}\) — the outside of the disc — is not convex: the segment from \((-2,0)\) to \((2,0)\) passes through the origin, which is excluded. A convex function's sublevel set (\(\le\)) is convex; its superlevel set (\(\ge\)) generally is not. This is exactly why a \(\ge\) constraint on a convex function makes an NLP hard.

Problem 2 — Classifying a quadratic function

Classify \(f(x_1,x_2)=2x_1^{2}+3x_2^{2}+4x_1x_2-6x_1-3x_2+8\), and find its stationary point.

Solution.

Step 1 — the gradient.

\[\nabla f=\begin{pmatrix}4x_1+4x_2-6\\ 6x_2+4x_1-3\end{pmatrix}\]

Step 2 — the Hessian (constant, since \(f\) is quadratic).

\[H=\begin{pmatrix}4&4\\4&6\end{pmatrix}\]

Step 3 — classify.

\[a=4>0,\qquad \det H=4(6)-4^2=24-16=8>0\]

Both leading principal minors are positive \(\Rightarrow\) \(H\) is positive definite \(\Rightarrow\) \(f\) is strictly convex.

Eigenvalue check: \(\mathrm{tr}=10\), \(\det=8\), so \(\lambda=\dfrac{10\pm\sqrt{100-32}}{2} =\dfrac{10\pm8.2462}{2}=9.1231,\ 0.8769\) — both positive ✓.

Step 4 — the stationary point. Solve \(\nabla f=\mathbf{0}\):

\[4x_1+4x_2=6,\qquad 4x_1+6x_2=3\]

Subtracting: \(2x_2=-3\), so \(x_2=-1.5\) and \(4x_1=6-4(-1.5)=12\), giving \(x_1=3\).

\[\boxed{\mathbf{x}^{*}=(3,\,-1.5)}\]
\[f(\mathbf{x}^{*})=2(9)+3(2.25)+4(3)(-1.5)-6(3)-3(-1.5)+8=18+6.75-18-18+4.5+8=\mathbf{1.25}\]

Conclusion. Because \(f\) is strictly convex, \((3,-1.5)\) is the unique global minimum. No further search is needed — the convexity test converted a local statement into a global one.

Problem 3 — A saddle point

Classify \(f(x_1,x_2)=x_1^{2}-x_2^{2}+2x_1x_2\) at its stationary point.

Solution.

\[\nabla f=\begin{pmatrix}2x_1+2x_2\\ -2x_2+2x_1\end{pmatrix}=\mathbf{0} \ \Rightarrow\ x_1=-x_2 \text{ and } x_1=x_2 \ \Rightarrow\ \mathbf{x}^{*}=(0,0)\]
\[H=\begin{pmatrix}2&2\\2&-2\end{pmatrix},\qquad \det H=2(-2)-4=-8<0\]

Indefinite — eigenvalues \(\lambda=\pm\sqrt{8}=\pm2.828\), of opposite signs.

\[\boxed{(0,0)\text{ is a SADDLE POINT, neither a maximum nor a minimum}}\]

Verification along two lines.

  • Along \(x_2=0\): \(f=x_1^2\ge0\), a minimum at the origin.
  • Along \(x_1=0\): \(f=-x_2^2\le0\), a maximum at the origin.

The function rises in one direction and falls in another — the shape of a horse's saddle.

Interpretation. \(\nabla f=\mathbf{0}\) is necessary but not sufficient. This is exactly why every gradient-based algorithm needs a second-order check, and why saddle points are the principal obstacle in modern high-dimensional optimisation: in \(n\) dimensions, a random stationary point is far more likely to be a saddle than a minimum.

Problem 4 — Convexity of the EOQ cost function

Show that \(TC(Q)=\dfrac{C_oD}{Q}+\dfrac{C_hQ}{2}\) is strictly convex for \(Q>0\), and comment on what this proves about Lesson 31.

Solution.

\[\frac{dTC}{dQ}=-\frac{C_oD}{Q^{2}}+\frac{C_h}{2},\qquad \frac{d^{2}TC}{dQ^{2}}=\frac{2C_oD}{Q^{3}}\]

For \(Q>0\) and \(C_o,D>0\) we have \(\dfrac{d^2TC}{dQ^2}>0\) everywhere, so \(TC\) is strictly convex on \((0,\infty)\).

\[\boxed{Q^{*}=\sqrt{2C_oD/C_h}\text{ is the UNIQUE GLOBAL minimum}}\]

Interpretation. Lesson 31 set the derivative to zero and checked the second derivative — which is precisely the convexity test of §3.1 in one dimension. The claim "this is a global minimum" was justified by convexity, not by the derivative alone. Without convexity, \(\frac{dTC}{dQ}=0\) would have located only a candidate.

The same argument covers the queueing cost of Lesson 25: \(TC(\mu)=\dfrac{C_w\lambda}{\mu-\lambda}+C_s\mu\) has \(\dfrac{d^2TC}{d\mu^2}=\dfrac{2C_w\lambda}{(\mu-\lambda)^3}>0\) for \(\mu>\lambda\) — strictly convex, so \(\mu^{*}\) is the unique global optimum. Unit III relied on convexity throughout without naming it.

Problem 5 — Unimodality and its failure

Is \(f(x)=x^{4}-4x^{2}+x\) unimodal on \([-2.5,\,2.5]\)? Find its stationary points and say what a golden-section search would do at its first step.

Solution.

\[f'(x)=4x^{3}-8x+1,\qquad f''(x)=12x^{2}-8\]

Solving the cubic \(4x^{3}-8x+1=0\) numerically gives three stationary points:

\(x\) \(f''(x)\) Type \(f(x)\)
\(-1.47300\) \(+18.037\) local minimum \(\mathbf{-5.44419}\)
\(0.12600\) \(-7.810\) local maximum \(0.06275\)
\(1.34700\) \(+13.773\) local minimum \(-2.61856\)
\[\boxed{\text{NOT unimodal — two local minima separated by a local maximum}}\]

The global minimum is \(x=-1.4730\) with \(f=-5.4442\); the minimum at \(x=1.3470\) is more than \(2.8\) units worse and is a trap for any method that lands near it.

What golden-section search would do at its first step. The two probes on \([-2.5,\,2.5]\) are

\[x_1=-2.5+0.382(5)=-0.59017,\qquad x_2=-2.5+0.618(5)=+0.59017\]
\[f(x_1)=-1.86206,\qquad f(x_2)=-0.68172\]

Since \(f(x_1)<f(x_2)\), the elimination rule discards \([0.59017,\ 2.5]\) and keeps \([-2.5,\ 0.59017]\) — which does contain the global minimum, so the step was correct.

Interpretation. But the correctness was luck, not logic. The elimination rule is a theorem only for unimodal functions; here it happened to point the right way because the deeper minimum lies on the side with the lower probe. Shift the function to \(f(x)=x^4-4x^2-x\) — a mirror image — and the same rule discards the left half at the first step, again correctly. Perturb the two minima so that the shallower one sits nearer the probes and the rule will confidently delete the interval containing the answer, reporting a local minimum as though it were global. Nothing in the output would reveal the error.

Always plot the function, or bracket the minimum first (Lesson 38), before running an elimination method. The standard remedies for multi-modal problems are multi-start from several brackets, a coarse grid search followed by local refinement, or a global method such as simulated annealing. None is free — which is why so much effort in practice goes into reformulating problems to be convex.

36.8 Practice Problems

  1. Is \(f(x_1,x_2)=x_1^2+4x_2^2-2x_1x_2\) convex? (Answer: \(H=\begin{pmatrix}2&-2\\-2&8\end{pmatrix}\), \(a=2>0\), \(\det=12>0\) — positive definite, strictly convex)
  2. Classify the stationary point of \(f=x_1^2+x_2^2+x_1x_2-3x_1\). (Answer: \(\nabla f=0\) at \((2,-1)\); \(H=\begin{pmatrix}2&1\\1&2\end{pmatrix}\), \(\det=3>0\) — a strict global minimum, \(f=-3\))
  3. Show that \(\{(x_1,x_2): x_1x_2\ge1,\ x_1>0\}\) is convex. (Hint: \(-\ln x_1-\ln x_2\le0\) and \(-\ln\) is convex.)
  4. Is \(f(x)=x^3\) convex on \(\mathbb{R}\)? On \([0,\infty)\)? (Answer: no — \(f''=6x<0\) for \(x<0\); yes on \([0,\infty)\). Convexity depends on the domain.)
  5. Give an example of a function that is unimodal but not convex, and one that is convex but not differentiable. (Answers: \(f(x)=\sqrt{\lvert x\rvert}\) is unimodal, not convex; \(f(x)=\lvert x\rvert\) is convex, not differentiable at \(0\).)

36.9 Summary

  • Non-linearity destroys the guarantees of LP: the optimum need not be at a vertex, local optima may be many, and algorithms become iterative rather than finite.
  • A set is convex if it contains every segment between its points. Intersections of convex sets are convex; sublevel sets \(\{g\le0\}\) of convex \(g\) are convex.
  • A function is convex if every chord lies above the graph; equivalently every tangent lies below it; equivalently \(\nabla^{2}f\succeq0\).
  • \(2\times2\) test: \(a>0\) and \(\det H>0\) \(\Rightarrow\) positive definite (strictly convex); \(\det H<0\) \(\Rightarrow\) indefinite (saddle).
  • The fundamental theorem: for a convex \(f\) on a convex set, every local minimum is global, and strict convexity makes it unique. This is the property worth checking before anything else.
  • The real divide in optimisation is convex versus non-convex, not linear versus non-linear.
  • \(\nabla f=\mathbf{0}\) is necessary, not sufficient: it also holds at maxima and saddles.
  • Unimodality — one minimum, decreasing then increasing — is all the one-dimensional methods need. Its elimination property is the engine of Lessons 38–41, and it fails silently on multi-modal functions.
  • Unit III's EOQ and queueing-cost results were convex optimisation problems all along.

Next lesson: L37 — Conditions for unconstrained optimality in one and several variables.

Practise now: unit4-nlp-search-lab.html → Convexity Explorer: type a function, see its graph, Hessian, eigenvalues and a live convex/concave/saddle verdict.