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

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(→‎Example:)
K
 
(7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 4: Zeile 4:
 
----
 
----
  
 +
 +
== Introduction ==
  
 
Several efficient algorithms have been developed for this case under the assumption that F(x) is concave for maximization problems and convex for minimization problems. One of the most known of these algorithms may be the [[Wolfe algorithm]] (also known as the modified simplex method). In this article we just provide the preparatory work for applying the algorithm. So far it is not solving the quadratic problems.
 
Several efficient algorithms have been developed for this case under the assumption that F(x) is concave for maximization problems and convex for minimization problems. One of the most known of these algorithms may be the [[Wolfe algorithm]] (also known as the modified simplex method). In this article we just provide the preparatory work for applying the algorithm. So far it is not solving the quadratic problems.
 +
The methods shown here will not be suitable solving not-concave, quadratic problems.
 +
 +
At first the ''quadratic form'' should be defined, with which the quadratic components of a objective function F(x) can be expressed:
  
−
The methods shown here will not be suitable solving not-concave, quadratic problems. At first the "quadratic form" should be defined, with which the quadratic components of a objective function F(x) can be expressed:
 
 
  <math>F(x)=x^TCx</math>
 
  <math>F(x)=x^TCx</math>
  
Zeile 14: Zeile 18:
  
 
== Maximization problems ==
 
== Maximization problems ==
−
 
 
−
<math>F(x)=cx-\frac{1}{2}x^TCx</math>
 
  
−
subject to the constraints 
+
<math>F(x)=cx-\frac{1}{2}x^TCx</math>
  
−
  <math> Ax \leq b </math>
+
subject to the constraints <br>
 +
 
 +
<math> Ax \leq b </math><br>
 
   
 
   
−
<math> x \geq 0</math>
+
<math> x \geq 0</math>
  
 
with:c  row vector,
 
with:c  row vector,
Zeile 30: Zeile 34:
  
 
== Minimization problems ==
 
== Minimization problems ==
−
<math>F(x)=c^Tx+\frac{1}{2}x^TCx</math>
+
 
 +
<math>F(x)=c^Tx+\frac{1}{2}x^TCx</math>
  
 
If a quadratic objective function F(x) is concave or convex depends on the quadratic form and thus on the characteristics of the matrix C.
 
If a quadratic objective function F(x) is concave or convex depends on the quadratic form and thus on the characteristics of the matrix C.
 +
 
  A function <math>F(x)=c^Tx-\frac{1}{2}x^TCx</math> (resp. <math>F(x)=c^Tx+\frac{1}{2}x^TCx</math>) is concave (convex) if the symmetric matrix C is positive semidefinite.
 
  A function <math>F(x)=c^Tx-\frac{1}{2}x^TCx</math> (resp. <math>F(x)=c^Tx+\frac{1}{2}x^TCx</math>) is concave (convex) if the symmetric matrix C is positive semidefinite.
  
Zeile 38: Zeile 44:
  
 
Taking a closer look on  
 
Taking a closer look on  
−
<math>max F(x)=c^Tx-\frac{1}{2}x^TCx</math>
+
 
 +
<math>max F(x)=c^Tx-\frac{1}{2}x^TCx</math>
  
 
constraints:   
 
constraints:   
  
−
<math> Ax\leq b </math>
+
<math> Ax\leq b </math><br>
−
<math> x \geq 0</math>
+
<math> x \geq 0</math>
  
 
it is obvious that <math>H(x)=-C</math> applies
 
it is obvious that <math>H(x)=-C</math> applies
Zeile 49: Zeile 56:
 
That means C is determinable right out of the Hessian matrix.
 
That means C is determinable right out of the Hessian matrix.
  
−
== Example: ==
+
== Example ==
  
  
 
Maximize  
 
Maximize  
−
<math>f(x_1,x_2)=15x_1+30x_2+4x_1x_2-2x_1^2-4x_2^2</math><br>
+
 
−
subject to  
+
<math>f(x_1,x_2)=15x_1+30x_2+4x_1x_2-2x_1^2-4x_2^2</math><br>
−
<math>x_1+x_2\leq 30</math><br>
+
 
−
<math>x_1, x_2\geq 0</math>.<br>
+
subject to <br>
 +
<math>x_1+x_2\leq 30</math><br>
 +
<math>x_1, x_2\geq 0</math>.<br>
  
 
[[Datei:Function_plott.jpg]]
 
[[Datei:Function_plott.jpg]]
Zeile 73: Zeile 82:
  
 
If the form of equation <math>max F(x)=c^Tx-\frac{1}{2}x^TCx</math> is applied, the solution would be:<br>
 
If the form of equation <math>max F(x)=c^Tx-\frac{1}{2}x^TCx</math> is applied, the solution would be:<br>
−
<math>max F(x)= (15,30)\binom{x_1}{x_2}-\frac{1}{2}(x_1,x_2)\begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix}\binom{x_1}{x_2}</math>
+
 
 +
