# Introduction to Mathematical Optimization¶

Description: Basic introduction to optimization and AMPL via unconstrained optimization

Tags: ampl-lecture, amplpy, ampl, introduction, optimization, convexity, unconstrained

Notebook author: Gyorgy Matyasfalvi <gyorgy@ampl.com>

References:

• AMPL a Modeling Language for Mathematical Programming – Robert Fourer et al.

• Linear Programming (Foundations and Extensions) – Robert J. Vanderbei

• Introduction to Linear Optimization – Dimitris Bertsimas et al.

• Convex Analysis and Optimization – Dimitri P. Bertsekas et al.

# Install dependencies
%pip install -q amplpy pandas numpy matplotlib

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
modules=["open", "gurobi"],  # modules to install
)  # instantiate AMPL object and register magics

# Import all necessary libraries
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from math import log, cos, sin, pi, sqrt


## Problem types¶

An optimization problem, in its most general form, can be expressed as follows: $$$\begin{array}{lll} &\min & f(x) & \ &\textrm{s.t.} & x \in \Omega, \end{array} \tag{1}$$$ 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:

1. They provide a guarantee of global optimality.

2. 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 $$$\lambda x + (1-\lambda) y \in \Omega \qquad \forall x,y \in \Omega, \quad \forall \lambda \in [0,1]. \tag{2}$$$

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

$$$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}$$$

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.

# Plot convex functions

# Define the functions
def easy(x):
return x**2

def not_so_easy(x):
return (x - 1) ** 2 + x

# Generate x values
x = np.linspace(-4, 4, 400)

# Generate y values
ye = easy(x)
yne = not_so_easy(x)

# Create the plot
plt.figure(figsize=(8, 6))
plt.plot(x, ye, label="easy: y = x^2")
plt.plot(x, yne, label="not_so_easy: y = (x-1)^2 + x")

# Add a line that connects two points
x_not_so_easy = [-3, 3]
y_not_so_easy = [not_so_easy(-3), not_so_easy(3)]
plt.plot(
x_not_so_easy,
y_not_so_easy,
color="orange",
linestyle="--",
label="convex comb of (-3, not_so_easy(-3)) and (3, not_so_easy(3))",
)
x_easy = [-2, 2]
y_easy = [easy(-2), easy(2)]
plt.plot(
x_easy,
y_easy,
color="blue",
linestyle="--",
label="convex comb of (-2, easy(-2)) and (2, easy(2))",
)

plt.title("Convex functions: easy and not_so_easy")
plt.xlabel("x")
plt.ylabel("y")
plt.legend()
plt.grid(True)
plt.show()


### How about the not-so-easy function?¶

%%ampl_eval
reset; reset option;                # reset AMPL, this is needed for when we run the cell multiple times,
# AMPL complains about redeclaration of entities.
var x;                              # Declare our variable
minimize not_so_easy: (x-1)^2 + x;  # Define our objective function
solve;                              # Attempt to solve

Error executing "solve" command:
No solver specified:  option solver is ''.


Whoops!!! We always need to specify the solver before attempting to solve!

%%ampl_eval
option solver ipopt;                        # Use Ipopt as our solver
solve;                                      # Issue solve command and send the problem, this time, to Ipopt
# After succesful completion of solve AMPL retrieves the solutions from Ipopt
print;                                      # Add a new line (only for formatting purposes)
print "Optimum: (", x, not_so_easy, ")";    # Let's also print the solution!

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).
******************************************************************************

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¶

# Draw a difficult to optimize convex function

# Define the function
def difficult(x):
return (x - 1) ** 2 - log(x + 1)

# Generate x values
x = np.linspace(-0.9999, 10, 400)

# Generate y values
y = [difficult(i) for i in x]

# Create the plot
plt.figure(figsize=(8, 6))
plt.plot(x, y, label="y = (x-1)^2 - log(x+1)")

# Add a line that connects two points
x_difficult = [-0.5, 6]
y_difficult = [difficult(-0.5), difficult(6)]
plt.plot(
x_difficult,
y_difficult,
color="blue",
linestyle="--",
label="convex comb of (-0.5, difficult(-0.5)) and (6, difficult(6))",
)

plt.title("Convex function: difficult")
plt.xlabel("x")
plt.ylabel("y")
plt.legend()
plt.grid(True)
plt.show()


### How do we know function difficult is convex?¶

1. We can apply the definition.

2. 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.

3. 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:

$$$g(x) = \lambda_1 f_1(x) + \ldots + \lambda_m f_m(x).\tag{4}$$$

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:

$$$g(x) = f(Ax).\tag{5}$$$

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:

