User guide · 2.0 development

Nonlinear Problems

SHOT is designed for nonlinear problems. You can use various nonlinear expressions:

  • Exponential and logarithm: SHOTpy.exp(), SHOTpy.log()

  • Trigonometric: SHOTpy.sin(), SHOTpy.cos(), SHOTpy.tan()

  • Square root: SHOTpy.sqrt()

  • Power functions: x**n

  • Arithmetic operators: +, -, *, /

Constraints and objectives can be written directly with these expressions. A comparison with <=, >= or == creates a constraint, which problem.addConstraint() adds with an optional name, and problem.setObjective() takes an expression and a direction:

problem.addConstraint(SHOTpy.exp(x + y) <= 10, "c1")
problem.addConstraint(x * y >= x + 1, "c2")             # moved to one side: x*y - (x + 1) >= 0
problem.addConstraint(SHOTpy.inequality(1, x * y, 5), "c3")
problem.setObjective(SHOTpy.exp(x) + SHOTpy.exp(y), SHOTpy.ObjectiveDirection.Minimize)

A constraint with both a lower and an upper bound is written with SHOTpy.inequality(lower, expression, upper): a chained comparison such as 1 <= x * y <= 5 raises a TypeError, since Python would evaluate it as (1 <= x * y) and (x * y <= 5) and lose one of the bounds. For the same reason !=, and == used as a truth value, e.g., if x == y: or y in [x], raise a TypeError; use is and is not to check whether two variables are the same object.

A bound of inf or -inf means that there is no bound, and a bound of NaN, an equality with an infinite value, or a bound that no value can fulfil, e.g., f <= -inf, raises a ValueError.

finalize() decides the class of such a constraint or objective, e.g., LinearConstraint, QuadraticConstraint or NonlinearConstraint, as described in the section “Writing Terms as Expressions” below, and may replace it. Read a constraint back after finalize() with problem.getConstraint(name). A constraint without a name is named constraint_<index>. The names are not checked when the constraints are added, so give each constraint its own name: getConstraint(name) raises a KeyError if no constraint has the name and a ValueError if several have it.

The constraints and objectives can also be created from the classes directly, as in the later examples.

Example: Geometric Programming

\[\begin{split} \begin{aligned} \text{minimize} \quad & e^x + e^y \\ \text{subject to} \quad & e^{x+y} \leq 10 \\ & x, y \geq 0.1 \end{aligned} \end{split}\]
solver = SHOTpy.Solver()
problem = SHOTpy.Problem(solver)

x = problem.addVariable("x", SHOTpy.VariableType.Real, 0.1, 10.0)
y = problem.addVariable("y", SHOTpy.VariableType.Real, 0.1, 10.0)

# Nonlinear objective: exp(x) + exp(y)
problem.setObjective(SHOTpy.exp(x) + SHOTpy.exp(y), SHOTpy.ObjectiveDirection.Minimize)

# Nonlinear constraint: exp(x + y) <= 10
problem.addConstraint(SHOTpy.exp(x + y) <= 10, "nl_constraint")

# The same constraint created from its class:
#   constraint = SHOTpy.NonlinearConstraint("nl_constraint", SHOTpy.exp(x + y), SHOTpy.SHOT_DBL_MIN, 10.0)
#   problem.addConstraint(constraint)

problem.finalize()
assert solver.setProblem(problem)
assert solver.solveProblem()
assert solver.getModelReturnStatus() == SHOTpy.ModelReturnStatus.OptimalGlobal

sol = solver.getPrimalSolution()
print(f"Optimal objective value: {sol.objValue:.4f}")
print(f"Optimal solution: x = {sol.point[0]:.4f}, y = {sol.point[1]:.4f}")

# Both variables are at their lower bounds 0.1
assert abs(sol.objValue - 2 * math.exp(0.1)) < 1e-3

Example: Mixed Terms

Linear, quadratic and nonlinear parts can be combined in one expression; finalize() extracts the linear and quadratic terms from it:

solver = SHOTpy.Solver()
problem = SHOTpy.Problem(solver)

x = problem.addVariable("x", SHOTpy.VariableType.Real, 0.1, 5.0)
y = problem.addVariable("y", SHOTpy.VariableType.Real, 0.1, 5.0)

# Mixed objective: x + y^2 + log(x), i.e., a linear, a quadratic and a nonlinear term
problem.setObjective(x + y**2 + SHOTpy.log(x), SHOTpy.ObjectiveDirection.Minimize)

# Constraint: x + y >= 1
problem.addConstraint(x + y >= 1, "bound")

