Behzad Samadi

February 17, 2014

\(\DeclareMathOperator{\sign}{sgn} \newcommand{\CO}{\textbf{\rm conv}} \newcommand{\RR}{{\mathcal R}} \newcommand{\RE}{\mathbb{R}} \newcommand{\TR}{\text{T}} \newcommand{\beq}{\begin{equation}} \newcommand{\eeq}{\end{equation}} \newcommand{\bmat}{\left[\begin{array}} \newcommand{\emat}{\end{array}\right]} \newcommand{\bsmat}{\left[\begin{smallmatrix}} \newcommand{\esmat}{\end{smallmatrix}\right]} \newcommand{\barr}{\begin{array}} \newcommand{\earr}{\end{array}} \newcommand{\bsm}{\begin{smallmatrix}} \newcommand{\esm}{\end{smallmatrix}}\)

Introduction

Convex sets

Convex functions

Convex optimization

Linear program

Quadratic program

Second order cone program

Semidefinite program

Applications

Stability

Dissipativity

In this presentation, the definitions are taken from the Convex Optimization book by Stephen Boyd and Lieven Vandenberghe unless otherwise stated. The reader is referred to the book for a detailed review of the theory of convex optimization and applications.

\(\begin{align} \text{minimize}&f(x)\nonumber \newline \text{subject to}& x\in C \end{align}\)

where \(f\) is a convex function and \(C\) is a convex set.

Convex optimization problems:

can be solved numerically with great efficiency

have extensive useful theory

occur often in engineering problems

often go unrecognised

Given \(m\) points in \(\RR^n\) denoted by \(x_i\) for \(i=1,\ldots,m\), \(x\) is convex combination of the \(m\) points if it can be written as:

\(\begin{equation} x = \sum_{i=1}^m \lambda_ix_i \end{equation}\)

where \(\lambda_i\geq 0\) and

\(\begin{equation} \sum_{i=1}^m\lambda_i=1 \end{equation}\)

**Convex set:** A set \(C\subseteq\RR^n\) is convex if the convex combination of any two points in \(C\) belongs to \(C\).

**Convex hull:** The convex hull of a set \(S\), denoted by \(\text{conv}(S)\), is the set of all convex combinations of points in \(S\).

**Affine combination:** \(x\) is an affine combination of \(x_1\) and \(x_2\) if it can be written as:

**Affine set:** A set \(C\subseteq\RR^n\) is affine if the affine combination of any two points in \(C\) belongs to \(C\).

**Cone (nonnegative) combination:** Cone combination of two points \(x_1\) and \(x_2\) is a point \(x\) that can be written as:

with \(\theta_1\geq 0\) and \(\theta_2\geq 0\).

**Convex cone:** A set \(S\) is a convex cone, if it contains all convex combinations of points in the set.

**Hyperplane:** A hyperplane is a set of the form \(\{x|a^\text{T}x=b\}\) with \(a\neq 0\).

**Halfspace:** A halfspace is a set of the form \(\{x|a^\text{T}x\leq b\}\) with \(a\neq 0\).

**Polyhedron:** A polyhedron is the intersection of finite number of hyperplanes and halfspaces. A polyhedron can be written as:

where \(\preceq\) denotes componentwise inequality.

**Euclidean ball:** A ball with center \(x_c\) and radius \(r\) is defined as:

\(\begin{equation} B(x_c,r)=\{x| \|x-x_c\|_2\leq r\}=\{x| x=x_c+ru, \|u\|_2\leq r\} \end{equation}\)

**Ellipsoid:** An ellipsoid is defined as: \(\begin{equation} \{x | (x-x_c)^\text{T}P^{-1}(x-x_c)\leq 1\} \end{equation}\) where \(P\) is a positive definite matrix. It can also be defined as: \(\begin{equation} \{x| x=x_c+Au, \|u\|_2\leq r\} \end{equation}\)

**Proper cone:**A cone is proper if it is:**closed**(contains its boundary)**solid**(has nonempty interior)**pointed**(contains no lines)

The nonnegative orthant of \(\mathbb{R}^n\), \(\{x|x\in\mathbb{R}^n,x_i\geq 0, i=1,\ldots,n \}\) is a proper cone.

Also the cone of positive semidefinite matrices in \(\mathbb{R}^{n\times n}\) is a proper cone.

A **generalized inequality** is defined by a proper cone \(K\):

\(\begin{equation} x\preceq_K y \Leftrightarrow y-x\in K \end{equation}\)

\(\begin{equation} x\prec_K y \Leftrightarrow y-x\in \text{interior}(K) \end{equation}\)

In this context, we deal with the following inequalities:

The

**inequality on real numbers**is defined based on the proper cone of nonnegative real numbers \(K=\mathbb{R}_+\).The

**componentwise inequality**on real vectors in \(\mathbb{R}^n\) is defined based on the nonnegative orthant \(K=\mathbb{R}^n_+\).The

**matrix inequality**is defined based on the proper cone of positive semidefinite matrices \(K=S^n_+\).

**Definition:** A function \(f:X_D \rightarrow X_R\) with \(X_D\subseteq\RR^n\) and \(X_R\subseteq\RR\) is a convex function if for any \(x_1\) and \(x_2\) in \(X_D\) and \(\lambda_1 \geq 0\), \(\lambda_2 \geq 0\) such that \(\lambda_1+\lambda_2=1\), we have: \(\begin{equation} f(\lambda_1x_1+\lambda_2x_2)\leq \lambda_1f(x_1)+\lambda_2f(x_2) \end{equation}\)

