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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
"""
Sum of Squares Package
======================
This is a package to solve sum-of-squares optimization problems.
Module Overview
---------------
Class diagram: Arrows denote inheritance, diamonds indicate composition.
::
┏━━sumofsquares package━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ ┃
┃ ┌─.abc──────────────┐ ┌─.problems────────────────────────────────────────────────────┐ ┃
┃ │ ┌──────────────┐ │ │ │ ┃
┃ │ │ Problem │◀─┼───┼────────────┬───────────────────┬──────────────────┐ │ ┃
┃ │ └──────────────┘ │ │ │ │ │ │ ┃
┃ │ │ │ │ ┌───────────────────┐ ┌────────────┐ ┌──────────────────┐ │ ┃
┃ │ ◇ │ │ │ ConicProblem │ │ SOSProblem │ │InternalSOSProblem│ │ ┃
┃ │ ┌──────────────┐ │ │ └───────────────────┘ └────────────┘ └──────────────────┘ │ ┃
┃ │ │ Solver(Enum) │ │ │ ▲ │ ┃
┃ │ └──────────────┘ │ │ ┌────┴────────────────┐ │ ┃
┃ │ │ │ │ │ │ ┃
┃ │ ┌──────────────┐ │ │ ┌─────────────┐ ┌─────────────────┐ ┌────────────────────┐ │ ┃
┃ │ │ Result │◀─┼───┼─│ ConicResult │ │PutinarSOSProblem│ │SchmuedgenSOSProblem│ │ ┃
┃ │ └──────────────┘ │ │ └─────────────┘ └─────────────────┘ └────────────────────┘ │ ┃
┃ │ │ │ └──────────────────────────────────────────────────────────────┘ ┃
┃ │ │ │ ┃
┃ │ ◇ │ ┌─.solvers.cvxopt──┐ ┌─.solvers.scs─────┐ ┌─.solvers.mosek───┐ ┃
┃ │ ┌──────────────┐ │ │ │ │ │ │ │ ┃
┃ │ │ SolverInfo │◀─┼───┼───────┬──────────┼──┼──────┬───────────┼──┼──────┐ │ ┃
┃ │ └──────────────┘ │ │ │ │ │ │ │ │ │ │ ┃
┃ │ │ │ ┌──────────┐ │ │ ┌─────────┐ │ │ ┌─────────┐ │ ┃
┃ │ │ │ │CVXOptInfo│ │ │ │ SCSInfo │ │ │ │MosekInfo│ │ ┃
┃ │ │ │ └──────────┘ │ │ └─────────┘ │ │ └─────────┘ │ ┃
┃ │ │ └──────────────────┘ └──────────────────┘ └──────────────────┘ ┃
┃ │ │ ┃
┃ │ │ ┌─.constraints──────────────────────────────────────────────────────┐ ┃
┃ │ ┌──────────────┐ │ │ │ ┃
┃ │ │ Constraint │◀─┼───┼───────────────────────────┬────────┬──────────┬─────────┐ │ ┃
┃ │ └──────────────┘ │ │ │ │ │ │ │ ┃
┃ │ ┌──────────────┐ │ │ ┌───────────────────────┐ │ ┌───────────┐ │ ┌───────────────┐ │ ┃
┃ │ │ Set │◀─┼───┼─│ BasicSemialgebraicSet │ │ │EqualToZero│ │ │ExponentialCone│ │ ┃
┃ │ └──────────────┘ │ │ └───────────────────────┘ │ └───────────┘ │ └───────────────┘ │ ┃
┃ │ │ │ ◇ │ │ │ ┃
┃ │ │ │ │ ┌───────────┐ ┌────────────────────┐ │ ┃
┃ │ │ │ └───────│NonNegative│ │PositiveSemiDefinite│ │ ┃
┃ │ │ │ └───────────┘ └────────────────────┘ │ ┃
┃ │ │ │ │ ┃
┃ │ │ │ │ ┃
┃ └───────────────────┘ └───────────────────────────────────────────────────────────────────┘ ┃
┃ ┃
┃ ┌─.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_name as internal_from_name,
from_names as internal_from_names)
# export optimization variable constructors
from_name = internal_from_name
from_names = internal_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)
|