problem.finalize()
assert solver.setProblem(problem)
assert solver.solveProblem()
# log(x) is concave, so the objective is nonconvex and SHOT finds a feasible solution without proving that it is
# globally optimal. Here it is: x + log(x) increases with x, so x is as small as x + y >= 1 and y^2 allow
assert solver.getModelReturnStatus() in (SHOTpy.ModelReturnStatus.FeasibleSolution,
                                         SHOTpy.ModelReturnStatus.OptimalGlobal)

sol = solver.getPrimalSolution()
print(f"Objective value: {sol.objValue:.4f}")
print(f"Solution: x = {sol.point[0]:.4f}, y = {sol.point[1]:.4f}")

assert abs(sol.objValue - (0.1 + 0.9**2 + math.log(0.1))) < 1e-3

Advanced Nonlinear Expressions

Complex nested expressions are also supported:

problem = SHOTpy.Problem(solver)

x = problem.addVariable("x", SHOTpy.VariableType.Real, 0.1, 3.14)
y = problem.addVariable("y", SHOTpy.VariableType.Real, 1.0, 10.0)

# Complex expression: exp(x) * sin(x) + log(y) * cos(x)
problem.setObjective(SHOTpy.exp(x) * SHOTpy.sin(x) + SHOTpy.log(y) * SHOTpy.cos(x))

# Simple constraint
problem.addConstraint(x >= 0.5, "bound")

problem.finalize()
print("\nProblem structure:")
print(problem.toString())

Writing Terms as Expressions

The operators on variables (+, -, *, /, **) and the functions (SHOTpy.exp, log, sqrt, sin, …) build nonlinear expressions. An expression can be compared to create a constraint for problem.addConstraint(), given to problem.setObjective(), or given to NonlinearConstraint and NonlinearObjectiveFunction, while the linear and quadratic classes only take term objects such as LinearTerm and QuadraticTerm. You don’t have to write the terms yourself, though: problem.finalize() extracts them from the expressions:

Written as

After finalize()

2*x1*x2, x1**2

quadratic term

3*x1 + 2*x2 - 1

linear terms and a constant

x1*x2*x3

monomial term

x1**0.5 * x2**-1, x1**3, x1/x2

signomial term

exp(x3)

stays a nonlinear expression

If nothing nonlinear is left, the constraint or objective becomes a QuadraticConstraint or LinearConstraint (or the corresponding objective class). The extraction is controlled by the settings Model.Reformulation.Quadratics.ExtractStrategy (0 = do not extract), Model.Reformulation.Monomials.Extract and Model.Reformulation.Signomials.Extract, which have to be set before finalize().

finalize() also rewrites the model into the form SHOT works with:

  • a constraint whose class changes is replaced by a new object at the same position,

  • a constraint with only a lower bound, f(x) >= L, becomes -f(x) <= -L,

  • a constraint with both bounds, L <= f(x) <= U, e.g., an equality constraint, is kept as it is.

So the objects created before finalize() do not always describe the problem afterwards. Read the constraints and the objective back from the problem after finalize(), e.g., by name:

problem = SHOTpy.Problem(solver)

x1 = SHOTpy.Variable("x1", SHOTpy.VariableType.Real, 0.1, 10.0)
x2 = SHOTpy.Variable("x2", SHOTpy.VariableType.Real, 0.1, 10.0)
x3 = SHOTpy.Variable("x3", SHOTpy.VariableType.Real, 0.1, 10.0)
for v in [x1, x2, x3]:
    problem.addVariable(v)

# 1 <= 2*x1*x2 <= 5
problem.addConstraint(SHOTpy.inequality(1, 2 * x1 * x2, 5), "q")

# 2*x1 >= 1
problem.addConstraint(2 * x1 >= 1, "lin")

# minimize x1*x2*x3 + sqrt(x1)
problem.setObjective(x1 * x2 * x3 + x1**0.5)

problem.finalize()

# Read the constraints and the objective back from the problem
constraints = {c.name: c for c in problem.numericConstraints}
objective = problem.objectiveFunction

def bound(value):
    if abs(value) >= SHOTpy.SHOT_DBL_MAX:
        return "-inf" if value < 0 else "inf"
    return f"{value:g}"

for name, c in constraints.items():
    print(f"{name:4s} {type(c).__name__:20s} {bound(c.valueLHS):>5s} <= f(x) <= {bound(c.valueRHS)}")

props = objective.properties
print(f"objective: {type(objective).__name__}, monomial terms: {props.hasMonomialTerms}, "
      f"signomial terms: {props.hasSignomialTerms}")

point = [1.0, 2.0, 3.0]
print(f"f(x) of q: {constraints['q'].calculateFunctionValue(point)}, of lin: {constraints['lin'].calculateFunctionValue(point)}")