$$$g(x) = \max_{i \in I} f_i(x). \tag{6}$$$

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.

# EXERCISE 1¶

1. Create a code cell below.

2. Start with the magic: %%ampl_eval

3. Reset the state of the AMPL interpreter with reset; and reset option;.

4. Then use the AMPL keywords var and minimize, as well as the built-in function log() to formulate the model that minimizes difficult() (the built-in AMPL function log() is base $e$ just like the Python function log()).

5. Compute the minimum using the ipopt solver.

6. Then print the solution using AMPL’s print command.

## SOLUTION¶

%%ampl_eval
reset; reset option;                # reset AMPL, this is needed for when we run the cell multiple times,
# AMPL complains about redeclaration of entities.
var x;                              # Declare our variable
minimize difficult: (x-1)^2 - log(x+1);  # Define our objective function
option solver ipopt;                # Use Ipopt as our solver
solve;                              # Attempt to solve
print;                              # Add a new line (only for formatting purposes)
print "Optimum: (", x, difficult, ")";    # Let's also print the solution!

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).
******************************************************************************

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 3.00e+00  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
1 -6.9314718e-01 0.00e+00 5.00e-01  -1.0 1.00e+00    -  1.00e+00 1.00e+00f  1
2 -7.4912498e-01 0.00e+00 5.56e-03  -1.7 2.22e-01    -  1.00e+00 1.00e+00f  1
3 -7.4913199e-01 0.00e+00 5.79e-07  -3.8 2.52e-03    -  1.00e+00 1.00e+00f  1
4 -7.4913199e-01 0.00e+00 6.11e-15  -8.6 2.63e-07    -  1.00e+00 1.00e+00f  1

Number of Iterations....: 4

(scaled)                 (unscaled)
Objective...............:  -7.4913198728379427e-01   -7.4913198728379427e-01
Dual infeasibility......:   6.1062266354383610e-15    6.1062266354383610e-15
Constraint violation....:   0.0000000000000000e+00    0.0000000000000000e+00
Complementarity.........:   0.0000000000000000e+00    0.0000000000000000e+00
Overall NLP error.......:   6.1062266354383610e-15    6.1062266354383610e-15

Number of objective function evaluations             = 5
Number of objective gradient evaluations             = 5
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             = 4
Total CPU secs in IPOPT (w/o function evaluations)   =      0.004
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: ( 1.2247448713915863 -0.7491319872837943 )


## Non-convex functions¶

We’ve consistently found the optimal solution without much difficulty. This is expected since we’ve been dealing with convex smooth functions. Local non-linear solvers like Ipopt are well-equipped for these types of problems. Now, let’s examine a non-convex function and observe the outcome.

# Draw a non-convex function

# Define the function
def non_convex(x):
return 1 + (x - 2) ** 2 - cos(2 * pi * x)

# Generate x values
x = np.linspace(-1, 5, 400)

# Generate y values
y = [non_convex(i) for i in x]

# Create the plot
plt.figure(figsize=(8, 6))
plt.plot(x, y, label="y = 1 + (x-2)^2 - cos(2*pi*x)")

# Add a line that connects two points
x_non_convex = [0, 3]
y_non_convex = [non_convex(0), non_convex(3)]
plt.plot(
x_non_convex,
y_non_convex,
color="red",
linestyle="--",
label="convex comb of (0, non_convex(0)) and (3, non_convex(3))",
)

plt.title("Non-convex function: non_convex")
plt.xlabel("x")
plt.ylabel("y")
plt.legend()
plt.grid(True)
plt.show()


## For the second exercise you will need a new AMPL entity called a parameter¶

### Parameter declarations¶

For the second exercise, we will declare $\pi$ as a parameter in AMPL. To do this, we use the keyword param, followed by the parameter name. While assigning an initial is generally optional, in this instance we provide one. The declaration is then concluded with a semi-colon.

# EXERCISE 2¶

1. Create a code cell below.

2. Start with the magic: %%ampl_eval

3. Reset the state of the AMPL interpreter with reset; and reset option;.

4. Then use the following parameter definition: param pi = 4 * atan(1); to declare $\pi$.

5. Next, use keywords var and minimize, as well as the built-in function cos() to formulate the model that minimizes non_convex().

6. Compute the minimum using the ipopt solver.

7. Then print the solution using AMPL’s print command.

## SOLUTION¶

