Optimization Theory and Practice

Welcome and Introduction


Instructor: Hasan A. Poonawala

Mechanical and Aerospace Engineering
University of Kentucky, Lexington, KY, USA

Topics:
Optimization
Types of Problems
Algorithms
Examples

Optimization

What is mathematical optimization?

We have a complex decision problem to solve.

  • Running a business: maximize profit, minimize loss, maximize efficiency, or minimize risk.
  • Design: minimize the weight of a bridge/truss and maximize the strength within the design constraints.
  • Planning: select a flight route to minimize time or fuel consumption of an airplane.

Philosophy

Approach the problem of selecting values for a number of interrelated decision variables by focusing attention on a single objective function that quantifies the quality of the decision.

Important

This single objective is optimized subject to the constraints that may limit the selection of decision variable values.

Optimization Problems

minimizef(𝐱)subject to𝐱∈Ω. \begin{align} \operatorname{minimize} & f(\bm{x}) \\ \text{subject to} & \bm{x} \in \Omega. \end{align}

minimizef(𝐱)subject togi(𝐱)≀0,i=1,…,mhi(𝐱)=0,i=1,…,pπ±βˆˆΞ©β€². \begin{align} \operatorname{minimize} & f(\bm{x}) \\ \text{subject to} & g_{i}(\bm{x}) \leq 0,\;\; i = 1,\dots,m\\ & h_{i}(\bm{x}) = 0,\;\; i = 1,\dots,p\\ & \bm{x} \in \Omega'. \end{align}

xx: decision variables

ff: objective function

Ξ©\Omega: admissible/allowable options for xx

hih_{i}: equality constraints

gig_{i}: inequality constraints

The type of functions ff, gig_i, hih_i determine the β€˜type’ of optimization problem

Most optimization books disagree on notation.

Simple Examples

Convex Problems

A quadratic program (QP)

minimizef(x)=(x1βˆ’1)2+(x2βˆ’1)2 \begin{align} \operatorname{minimize} & f(x) = (x_1 - 1)^2 + (x_2 - 1)^2 \end{align}

A linearly constrained quadratic program (QP)

minimizef(x)=(x1βˆ’1)2+(x2βˆ’1)2subject tox1+x2=3. \begin{align} \operatorname{minimize} & f(x) = (x_1 - 1)^2 + (x_2 - 1)^2 \\ \text{subject to} & x_1 + x_2 = 3. \end{align}

A linear program (LP)

maximizef(x)=2x1+x2subject tox1+x2≀1,x1,x2β‰₯0. \begin{align} \operatorname{maximize} & f(x) = 2x_1 + x_2\\ \text{subject to} & x_1 + x_2 \leq 1, \\ & x_1, x_2 \geq 0. \end{align}

  • The optimal solution is 𝐱*=(1,0)\bm{x}^\ast = (1, 0).

Conic Linear Programming

Conic Linear Programming, (CLP), is a natural extension of linear programming.

  • In LP, variables form a vector or point that is subjected to be component-wise non-negative.
  • In ConicLP, they form a point in a general pointed convex cone such as a vector or a matrix.

min2x1+x2+x3subject tox1+x2+x3=1,x1,x2,x3β‰₯𝟎, \begin{align} \operatorname{min} &2x_1+x_2+x_3 \\ \text{subject to} &x_1 + x_2 + x_3 = 1, \\ & x_1, x_2, x_3 \geq \mathbf {0}, \end{align}

min2x1+x2+x3subject tox1+x2+x3=1,x22+x32≀x1, \begin{align} \operatorname{min} &2x_1+x_2+x_3 \\ \text{subject to} &x_1 + x_2 + x_3 = 1, \\ & \sqrt{x_2^2 + x_3^2} \leq x_1, \end{align}

min2x1+x2+x3subject tox1+x2+x3=1,(x1x2x2x3)β‰½πŸŽ. \begin{align} \operatorname{min} &2x_1+x_2+x_3 \\ \text{subject to} &x_1 + x_2 + x_3 = 1, \\ & \begin{pmatrix} x_1 & x_2 \\ x_2 & x_3 \end{pmatrix}\succeq \mathbf 0. \end{align}

Constraints form a vector in the nonnegative orthant cone.

A cone is a set KK where x∈K⟹λx∈Kx \in K \implies \lambda x \in K for all Ξ»β‰₯0\lambda \geq 0.

Constraints form a vector in a cone shaped like an ice-cream cone, called a second-order cone.

Constraints form a 22-dimensional symmetric matrix required to be positive semidefinite or to be in a semidefinite cone.

Nonlinear Problems

A convex nonlinear problem

minimizef(x)=(x1βˆ’2)2+(x2βˆ’1)2subject tox12βˆ’x2≀0,x1+x2≀2. \begin{align} \operatorname{minimize} & f(x) = (x_1-2)^2 + (x_2-1)^2\\ \text{subject to} & x_1^2 - x_2 \leq 0, \\ &x_1 + x_2 \leq 2. \\ \end{align}

Important

Convex vs non-convex is more important than linear vs nonlinear.

Nonlinear Problems

A nonlinear program (NLP)

maximizef(x)=(x1+x2)2subject tox1x2β‰₯0,βˆ’2≀x1≀1,βˆ’2≀x2≀1. \begin{align} \operatorname{maximize} & f(x) = (x_1+x_2)^2\\ \text{subject to} & x_1x_2 \geq 0, \\ & -2 \leq x_1 \leq 1, \\ & -2 \leq x_2 \leq 1. \end{align}

  • The point 𝐱c=(1,1)\bm{x}_c = (1,1) has an objective value f(𝐱c)=4f(\bm{x}_c) = 4, which is higher than any of its β€œnearby” feasible points (local optimizer).

  • In contrast, the point 𝐱*=(βˆ’2,βˆ’2)\bm{x}^\ast = (-2, -2) has an objective value f(𝐱*)=16f(\bm{x}^\ast) = 16, which is the best among all feasible points (global optimizer).

