Optimization Methods

Optimization is the branch of mathematics which faces the problem of selecting a best element (with respect to some criteria) from some set of available alternatives. A general optimization problem can be represented in the following way: <math display='block'> <mtable columnalign='left'> <mtr> <mtd> <mi>max</mi><mtext>&#x2003;</mtext><mi>f</mi><mrow><mo>(</mo> <mi>x</mi> <mo>)</mo></mrow> </mtd> </mtr> <mtr> <mtd> <mtext>&#x2009;</mtext><mtext>&#x2009;</mtext><mi>s</mi><mo>.</mo><mi>t</mi><mo>.</mo><mtext>&#x2003;</mtext><mi>x</mi><mo>&#x2208;</mo><mi>X</mi> </mtd> </mtr> </mtable> </math>$$\begin{gathered} \max \quad f\left( x \right) \hfill \\ \,\;s.t.\quad x\in X \hfill \\ \end{gathered}$$ where f maps the elements of a set A to the set of real numbers and X ⊆ A is the set of choices. The simplest optimization problem consists in maximizing a real function over an allowed set. By convention, here the standard form of an optimization problem is stated in terms of maximization, but it is always possible to switch from minimization to maximization using the relationship <math display='block'> <mrow> <munder> <mrow> <mi>min</mi> </mrow> <mrow> <mi>x</mi><mo>&#x2208;</mo><mi>X</mi> </mrow> </munder> <mi>f</mi><mrow><mo>(</mo> <mi>x</mi> <mo>)</mo></mrow><mo>=</mo><mo>&#x2212;</mo><munder> <mrow> <mi>max</mi> </mrow> <mrow> <mi>x</mi><mo>&#x2208;</mo><mi>X</mi> </mrow> </munder> <mrow><mo>(</mo> <mrow> <mo>&#x2212;</mo><mi>f</mi><mrow><mo>(</mo> <mi>x</mi> <mo>)</mo></mrow> </mrow> <mo>)</mo></mrow><mo>.</mo> </mrow> </math>$$\mathop{{\min }}\limits_{{x\in X}}f\left( x \right)=-\mathop{{\max }}\limits_{{x\in X}}\left( {-f\left( x \right)} \right).$$ Optimization problems are commonly divided into classes, depending on the mathematical properties of the function f and the geometrical form of X. For every class of problems suitable optimization methods have been developed. When f is a linear function of x, and X can be described using linear (in)equalities, then the problem is said to be a Linear Optimization Problem. This is the subject of Section 2.1. When f is not linear, but constraints satisfy some regularity conditions, then the algorithm to solve the optimization problems differs from the linear case. This is the subject of Section 2.2. Finally, when the quantity we want to optimize is uncertain (for example the profit and loss of a trading position on a stock market), then the optimization problem is called stochastic and the solution methods are slightly different from the deterministic case. This is the subject of Section 2.5.