%%ampl_eval
reset; reset option;                # reset AMPL, this is needed for when we run the cell multiple times,
# AMPL complains about redeclaration of entities.
param pi = 4 * atan(1);             # Define pi
var x;                              # Declare our variable
minimize non_convex: 1 + (x-2)^2 - cos(2*pi*x);  # Define our objective function
option solver ipopt;                # Use Ipopt as our solver
solve;                              # Attempt to solve
print;                              # Add a new line (only for formatting purposes)
print "Optimum: (", x, non_convex, ")";    # Let's also print the solution!

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).
******************************************************************************

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  4.0000000e+00 0.00e+00 4.00e+00  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
1  3.8015805e+00 0.00e+00 2.29e-01  -1.0 9.64e-02    -  1.00e+00 1.00e+00f  1
2  3.8008142e+00 0.00e+00 3.18e-03  -1.7 6.64e-03    -  1.00e+00 1.00e+00f  1
3  3.8008141e+00 0.00e+00 6.73e-07  -3.8 9.48e-05    -  1.00e+00 1.00e+00f  1
4  3.8008141e+00 0.00e+00 3.02e-14  -8.6 2.01e-08    -  1.00e+00 1.00e+00f  1

Number of Iterations....: 4

(scaled)                 (unscaled)
Objective...............:   3.8008140784160975e+00    3.8008140784160975e+00
Dual infeasibility......:   3.0198066269804258e-14    3.0198066269804258e-14
Constraint violation....:   0.0000000000000000e+00    0.0000000000000000e+00
Complementarity.........:   0.0000000000000000e+00    0.0000000000000000e+00
Overall NLP error.......:   3.0198066269804258e-14    3.0198066269804258e-14

Number of objective function evaluations             = 5
Number of objective gradient evaluations             = 5
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             = 4
Total CPU secs in IPOPT (w/o function evaluations)   =      0.004
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.1031696971029012 3.8008140784160975 )


## Did we find the optimum?¶

Let’s check by plotting the results.

# Now instead of using magic cells we will be using the AMPL API directly
ampl = AMPL()  # Instantiate an AMPL object
ampl.reset()  # Reset AMPL
ampl.eval(
r"""
var x;
param pi = 4 * atan(1);
minimize non_convex: 1 + (x-2)^2 - cos(2*pi*x);
"""
)
ampl.option["solver"] = "ipopt"  # Use Ipopt as our solver
ampl.solve()  # Solve the problem with Ipopt
sol_df = ampl.get_data(
"x, non_convex"
).to_pandas()  # Retrieve the solution (we can retrieve x and non_convex because they are indexed over the same set).

# Define the function
def non_convex(x):
return 1 + (x - 2) ** 2 - cos(2 * pi * x)

# Generate x values
x = np.linspace(-1, 5, 400)

# Generate y values
y = [non_convex(i) for i in x]

# Create the plot
plt.figure(figsize=(8, 6))
plt.plot(x, y, label="y = 1 + (x-2)^2 - cos(2*pi*x)")

# Plot the values in sol_df
plt.scatter(
sol_df["x"], sol_df["non_convex"], color="red", s=100, label="solution point"
)

plt.title("Non-convex function: non_convex")
plt.xlabel("x")
plt.ylabel("y")
plt.legend()
plt.grid(True)
plt.show()

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).
******************************************************************************

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  4.0000000e+00 0.00e+00 4.00e+00  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
1  3.8015805e+00 0.00e+00 2.29e-01  -1.0 9.64e-02    -  1.00e+00 1.00e+00f  1
2  3.8008142e+00 0.00e+00 3.18e-03  -1.7 6.64e-03    -  1.00e+00 1.00e+00f  1
3  3.8008141e+00 0.00e+00 6.73e-07  -3.8 9.48e-05    -  1.00e+00 1.00e+00f  1
4  3.8008141e+00 0.00e+00 3.02e-14  -8.6 2.01e-08    -  1.00e+00 1.00e+00f  1

Number of Iterations....: 4

(scaled)                 (unscaled)
Objective...............:   3.8008140784160975e+00    3.8008140784160975e+00
Dual infeasibility......:   3.0198066269804258e-14    3.0198066269804258e-14
Constraint violation....:   0.0000000000000000e+00    0.0000000000000000e+00
Complementarity.........:   0.0000000000000000e+00    0.0000000000000000e+00
Overall NLP error.......:   3.0198066269804258e-14    3.0198066269804258e-14

Number of objective function evaluations             = 5
Number of objective gradient evaluations             = 5
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             = 4
Total CPU secs in IPOPT (w/o function evaluations)   =      0.003
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;


## As expected we only found a local optimum¶

To address this, let’s switch to a global solver. Global solvers excel at managing non-convex functions characterized by multiple local optima. In situations where pinpointing the global optimum is crucial, these solvers come into their own. However, it’s worth noting that they typically operate at a slower speeds compared to local solvers.

