Nonlinear Opt.: Quadratic Problems 1

Quadratic Problems have a quadratic objective function which is maximized or minimized subject to linear constraints and nonnegativity restrictions on the variables. The objective functions involve the square of a variable Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{jj}\cdot x_j^2

or the product of two variables Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}\cdot x_i\cdot x_j

.

---

Introduction

Several efficient algorithms have been developed for this case under the assumption that F(x) is concave for maximization problems and convex for minimization problems. One of the most known of these algorithms may be the Wolfe algorithm (also known as the modified simplex method). In this article we just provide the preparatory work for applying the algorithm. So far it is not solving the quadratic problems. The methods shown here will not be suitable solving not-concave, quadratic problems.

At first the quadratic form should be defined, with which the quadratic components of a objective function F(x) can be expressed:

$F(x)=x^{T}Cx$

Standard quadratic problems may be formulated as follows:

Maximization problems

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x)=cx-\frac{1}{2}x^TCx

subject to the constraints

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

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

with:c row vector, x and b column vector,C andA matrices, subscript T denotes transpose.

The elements of C are given constants such that $c_{ji}=c_{ji}$ (which is the reason for the factor of 1/2 in the objective function)

Minimization problems

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

If a quadratic objective function F(x) is concave or convex depends on the quadratic form and thus on the characteristics of the matrix C.

A function Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x)=c^Tx-\frac{1}{2}x^TCx
(resp. $F(x)=c^{T}x+{\frac {1}{2}}x^{T}Cx$) is concave (convex) if the symmetric matrix C is positive semidefinite.

Positive semidefinite means all eigenvalues are equal or greater than 0.

Taking a closer look on

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max F(x)=c^Tx-\frac{1}{2}x^TCx

constraints:

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

it is obvious that Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): H(x)=-C

applies

That means C is determinable right out of the Hessian matrix.

Example

Maximize

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

subject to
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1+x_2\leq 30
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1, x_2\geq 0 .

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

Just taking the quadratic components of the objective function and transforms it into the Form Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x)=c^Tx-1/2x^TCx

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x_1,x_2)=-2x_1^2+4x_1x_2-4x_2^2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): =(-2x_1+4x_2)x_1+(-4x_2)x_2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): =(-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.): =-\frac{1}{2}(4x_1-4x_2)x_1+(-4x_1+8x_2)x_2 .

Going with the Hessian-Matrix: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): H(x)=\begin{pmatrix}\frac{{\partial^2 f}}{{\partial^2 x_1}} & \frac{{\partial^2 f}}{{\partial x_1}{\partial x_2}} \\ \frac{{\partial^2 f}}{{\partial x_1}{\partial x_2}} & \frac{{\partial^2 f}}{{\partial^2 x_2}}\end{pmatrix}=\begin{pmatrix} -4 & 4 \\ 4 & -8 \end{pmatrix}
with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): H(x)=-C
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{pmatrix} -4 & 4 \\ 4 & -8 \end{pmatrix}=-1\cdot \begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix}

If the form of equation Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max F(x)=c^Tx-\frac{1}{2}x^TCx

is applied, the solution would be:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max F(x)= (15,30)\binom{x_1}{x_2}-\frac{1}{2}(x_1,x_2)\begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix}\binom{x_1}{x_2}

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

(symmetric matrix C)

One can easily transform the quadratic components of every objective function $F(x)$ to the form shown above. Writing down the quadratic components with a real coefficient ${\tilde {c}}_{ij}$ provides the following equation:

$Q\left(x_{1},...,x_{n}\right)={\tilde {c}}_{11}x_{1}^{2}+2{\tilde {c}}_{12}x_{1}x_{2}+2{\tilde {c}}_{13}x_{1}x_{3}+...+2{\tilde {c}}_{1n}x_{1}x_{n}+$
${\tilde {c}}_{22}x_{2}^{2}+2{\tilde {c}}_{23}x_{2}x_{3}+...+2{\tilde {c}}_{2n}x_{2}x_{n}+$
${\tilde {c}}_{33}x_{3}^{2}+...+2{\tilde {c}}_{3n}x_{3}x_{n}+$
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \vdots
$+{\tilde {c}}_{nn}x_{n}^{2}$.

After symmetrizising the expression ($2{\tilde {c}}_{ij}$ becomes $c_{ij}=c_{ji}={\tilde {c}}_{ij}$) one can write as well:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Q\left(x_{1},...,x_{n}\right)=x_{1}\left(c_{11}*x_{1}+c_{12}x_{2}+...+c_{1n}x_{n} \right)+
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}*\left(c_{21}x_{1}+c_{22}x_{2}+...+c_{2n}x_{n} \right)+
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \vdots
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): +x_{n}*\left(c_{n1}x_{1}+c_{n2}x_{2}+...+c_{nn}x_{n}\right) .

Aggregating the coefficients $c_{ij}$ to a symmetric (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): n \times n )-Matrix C and the variables $x_{i}$ to a real column vector $x$, supplies the right side as a product of the row vector $x^{T}$ with the column vector $Cx$.

Now we need to prove the matrix C is positive semidefinite:

A symetric matrix is positive semidefinite if all eigenvalues are equal or grater than 0.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): C=\begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix} \Rightarrow C-\lambda E=\begin{pmatrix} 4-\lambda & -4 \\ -4 & 8-\lambda \end{pmatrix}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): det(C-\lambda E)=(4-\lambda)(8-\lambda )-(-4)(-4)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): =32-4\lambda -8\lambda +\lambda ^2-16
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): =\lambda ^2-12\lambda +16

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_{1/2}=\frac{12\pm \sqrt{(-12)^2-4\cdot 1\cdot 16}}{2\cdot 1}=\frac{12\pm \sqrt{144-64}}{2}=\frac{12\pm \sqrt{80}}{2}=\frac{12\pm 4\sqrt{5}}{2}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_1=\frac{12+4\sqrt{5}}{2}\approx 10{,}4721
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_2=\frac{12-4\sqrt{5}}{2}\approx 1{,}52786

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

all of the eigenvalues are positive, for this reason the matrix C is positive semidefinite and therewith the objective function is concave.

References

Müller-Merbach, Operations Research : Methoden und Modelle der Optimalplanung, Vahlen, München, 1973
Domschke, Einführung in Operation Research, 2011, Springer-Verlag
Martos, "Nonlinear programming theory & methods", 1975, North Holland Publishing Company
Mangasarian, "Nonlinear Programming", 1969, Tata McGraw-Hill Publishing Comp. Ltd.
Vajda, "Theory of linear and non-linear programming", 1974, William Clowes & Sons Ltd.
Hillier, Liebermann, "Introduction to Operations Research", 4.Edition, 1986, Holden-Day Inc.
Peressini, Sullivan, Uhl, "The mathematics of nonlinear Programming", 1988, Springer-Verlag