> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/math/optimization.md).

# optimization

## Basic idea

Optimization studies how to minimize or maximize objectives under constraints. In computer science it supplies algorithms, relaxations, bounds, and certificates for scheduling, flows, matching, learning, verification, and approximation.

## Key formulas

* Primal form: minimize $c^Tx$ subject to $Ax\ge b$.
* Dual variables attach prices or certificates to primal constraints.
* Weak duality bounds every primal feasible objective by every dual feasible objective.
* Strong duality equates optimal primal and dual values under the relevant hypotheses.
* Von Neumann minimax equates maximin and minimax values for finite two-player zero-sum games.