<math>max F(x)= (15,30)\binom{x_1}{x_2}-\frac{1}{2}(x_1,x_2)\begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix}\binom{x_1}{x_2}</math>
  
 
<math>\Rightarrow C=\begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix}</math> (symmetric matrix C)
 
<math>\Rightarrow C=\begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix}</math> (symmetric matrix C)
Zeile 80: Zeile 90:
 
Writing down the quadratic components with a real coefficient <math>\tilde c_{ij}</math> provides the following equation:
 
Writing down the quadratic components with a real coefficient <math>\tilde c_{ij}</math> provides the following equation:
  
−
<math> Q\left(x_{1},...,x_{n}\right)=\tilde{c}_{11}x_{1}^{2}+2\tilde{c}_{12}x_{1}x_{2}+2\tilde{c}_{13}x_{1}x_{3}+...+2    \tilde{c}_{1n}x_{1}x_{n}+</math>
+
<math> Q\left(x_{1},...,x_{n}\right)=\tilde{c}_{11}x_{1}^{2}+2\tilde{c}_{12}x_{1}x_{2}+2\tilde{c}_{13}x_{1}x_{3}+...+2    \tilde{c}_{1n}x_{1}x_{n}+</math><br>
−
<math>\tilde{c}_{22}x_{2}^{2}+2\tilde{c}_{23}x_{2}x_{3}+...+2\tilde{c}_{2n}x_{2}x_{n}+</math>
+
<math>\tilde{c}_{22}x_{2}^{2}+2\tilde{c}_{23}x_{2}x_{3}+...+2\tilde{c}_{2n}x_{2}x_{n}+</math><br>
−
<math>\tilde{c}_{33}x_{3}^{2}+...+2\tilde{c}_{3n}x_{3}x_{n}+...</math>
+
<math>\tilde{c}_{33}x_{3}^{2}+...+2\tilde{c}_{3n}x_{3}x_{n}+</math><br>
−
<math>.....+\tilde{c}_{nn}x_{n}^{2}</math>.
+
<math>\vdots</math><br>
 +
<math>+\tilde{c}_{nn}x_{n}^{2}</math>.
  
 
After symmetrizising the expression (<math>2\tilde c_{ij}</math> becomes <math>c_{ij}=c_{ji}=\tilde c_{ij}</math>) one can write as well:
 
After symmetrizising the expression (<math>2\tilde c_{ij}</math> becomes <math>c_{ij}=c_{ji}=\tilde c_{ij}</math>) one can write as well:
  
