mathematics//optimization//convex optimization

Convex optimization is the class of optimization problems whose cost function is convex and whose set of allowed points is convex, so that every local minimum is the global one; it matters to an engineer because these are the problems that solvers handle reliably, quickly and with a proof of optimality, which is why linear MPC, least squares, LQR and logistic regression can run unattended in products. A function is convex when the chord between any two points of its graph lies on or above the graph.

Convex optimization is the class of optimization problems whose cost function is convex and whose set of allowed points is convex, so that every local minimum is the global one; it matters to an engineer because these are the problems that solvers handle reliably, quickly and with a proof of optimality, which is why linear MPC, least squares, LQR and logistic regression can run unattended in products. A function is convex when the chord between any two points of its graph lies on or above the graph.

f(θx+(1−θ)y)  ≤  θf(x)+(1−θ)f(y),0≤θ≤1f\big(\theta x+(1-\theta)y\big)\;\le\;\theta f(x)+(1-\theta)f(y),\qquad 0\le\theta\le1f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y),0≤θ≤1

Picture a bowl against a mountain range. On the bowl, walking downhill from anywhere ends at the bottom, and the slope at a point says in which direction the bottom lies. On the range a descent can stop in a side valley that is far from the lowest one, and nothing at that point reveals it. The members most used in engineering are least squares, the linear program and the quadratic program, with second-order cone and semidefinite programs for problems with norms and matrix inequalities.

The great divide of optimization runs between convex and non-convex. A convex formulation buys a single optimum, algorithms with guarantees and solve times that can be bounded, which is what certification and a real-time deadline need; so the first move with a new problem is to try to write it as convex.

Convexity comes with a certificate. Interior-point and similar solvers track a dual bound alongside the solution (duality), so they stop when the gap is provably small and report reliably when the problem has no solution. Modelling tools such as cvxpy check that a formulation is convex before solving it.

Convexity is lost as soon as the model is nonlinear inside a constraint or the cost has several valleys. A nonlinear MPC and the training of a neural network (loss landscape) live there: the result depends on where the solver starts and the solve time varies. A common remedy is to convexify locally and repeat (sequential quadratic programming), one more case of linearize-solve-repeat.

The reference is Boyd and Vandenberghe's Convex Optimization, which the book recommends for knowing when an optimization problem has a reliable solution.