import math
from collections.abc import Callable
from dataclasses import dataclass
from typing import NamedTuple
from plot import draw, draw_all, draw_diameters
from report import report_diameters
class Diameter(NamedTuple):
length: float
chord: tuple
@dataclass
class Shape:
_x: Callable
_y: Callable
name: str = ""
def x(self, t):
return self._x(t - math.floor(t))
def y(self, t):
return self._y(t - math.floor(t))
def point(self, t):
return self.x(t), self.y(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 pair of functions of one parameter. Shape holds them and does nothing else. x(t) and y(t) are ordinary callables, and point(t) returns both. 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
def rectangle(width, height):
def x(t):
if t < 0.25:
return 4 * width * t
if t < 0.50:
return width
if t < 0.75:
return width - 4 * width * (t - 0.5)
return 0.0
def y(t):
if t < 0.25:
return 0.0
if t < 0.50:
return 4 * height * (t - 0.25)
if t < 0.75:
return height
return height - 4 * height * (t - 0.75)
return Shape(x, y, f"rectangle({width}, {height})")
HARMONICS = [
lambda t: math.cos(t * 4 * math.pi),
lambda t: math.sin(t * 4 * math.pi),
lambda t: math.cos(t * 6 * math.pi),
lambda t: math.sin(t * 6 * math.pi),
lambda t: math.cos(t * 8 * math.pi),
lambda t: math.exp(-25 * (t - 0.5) ** 2) - math.exp(-25 * 0.25),
]
def weights(seed, count):
state = seed * 2654435761 % 2**31
drawn = []
for _ in range(count):
state = (1103515245 * state + 12345) % 2**31
drawn.append(state / 2**31)
return drawn
def blob(seed, roughness=0.45):
drawn = weights(seed, len(HARMONICS))
amplitudes = [roughness * (2 * w - 1) / k for k, w in enumerate(drawn, 1)]
def radius(t):
return 1 + sum(a * f(t) for a, f in zip(amplitudes, HARMONICS, strict=True))
return Shape(
lambda t: radius(t) * math.cos(t * 2 * math.pi),
lambda t: radius(t) * math.sin(t * 2 * math.pi),
f"blob({seed})",
)
def transform(shape, matrix):
return Shape(
lambda t: matrix[0][0] * shape.x(t) + matrix[0][1] * shape.y(t),
lambda t: matrix[1][0] * shape.x(t) + matrix[1][1] * shape.y(t),
f"transform({shape.name})",
)The 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
import math
import knitroThe variables and the solve are built the usual way. The objective is not. There is no expression to hand over, so it goes in as a callback that Knitro calls with a pair of parameter values and that answers with the distance between the two points. Problem exposes the underlying context as prob.kc, the handle KN_add_eval_callback needs.
def maximize_diameter(shape, *, multistart=False, num_threads=1):
prob = knitro.Problem()
t = [prob.add_variable(lb=0, ub=1) for _ in range(2)]
def objective(kc, cb, request, result, params):
if request.type != knitro.KN_RC_EVALFC:
return -1
t1, t2 = request.x
result.obj = math.dist(shape.point(t1), shape.point(t2))
return 0
knitro.KN_set_obj_goal(prob.kc, knitro.KN_OBJGOAL_MAXIMIZE)
knitro.KN_add_eval_callback(prob.kc, evalObj=True, funcCallback=objective)
if multistart:
prob.set_param(knitro.KN_PARAM_MSENABLE, knitro.KN_MS_ENABLE_YES)
prob.set_param(knitro.KN_PARAM_NUMTHREADS, num_threads)
prob.solve()
value = prob.get_attr(knitro.KN_ATTR_OBJ_VALUE)
return Diameter(value, (t[0].value, t[1].value))request.type is checked because Knitro reuses one callback for several kinds of evaluation; returning -1 for anything else says this callback does not answer it. 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[1])=======================================
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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
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 1.38e-08 1.62e-07 0.02
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) = 1.38e-08 / 1.38e-08
# of iterations = 10
# of CG iterations = 0
# of function evaluations = 56
# of gradient evaluations = 0
Total program time (secs) = 0.01996 ( 0.018 CPU time)
Time spent in evaluations (secs) = 0.00676
================================================================================
Show the full outputHide the full output
draw(shapes[1], 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[1], 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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
ms_enable 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 1.38479e-08 8.75080e-03 1.15531e-02
1 0 0 2.51988 0.00000e+00 9.77266e-08 1.06799e-02 2.23934e-02
2 0 0 1.97992 0.00000e+00 3.31943e-06 6.33689e-03 2.88838e-02
3 0 0 2.51988 0.00000e+00 6.53672e-07 6.63569e-03 3.56612e-02
4 0 0 1.86433 0.00000e+00 4.43137e-07 7.32824e-03 4.31238e-02
5 0 0 2.51988 0.00000e+00 8.39119e-08 6.78717e-03 5.00438e-02
6 0 0 1.97992 0.00000e+00 9.05723e-07 7.68508e-03 5.78776e-02
7 0 0 2.51988 0.00000e+00 8.72639e-07 7.08811e-03 6.51255e-02
8 0 0 2.51988 0.00000e+00 1.00690e-07 7.35491e-03 7.26410e-02
9 0 0 2.51988 0.00000e+00 4.18915e-08 9.22877e-03 8.20228e-02
10 0 0 2.51988 0.00000e+00 1.80353e-07 7.20581e-03 8.93783e-02
11 0 0 1.97992 0.00000e+00 1.06301e-08 4.87679e-03 9.44104e-02
12 0 0 2.51988 0.00000e+00 1.12118e-07 6.90799e-03 0.101458
13 0 0 2.51988 0.00000e+00 3.17425e-09 7.89650e-03 0.109494
14 0 0 2.51988 0.00000e+00 1.67819e-08 9.85946e-03 0.119502
15 0 0 2.51988 0.00000e+00 1.34253e-07 7.08948e-03 0.126733
16 0 0 1.86433 0.00000e+00 5.36819e-09 7.92168e-03 0.134811
17 0 0 2.51988 0.00000e+00 1.40632e-08 7.29919e-03 0.142269
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.01e-07 / 1.01e-07
# of iterations = 164
# of CG iterations = 0
# of function evaluations = 940
# of gradient evaluations = 0
Total program time (secs) = 0.14236 ( 0.146 CPU time)
================================================================================
Show the full outputHide the full output
draw(shapes[1], 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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
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.01
20 1.000000e+01 0.00e+00 5.00e-01 0.00e+00 0.02
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.02202 ( 0.023 CPU time)
Time spent in evaluations (secs) = 0.01910
================================================================================
=======================================
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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
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 1.38e-08 1.62e-07 0.01
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) = 1.38e-08 / 1.38e-08
# of iterations = 10
# of CG iterations = 0
# of function evaluations = 56
# of gradient evaluations = 0
Total program time (secs) = 0.00899 ( 0.009 CPU time)
Time spent in evaluations (secs) = 0.00656
================================================================================
=======================================
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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
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 2.38e-08 1.87e-06 0.01
EXIT: Locally optimal solution found.
Final Statistics
----------------
Final objective value = 2.10251132372658e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 2.38e-08 / 5.84e-09
# of iterations = 7
# of CG iterations = 0
# of function evaluations = 44
# of gradient evaluations = 0
Total program time (secs) = 0.00623 ( 0.007 CPU time)
Time spent in evaluations (secs) = 0.00429
================================================================================
=======================================
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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
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.22e-08 3.44e-07 0.01
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.22e-08 / 3.22e-08
# of iterations = 9
# of CG iterations = 0
# of function evaluations = 54
# of gradient evaluations = 0
Total program time (secs) = 0.00805 ( 0.009 CPU time)
Time spent in evaluations (secs) = 0.00601
================================================================================
=======================================
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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
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.01
EXIT: Locally optimal solution found.
Final Statistics
----------------
Final objective value = 2.35679909647068e+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.00801 ( 0.008 CPU time)
Time spent in evaluations (secs) = 0.00602
================================================================================
=======================================
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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
ms_enable 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.10609e-02 2.31051e-02
1 0 -102 10.0000 0.00000e+00 0.467589 1.97773e-02 4.30390e-02
2 0 -102 10.0000 0.00000e+00 0.500000 2.13297e-02 6.45470e-02
3 0 -102 10.0000 0.00000e+00 0.500000 1.51409e-02 7.98984e-02
4 0 -102 10.0000 0.00000e+00 0.500000 1.34112e-02 9.35112e-02
5 0 -102 10.0000 0.00000e+00 0.500000 2.00708e-02 0.113774
6 0 0 10.0000 0.00000e+00 1.09855e-11 1.44457e-02 0.128412
7 0 -102 10.0000 0.00000e+00 0.500000 2.02538e-02 0.148869
7 0 * 10.0000 0.00000e+00
8 0 -103 10.0000 0.00000e+00 6.67387 3.77090e-02 0.186773
9 0 -102 10.0000 0.00000e+00 2.70977 2.92370e-02 0.216195
10 0 -102 10.0000 0.00000e+00 10.9106 2.53977e-02 0.241779
11 0 -102 10.0000 0.00000e+00 0.500000 2.85609e-02 0.270521
12 0 -102 10.0000 0.00000e+00 0.500000 1.91205e-02 0.289822
13 0 0 10.0000 0.00000e+00 1.98682e-07 1.95088e-02 0.309515
14 0 -102 10.0000 0.00000e+00 2.76922 2.71452e-02 0.336849
15 0 -102 10.0000 0.00000e+00 0.876471 2.31107e-02 0.360144
15 0 * 10.0000 0.00000e+00
16 0 -102 10.0000 0.00000e+00 0.500000 1.73580e-02 0.377685
17 0 -102 10.0000 0.00000e+00 0.500000 1.81346e-02 0.395994
17 0 * 10.0000 0.00000e+00
18 0 -102 10.0000 0.00000e+00 0.500000 2.33068e-02 0.419483
19 0 -101 10.0000 0.00000e+00 0.500000 2.50292e-02 0.444697
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.44479 ( 0.450 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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
ms_enable 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 1.38479e-08 7.95019e-03 1.03225e-02
1 0 0 2.51988 0.00000e+00 9.77266e-08 9.68607e-03 2.01441e-02
2 0 0 1.97992 0.00000e+00 3.31943e-06 6.29289e-03 2.65774e-02
3 0 0 2.51988 0.00000e+00 6.53672e-07 6.59915e-03 3.33170e-02
4 0 0 1.86433 0.00000e+00 4.43137e-07 7.46462e-03 4.09231e-02
5 0 0 2.51988 0.00000e+00 8.39119e-08 6.75207e-03 4.78140e-02
6 0 0 1.97992 0.00000e+00 9.05723e-07 6.94946e-03 5.49012e-02
7 0 0 2.51988 0.00000e+00 8.72639e-07 6.60141e-03 6.16436e-02
8 0 0 2.51988 0.00000e+00 1.00690e-07 7.47827e-03 6.92668e-02
9 0 0 2.51988 0.00000e+00 4.18915e-08 7.75773e-03 7.71827e-02
10 0 0 2.51988 0.00000e+00 1.80353e-07 4.86910e-03 8.22181e-02
11 0 0 1.97992 0.00000e+00 1.06301e-08 4.10358e-03 8.64821e-02
12 0 0 2.51988 0.00000e+00 1.12118e-07 6.99515e-03 9.36404e-02
13 0 0 2.51988 0.00000e+00 3.17425e-09 7.97953e-03 0.101783
14 0 0 2.51988 0.00000e+00 1.67819e-08 9.98854e-03 0.111939
15 0 0 2.51988 0.00000e+00 1.34253e-07 7.92728e-03 0.120025
16 0 0 1.86433 0.00000e+00 5.36819e-09 8.10416e-03 0.128285
17 0 0 2.51988 0.00000e+00 1.40632e-08 7.14723e-03 0.135591
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.01e-07 / 1.01e-07
# of iterations = 164
# of CG iterations = 0
# of function evaluations = 940
# of gradient evaluations = 0
Total program time (secs) = 0.13567 ( 0.138 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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
ms_enable 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 2.37895e-08 6.33385e-03 8.65628e-03
1 0 0 2.73711 0.00000e+00 1.28828e-08 8.46130e-03 1.72453e-02
2 0 0 2.73711 0.00000e+00 2.18290e-07 8.24103e-03 2.56013e-02
3 0 0 2.73711 0.00000e+00 1.51940e-07 6.29157e-03 3.20345e-02
4 0 0 2.73711 0.00000e+00 9.19105e-08 5.77469e-03 3.79771e-02
5 0 0 2.73711 0.00000e+00 1.28825e-08 8.09567e-03 4.62700e-02
6 0 0 2.73711 0.00000e+00 6.95917e-07 5.56888e-03 5.20360e-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.73710681448387e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 6.96e-07 / 6.96e-07
# of iterations = 64
# of CG iterations = 0
# of function evaluations = 374
# of gradient evaluations = 0
Total program time (secs) = 0.05212 ( 0.053 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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
ms_enable 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.21518e-08 5.89253e-03 7.72091e-03
1 0 0 2.35383 0.00000e+00 1.96010e-07 8.90828e-03 1.68263e-02
2 0 0 2.35383 0.00000e+00 5.14995e-08 4.83168e-03 2.18518e-02
3 0 0 2.35383 0.00000e+00 2.20716e-08 5.25192e-03 2.73004e-02
4 0 0 2.35383 0.00000e+00 1.47145e-08 6.48283e-03 3.39781e-02
5 0 0 2.35383 0.00000e+00 9.58703e-08 6.22263e-03 4.03993e-02
6 0 0 2.35383 0.00000e+00 8.23991e-07 8.92967e-03 4.95257e-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.35382655759701e+00
Final feasibility error (abs / rel) = 0.00e+00 / 0.00e+00
Final optimality error (abs / rel) = 9.59e-08 / 9.59e-08
# of iterations = 75
# of CG iterations = 0
# of function evaluations = 415
# of gradient evaluations = 0
Total program time (secs) = 0.04960 ( 0.050 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.
concurrent_evals 0
feastol 1e-06
feastol_abs 0.001
ms_enable 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 7.61019e-03 1.06803e-02
1 0 0 2.78954 0.00000e+00 9.41378e-07 9.39320e-03 2.02274e-02
2 0 0 1.92686 0.00000e+00 2.63523e-07 6.80679e-03 2.72158e-02
3 0 0 2.78954 0.00000e+00 1.27824e-07 7.55117e-03 3.49774e-02
4 0 0 2.35680 0.00000e+00 1.04144e-07 5.51400e-03 4.06955e-02
5 0 0 2.34668 0.00000e+00 2.79752e-07 7.69783e-03 4.86019e-02
6 0 0 2.35680 0.00000e+00 1.04097e-07 7.71760e-03 5.65205e-02
7 0 0 2.78954 0.00000e+00 1.58213e-08 8.65369e-03 6.53790e-02
8 0 0 2.08788 0.00000e+00 4.79384e-06 8.19878e-03 7.37742e-02
9 0 0 2.34668 0.00000e+00 4.60796e-07 8.89939e-03 8.28597e-02
10 0 0 1.92686 0.00000e+00 1.76993e-07 1.01305e-02 9.31794e-02
11 0 0 1.92686 0.00000e+00 2.32920e-08 9.27944e-03 0.102649
12 0 0 2.78954 0.00000e+00 3.38417e-07 9.90702e-03 0.112739
13 0 0 2.35680 0.00000e+00 2.32512e-06 9.57101e-03 0.122485
14 0 0 2.35680 0.00000e+00 5.78409e-08 9.00193e-03 0.131665
15 0 0 2.78954 0.00000e+00 5.83435e-08 7.77459e-03 0.139615
16 0 0 2.35680 0.00000e+00 7.44896e-12 7.57645e-03 0.147374
17 0 0 2.78954 0.00000e+00 1.16169e-08 9.20400e-03 0.156784
18 0 0 2.34668 0.00000e+00 6.46023e-07 9.10221e-03 0.166094
19 0 0 2.08788 0.00000e+00 2.92543e-06 7.00528e-03 0.173308
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) = 5.83e-08 / 5.83e-08
# of iterations = 158
# of CG iterations = 0
# of function evaluations = 948
# of gradient evaluations = 0
Total program time (secs) = 0.17341 ( 0.177 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.