Nonlinear Opt.: Quadratic Problems 5: Unterschied zwischen den Versionen

Aktuelle Version vom 14. August 2013, 00:26 Uhr

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 ${\displaystyle c_{j}x_{j}}$ and quadratic terms ${\displaystyle c_{jj}x_{j}^{2}}$ and/or ${\displaystyle 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:

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:

${\displaystyle 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 ${\displaystyle 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

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 ${\displaystyle H(x)=C}$.

Example:

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

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

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

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

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