Convexity and Non-convexity¶

Why It Matters¶

Convex problems are tractable - efficient algorithms exist. Non-convex problems are hard - approximations and heuristics are necessary. Knowing which you face sets expectations.

The Key Move¶

Ask: if I average two good solutions, is the average also good? If yes, problem is likely convex. If no (the average could be terrible), problem is non-convex. Non-convexity comes from either-or choices, increasing returns, and threshold effects.

Classic Application¶

Portfolio optimization with just means and variances is convex - averaging two good portfolios gives a good portfolio. Add realistic constraints (minimum trade sizes, integer shares) and it becomes non-convex.

Surprising Application¶

Work schedules. With flexible hours, optimizing is relatively convex. Add constraints like "meetings require synchronous presence," and it becomes non-convex - small schedule changes can have discontinuous effects on feasibility.

Failure Modes¶

• Using convex methods on non-convex problems (will find bad local optima)
• Giving up when problems are non-convex (heuristics often work)
• Ignoring that problem formulation affects convexity

Go Deeper¶

Boyd and Vandenberghe's "Convex Optimization" for the tractable cases.