Nonlinear Opt.: Quadratic Problems 5: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(→Nonlinear Optimization: Quadratic problem) |
(→Nonlinear Optimization: Quadratic problem) |
||
Zeile 26: | 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 |
Version vom 12. August 2013, 02:16 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
(minimization problem ) is concave (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 the quadratic maximization problem (and minimization problem) the Hesse Matrix is Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 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 positive => matrix = positive definite, 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