−
<math> Q\left(x_{1},...,x_{n}\right)=x_{1}\left(c_{11}*x_{1}+c_{12}x_{2}+...+c_{1n}x_{n} \right)+</math><br>
+
<math> Q\left(x_{1},...,x_{n}\right)=x_{1}\left(c_{11}*x_{1}+c_{12}x_{2}+...+c_{1n}x_{n} \right)+</math><br>
−
<math>x_{2}*\left(c_{21}x_{1}+c_{22}x_{2}+...+c_{2n}x_{n} \right)+...</math><br>
+
<math>x_{2}*\left(c_{21}x_{1}+c_{22}x_{2}+...+c_{2n}x_{n} \right)+</math><br>
−
<math>...+x_{n}*\left(c_{n1}x_{1}+c_{n2}x_{2}+...+c_{nn}x_{n}\right) </math>.
+
<math>\vdots</math><br>
 +
<math>+x_{n}*\left(c_{n1}x_{1}+c_{n2}x_{2}+...+c_{nn}x_{n}\right) </math>.
  
 
Aggregating the coefficients <math>c_{ij}</math> to a symmetric (<math>n \times n</math>)-Matrix C and the variables <math>x_i</math> to a real column vector <math>x</math>, supplies the right side as a product of the row vector <math>x^T</math> with the column vector <math>Cx</math>.
 
Aggregating the coefficients <math>c_{ij}</math> to a symmetric (<math>n \times n</math>)-Matrix C and the variables <math>x_i</math> to a real column vector <math>x</math>, supplies the right side as a product of the row vector <math>x^T</math> with the column vector <math>Cx</math>.
Zeile 109: Zeile 121:
 
<math>\Rightarrow</math> all of the eigenvalues are positive, for this reason the matrix C is positive semidefinite and therewith the objective function is concave.
 
<math>\Rightarrow</math> all of the eigenvalues are positive, for this reason the matrix C is positive semidefinite and therewith the objective function is concave.
  
−
== References: ==
+
== References ==
  
  

Aktuelle Version vom 30. Juni 2013, 22:33 Uhr

Quadratic Problems have a quadratic objective function which is maximized or minimized subject to linear constraints and nonnegativity restrictions on the variables. The objective functions involve the square of a variable Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{jj}\cdot x_j^2 

or the product of two variables Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c_{ij}\cdot x_i\cdot x_j

.


Introduction

Several efficient algorithms have been developed for this case under the assumption that F(x) is concave for maximization problems and convex for minimization problems. One of the most known of these algorithms may be the Wolfe algorithm (also known as the modified simplex method). In this article we just provide the preparatory work for applying the algorithm. So far it is not solving the quadratic problems. The methods shown here will not be suitable solving not-concave, quadratic problems.

At first the quadratic form should be defined, with which the quadratic components of a objective function F(x) can be expressed:

Standard quadratic problems may be formulated as follows:


Maximization problems

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x)=cx-\frac{1}{2}x^TCx


subject to the constraints

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Ax \leq b

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \geq 0


with:c row vector, x and b column vector,C andA matrices, subscript T denotes transpose.

The elements of C are given constants such that (which is the reason for the factor of 1/2 in the objective function)


Minimization problems

If a quadratic objective function F(x) is concave or convex depends on the quadratic form and thus on the characteristics of the matrix C. 

A function Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x)=c^Tx-\frac{1}{2}x^TCx
(resp. ) is concave (convex) if the symmetric matrix C is positive semidefinite.

Positive semidefinite means all eigenvalues are equal or greater than 0.

Taking a closer look on

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max F(x)=c^Tx-\frac{1}{2}x^TCx


constraints:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Ax\leq b
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \geq 0


it is obvious that Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): H(x)=-C 

applies

That means C is determinable right out of the Hessian matrix.

Example

Maximize

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x_1,x_2)=15x_1+30x_2+4x_1x_2-2x_1^2-4x_2^2

subject to
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1+x_2\leq 30
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1, x_2\geq 0 .

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Just taking the quadratic components of the objective function and transforms it into the Form Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x)=c^Tx-1/2x^TCx

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x_1,x_2)=-2x_1^2+4x_1x_2-4x_2^2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): =(-2x_1+4x_2)x_1+(-4x_2)x_2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): =(-2x_1+2x_2)x_1+(2x_1-4x_2)x_2
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): =-\frac{1}{2}(4x_1-4x_2)x_1+(-4x_1+8x_2)x_2 .