# EXERCISE 3¶

1. Go back to the previous code cell and change the solver to gurobi, then re-run the cell.

2. What happens if you change the default starting value of x := 0 to x := 1.5?

## SOLUTION¶

# Now instead of using magic cells we will be using the AMPL API directly
ampl = AMPL()  # Instantiate an AMPL object
ampl.reset()  # Reset AMPL
ampl.eval(
r"""
var x;
param pi = 4 * atan(1);
minimize non_convex: 1 + (x-2)^2 - cos(2*pi*x);
"""
)
ampl.option["solver"] = "gurobi"  # THIS TIME use Gurobi as our solver
ampl.solve()  # Solve the problem with Gurobi
sol_df = ampl.get_data(
"x, non_convex"
).to_pandas()  # Retrieve the solution (we can retrieve x and non_convex because they are indexed over the same set).

# Define the function
def non_convex(x):
return 1 + (x - 2) ** 2 - cos(2 * pi * x)

# Generate x values
x = np.linspace(-1, 5, 400)

# Generate y values
y = [non_convex(i) for i in x]

# Create the plot
plt.figure(figsize=(8, 6))
plt.plot(x, y, label="y = 1 + (x-2)^2 - cos(2*pi*x)")

# Plot the values in sol_df
plt.scatter(
sol_df["x"], sol_df["non_convex"], color="red", s=100, label="solution point"
)

plt.title("Non-convex function: non_convex")
plt.xlabel("x")
plt.ylabel("y")
plt.legend()
plt.grid(True)
plt.show()

Gurobi 11.0.0: Gurobi 11.0.0: optimal solution; objective 0.0001245693477
21 simplex iterations
1 branching nodes


# Now instead of using magic cells we will be using the AMPL API directly
ampl = AMPL()  # Instantiate an AMPL object
ampl.reset()  # Reset AMPL
ampl.eval(
r"""
var x := 1.5;                                             # Give x an initial value other than 0 (AMPL's default is 0)
param pi = 4 * atan(1);
minimize non_convex: 1 + (x-2)^2 - cos(2*pi*x);
"""
)
ampl.option["solver"] = "ipopt"  # Use Ipopt as our solver
ampl.solve()  # Solve the problem with Ipopt
sol_df = ampl.get_data(
"x, non_convex"
).to_pandas()  # Retrieve the solution (we can retrieve x and non_convex because they are indexed over the same set).

# Define the function
def non_convex(x):
return 1 + (x - 2) ** 2 - cos(2 * pi * x)

# Generate x values
x = np.linspace(-1, 5, 400)

# Generate y values
y = [non_convex(i) for i in x]

# Create the plot
plt.figure(figsize=(8, 6))
plt.plot(x, y, label="y = 1 + (x-2)^2 - cos(2*pi*x)")

# Plot the values in sol_df
plt.scatter(
sol_df["x"], sol_df["non_convex"], color="red", s=100, label="solution point"
)

plt.title("Non-convex function: non_convex")
plt.xlabel("x")
plt.ylabel("y")
plt.legend()
plt.grid(True)
plt.show()

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).
******************************************************************************

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  2.2500000e+00 0.00e+00 1.00e+00  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
1  2.2292158e+00 0.00e+00 1.60e+00  -1.7 1.60e-02   2.0 1.00e+00 1.00e+00f  1
2  2.2171747e+00 0.00e+00 1.86e+00  -1.7 6.97e-03   2.4 1.00e+00 1.00e+00f  1
3  2.1271626e+00 0.00e+00 3.15e+00  -1.7 3.58e-02   1.9 1.00e+00 1.00e+00f  1
4  2.0738808e+00 0.00e+00 3.68e+00  -1.7 1.56e-02   2.4 1.00e+00 1.00e+00f  1
5  1.6820191e+00 0.00e+00 5.88e+00  -1.7 8.05e-02   1.9 1.00e+00 1.00e+00f  1
6  3.6130577e-01 0.00e+00 5.01e+00  -1.7 9.62e-01   1.4 1.00e+00 5.00e-01f  2
7  3.8708552e-02 0.00e+00 1.78e+00  -1.7 1.79e-01    -  1.00e+00 1.00e+00f  1
8  2.2782440e-05 0.00e+00 4.35e-02  -1.7 4.44e-02    -  1.00e+00 1.00e+00f  1
9  4.3157924e-15 0.00e+00 5.98e-07  -2.5 1.05e-03    -  1.00e+00 1.00e+00f  1
iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
10  0.0000000e+00 0.00e+00 3.08e-15  -8.6 1.44e-08    -  1.00e+00 1.00e+00f  1

