Nonlinear Opt.: Quadratic Problems 5

Nonlinear Optimization: Quadratic problem

Theory:

In this section we focus on quadratic objective functions with linear restrictions. We do not consider any solution method but proof necessary conditions for solving such qudratic problems. A quadratic objective function consists of linear terms $c_{j}x_{j}$ and quadratic terms $c_{jj}x_{j}^{2}$ and/or $c_{ij}x_{i}x_{j}$ for some or all Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): i \ne j

General form of a Quadratic Problem:

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

Depending on whether we have a maximization or minimization problem we have to transform the quadratic problem into one of these two theorems:

Maximization problem:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(X)=c^T - \frac{1}{2} x^T Cx

Minimization problem:

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

Now we have to proof the objective function for concavity/convexity

Concavity of the objective function is a necessary condition for solving a quadratic maximization problem.

Convexity of the objective function is a necessary condition for solving a quadratic minimization problem.

Are these conditions fullfilled the quadratic problem can be solved by any solution method like the Wolfe`s algorithm.

The maximization problem Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(X)=c^T - \frac{1}{2} x^T Cx

is concave if the symmetric matrix C is positive semidefinite.

The minimization problem $f(X)=c^{T}+{\frac {1}{2}}x^{T}Cx$ is convex if the symmetric matrix C is positive semidefinite.

A symmetric nxn-matrix C is called positive semidefinite if Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x^T Cx \geq 0

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

The symmetric matrix C can also be determined by the Hesse-Matrix

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

For a quadratic maximization problem the Hesse Matrix is Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): H(x)=-C .

For a quadratic minimization problem the Hesse Matrix is $H(x)=C$.

Example:

We have a quadratic optimization problem with an objective function looking like this:

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

Now we transform it into the quadratic form Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(X)=c^T - \frac{1}{2} x^T Cx

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

Now we have to proof that the symmetric matrix C is concave:

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

The matrix C is concave if the main minors are bigger or equal zero.

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

The main minors are all positive => matrix = positive semidefinite, consequently the objective function is concave.

=> The quadratic optimization problem is solvable by the Wolfe`s algorithm.

References:

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

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

Skript Prof. Wendt Operations Research