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

Version vom 29. Juni 2013, 23:42 Uhr

Introduction

Quadratic problems are part of nonlinear optimisation problems. Each problem type has its own special solution technique. The difference between linear and quadratic optimazation problems is determined in the objective function F(x) which also contains quadratic terms ${\displaystyle (c_{ij}x_{ij}^{2}~or~c_{ij}x_{i}x{j})}$. There is no universal solution method - like the simplex is for linear optimisation problems - that can be used to solve quadratic problems. The three most common solution methods are Wolfe`s Algorithm, Achieve Set-Methods an the Dual Algorithm.

General Form

The general form of quadratic problems is given as:

min Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F=\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{i}x_{j}+\sum_{k=1}^{n}c_{k}x_{k}

s.t. linear constraints:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{j=1}^{n}a_{lj}x_{j}\leq b_{l}, \quad l=1,...,m

NNC: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{i}\geq 0, \quad j= 1,...,n

Quadratic Form

To transfer the general form of the quadratic problmen in the quadratic form, it is neccassary to summerzize...

...the coefficients${\displaystyle ~c_{ij}}$ in a symmetric n x n matrix C,

${\displaystyle a_{ij}}$ in a m x n matrix A,

${\displaystyle c_{k}}$in a column vector ${\displaystyle c~\epsilon ~\mathbb {R} ^{n}}$,

${\displaystyle b_{j}}$ column vector ${\displaystyle b~\epsilon ~\mathbb {R} ^{m}}$ and the

variables ${\displaystyle x_{j}}$ in a vector ${\displaystyle x~\epsilon ~\mathbb {R} ^{n}}$

This provides the Quadratic Problem in quadratic form:

min${\displaystyle f(x)=c^{T}x+{\frac {1}{2}}x^{T}C_{x}}$

or

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

linear constraints:

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

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

By using the coefficient ${\displaystyle ~{\frac {1}{2}}~}$ the KKT-conditions are easier to handle.

For maximization (minimization) problems the objective funktion hast to be convex (concav).

For ${\displaystyle x\epsilon \mathbb {R} }$ the function is:

concave, if Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): {F}''\leq 0

and

convex, if Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): {F}''\geq 0

For ${\displaystyle x\epsilon \mathbb {R} ^{n}}$ the function is:

concav, if the Hesse-Matrix is negative-semidefinit and

convex, if the Hesse-Matrix is positive-semidefinit.

A symmetric, quadratic matrix matrix C is positive (negative) semi-definite if all the Eigen-Values are positive (negative).

Example For Convex And Concave Functions

min ${\displaystyle F(x_{1},x_{2})=2x_{1}^{2}+3x_{2}^{2}+x_{1}x_{2}}$

Since this is a minimization problem, we have to verify that the function is a convex one.

First differentiations:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial F}{\partial x_{1}}=4x_{1}+x_{2}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial F}{\partial x_{2}}=6x_{2}+x_{2}

Second differentiations:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial F }{\partial^2 x_{1}}=4, \quad \frac{\partial F }{\partial x_{2}x_{1}}=1

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial F }{\partial x_{1}x_{2}}=1, \quad \frac{\partial F }{\partial^2 x_{2}}=6

The corresponding Hessematrix therefore is:${\displaystyle H={\begin{pmatrix}4&1\\1&6\end{pmatrix}}}$

Eigen-Value:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): det(h-\lambda E)= det\begin{pmatrix} 4-\lambda & 1\\ 1 & 6-\lambda \end{pmatrix} =(4-\lambda)(6-\lambda)-1=\lambda^{2}-10\lambda+23

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_{1,2}=5\pm\sqrt{25-23}

${\displaystyle \lambda _{1,2}>0}$ ==> F is positive defenit and therefore convex

2)

min Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x_{1},x_{2})=-2x_{1}^{2}-3x_{2}^{2}+x_{1}x_{2}

Since this is a minimization problem, we have to verify that the function is a convex one.

First differentiations:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial F}{\partial x_{1}}=-4x_{1}+x_{2}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial F}{\partial x_{2}}=-6x_{2}+x_{2}

Second differentiations:Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial F }{\partial x_{1}x_{2}}=1, \quad \frac{\partial F }{\partial x_{2}x_{1}}=1

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\partial F }{\partial^2 x_{1}}=-4, \quad \frac{\partial F }{\partial^2 x_{2}}=-6

The corresponding Hessematrix is: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): H=\begin{pmatrix} -4 & 1\\ 1 & -6 \end{pmatrix}

Eigen-Value:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): det(h-\lambda E)= det\begin{pmatrix} 4-\lambda & 1\\ 1 & 6-\lambda \end{pmatrix} =(-4-\lambda)(-6-\lambda)-1=\lambda^{2}+10\lambda+23

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_{1,2}=-5\pm\sqrt{25-23}

${\displaystyle \lambda _{1,2}<0}$ ==> F is negatice defenit and therefore concave

Example For A Quadratic Problem

Production program scheduling:

A monopolist produces two products (i=1,2) and wants to maximize its marginal revenue under observence of linear constraints.

The price-sales function of the two products is given as: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): p_{i}(x_{i})=10-x_{i}

The constant variable costs are: k_{i}=3

The marginal revenue of product i is:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): R(x_{i})=p_{i}(x_{i})-k_{i}x_{i}=(10-x_{i}x_{i})-2x_{i}=8x_{i}-x_{i}^{2}

With integration of linear restrictions we get the following Nonlinear Optimization Problem:

Objective function Max Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): ~ F(x_{1},x_{2})=8x_{1}-x_{1}^{2}+8x_{2}-x_{2}^{2}

linear constraints:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}+2x_{2}-11\leq 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3x_{1}+x_{2}-7\leq 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1},x_{2}\geq 0

Sources

Prof. Dr. Oliver Wendt: Skriptum Operations Research, Summer Term 2013

Domschke, Drexl: Einführung in Operations Research 7. Auflage

Domschke: Übungen und Fallbeispiele zum Operations-Research 6. Auflage