A mathematical optimization is convex if the objective is a convex function and the feasible set is a convex set. The standard form of a convex optimization problem is: \(\begin{align} \text{minimize } & f_0(x) \nonumber\newline \text{subject to } & f_i(x) \leq 0,\ i=1,\ldots,m\nonumber\newline & h_i(x) = 0,\ i=1,\ldots,p \end{align}\)

where \(f_i\)'s are convex and \(h_i\)'s are affine functions.

Linear programming (LP) is one of the best known forms of convex optimization.

\(\begin{align}\label{LP} \text{minimize }&c^\text{T}x\nonumber\newline \text{subject to }&a_i^\text{T}x\leq b_i,\ i=1,\ldots,m \end{align}\)

where \(x\), \(c\) and \(a_i\) for \(i=1,\ldots,m\) belong to \(\mathbb{R}^n\).

In general, no analytical solution

Numerical algorithms

- Early algorithm, the one developed by Kantorovich in 1940 [1]
The simplex method proposed by George Dantzig in 1947 [2]

The Russian mathematician L. G. Khachian developed a polynomial-time algorithm in 1979 [3]

The algorithm was an interior method, which was later improved by Karmarkar in 1984 [4]

If some of the entries of \(x\) are required to be integers, we have a Mixed Integer Linear Programming (MILP) program.

A MILP problem is in general difficult to solve (non-convex and NP-complete).

In practice, the global optimum can be found for many useful MILP problems.

\(\begin{align} \text{maximize: } & x + y\nonumber\\ \text{Subject to: } & x + y \geq -1 \\ \text{} & \frac{x}{2}-y \geq -2\nonumber\\ \text{} & 2x-y \leq -4\nonumber \end{align}\)

```
import numpy as np
from pylab import *
import matplotlib as mpl
import cvxopt as co
import cvxpy as cp
x = cp.Variable(1)
y = cp.Variable(1)
constraints = [ x+y >= -1.,
0.5*x-y >= -2.,
2.*x-y <= 4.]
objective = cp.Maximize(x+y)
p = cp.Problem(objective, constraints)
```

The solution of the LP problem is computed with the following command:

```
result = p.solve()
print(round(result,5))
8.0
```

The optimal solution is now given by:

```
x_star = x.value
print(round(x_star,5))
4.0
y_star = y.value
print(round(y_star,5))
4.0
```

\(\begin{align} \text{minimize: } & x + y\nonumber\\ \text{Subject to: } & x + y \geq -1 \\ \text{} & \frac{x}{2}-y \leq -2\nonumber\\ \text{} & 2x-y \leq -4\nonumber \end{align}\)

```
objective = cp.Minimize(x+y)
p = cp.Problem(objective, constraints)
result = p.solve()
print(round(result,5))
-1.0
```

The optimal solution is now given by:

```
x_star = x.value
print(round(x_star,5))
0.49742
y_star = y.value
print(round(y_star,5))
-1.49742
```

The optimal value of the objective function is unique.

Any point on the line connecting the two points (-2,1) and (1,-2) is the optimal solution.

This LP problem has infinite optimal solutions.

The code, however, returns just one of the optimal solutions.

Consider the following polyhedron:

\(\begin{equation} \mathcal{P} = \{x | a_i^Tx \leq b_i, i=1,...,m \} \end{equation}\)

The Chebyshev center of \(\mathcal{P}\) is the center of the largest ball in \(\mathcal{P}\):

\(\begin{equation} \mathcal{B}=\{x|\|x-x_c\|\leq r\} \end{equation}\)

For \(\mathcal{B}\) to be inside \(\mathcal{P}\), we need to have:

\(a_i^Tx\leq b_i,\ i=1,\ldots,m\) for all \(x\) in \(\mathcal{B}\)

For each \(i\), the point with the largest value of \(a_i^Tx\) is: \(x^\star=x_c+\frac{r}{\sqrt{a_i^Ta_i}}a_i=x_c+\frac{r}{\|a_i\|_2}a_i\)

Therefore:

\(a_i^Tx_c+r\|a_i\|_2\leq b_i, i=1,..,m\ \Rightarrow \mathcal{B}\) is inside \(\mathcal{P}\)

Now, we can write the problem as the following LP problem (LP3):

\(\begin{align} \text{maximize: } & r\nonumber\\ \text{Subject to: } & a_i^Tx_c + r\|a_i\|_2 \leq b_i,\ i=1,..,m \end{align}\)

[1] L.V. Kantorovich, “A new method of solving of some classes of extremal problems,” *Doklady Akademii Sci USSR*, vol. 28, 1940, pp. 211–214.

[2] G.B. Dantzig, “History of mathematical programming: a collection of personal reminiscences,” Lenstra, J.K., Kan, A.H.G.R., and Schrijver, A., Eds., Elsevier Science Publishers, 1991.

[3] L.G. Khachian, “A polynomial algorithm for linear programming,” *Doklady Akademii Nauk*, 1979, pp. 1093–1096.

[4] N. Karmarkar, “A new polynomial-time algorithm for linear programming,” *Combinatorica*, vol. 4, 1984, pp. 373–395.