Optimization
CSE 440: Introduction to Artificial Intelligence
Content Credits: CMU AI, http://ai.berkeley.edu
Today
- Optimization Setup
Optimization Problem: Definition
- Optimization Problem: Determine value of optimization variable within feasible region/set to optimize optimization objective $$ \begin{equation} \begin{aligned} \min_{\mathbf{x}} & f(\mathbf{x}) \\ \mbox{s.t. } & \mathbf{x} \in \mathcal{F} \end{aligned} \end{equation} $$
- Optimization variable $\mathbf{x} \in \mathbb{R}^n$
- Feasible region/set $\mathcal{F} \subseteq \mathbb{R}^n$
- Optimization objective: $f:\mathcal{F} \rightarrow \mathbb{R}$
- Optimal solution: $\mathbf{x}^* = \underset{\mathbf{x}\in \mathcal{F}}{\operatorname{arg min}} f(\mathbf{x})$
- Optimal objective value $f^*= \underset{\mathbf{x} \in \mathcal{F}}{\operatorname{min}} f(\mathbf{x}) = f(\mathbf{x}^*)$
Optimization Problem: Definition
$$ \begin{equation} \begin{aligned} \min_{\color{cyan}{\mathbf{x}}} & f(\mathbf{x}) \\ \mbox{s.t. } & \mathbf{x} \in \mathcal{F} \end{aligned} \end{equation} $$- Optimization variable $\mathbf{x} \in \mathbb{R}^n$
- Discrete variables: Combinatorial optimization
- Continuous variables: Continuous optimization
- Mixed: Some variables are discrete, and some are continuous
Optimization Problem: Definition
$$ \begin{equation} \begin{aligned} \min_{\mathbf{x}} & f(\mathbf{x}) \\ \mbox{s.t. } & \mathbf{x} \in {\color{cyan}{\mathcal{F}}} \end{aligned} \end{equation} $$- Feasible region/set $\mathcal{F} \subseteq \mathbb{R}^n$
- Unconstrained optimization: $\mathcal{F}=\mathbb{R}^n$
- Constrained optimization: $\mathcal{F} \subset \mathbb{R}^n$
- Finding a feasible point $\mathbf{x} \in \mathcal{F}$ can already be difficult
Optimization Problem: Definition
$$ \begin{equation} \begin{aligned} \min_{\mathbf{x}} & {\color{cyan}{f(\mathbf{x})}} \\ \mbox{s.t. } & \mathbf{x} \in \mathcal{F} \end{aligned} \end{equation} $$- Optimization objective $f:\mathcal{F}\rightarrow\mathbb{R}$
- $f(\mathbf{x}) = 1$: Feasibility problem
- Simple functions
- Linear function $f(\mathbf{x})=\mathbf{a}^T\mathbf{x}$
- Convex function (next lecture)
- Complicated functions
- Can be implicitly represented through an algorithm which takes $\mathbf{x}\in\mathcal{F}$ as input, and outputs a value
Optimization Problem: Definition
$$ \begin{equation} \begin{aligned} \color{cyan}{\min_{\mathbf{x}}} & {f(\mathbf{x})} \\ \mbox{s.t. } & \mathbf{x} \in \mathcal{F} \end{aligned} \end{equation} $$- Minimization can be converted to maximization (and vice versa) $$\begin{equation} \begin{aligned} \max_{\mathbf{x}} & \mbox{ } g(\mathbf{x}) = -f(\mathbf{x}) \\ \mbox{s.t. } & \mathbf{x} \in \mathcal{F} \end{aligned} \end{equation}$$
- Same optimal solution and optimal objective value $g^*=-f^*$
Optimization Problem: Example
- Example: Traveling Salesman Problem (TSP)
- Problem: $n$ cities, distance from city $i$ to city $j$ is $d(i,j)$, find a tour (a closed path that visits every city exactly once) with minimal total distance.
- Variable $\mathbf{x}$: ordered list of cities being visited
- $x_i$ is the index of the $i$-th city being visited
- Feasible set $\mathcal{F}=\{\mathbf{x}: \mbox{"each city visited exactly once"}\}$ $$\begin{equation} \mathcal{F} = \{\mathbf{x}:\mathbf{x}\in\{1,\dots,n\}^n; \sum_{k} \mathbb{I}(x_k=i)=1, \forall i\in\{1,\dots,n\}\} \end{equation}$$
- Objective function $f(\mathbf{x}) = \mbox{"total distance when following "} \mathbf{x}$ $$\begin{equation} f(\mathbf{x}) = d(x_n,x_1) + \sum_{k=1}^{n-1} d(x_k,x_{k+1}) \end{equation}$$
Optimization Problem: Example
$$ \begin{equation} \begin{aligned} \min_{\mathbf{x}} & f(\mathbf{x}) \\ \nonumber \mbox{s.t. } & \mathbf{x} \in \mathcal{F} \end{aligned} \end{equation} $$- Example: 8-Queens Problem (Solution 1)
- Variable $\mathbf{x}$: location of the queen in each column
- $x_i$ is the row index of the queen in $i$-th column
- Feasible set $\mathcal{F}=\{\mathbf{x}: \mbox{ "no queens in the row, col, diag" }\}$ $$\begin{equation} \mathcal{F}=\{\mathbf{x}: \mathbf{x}\in\{1,\dots,8\}^8; x_i\neq x_j,|x_i-x_j|\neq |i-j|, \forall i, j\in\{1,\dots,8\}\} \nonumber \end{equation}$$
- Objective function $f(\mathbf{x})=1$ (dummy)
Optimization Problem: Example
$$ \begin{equation} \begin{aligned} \min_{\mathbf{x}} & f(\mathbf{x}) \\ \nonumber \mbox{s.t. } & \mathbf{x} \in \mathcal{F} \end{aligned} \end{equation} $$- Example: 8-Queens Problem (Solution 2)
- Variable $x_i,y_i$: index of row and column of the $i$-th queen
- Feasible set $F=\{x,y:\mbox{ "no queens in the row, col, diag"}\}$ $$\begin{equation} \begin{aligned} F&=\{x,y:x,y\in\{1,\dots,8\}^8;\sum_{i}\mathbb{I}(x_i=k)=1,\forall k\in\{1,\dots,8\}; \\ & \sum_i \mathbb{I}(y_i=k)=1 , \forall k\in\{1,\dots,8\}; |x_i-x_j| \neq |y_i-y_j|, \forall i,j\in \{1,\dots,8\}\nonumber \end{aligned} \end{equation}$$
- Objective function $f(x)=1$ (dummy)
Optimization Problem: Example
| $x_i$ | 1.0 | 2.0 | 3.0 |
|---|---|---|---|
| $y_i$ | 2.1 | 3.98 | 7.0 |
- Example: Linear Regression
- Problem: Find $a$ such that $y_i \approx ax_i, \forall i=\{1,2,3\}$
- Variable $a$
- Feasible region $\mathbb{R}$
- Objective function $f(a)$?
$$\begin{equation}
\begin{aligned}
\min_{a} & \sum_{i=1}^3 |y_i-ax_i| \\
\mbox{s.t. } & a \in \mathbb{R}
\end{aligned}
\end{equation}$$
$$\begin{equation}
\begin{aligned}
\min_{a} & \sum_{i=1}^3 (y_i-ax_i)^2 \\
\mbox{s.t. } & a \in \mathbb{R}
\end{aligned}
\end{equation}$$
Optimization Problem: How to Solve?
- No general way to solve
- Many algorithms developed for special classes of optimization problems (i.e., when $f(x)$ and $\mathcal{F}$ satisfy certain constraints
- Convex optimization problem (CO)
- Linear Program (LP)
- (Mixed) Integer Linear Program (MILP)
- Quadratic program (QP), (Mixed) Integer Quadratic program (MIQP), Semidefinite program (SDP), Second-order cone program (SOCP), $\dots$
- Existing solvers and code packages for these problems
- Cplex (LP, MILP, QP), Gurobi (LP, MILP, MIQP), GLPK (LP, MILP), Cvxopt (CO), DSDP5 (SDP), MOSEK (QP, SOCP), Yalmip (SDP), $\dots$
Optimization Problem: Why Useful?
- Why formulate problems as optimization problems?
- For many class of optimization problems, algorithms or algorithmic frameworks have been developed
- Decouple "representation" and "problem solving"
- Lazy mode
- Formulate a problem as an optimization problem
- Identify which class the formulation belongs to
- Call the corresponding solver
- Done !!
Q & A
