struct Diameter
length::Float64
chord::Tuple{Float64,Float64}
end
struct Shape
at::Function
name::String
end
point(shape::Shape, t) = shape.at(t - floor(t))Largest Diameter
Find the two points of a closed shape that lie furthest apart, when the shape is a black box the solver can only evaluate.
Introduction
The goal of this example is to show a non-convex nonlinear problem involving a black-box function.
We consider a two-dimensional simple shape given as a function \(f: t \mapsto (x(t), y(t))\) that takes a parameter \(t \ge 0\) as input and returns the corresponding point in the plane. The goal is to find two points from the shape with the largest distance between them.
Example by Pierre Lemaire.
Problem description
Input
- A closed shape \(f: t \mapsto (x(t), y(t))\), where \(t\) and \(t + 1\) give the same point
Variables
- \(t_1, t_2 \ge 0\), the parameters of the 2 points we are looking for
Objective: maximize the distance between the two points
\[ \max_{t_1,\, t_2} \quad \sqrt{\big(x(t_2) - x(t_1)\big)^2 + \big(y(t_2) - y(t_1)\big)^2} \]
Note that there are no constraints.
The problem has the following properties:
- 2 continuous variables: the parameters of the 2 points we are looking for
- A black-box function
- The black-box function is non-convex
- The black-box function is “roughly” differentiable
- An evaluation of the black-box function is cheap
The non-convexity of the objective function can be seen from the plots below. Indeed, the shapes contain multiple diameters that cannot be improved by infinitesimal changes of the variable values. These diameters all correspond to locally optimal solutions of the problem.
To illustrate this, we solve the problem first with the default configuration of Knitro. By default, Knitro stops as soon as it finds a locally optimal solution. Then we enable multistart. This option makes Knitro look for multiple locally optimal solutions and increases the chances of finding a globally optimal solution.
Input data
A shape is a function of one parameter returning a point. Shape holds that function and does nothing else. The parameter is reduced modulo one turn, so t and t + 1 give the same point, and the solver can wander outside [0, 1] without leaving the outline. Nothing about the geometry is exposed beyond the ability to call it.
Diameter carries what a solve returns, the length it found and the chord, the two parameters whose points lie that far apart.
Three kinds of outline are used. The rectangle is a control. It is convex, so its diameter is its diagonal. A blob is a circle whose radius is stirred by a mix of harmonics, deep enough that several chords cannot be lengthened by any small move, and a lower roughness keeps its lobes shallow. Each blob is seeded by its own number, so no two are alike and every run reproduces them.
Show the shape generators
function rectangle(width, height)
function at(t)
t < 0.25 && return (4 * width * t, 0.0)
t < 0.50 && return (width, 4 * height * (t - 0.25))
t < 0.75 && return (width - 4 * width * (t - 0.5), height)
return (0.0, height - 4 * height * (t - 0.75))
end
return Shape(at, "rectangle($width, $height)")
end
const HARMONICS = [
t -> cos(4 * pi * t),
t -> sin(4 * pi * t),
t -> cos(6 * pi * t),
t -> sin(6 * pi * t),
t -> cos(8 * pi * t),
t -> exp(-25 * (t - 0.5)^2) - exp(-25 * 0.25),
]
function weights(seed, count)
state = seed * 2654435761 % 2^31
drawn = Float64[]
for _ in 1:count
state = (1103515245 * state + 12345) % 2^31
push!(drawn, state / 2^31)
end
return drawn
end
function blob(seed; roughness=0.45)
drawn = weights(seed, length(HARMONICS))
amplitudes = [roughness * (2 * w - 1) / k for (k, w) in enumerate(drawn)]
radius(t) = 1 + sum(a * f(t) for (a, f) in zip(amplitudes, HARMONICS))
at(t) = (radius(t) * cos(2 * pi * t), radius(t) * sin(2 * pi * t))
return Shape(at, "blob($seed)")
end
function transform(shape::Shape, matrix)
function at(t)
x, y = point(shape, t)
return (
matrix[1, 1] * x + matrix[1, 2] * y, matrix[2, 1] * x + matrix[2, 2] * y
)
end
return Shape(at, "transform($(shape.name))")
endThe five shapes below are the convex control, three blobs of increasing waviness, and one of them stretched and sheared.
shapes = [
rectangle(6, 8),
blob(19),
blob(14),
blob(11),
transform(blob(35), [1.4 0.0; 0.0 0.7]),
]There are no axes. The coordinates say nothing on their own, only the form of the outline and the length of a chord across it. A chord that a solve stopped short at is drawn muted and dashed beside the best one found, so the two can be compared.
draw_all(shapes)Model implementation
using KNITROThere is no expression to hand over, so the model is not built through JuMP here: KNITRO.jl also wraps Knitro’s C API one function at a time, and that is the layer callbacks live at. A context is created, two bounded variables are added to it, and the objective goes in as a function Knitro calls with a pair of parameter values.
function maximize_diameter(shape; multistart=false, num_threads=1)
kc = KNITRO.KN_new()
KNITRO.KN_add_vars(kc, 2, C_NULL)
KNITRO.KN_set_var_lobnds_all(kc, [0.0, 0.0])
KNITRO.KN_set_var_upbnds_all(kc, [1.0, 1.0])
function objective(kc, cb, request, result, params)
request.evalRequestCode == KNITRO.KN_RC_EVALFC || return -1
t1, t2 = request.x
result.obj[1] = hypot((point(shape, t2) .- point(shape, t1))...)
return 0
end
KNITRO.KN_add_objective_callback(kc, objective)
KNITRO.KN_set_obj_goal(kc, KNITRO.KN_OBJGOAL_MAXIMIZE)
if multistart
KNITRO.KN_set_int_param(kc, KNITRO.KN_PARAM_MSENABLE, KNITRO.KN_MS_ENABLE_YES)
KNITRO.KN_set_int_param(kc, KNITRO.KN_PARAM_NUMTHREADS, num_threads)
end
KNITRO.KN_solve(kc)
_, value, x, _ = KNITRO.KN_get_solution(kc)
KNITRO.KN_free(kc)
return Diameter(value, (x[1], x[2]))
endevalRequestCode is checked because Knitro reuses one callback for several kinds of evaluation; returning -1 for anything else says this callback does not answer it. The value goes back in result.obj[1] rather than as a return value, the return code being reserved for whether the evaluation succeeded. No gradient is supplied, so Knitro takes finite differences of the same function, and that is why the shape has to be roughly differentiable.
One shape, one solve
By default, Knitro stops as soon as it finds a locally optimal solution, wherever the search happens to land.
single = maximize_diameter(shapes[2]);=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Coefficient range:
linear objective: [0e+00, 0e+00] | [0e+00, 0e+00]
linear constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic objective: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
variable bounds: [1e+00, 1e+00] | [1e+00, 1e+00]
constraint bounds: [0e+00, 0e+00] | [0e+00, 0e+00]
Knitro using the Interior-Point/Barrier Direct algorithm.
Iter Objective FeasError OptError ||Step|| Time
-------- -------------- --------- --------- --------- --------
0 1.374231e+00 0.00e+00
10 1.864329e+00 0.00e+00 2.08e-08 1.63e-07 0.19
EXIT: Locally optimal solution found.
Final Statistics
----------------
Final objective value = 1.86432897978291e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 2.08e-08 / 2.08e-08
# of iterations = 10
# of CG iterations = 0
# of function evaluations = 56
# of gradient evaluations = 0
Total program time (secs) = 0.19376 ( 0.189 CPU time)
Time spent in evaluations (secs) = 0.00064
================================================================================
Show the full outputHide the full output
draw(shapes[2]; chord=single.chord, title="One solve")The same shape, with multistart
KN_PARAM_MSENABLE restarts the search from many initial parameter pairs and keeps the best. On a two-variable problem whose objective costs two function calls and a square root, that is cheap enough to be the default worth reaching for.
best = maximize_diameter(shapes[2]; multistart=true);=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_enable 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Knitro multistart will run with 1 thread.
Return codes description
------------------------
0: The final solution satisfies the termination conditions for verifying optimality.
-100 to -199: A feasible approximate solution was found.
-200 to -299: Knitro terminated at an infeasible point.
-300 to -301: The problem was determined to be unbounded.
-400 to -499: Knitro terminated because it reached a pre-defined limit.
-400 to -409: A feasible point was found.
-410 to -419: No feasible point was found.
-500 to -599: Knitro terminated with an input error or some non-standard error.
A more detailed description of individual return codes and their corresponding
termination messages is provided at
https://www.artelys.com/app/docs/knitro/3_referenceManual/returnCodes.html
Solve Thrd Status Objective FeasError Opt Error Solve Time Real Time
----- ---- ------ ------------ ----------- ----------- ----------- -----------
0 0 0 1.86433 0.00000e+00 2.07697e-08 3.04306e-03 3.82186e-03
1 0 0 2.51988 0.00000e+00 8.37698e-08 1.62035e-03 5.56744e-03
2 0 0 1.97992 0.00000e+00 3.31943e-06 1.03482e-03 6.71096e-03
3 0 0 2.51988 0.00000e+00 6.42402e-07 1.07278e-03 7.89362e-03
4 0 0 1.86433 0.00000e+00 4.36215e-07 1.15643e-03 9.16378e-03
5 0 0 2.51988 0.00000e+00 4.19539e-08 1.16345e-03 1.04393e-02
6 0 0 1.97992 0.00000e+00 8.91931e-07 1.09817e-03 1.16527e-02
7 0 0 2.51988 0.00000e+00 8.72639e-07 1.02463e-03 1.27945e-02
8 0 0 2.51988 0.00000e+00 1.09081e-07 1.15752e-03 1.40725e-02
9 0 0 2.51988 0.00000e+00 2.25420e-08 1.38333e-03 1.55813e-02
10 0 0 2.51988 0.00000e+00 1.80353e-07 1.15151e-03 1.68590e-02
11 0 0 1.97992 0.00000e+00 4.60065e-09 1.07754e-03 1.80596e-02
12 0 0 2.51988 0.00000e+00 1.26075e-07 1.09520e-03 1.92786e-02
13 0 0 2.51988 0.00000e+00 1.12705e-08 1.20872e-03 2.06104e-02
14 0 0 2.51988 0.00000e+00 2.22191e-08 1.48863e-03 2.22249e-02
15 0 0 2.51988 0.00000e+00 1.34253e-07 1.08518e-03 2.34339e-02
16 0 0 1.86433 0.00000e+00 9.06238e-09 1.20645e-03 2.47717e-02
17 0 0 2.51988 0.00000e+00 1.40632e-08 1.09638e-03 2.59904e-02
MULTISTART: Best locally optimal solution is returned.
EXIT: Multi-start stopped because of a low estimated probability of finding
an unobserved solution. Set ms_terminate=0 to disable multi-start rule-based
termination procedure.
18 solve(s) returned satisfactory solutions.
Final Statistics
----------------
Final objective value = 2.51988484663122e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 1.09e-07 / 1.09e-07
# of iterations = 166
# of CG iterations = 0
# of function evaluations = 946
# of gradient evaluations = 0
Total program time (secs) = 0.02606 ( 0.026 CPU time)
================================================================================
Show the full outputHide the full output
draw(shapes[2]; chord=best.chord, missed=single.chord, title="With multistart")Both chords end on the outline and neither can be lengthened by nudging either end. The dashed one is a quarter shorter all the same.
Every shape
plain = [maximize_diameter(shape) for shape in shapes]
restarted = [maximize_diameter(shape; multistart=true) for shape in shapes];Show the full outputHide the full output
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Coefficient range:
linear objective: [0e+00, 0e+00] | [0e+00, 0e+00]
linear constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic objective: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
variable bounds: [1e+00, 1e+00] | [1e+00, 1e+00]
constraint bounds: [0e+00, 0e+00] | [0e+00, 0e+00]
Knitro using the Interior-Point/Barrier Direct algorithm.
Iter Objective FeasError OptError ||Step|| Time
-------- -------------- --------- --------- --------- --------
0 4.640061e+00 0.00e+00
10 9.993806e+00 0.00e+00 4.80e+00 4.51e-03 0.04
20 1.000000e+01 0.00e+00 5.00e-01 0.00e+00 0.05
EXIT: Primal feasible solution estimate cannot be improved; desired accuracy
in dual feasibility could not be achieved.
HINT: Performance may improve by trying a different value for user option
bar_murule or by enabling the concurrent solver (concurrent_solver=1).
Final Statistics
----------------
Final objective value = 9.99999983588116e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 5.00e-01 / 3.47e-02
# of iterations = 20
# of CG iterations = 5
# of function evaluations = 214
# of gradient evaluations = 0
Total program time (secs) = 0.04551 ( 0.046 CPU time)
Time spent in evaluations (secs) = 0.02075
================================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Coefficient range:
linear objective: [0e+00, 0e+00] | [0e+00, 0e+00]
linear constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic objective: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
variable bounds: [1e+00, 1e+00] | [1e+00, 1e+00]
constraint bounds: [0e+00, 0e+00] | [0e+00, 0e+00]
Knitro using the Interior-Point/Barrier Direct algorithm.
Iter Objective FeasError OptError ||Step|| Time
-------- -------------- --------- --------- --------- --------
0 1.374231e+00 0.00e+00
10 1.864329e+00 0.00e+00 2.08e-08 1.63e-07 0.00
EXIT: Locally optimal solution found.
Final Statistics
----------------
Final objective value = 1.86432897978291e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 2.08e-08 / 2.08e-08
# of iterations = 10
# of CG iterations = 0
# of function evaluations = 56
# of gradient evaluations = 0
Total program time (secs) = 0.00167 ( 0.002 CPU time)
Time spent in evaluations (secs) = 0.00059
================================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Coefficient range:
linear objective: [0e+00, 0e+00] | [0e+00, 0e+00]
linear constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic objective: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
variable bounds: [1e+00, 1e+00] | [1e+00, 1e+00]
constraint bounds: [0e+00, 0e+00] | [0e+00, 0e+00]
Knitro using the Interior-Point/Barrier Direct algorithm.
Iter Objective FeasError OptError ||Step|| Time
-------- -------------- --------- --------- --------- --------
0 1.423355e+00 0.00e+00
7 2.102511e+00 0.00e+00 3.96e-08 1.87e-06 0.00
EXIT: Locally optimal solution found.
Final Statistics
----------------
Final objective value = 2.10251132372656e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 3.96e-08 / 9.73e-09
# of iterations = 7
# of CG iterations = 0
# of function evaluations = 44
# of gradient evaluations = 0
Total program time (secs) = 0.00114 ( 0.001 CPU time)
Time spent in evaluations (secs) = 0.00046
================================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Coefficient range:
linear objective: [0e+00, 0e+00] | [0e+00, 0e+00]
linear constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic objective: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
variable bounds: [1e+00, 1e+00] | [1e+00, 1e+00]
constraint bounds: [0e+00, 0e+00] | [0e+00, 0e+00]
Knitro using the Interior-Point/Barrier Direct algorithm.
Iter Objective FeasError OptError ||Step|| Time
-------- -------------- --------- --------- --------- --------
0 1.418479e+00 0.00e+00
9 2.353827e+00 0.00e+00 3.75e-08 3.44e-07 0.00
EXIT: Locally optimal solution found.
Final Statistics
----------------
Final objective value = 2.35382655759700e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 3.75e-08 / 3.75e-08
# of iterations = 9
# of CG iterations = 0
# of function evaluations = 54
# of gradient evaluations = 0
Total program time (secs) = 0.00123 ( 0.001 CPU time)
Time spent in evaluations (secs) = 0.00056
================================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Coefficient range:
linear objective: [0e+00, 0e+00] | [0e+00, 0e+00]
linear constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic objective: [0e+00, 0e+00] | [0e+00, 0e+00]
quadratic constraints: [0e+00, 0e+00] | [0e+00, 0e+00]
variable bounds: [1e+00, 1e+00] | [1e+00, 1e+00]
constraint bounds: [0e+00, 0e+00] | [0e+00, 0e+00]
Knitro using the Interior-Point/Barrier Direct algorithm.
Iter Objective FeasError OptError ||Step|| Time
-------- -------------- --------- --------- --------- --------
0 1.928182e+00 0.00e+00
6 2.356799e+00 0.00e+00 4.69e-06 3.18e-05 0.00
EXIT: Locally optimal solution found.
Final Statistics
----------------
Final objective value = 2.35679909647069e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 4.69e-06 / 7.23e-07
# of iterations = 6
# of CG iterations = 0
# of function evaluations = 40
# of gradient evaluations = 0
Total program time (secs) = 0.00117 ( 0.001 CPU time)
Time spent in evaluations (secs) = 0.00050
================================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_enable 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Knitro multistart will run with 1 thread.
Return codes description
------------------------
0: The final solution satisfies the termination conditions for verifying optimality.
-100 to -199: A feasible approximate solution was found.
-200 to -299: Knitro terminated at an infeasible point.
-300 to -301: The problem was determined to be unbounded.
-400 to -499: Knitro terminated because it reached a pre-defined limit.
-400 to -409: A feasible point was found.
-410 to -419: No feasible point was found.
-500 to -599: Knitro terminated with an input error or some non-standard error.
A more detailed description of individual return codes and their corresponding
termination messages is provided at
https://www.artelys.com/app/docs/knitro/3_referenceManual/returnCodes.html
Solve Thrd Status Objective FeasError Opt Error Solve Time Real Time
----- ---- ------ ------------ ----------- ----------- ----------- -----------
0 0 -102 10.0000 0.00000e+00 0.500000 2.31417e-03 2.80963e-03
0 0 * 10.0000 0.00000e+00
1 0 -102 10.0000 0.00000e+00 0.467589 1.70359e-03 4.65350e-03
2 0 -102 10.0000 0.00000e+00 0.500000 7.31171e-02 7.79101e-02
3 0 -102 10.0000 0.00000e+00 0.500000 2.52053e-02 0.103276
4 0 -102 10.0000 0.00000e+00 0.500000 2.15240e-03 0.105565
4 0 * 10.0000 0.00000e+00
5 0 -102 10.0000 0.00000e+00 0.500000 2.21548e-03 0.107932
6 0 0 10.0000 0.00000e+00 1.09855e-11 2.08072e-03 0.110158
7 0 -102 10.0000 0.00000e+00 0.500000 1.83608e-03 0.112131
8 0 -103 10.0000 0.00000e+00 6.67387 3.25957e-03 0.115543
9 0 -102 10.0000 0.00000e+00 2.70977 2.54912e-03 0.118252
9 0 * 10.0000 0.00000e+00
10 0 -102 10.0000 0.00000e+00 10.9106 2.40306e-02 0.142442
10 0 * 10.0000 0.00000e+00
11 0 -102 10.0000 0.00000e+00 0.500000 2.90928e-03 0.145536
12 0 -102 10.0000 0.00000e+00 0.500000 1.86104e-03 0.147541
12 0 * 10.0000 0.00000e+00
13 0 0 10.0000 0.00000e+00 1.98682e-07 1.75934e-03 0.149463
14 0 -102 10.0000 0.00000e+00 2.76922 2.39383e-03 0.152008
15 0 -102 10.0000 0.00000e+00 0.876471 2.04403e-03 0.154194
16 0 -102 10.0000 0.00000e+00 0.500000 1.61240e-03 0.155936
16 0 * 10.0000 0.00000e+00
17 0 -102 10.0000 0.00000e+00 0.500000 1.64995e-03 0.157724
17 0 * 10.0000 0.00000e+00
18 0 -102 10.0000 0.00000e+00 0.500000 2.11815e-03 0.159982
18 0 * 10.0000 0.00000e+00
19 0 -101 10.0000 0.00000e+00 0.500000 2.26059e-03 0.162390
MULTISTART: Best locally optimal solution is returned.
EXIT: All multi-start solves have terminated.
2 solve(s) returned satisfactory solutions.
1 solve(s) reached xtol limit.
16 solve(s) reached no improvement limit.
1 solve(s) reached ftol limit.
Final Statistics
----------------
Final objective value = 9.99999986251271e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 1.10e-11 / 7.63e-13
# of iterations = 469
# of CG iterations = 0
# of function evaluations = 4742
# of gradient evaluations = 0
Total program time (secs) = 0.16246 ( 0.162 CPU time)
================================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_enable 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Knitro multistart will run with 1 thread.
Return codes description
------------------------
0: The final solution satisfies the termination conditions for verifying optimality.
-100 to -199: A feasible approximate solution was found.
-200 to -299: Knitro terminated at an infeasible point.
-300 to -301: The problem was determined to be unbounded.
-400 to -499: Knitro terminated because it reached a pre-defined limit.
-400 to -409: A feasible point was found.
-410 to -419: No feasible point was found.
-500 to -599: Knitro terminated with an input error or some non-standard error.
A more detailed description of individual return codes and their corresponding
termination messages is provided at
https://www.artelys.com/app/docs/knitro/3_referenceManual/returnCodes.html
Solve Thrd Status Objective FeasError Opt Error Solve Time Real Time
----- ---- ------ ------------ ----------- ----------- ----------- -----------
0 0 0 1.86433 0.00000e+00 2.07697e-08 1.17977e-03 1.72221e-03
1 0 0 2.51988 0.00000e+00 8.37698e-08 1.40398e-03 3.22544e-03
2 0 0 1.97992 0.00000e+00 3.31943e-06 9.54673e-04 4.27941e-03
3 0 0 2.51988 0.00000e+00 6.42402e-07 1.00081e-03 5.38209e-03
4 0 0 1.86433 0.00000e+00 4.36215e-07 1.10445e-03 6.59069e-03
5 0 0 2.51988 0.00000e+00 4.19539e-08 1.12032e-03 7.81711e-03
6 0 0 1.97992 0.00000e+00 8.91931e-07 1.07004e-03 8.99627e-03
7 0 0 2.51988 0.00000e+00 8.72639e-07 9.97969e-04 1.01058e-02
8 0 0 2.51988 0.00000e+00 1.09081e-07 1.11975e-03 1.13400e-02
9 0 0 2.51988 0.00000e+00 2.25420e-08 1.35106e-03 1.28172e-02
10 0 0 2.51988 0.00000e+00 1.80353e-07 1.13401e-03 1.40715e-02
11 0 0 1.97992 0.00000e+00 4.60065e-09 1.06609e-03 1.52536e-02
12 0 0 2.51988 0.00000e+00 1.26075e-07 1.06503e-03 1.64371e-02
13 0 0 2.51988 0.00000e+00 1.12705e-08 1.22115e-03 1.77788e-02
14 0 0 2.51988 0.00000e+00 2.22191e-08 1.51656e-03 1.94209e-02
15 0 0 2.51988 0.00000e+00 1.34253e-07 1.09885e-03 2.06409e-02
16 0 0 1.86433 0.00000e+00 9.06238e-09 1.21244e-03 2.19787e-02
17 0 0 2.51988 0.00000e+00 1.40632e-08 1.09740e-03 2.31970e-02
MULTISTART: Best locally optimal solution is returned.
EXIT: Multi-start stopped because of a low estimated probability of finding
an unobserved solution. Set ms_terminate=0 to disable multi-start rule-based
termination procedure.
18 solve(s) returned satisfactory solutions.
Final Statistics
----------------
Final objective value = 2.51988484663122e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 1.09e-07 / 1.09e-07
# of iterations = 166
# of CG iterations = 0
# of function evaluations = 946
# of gradient evaluations = 0
Total program time (secs) = 0.02327 ( 0.023 CPU time)
================================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_enable 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Knitro multistart will run with 1 thread.
Return codes description
------------------------
0: The final solution satisfies the termination conditions for verifying optimality.
-100 to -199: A feasible approximate solution was found.
-200 to -299: Knitro terminated at an infeasible point.
-300 to -301: The problem was determined to be unbounded.
-400 to -499: Knitro terminated because it reached a pre-defined limit.
-400 to -409: A feasible point was found.
-410 to -419: No feasible point was found.
-500 to -599: Knitro terminated with an input error or some non-standard error.
A more detailed description of individual return codes and their corresponding
termination messages is provided at
https://www.artelys.com/app/docs/knitro/3_referenceManual/returnCodes.html
Solve Thrd Status Objective FeasError Opt Error Solve Time Real Time
----- ---- ------ ------------ ----------- ----------- ----------- -----------
0 0 0 2.10251 0.00000e+00 3.96453e-08 9.88733e-04 1.50152e-03
1 0 0 2.73711 0.00000e+00 2.57638e-08 1.30098e-03 2.90148e-03
2 0 0 2.73711 0.00000e+00 2.29779e-07 1.25542e-03 4.25764e-03
3 0 0 2.73711 0.00000e+00 1.65753e-07 1.06187e-03 5.42210e-03
4 0 0 2.73711 0.00000e+00 1.03399e-07 1.20948e-03 6.73617e-03
5 0 0 2.73711 0.00000e+00 5.74448e-09 1.26175e-03 8.10573e-03
6 0 0 2.73711 0.00000e+00 7.21679e-07 1.25997e-03 9.48212e-03
MULTISTART: Best locally optimal solution is returned.
EXIT: Multi-start stopped because of a low estimated probability of finding
an unobserved solution. Set ms_terminate=0 to disable multi-start rule-based
termination procedure.
7 solve(s) returned satisfactory solutions.
Final Statistics
----------------
Final objective value = 2.73710681448387e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 7.22e-07 / 7.22e-07
# of iterations = 64
# of CG iterations = 0
# of function evaluations = 374
# of gradient evaluations = 0
Total program time (secs) = 0.00954 ( 0.009 CPU time)
================================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_enable 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Knitro multistart will run with 1 thread.
Return codes description
------------------------
0: The final solution satisfies the termination conditions for verifying optimality.
-100 to -199: A feasible approximate solution was found.
-200 to -299: Knitro terminated at an infeasible point.
-300 to -301: The problem was determined to be unbounded.
-400 to -499: Knitro terminated because it reached a pre-defined limit.
-400 to -409: A feasible point was found.
-410 to -419: No feasible point was found.
-500 to -599: Knitro terminated with an input error or some non-standard error.
A more detailed description of individual return codes and their corresponding
termination messages is provided at
https://www.artelys.com/app/docs/knitro/3_referenceManual/returnCodes.html
Solve Thrd Status Objective FeasError Opt Error Solve Time Real Time
----- ---- ------ ------------ ----------- ----------- ----------- -----------
0 0 0 2.35383 0.00000e+00 3.75103e-08 1.24075e-03 1.81209e-03
1 0 0 2.35383 0.00000e+00 2.22144e-07 1.54616e-03 3.46268e-03
2 0 0 2.35383 0.00000e+00 4.41424e-08 1.01474e-03 4.57853e-03
3 0 0 2.35383 0.00000e+00 7.35753e-09 1.08233e-03 5.76488e-03
4 0 0 2.35383 0.00000e+00 1.30708e-08 1.37413e-03 7.24716e-03
5 0 0 2.35383 0.00000e+00 7.19097e-08 1.31725e-03 8.67493e-03
6 0 0 2.35383 0.00000e+00 8.01920e-07 1.53688e-03 1.03280e-02
MULTISTART: Best locally optimal solution is returned.
EXIT: Multi-start stopped because of a low estimated probability of finding
an unobserved solution. Set ms_terminate=0 to disable multi-start rule-based
termination procedure.
7 solve(s) returned satisfactory solutions.
Final Statistics
----------------
Final objective value = 2.35382655759700e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 7.19e-08 / 7.19e-08
# of iterations = 75
# of CG iterations = 0
# of function evaluations = 415
# of gradient evaluations = 0
Total program time (secs) = 0.01039 ( 0.010 CPU time)
================================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro using 1 thread.
No start point provided -- Knitro computing one.
Knitro performing finite-difference gradient computation with 1 thread.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
feastol 1e-06
feastol_abs 0.001
mip_numthreads 1
ms_enable 1
ms_numthreads 1
numthreads 1
opttol 1e-06
opttol_abs 0.001
Problem Characteristics | Presolved
-----------------------
Problem type: NLP (bound constrained)
Objective: maximize / general
Number of variables: 2 | 2
bounds: lower upper range | lower upper range
0 0 2 | 0 0 2
free fixed | free fixed
0 0 | 0 0
Number of constraints: 0 | 0
eq. ineq. range | eq. ineq. range
linear: 0 0 0 | 0 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 0 0 0 | 0 0 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 0 0 | 0 0
quadratic: 0 0 0 | 0 0 0
nonlinear: 2 0 0 | 2 0 0
total: 2 0 0 | 2 0 3
Knitro multistart will run with 1 thread.
Return codes description
------------------------
0: The final solution satisfies the termination conditions for verifying optimality.
-100 to -199: A feasible approximate solution was found.
-200 to -299: Knitro terminated at an infeasible point.
-300 to -301: The problem was determined to be unbounded.
-400 to -499: Knitro terminated because it reached a pre-defined limit.
-400 to -409: A feasible point was found.
-410 to -419: No feasible point was found.
-500 to -599: Knitro terminated with an input error or some non-standard error.
A more detailed description of individual return codes and their corresponding
termination messages is provided at
https://www.artelys.com/app/docs/knitro/3_referenceManual/returnCodes.html
Solve Thrd Status Objective FeasError Opt Error Solve Time Real Time
----- ---- ------ ------------ ----------- ----------- ----------- -----------
0 0 0 2.35680 0.00000e+00 4.69038e-06 1.03177e-03 1.60971e-03
1 0 0 2.78954 0.00000e+00 9.41378e-07 1.23942e-03 2.94671e-03
2 0 0 1.92686 0.00000e+00 2.71389e-07 1.12742e-03 4.17330e-03
3 0 0 2.78954 0.00000e+00 1.16209e-07 1.39473e-03 5.67188e-03
4 0 0 2.35680 0.00000e+00 1.04144e-07 1.00564e-03 6.78170e-03
5 0 0 2.34668 0.00000e+00 2.96207e-07 1.40863e-03 8.29897e-03
6 0 0 2.35680 0.00000e+00 8.09767e-08 1.15545e-03 9.56516e-03
7 0 0 2.78954 0.00000e+00 1.16158e-08 1.45611e-03 1.11384e-02
8 0 0 2.08788 0.00000e+00 4.78238e-06 1.08966e-03 1.23444e-02
9 0 0 2.34668 0.00000e+00 4.52568e-07 1.03876e-03 1.35048e-02
10 0 0 1.92686 0.00000e+00 1.76993e-07 1.28084e-03 1.49066e-02
11 0 0 1.92686 0.00000e+00 1.16464e-08 1.20412e-03 1.62285e-02
12 0 0 2.78954 0.00000e+00 3.35834e-07 1.31082e-03 1.76590e-02
13 0 0 2.35680 0.00000e+00 2.33311e-06 1.24963e-03 1.90301e-02
14 0 0 2.35680 0.00000e+00 6.94009e-08 1.18789e-03 2.03386e-02
15 0 0 2.78954 0.00000e+00 6.36924e-08 1.05045e-03 2.15079e-02
16 0 0 2.35680 0.00000e+00 7.44896e-12 9.98688e-04 2.26259e-02
17 0 0 2.78954 0.00000e+00 2.58349e-09 1.29072e-03 2.40357e-02
18 0 0 2.34668 0.00000e+00 4.11399e-07 1.42637e-03 2.55910e-02
19 0 0 2.08788 0.00000e+00 2.92543e-06 1.10825e-03 2.68325e-02
MULTISTART: Best locally optimal solution is returned.
EXIT: All multi-start solves have terminated.
20 solve(s) returned satisfactory solutions.
Final Statistics
----------------
Final objective value = 2.78953619795665e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 6.37e-08 / 6.37e-08
# of iterations = 158
# of CG iterations = 0
# of function evaluations = 945
# of gradient evaluations = 0
Total program time (secs) = 0.02690 ( 0.027 CPU time)
================================================================================
draw_diameters(shapes, plain, restarted)What multistart is worth
Solving each shape both ways puts two numbers side by side, the first chord Knitro settles on and then the best of the restarts.
report_diameters(shapes, plain, restarted)shape one solve multistart gain
----------------------------------------------------
rectangle(6, 8) 10.000 10.000 +0.0%
blob(19) 1.864 2.520 +35.2%
blob(14) 2.103 2.737 +30.2%
blob(11) 2.354 2.354 +0.0%
transform(blob(35)) 2.357 2.790 +18.4%The rectangle is the control. It is convex, every local optimum is the global one, and the two solves agree exactly. So do some of the wrinkled outlines. On others the single solve lands a sixth to a quarter short of the answer. That is not a rounding gap but a different chord across a different pair of lobes.
The point is not the size of the gain but that nothing in the first solve tells you which case you are in. A black-box objective offers no bound and no certificate; the only evidence that a chord is the longest is having started from many places and come back to it.