Description: Basic introduction to optimization and AMPL via unconstrained optimization
Tags: ampl-lecture, amplpy, ampl, introduction, optimization, convexity, unconstrained
Problem types
An optimization problem, in its most general form, can be expressed as follows:
$
\begin{equation}
\begin{array}{lll}
&\min & f(x) & \
&\textrm{s.t.} & x \in \Omega,
\end{array} \tag{1}
\end{equation}
$
In this equation, $ f: \mathbb{R}^n \rightarrow \mathbb{R} $ and $ \Omega \subset \mathbb{R}^n $.
We refer to $ f $ as the objective function, $ x \in \Omega $ as the constraints, and the vector $ x $ as the decision variables.
A vector $x \in \mathbb{R}^n$ satisfying all of the constraints (i.e. $x \in \mathbb{\Omega}$) is called a feasible solution.
A feasible solution $x^*$ that minimizes the objective function is called an optimal feasible solution, or simply, an optimal solution.
If $ \Omega $ is equal to $ \mathbb{R}^n $, we are dealing with an unconstrained optimization problem. These are significantly easier to solve compared to constrained optimization problems.
In our exploration of optimization problems, it’s crucial to understand the nature of functions and constraints.
We need to distinguish between convex and non-convex problems, as well as between linear and non-linear ones.
While our primary focus in this training is on linear constrained optimization problems, we will initially delve into some non-linear and non-convex challenges to elucidate key concepts.
Convex problems
Convex problems, particularly those that are smooth, are preferred for two main reasons:
They provide a guarantee of global optimality.
There are many efficient algorithms (implemented in various solvers) available for solving these problems.
A problem defined by the above equation (1) is considered convex if $ f $ is a convex function and $ \Omega $ is a nonempty closed convex set.
Definition of convexity
Convex set: A subset $\Omega$ of $\mathbb{R}^n$ is called convex if
$
\begin{equation}
\lambda x + (1-\lambda) y \in \Omega \qquad \forall x,y \in \Omega, \quad \forall \lambda \in [0,1]. \tag{2}
\end{equation}
$
Geometrically, the line segment connecting $x$ to $y$ must also lie within the set $\Omega$.
Convex function: Let $\Omega$ be a convex subset of $\mathbb{R}^n$. A function $\Omega : \mathbb{R}^n \rightarrow \mathbb{R}$ is convex if we have
$
\begin{equation}
f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y) \qquad \forall x,y \in \Omega, \quad \forall \lambda \in [0,1]. \tag{3}
\end{equation}
$
Geometrically, the line segment connecting $(x, f (x))$ to $(y, f (y))$ must sit above the graph of $f$.
Also geometrically, a function is convex if and only if the area above its graph is convex.
Where/what is the minimum of the easy function? ;-)
How about the not-so-easy function?
Let’s ask AMPL!
Error executing "solve" command:
No solver specified: option solver is ''.
Whoops!!! We always need to specify the solver before attempting to solve!
Ipopt 3.12.13:
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
This is Ipopt version 3.12.13, running with linear solver mumps.
NOTE: Other linear solvers might be more efficient (see Ipopt documentation).
Number of nonzeros in equality constraint Jacobian...: 0
Number of nonzeros in inequality constraint Jacobian.: 0
Number of nonzeros in Lagrangian Hessian.............: 1
Total number of variables............................: 1
variables with only lower bounds: 0
variables with lower and upper bounds: 0
variables with only upper bounds: 0
Total number of equality constraints.................: 0
Total number of inequality constraints...............: 0
inequality constraints with only lower bounds: 0
inequality constraints with lower and upper bounds: 0
inequality constraints with only upper bounds: 0
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
0 1.0000000e+00 0.00e+00 1.00e+00 -1.0 0.00e+00 - 0.00e+00 0.00e+00 0
1 7.5000000e-01 0.00e+00 0.00e+00 -1.7 5.00e-01 - 1.00e+00 1.00e+00f 1
Number of Iterations....: 1
(scaled) (unscaled)
Objective...............: 7.5000000000000000e-01 7.5000000000000000e-01
Dual infeasibility......: 0.0000000000000000e+00 0.0000000000000000e+00
Constraint violation....: 0.0000000000000000e+00 0.0000000000000000e+00
Complementarity.........: 0.0000000000000000e+00 0.0000000000000000e+00
Overall NLP error.......: 0.0000000000000000e+00 0.0000000000000000e+00
Number of objective function evaluations = 2
Number of objective gradient evaluations = 2
Number of equality constraint evaluations = 0
Number of inequality constraint evaluations = 0
Number of equality constraint Jacobian evaluations = 0
Number of inequality constraint Jacobian evaluations = 0
Number of Lagrangian Hessian evaluations = 1
Total CPU secs in IPOPT (w/o function evaluations) = 0.001
Total CPU secs in NLP function evaluations = 0.000
EXIT: Optimal Solution Found.
Ipopt 3.12.13: Optimal Solution Found
suffix ipopt_zU_out OUT;
suffix ipopt_zL_out OUT;
Optimum: ( 0.5 0.75 )
Let’s try a more difficult case
How do we know function difficult is convex?
We can apply the definition.
We can examine the epigraph of the function (or in this simple case just look at the graph of the function) and make conclusions based off of that.
Also, if we know that $x^2$ and $-\log(x)$ are convex then there are some powerful theorems we can use to help us recognize convex functions:
Sum of convex functions is convex: Let $f_i: \mathbb{R}^n \rightarrow \mathbb{R}$, $i = 1,\ldots,m$, let $\lambda_1, \ldots, \lambda_m$ be positive scalars, and consider the function $g: \mathbb{R}^n \rightarrow \mathbb{R}$ given by:
$
\begin{equation}
g(x) = \lambda_1 f_1(x) + \ldots + \lambda_m f_m(x).\tag{4}
\end{equation}
$
If $f_1, \ldots, f_m$ are convex, then $g$ is also convex.
Transformations preserving convexity of domain: Let $f: \mathbb{R}^m \rightarrow \mathbb{R}$ be a given function, let $A \in \mathbb{R}^{m \times n}$ matrix, and consider the function $g: \mathbb{R}^n \rightarrow \mathbb{R}$ given by:
$
\begin{equation}
g(x) = f(Ax).\tag{5}
\end{equation}
$
If $f$ is convex, then $g$ is also convex (e.g norm functions are convex and so are least squares type problems, e.g. $\min_{x \in \mathbb{R}^n} || Ax -b||^2_2$).
Maximum of convex functions is convex: Let $f_i: \mathbb{R}^n \rightarrow \mathbb{R}$, $i \in I$, where $I$ is an arbitrary index set, and consider the function $g: \mathbb{R}^n \rightarrow \mathbb{R}$ given by:
$
\begin{equation}
g(x) = \max_{i \in I} f_i(x). \tag{6}
\end{equation}
$
If $f_i, ; i \in I$, are convex, then $g$ is also convex.
Let’s get ready for our first exercise with some basic AMPL syntax
More details later (or in the AMPL book, or just ask ;-)
Variable declarations
To declare our variables in AMPL, we first use the var keyword followed by the variable name, optional attributes, and a semicolon.
It is also worth mentioning that by default, AMPL initializes all variables to zero unless an initial value is provided via an attribute (e.g. var x := 1; in which case the initial value of x becomes 1).
This will be important to keep in mind later on when we discuss computing the value of expressions that involve variables.
Reminder: Each AMPL statement ends with a semicolon.
Objective declarations
To specify an objective function in AMPL, we first have to specify the direction of optimization via the keywords maximize or minimize, which is followed by a name, a colon, an expression involving our variables, and a semicolon.
Reminder: Variables must be declared before they can be used in an expression.
It’s good practice to use a descriptive name for the objective function, such as profit, which reflects what we’re trying to optimize.
In the next example you might choose to use the difficult qualifier.
The expression should be a mathematical formula involving our variables that reflect the goal of the optimization problem.