1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
"""
Sum of Squares Package
======================
This is a package to solve sum-of-squares optimization problems.
Module Overview
---------------
Class diagram, arrows denote inheritance, whereas diamonds indicate composition.
::
┏━━sumofsquares package━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ ┌─.abc──────────────────────────────────────────────────────────────────────────────────────────┐ ┃
┃ │ ┌────────────┐ ┌──────────────┐ ┌─────────┐ ┌───────┐ ┌──────────────┐ │ ┃
┃ │ │ SolverInfo │◇─┐ │ Solver(Enum) │ │ Problem │ │ Set │ │ Constraint │ │ ┃
┃ │ └────────────┘ │ └──────────────┘ └─────────┘ └───────┘ └──────────────┘ │ ┃
┃ │ ▲ │ ▲ ▲ ▲ │ ┃
┃ └────────┼────────┼─────────────────────────┼─────────────┼───────────────┼─────────────────────┘ ┃
┃ │ │ ┌────────────┘ ┌──┘ ├─────────────┐ ┃
┃ │ │ │ │ │ │ ┃
┃ ┌─.cvxop│t─────┐ │ ┌─.problems┼──────────┐ ┌─.constrai│nts───────────────┼─────────────┼───────┐ ┃
┃ │ │ │ │ │ │ │ │ │ │ │ │ ┃
┃ │ ┌──────────┐ │ │ │ ┌─────────────────┐ │ │ ┌────────────────┐ ┌───────────┐ ┌───────────┐ │ ┃
┃ │ │CVXOptInfo│ │ │ │ │PutinarSOSProblem│ │ │ │ ArchimedeanSet │◇───│NonNegative│ │EqualToZero│ │ ┃
┃ │ └──────────┘ │ │ │ └─────────────────┘ │ │ └────────────────┘ └───────────┘ └───────────┘ │ ┃
┃ │ │ │ │ ┌────────┐ │ │ │ ┃
┃ │ │ └─┼─│ Result │ │ │ │ ┃
┃ │ │ │ └────────┘ │ │ │ ┃
┃ └──────────────┘ └─────────────────────┘ └───────────────────────────────────────────────────┘ ┃
┃ ┌─.variable─────────────────┐ ┃ ┏━━━polymatrix package━━━━━━━━━┓
┃ │ │ ┃ ┃ ┃
┃ │ ┌───────────┐ │ ┃ ┃ ┌──────────┐ ┌──────────┐ ┃
┃ │ │OptVariable│──────────┼──╋──╋─▶│ Variable │ │Expression│ ┃
┃ │ └───────────┘ │ ┃ ┃ └──────────┘ └──────────┘ ┃
┃ │ ▲ │ ┃ ┃ │ ┃
┃ │ │ │ ┃ ┃ ┌─────────┘ ┃
┃ │ │ │ ┃ ┃ ◇ ┃
┃ │ ┌────────────────┐ │ ┃ ┃ ┌─────────────────────┐ ┃
┃ │ │OptVariableMixin│────────┼──╋──╋─▶│ ExpressionBaseMixin │ ┃
┃ │ └────────────────┘ │ ┃ ┃ └─────────────────────┘ ┃
┃ └───────────────────────────┘ ┃ ┃ ┃
┃ ┃ ┃ ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
"""
from typing import Iterable
import polymatrix as poly
from polymatrix.expression.expression import Expression
from polymatrix.expressionstate import ExpressionState
from .abc import Problem, Result, Set, Constraint, Solver
from .constraints import BasicSemialgebraicSet, NonNegative
from .problems import PutinarSOSProblem
from .utils import partition
from .variable import OptVariable, from_names
def make_sos_constraint(expr: Expression, domain: Set | None = None) -> NonNegative:
return NonNegative(expr, domain)
def make_set(*polynomials: Iterable[Expression]):
return BasicSemialgebraicSet(polynomials)
def make_problem(
cost: Expression,
constraints: Iterable[Constraint] = (),
solver: Solver = Solver.CVXOPT,
state: ExpressionState | None = None
) -> Problem:
"""
Create a sum-of-squares optimization problem.
"""
if not state:
state = poly.make_state()
# Convert to polymatrix object to extract variables
state, _ = cost.apply(state)
for constr in constraints:
state, _ = constr.expression.apply(state)
# Collect decision variables from state object
def is_optvariable(v):
return isinstance(v, OptVariable)
poly_variables, opt_variables = partition(is_optvariable, state.indices.keys())
return PutinarSOSProblem(
cost=cost,
constraints=constraints,
variables=tuple(opt_variables),
polynomial_variables=tuple(poly_variables),
solver=solver,
state=state)
def solve_problem(
cost: Expression,
constraints: Iterable[Constraint] = (),
solver: Solver = Solver.CVXOPT,
verbose: bool = False
) -> tuple[Problem, Result]:
"""
Solve a sum-of-squares optimization problem.
"""
prob = make_problem(cost, constraints, solver)
return prob, prob.solve(verbose)
|
