Nonlinear Opt.: Quadratic Problems 2

Theory

In this section of nonlinear optimization we look for problems which differ only their target function F(x).Besides the linear term $c_{j}x_{j}$ contain also a quadratic form $c_{ij}x_{j}^{2}$ and/or $c_{ij}x_{i}x_{j}$ for some or all i≠j.

We describe some solutions for quadratic maximization problems with a concave target function (and accordingly minimization problems with a convex target function).

At first we define the quadratic form we mean a function which look like: $Q(x)=x^{T}Cx$

X is a column vector of the dimension n ; C is a symmetric (n x n)-matrix with real-valued coefficient $c_{ij}$

So we can convert the quadratic sections of every target function F(x) with a problem in a quadratic optimization like: $Q(x)=x^{T}Cx$

In the first instance we write down the quadratic sections with real-valued coefficients ${\hat {c}}$

${\begin{alignedat}{6}Q(x_{1},...,x_{n})=&&{\hat {c}}_{11}&x_{1}^{2}&+2{\hat {c}}_{12}&x_{1}x_{2}&+2{\hat {c}}_{13}&x_{1}x_{3}&+...&&+2{\hat {c}}_{1n}&x_{n}\\&&&&+{\hat {c}}_{22}&x_{2}^{2}&+2{\hat {c}}_{23}&x_{2}x_{3}&+...&&+2{\hat {c}}_{2n}&x_{n}\\&&&&&&+{\hat {c}}_{33}&x_{3}^{2}&+...&&+2{\hat {c}}_{3n}&x_{n}\\&&&&&&&&&&:\\&&&&&&&&&&+{\hat {c}}_{nn}&x_{n}\end{alignedat}}$

When we symmetrisize the term ($2{\hat {c}}_{ij}$ become $c_{ij}:=c_{ji}:={\hat {c}}_{ij}$), so we can also write :

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

If we sum up the coefficients cij to a symmetric (nxn)-matrix C and the variable xi to a real-valued column vector x, the right side is the product of the row vector $x^{T}$ with the column vector Cx.

If we act on the assumption from the second notation we frame every quadratic maximization problem with linear side donditions like this :

$MaximzieF(x)=c^{T}x+{\frac {1}{2}}x^{T}Cx$

Restriction:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Ax \le b

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \ge 0

In quadratic minimization problems we use the target function :

$MinimizeF(x)=c^{T}x+{\frac {1}{2}}x^{T}Cx$

Example

There is a business that sells two types of insulation stuff. Therefore they use two materials row wood $x_{1}$ and recycled wood wool $x_{2}$. The costs of recycling old furniture and building timber is higher then the raw wood but the recycling type has to contain twice as much recycling material then raw material. In Sum they can only produce 20 units of mixed recycling insulation and unlimited units of pure wood insulation. The business wants to minimize their costs.

$c(x_{1})=x_{1}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c(x_2)=-2x_1+2x_2

Total costs: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_t (x_1,x_2)= x_1^2 -2x_1x_2 +2x_2^2

Restriction:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1,x_2 \ge 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_1+x_2\le 40

The example shows a optimisation problem with linear restriction, similar to the linear optimisation but a quadratic target function. Following we show how to handle/transform this function.

First we transform the problem in the quadratic form: $F(x)=c^{T}x+{\frac {1}{2}}x^{T}Cx$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c(x_1,x_2)= x_1^2 -2x_1x_2 +2x_2^2

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow c(x_1,x_2)= (x_1 -2x_2)x_1)+(2x_2)x_2

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow c(x_1,x_2)= (x_1 -x_2)x_1)+(-x_1+x_2)x_2

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow c(x_1,x_2)= \frac{1}{2} [(2x_1 -2x_2)x_1)+(-2x_1+4x_2)x_2]

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c=\frac{1}{2} \begin{pmatrix} 2&-2 \\ -2&4 \end{pmatrix}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c(x_1,x_2)=\begin{pmatrix} 0 & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} +\frac{1}{2}\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \begin{pmatrix} 2&-2 \\ -2&4 \end{pmatrix} \begin{pmatrix} x_1 & x_2 \end{pmatrix}

Secondly we must proof if it´s a konvex or koncav funktion thus if it´s positiv or negativ definite. It should be positiv definite to represent a global minimum costs.

To test the form of the graph, we draw up the Hesse matrix.

$H(x_{1},x_{2})={\begin{pmatrix}{\frac {d^{2}f}{dx_{1}dx_{1}}}(x)&{\frac {d^{2}f}{dx_{1}dx_{2}}}(x)\\{\frac {d^{2}f}{dx_{2}dx_{1}}}(x)&{\frac {d^{2}f}{dx_{2}dx_{2}}}(x)\end{pmatrix}}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow H(x_1,x_2)= \begin{pmatrix} 2&-2 \\ -2&4 \end{pmatrix}

If the main mintors are bigger (or equal) zero, then the matrix is positiv definit (positiv semidefinit) and is is konvex.

$det{\begin{vmatrix}2\end{vmatrix}}=2$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): det \begin{vmatrix} 2&-2 \\ -2&4 \end{vmatrix} =4

Both mintors are bigger zero and as consequence of konvexity there must be a global minimum of costs. To calculate this, there are diffrent methods e.g. to set the gradient equal to zero and solve it.

Sources

Domschke, Wolfgang, Einführung in Operations Research, Berlin 2005

Domschke, Wolfgang, Übungen und Fallbeispiele zum Operations Research, Berlin 2005

Authors: 369772,380974,375495