Nonlinear Opt.: Quadratic Problems 5: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(Die Seite wurde neu angelegt: „ == Nonlinear Optimization: Quadratic problem == '''Theory:''' In this section we focus on quadratic objective functions with linear restrictions. We do no…“) |
(→Nonlinear Optimization: Quadratic problem) |
||
(4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 15: | Zeile 15: | ||
Depending on whether we have a maximization or minimization problem we have to transform the quadratic problem into one of these two theorems: | 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:''' | '''Maximization problem:''' | ||
Zeile 25: | Zeile 26: | ||
− | Now we have to proof the objective function for concavity/ | + | Now we have to proof the objective function for concavity/convexity |
'''Concavity''' of the objective function is a necessary condition for solving a | '''Concavity''' of the objective function is a necessary condition for solving a | ||
Zeile 36: | Zeile 37: | ||
− | The maximization problem <math>f(X)=c^T - \frac{1}{2} x^T Cx</math> | + | The maximization problem <math>f(X)=c^T - \frac{1}{2} x^T Cx</math> is concave if the symmetric matrix C is positive semidefinite. |
+ | |||
+ | The minimization problem <math>f(X)=c^T + \frac{1}{2} x^T Cx</math> is convex if the symmetric matrix C is positive semidefinite. | ||
+ | |||
A symmetric nxn-matrix C is called positive semidefinite if <math>x^T Cx \geq 0</math> for all <math>x \ne 0</math> . | A symmetric nxn-matrix C is called positive semidefinite if <math>x^T Cx \geq 0</math> for all <math>x \ne 0</math> . | ||
Zeile 44: | Zeile 48: | ||
[[Datei:Or4.JPG]] | [[Datei:Or4.JPG]] | ||
− | For | + | For a quadratic maximization problem the Hesse Matrix is <math>H(x)=-C</math>. |
− | + | ||
+ | For a quadratic minimization problem the Hesse Matrix is <math>H(x)=C</math>. | ||
== Example: == | == Example: == | ||
Zeile 71: | Zeile 75: | ||
− | The main minors are positive => matrix = positive | + | 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. | => The quadratic optimization problem is solvable by the Wolfe`s algorithm. | ||
− | |||
== References: == | == References: == |
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 and quadratic terms and/or 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:
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 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 .
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