Nonlinear Opt.: Quadratic Problems 3

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 $(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
• and the Dual Algorithm.

General Form

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 transfer

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

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

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

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

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

This provides the Quadratic Problem in quadratic form:

min$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 $~{\frac {1}{2}}~$ the KKT-conditions are easier to handle.

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

For $\quad x\epsilon \mathbb {R} \quad$ 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 $\quad x\epsilon \mathbb {R} ^{n}\quad$ 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

1)

min $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:$H={\begin{pmatrix}4&1\\1&6\end{pmatrix}}$

Eigen-Value of the Hessematrix:

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}

$\lambda _{1,2}>0$ ==> F is positive definit 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 of the Hessematrix:

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}

$\lambda _{1,2}<0$ ==> F is negative definit and therefore concave

Example For A Quadratic Problem

Production program scheduling:

A monopolist produces T-Shirts $(x_{1})$ and Tank-Tops $(x_{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_{1}(x_{1})=10-x_{1}

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

(Remember: Since this is a monopolist, he determines the price and the consumers react with their demand)

The constant variable costs are:

$k_{1}=3$

$k_{2}=2$

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}=10x_{1}-x_{1}^{2}+10_x{2}-x_{1}x_{2}-x_{2}^{2}-3x_{1}-5x_{2}=-x_{1}^{2}+7x_{1}-x_{1}x_{2}-x_{2}^{2}+5x_{2}

With integration of linear constraints 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})=-x_{1}^{2}+7x_{1}-x_{1}x_{2}-x_{2}^{2}+5x_{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

Transormation in Quadratic Form:

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

Conveying in matrix notation:

Max Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \quad F(x_{1},x_{2})= \begin{pmatrix}7 & 5 \end{pmatrix} \begin{pmatrix}x_1 \\ x_2 \end{pmatrix} - \frac{1}{2} \begin{pmatrix}x_1 & x_2 \end{pmatrix} \begin{pmatrix} 2 & 1\\ 2 & 1 \end{pmatrix} \begin{pmatrix}x_1 \\ x_2 \end{pmatrix}

Linear constraints:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{pmatrix} 1&2 \\ 3&1 \end{pmatrix} \binom{x_1}{x_2}\leq \binom{11}{7}

NNC: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \quad \binom{x_1}{x_2}\leq \binom{0}{0}

References

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

Domschke, Drexl: "Einführung in Operations Research" 7. Auflage, Darmstadt/Kiel 2006, Springer Verlag

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