Number of Iterations....: 10

(scaled)                 (unscaled)
Objective...............:   0.0000000000000000e+00    0.0000000000000000e+00
Dual infeasibility......:   3.0778731099548636e-15    3.0778731099548636e-15
Constraint violation....:   0.0000000000000000e+00    0.0000000000000000e+00
Complementarity.........:   0.0000000000000000e+00    0.0000000000000000e+00
Overall NLP error.......:   3.0778731099548636e-15    3.0778731099548636e-15

Number of objective function evaluations             = 16
Number of objective gradient evaluations             = 11
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             = 10
Total CPU secs in IPOPT (w/o function evaluations)   =      0.010
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;


# EXERCISE 4¶

1. Let’s return to our difficult function and try solving it with another solver called highs. Did we find the optimum?

## SOLUTION¶

ampl = AMPL()  # Instantiate an AMPL object
ampl.eval(
r"""
var x;                                              # Declare our variable
minimize difficult: (x-1)^2 - log(x+1);             # Define our objective function
"""
)

ampl.option["solver"] = "highs"  # Select the solver
ampl.solve()  # Attempt to solve

HiGHS 1.6.0:
------------ WARNINGS ------------
WARNING:  "PLApprox"
An expression of type 'LogConstraint' has been
piecewise-linearly approximated. Set cvt:plapprox:reltol
to control precision (currently 0.010000).
WARNING:  "PLApproxDomain"
Argument domain of a 'LogConstraint'
has been reduced to [0.000001, 1000000.000000] for numerical reasons
(partially controlled by cvt:plapprox:domain.)
------------ WARNINGS ------------
WARNING:  "PLApprox"
An expression of type 'LogConstraint' has been
piecewise-linearly approximated. Set cvt:plapprox:reltol
to control precision (currently 0.010000).
WARNING:  "PLApproxDomain"
Argument domain of a 'LogConstraint'
has been reduced to [0.000001, 1000000.000000] for numerical reasons
(partially controlled by cvt:plapprox:domain.)
Error -1 for call Highs_run(lp())


HiGHS is a solver adept at tackling Mixed Integer Programming (MIP) and Quadratic Programming (QP) problems, which means it can efficiently handle linear programming, integer programming, and quadratic programming challenges. However, it encounters limitations with our objective function, which includes a logarithmic term.

As HiGHS cannot directly process the logarithmic element, the MP solver driver compensates by approximating this term using piecewise linear functions. The WARNING message you encountered is to alert you that such an approximation has been applied.

The term ‘LogConstraint’ might seem misleading. This stems from AMPL’s bookkeeping method where the objective function is treated as the 0th constraint. Despite the approximation, HiGHS is unable to minimize our function and consequently returns an error.

## Programmatically checking the solve result status¶

The following code segment demonstrates how to verify programmatically whether a satisfactory solution has been attained.

ampl = AMPL()  # Instantiate an AMPL object
ampl.eval(
r"""
var x;                                              # Declare our variable
minimize difficult: (x-1)^2 - log(x+1);             # Define our objective function
"""
)

ampl.option["solver"] = "highs"  # Select the solver
ampl.solve()  # Attempt to solve
print(
ampl.option["solve_result_table"]
)  # Print the solve result table, this will inform us of the various solution codes.
result_df = ampl.get_data("solve_result_num").to_pandas()  # Retrieve solution status
# Check if the problem was solved if not print warning
srn = result_df["solve_result_num"].iloc[0]
if srn != 0:
print(f"Warning: Problem not solved to optimality!\n\t solve_result_num = {srn}")

HiGHS 1.6.0:
------------ WARNINGS ------------
WARNING:  "PLApprox"
An expression of type 'LogConstraint' has been
piecewise-linearly approximated. Set cvt:plapprox:reltol
to control precision (currently 0.010000).
WARNING:  "PLApproxDomain"
Argument domain of a 'LogConstraint'
has been reduced to [0.000001, 1000000.000000] for numerical reasons
(partially controlled by cvt:plapprox:domain.)
------------ WARNINGS ------------
WARNING:  "PLApprox"
An expression of type 'LogConstraint' has been
piecewise-linearly approximated. Set cvt:plapprox:reltol
to control precision (currently 0.010000).
WARNING:  "PLApproxDomain"
Argument domain of a 'LogConstraint'
has been reduced to [0.000001, 1000000.000000] for numerical reasons
(partially controlled by cvt:plapprox:domain.)
Error -1 for call Highs_run(lp())

0	solved
100	solved?
200	infeasible
300	unbounded
400	limit
500	failure

Warning: Problem not solved to optimality!
solve_result_num = 500