Problem transcription

  • Always involves a trade-off between conflicting goals:
    • building a mathematical model that accurately captures the problem description,
    • building a model that is tractable.
  • Knowledge about how mathematical optimization works helps produce better optimization problems
    • You operate on a better trade-off curve
  • One must learn to distinguish tractable models from intractable ones
    • study of available theory
    • nurturing the capability to extend existing theory to new situations.

Example: A Transportation Problem

Scene / Data

  • A chemical company has 2 factories F1F_{1} and F2F_{2} and a dozen retail outlets R1R_{1},R2R_{2},…\dots,R12R_{12}.
  • Each factory FiF_{i} can produce aia_{i} tons of a certain chemical product each week; aia_{i} is called the capacity of the plant.
  • Each retail outlet RjR_{j} has a known weekly demand of bjb_{j} tons of the product.
  • The cost of shipping one ton of the product from factory FiF_i to retail outlet RjR_j is cij.c_{ij}.

Task

Model the problem of choosing how much product to ship from each factory to each outlet so that the company meets demand at the least cost.

Task

Modify the problem to reflect that the company has one truck for each store, and the trucks can make only one round-trip journey to a factory each week

Example: A Transportation Problem Solution

minimizef(x)=βˆ‘i,jcijxiji∈{1,2},j∈{1,…,12}subject toβˆ‘j=112xij≀ai,i∈{1,2}βˆ‘i=12xijβ‰₯bj,j∈{1,…,12}xijβ‰₯0,i∈{1,2},j∈{1,…,12} \begin{align} \operatorname{minimize} & f(x) = \sum_{i,j} c_{ij} x_{ij} && i \in \{1,2\},\ j \in \{1,\dots,12\} \\ \text{subject to} & \sum_{j=1}^{12} x_{ij} \leq a_i, && i \in \{1,2\ \} \\ & \sum_{i=1}^{2} x_{ij} \geq b_j, && j \in \{1,\dots,12\}\\ & x_{ij} \geq 0, &&i \in \{1,2\},\ j \in \{1,\dots,12\} \\ \end{align}

Task

Modify the problem to reflect that the company has one truck for each store, and the trucks can make only one round-trip journey to a factory each week

Example: A Transportation Problem Solution

minimizexijf(x)=βˆ‘i,jcijxiji∈{1,2},j∈{1,…,12}subject toβˆ‘j=112xij≀ai,i∈{1,2}βˆ‘i=12xijβ‰₯bj,j∈{1,…,12}xijβ‰₯0,i∈{1,2},j∈{1,…,12}Eitherx1j≀0 or x2j≀0 \begin{align} \operatorname{minimize}_{x_{ij}} & f(x) = \sum_{i,j} c_{ij} x_{ij} && i \in \{1,2\},\ j \in \{1,\dots,12\} \\ \text{subject to} & \sum_{j=1}^{12} x_{ij} \leq a_i, && i \in \{1,2\ \} \\ & \sum_{i=1}^{2} x_{ij} \geq b_j, && j \in \{1,\dots,12\}\\ & x_{ij} \geq 0, &&i \in \{1,2\},\ j \in \{1,\dots,12\} \\ & \text{Either} x_{1j} \leq 0 \text{ or } x_{2j} \leq 0\\ \end{align}

Algorithms

Algorithms come from theory

Basic optimization theory builds necessary and sufficient optimality conditions that end up being a set of equations or inequalities.

Most algorithms are programs that find decision variables that satisfy (β€˜solve’) the conditions.

Computers perform repetitive operations efficiently - optimization algorithms are usually iterative in nature.

Iterative Algorithms

  • An initial variable 𝐱0\bm{x}_0 is selected and the algorithm generates an improved variable 𝐱1\bm{x}_1.

    • Improvement means f(𝐱1)<f(𝐱0)f(\bm{x}_1) < f(\bm{x}_0)

  • This iteration is repeated to get a still better variable 𝐱2\bm{x}_2.

  • Continuing this way, a sequence of ever-improving variables 𝐱0,𝐱1,…,𝐱k,…\bm{x}_0, \bm{x}_1, \ldots, \bm{x}_k, \ldots is found that approaches a solution point 𝐱*\bm{x}^\ast.

  • For linear programming this sequence may be made finite: simplex method.

Types of Algorithms

  • The solvability of the optimality conditions for different types of optimization algorithms determine what algorithm will be suitable
  • Some factors that differentiate conditions:
    • Type of functions: convex or non-convex
    • Type of constraints: none, all equality, inequalities
    • Type of variable: continuous or discrete

Analysis of Algorithms

  • Algorithms must be analyzed to check if they will converge to a solution point.

  • The rate at which they converge (if they do) are also analyzed: complexity analysis.

In some cases, convergence at a slow rate is acceptable; usually not.

Size of Problems

Size: # of unknown variables and/or # of constraints.

  • small-scale problems: ≀5\leq 5 unknowns and constraints,
  • intermediate-scale problems: 5βˆ’100/10005 - 100/1000 variables and constraints,
  • large-scale problems: 1000βˆ’1061000 - 10^6 variables and constraints.

Complexity theory studies how fast the computation time increases as a function of the increases in the number of variables and constraints

Next Class:

  • Bring a laptop
  • Make sure it is charged or bring a charger/chord
  • Be ready to run a script or compile code in your favorite language
    • Python, Matlab, Julia are widely used
    • You can use C++ or Rust if you are comfortable