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 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