Going with the Hessian-Matrix: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): H(x)=\begin{pmatrix}\frac{{\partial^2 f}}{{\partial^2 x_1}} & \frac{{\partial^2 f}}{{\partial x_1}{\partial x_2}} \\ \frac{{\partial^2 f}}{{\partial x_1}{\partial x_2}} & \frac{{\partial^2 f}}{{\partial^2 x_2}}\end{pmatrix}=\begin{pmatrix} -4 & 4 \\ 4 & -8 \end{pmatrix}
with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): H(x)=-C
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{pmatrix} -4 & 4 \\ 4 & -8 \end{pmatrix}=-1\cdot \begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix}

If the form of equation Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max F(x)=c^Tx-\frac{1}{2}x^TCx 

is applied, the solution would be:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max F(x)= (15,30)\binom{x_1}{x_2}-\frac{1}{2}(x_1,x_2)\begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix}\binom{x_1}{x_2}


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow C=\begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix} 

(symmetric matrix C)

One can easily transform the quadratic components of every objective function to the form shown above. Writing down the quadratic components with a real coefficient provides the following equation:




Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \vdots
.

After symmetrizising the expression ( becomes ) one can write as well:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Q\left(x_{1},...,x_{n}\right)=x_{1}\left(c_{11}*x_{1}+c_{12}x_{2}+...+c_{1n}x_{n} \right)+
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}*\left(c_{21}x_{1}+c_{22}x_{2}+...+c_{2n}x_{n} \right)+
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \vdots
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): +x_{n}*\left(c_{n1}x_{1}+c_{n2}x_{2}+...+c_{nn}x_{n}\right) .

Aggregating the coefficients to a symmetric (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): n \times n )-Matrix C and the variables to a real column vector , supplies the right side as a product of the row vector with the column vector .

Now we need to prove the matrix C is positive semidefinite:

A symetric matrix is positive semidefinite if all eigenvalues are equal or grater than 0.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): C=\begin{pmatrix} 4 & -4 \\ -4 & 8 \end{pmatrix} \Rightarrow C-\lambda E=\begin{pmatrix} 4-\lambda & -4 \\ -4 & 8-\lambda \end{pmatrix}


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): det(C-\lambda E)=(4-\lambda)(8-\lambda )-(-4)(-4)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): =32-4\lambda -8\lambda +\lambda ^2-16
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): =\lambda ^2-12\lambda +16

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_{1/2}=\frac{12\pm \sqrt{(-12)^2-4\cdot 1\cdot 16}}{2\cdot 1}=\frac{12\pm \sqrt{144-64}}{2}=\frac{12\pm \sqrt{80}}{2}=\frac{12\pm 4\sqrt{5}}{2}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_1=\frac{12+4\sqrt{5}}{2}\approx 10{,}4721
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_2=\frac{12-4\sqrt{5}}{2}\approx 1{,}52786

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow 

all of the eigenvalues are positive, for this reason the matrix C is positive semidefinite and therewith the objective function is concave.

References

Müller-Merbach, Operations Research : Methoden und Modelle der Optimalplanung, Vahlen, München, 1973
Domschke, Einführung in Operation Research, 2011, Springer-Verlag
Martos, "Nonlinear programming theory & methods", 1975, North Holland Publishing Company
Mangasarian, "Nonlinear Programming", 1969, Tata McGraw-Hill Publishing Comp. Ltd.
Vajda, "Theory of linear and non-linear programming", 1974, William Clowes & Sons Ltd.
Hillier, Liebermann, "Introduction to Operations Research", 4.Edition, 1986, Holden-Day Inc.
Peressini, Sullivan, Uhl, "The mathematics of nonlinear Programming", 1988, Springer-Verlag

Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Nonlinear_Opt.:_Quadratic_Problems_1&oldid=5912“