Nonlinear Opt.: Quadratic Problems 5: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(→Nonlinear Optimization: Quadratic problem) |
(→Nonlinear Optimization: Quadratic problem) |
||
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
Zeile 38: | Zeile 38: | ||
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 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. | 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. | ||
Zeile 48: | Zeile 49: | ||
For a quadratic maximization problem the Hesse Matrix is <math>H(x)=-C</math>. | 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>. | For a quadratic minimization problem the Hesse Matrix is <math>H(x)=C</math>. | ||
Zeile 73: | 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