Problems#

Problem#

Problem statement for Cvxium: an objective, inequality layers, and equalities.

Defines Problem, the passive statement of a convex optimization problem

minimize    f0(w)
subject to  A w = b,
            f_i(w) ≤ 0 for each inequality layer,

kept separate from the Solver that solves it. A Problem is built fluently with Problem.minimize, Problem.maximize and subject_to, and it carries the two pieces of assembly the solvers share: the weighted Newton-system Hessian (build_hessian_system) and the Phase I problem that finds a strictly feasible start (make_phase1).

Sense records whether the problem minimizes or maximizes; OnInfeasible names the policy a feasibility solve follows on an infeasibility certificate. _SubjectToDescriptor lets subject_to work on both the class and an instance.

class cvxium.problems.problem.Sense(*values)[source]#

Bases: Enum

Optimization sense of a Problem: minimize or maximize.

Cvxium’s solvers only minimize, so a Problem minimizes by default. Problem.maximize records MAXIMIZE alongside a NegatedObjective, and Problem.solve reads the sense back to report the objective value as g(w*) rather than the -g(w*) the solver computed. The sense changes only how the result is reported, never the point the solver converges to.

class cvxium.problems.problem.Problem(obj=None, eq=None, ineq=<factory>, sense=Sense.MINIMIZE)[source]#

Bases: object

Convex optimization problem in composition form.

A passive container holding an Objective (or None for a feasibility problem), an ordered list of inequality ConstraintLayer objects, and an optional linear equality constraint. It states what to optimize, separately from how (the Solver):

minimize    f0(w)
subject to  A w = b                   (when ``eq`` is given),
            f_i(w) ≤ 0                (for each layer in ``ineq``).

A Problem performs no optimization itself. Besides the builders (minimize, maximize, subject_to) and simple queries (dimension, is_feasible, num_inequality_constraints), it assembles the Newton-system Hessian (build_hessian_system) and the Phase I problem (make_phase1) for the solvers. problem.solve(solver) delegates to solver.solve(problem) and reports the result in the problem’s sense.

The decision-variable dimension M is not stored: dimension reads it from whichever component is present, and __post_init__ checks at construction that every component agrees on it.

Fields:

obj (Objective | None) – The objective f0(w) to minimize, or None for a feasibility problem (find any w satisfying the constraints). A feasibility problem must carry at least one equality or inequality constraint, or construction raises ValueError.
eq (EqualityConstraintLayer | None) – Linear equality constraint A w = b, or None for no equalities.
ineq (list[ConstraintLayer]) – Inequality-constraint layers, in caller-chosen order; the last is the active layer for Phase I. May be empty.
sense (Sense) – Whether obj is minimized (the default) or maximized. The solvers always minimize, so a maximization carries a NegatedObjective and solve flips the reported value back. With an objective present, Sense.MAXIMIZE is valid only on a NegatedObjective, and construction raises ValueError otherwise, so Problem.maximize is the supported way to build a maximization. A feasibility problem may carry either sense harmlessly, since there is no objective value to report.

classmethod minimize(obj)[source]#

Begin a builder chain for the problem minimize obj.

Chain .subject_to(eq=..., ineq=[...]) onto the result to attach constraints while keeping the objective. Each builder call returns a new frozen Problem.

Parameters:: obj (Objective) – The objective f0(w) to minimize.
Returns:: problem – An unconstrained Problem carrying obj.
Return type:: Problem

classmethod maximize(obj)[source]#

Begin a builder chain for the problem maximize obj.

Cvxium’s solvers only minimize, so maximizing a concave g is done by minimizing -g. The returned Problem carries NegatedObjective(obj) with sense=Sense.MAXIMIZE, so solve reports the objective value as g(w*), not the -g(w*) the solver computes. The solution point is the same either way.

For the round trip to cost no extra arithmetic, obj should advertise its concave (negative-definite) curvature honestly, so that obj.hessian_contribution(w) is a negated() view of a positive-definite system. NegatedObjective then negates it once more, collapsing the two sign flips, and the solver only ever factors the positive-definite system.

Chain .subject_to(eq=..., ineq=[...]) onto the result to attach constraints; the maximization sense is kept across the chain.

Parameters:: obj (Objective) – The concave objective g(w) to maximize.
Returns:: problem – An unconstrained maximization Problem carrying NegatedObjective(obj) and sense=Sense.MAXIMIZE.
Return type:: Problem

subject_to(ineq=None)#

Attach equality and inequality constraints, returning a new Problem.

Accessed on the class, this builds a feasibility problem with obj=None; accessed on an instance, it builds a new problem carrying that instance’s objective and sense. Either way it returns a new frozen Problem and leaves the receiver unchanged.

The semantics are replace, not accumulate: eq and ineq become the new problem’s constraints outright, discarding any the receiver had.

Parameters:

eq (EqualityConstraintLayer | None) – Linear equality constraint A w = b, or None for none.
ineq (list[ConstraintLayer] | None) – Inequality-constraint layers; None is treated as an empty list.

Returns:

problem – A new frozen Problem carrying the bound objective (None under class access) and sense, together with eq and ineq.

Return type:

Problem

Raises:

ValueError – Propagated from Problem.__post_init__: when the components disagree on the dimension, or when class access supplies no constraint at all.

property dimension#

Return the decision-variable dimension M, derived from the components.

A Problem does not store M; it reads it from the objective if present, else the equality constraint, else the first inequality layer. Construction checked that the components agree, so the choice does not matter.

Returns:: M – The decision-variable dimension.
Return type:: int
Raises:: ValueError – When the problem has no components, which __post_init__ rules out.

solve(solver, x0=None, on_infeasible='raise')[source]#

Run a solver on this problem, reporting the result in this problem’s sense.

For a minimization this returns the solver’s result unchanged. For a maximization (built with maximize) the solver minimizes the carried -g, so the objective outcome is negated back (ObjectiveOutcome.negated) and objective_value reads g(w*). The solution point is never altered.

This is the sense-aware entry point: calling solver.solve(problem) directly skips the flip and reports the raw -g minimization.

Parameters:

solver (Solver) – The algorithm to run, for example BarrierSolver().
x0 (npt.NDArray[np.float64] | None) – Initial guess of length M, forwarded to the solver; None lets the solver choose its start.
on_infeasible (OnInfeasible) – How a feasibility solve responds to an infeasibility certificate: "raise" raises as soon as the certificate appears; "continue" first drives the Phase I slack to its optimum and attaches that best-effort result to the raised exception.

Returns:

result – The solver’s result, with result.objective in this problem’s sense. Only that outcome is flipped: for a maximization, the diagnostics trajectory and any nested Phase I result (phase1) stay in the solver’s internal minimization sense, so they record what the solver actually did.

Return type:

SolveResult

Raises:

NotImplementedError – Propagated from the solver when it cannot honor on_infeasible="continue".
ValueError – Propagated from the solver when it does not support the problem’s shape.
ProblemInfeasibleError – Propagated from the solver when the problem is infeasible.

is_feasible(w)[source]#

Check whether a point strictly satisfies every inequality layer.

Equality constraints are not checked; a caller that needs A w = b checks the residual itself, as Solver._solve_feasibility does.

Parameters:: w (npt.NDArray[np.float64]) – Point to test, of length M.
Returns:: feasible – True when every layer is strictly satisfied at w, and True when there are no inequality layers.
Return type:: bool

num_inequality_constraints()[source]#

Count the inequality constraints across all layers.

Returns:: m – The sum of num_constraints over the layers in ineq, at this problem’s dimension.
Return type:: int

build_hessian_system(x, point, objective_scale, lmbda)[source]#

Assemble the weighted Hessian of the Newton system as a MatrixSystem.

Builds

s ∇^2 f0(x) + ∑ λ_i C_i(x),   C_i = ∇^2 f_i - (1 / f_i) ∇f_i ∇f_i^T,

where s is objective_scale and C_i is the per-constraint curvature atom of ConstraintLayer.hessian_contribution. One contract serves both interior-point methods:

Barrier: objective_scale = t and lmbda = -1 / f, giving t ∇^2 f0 + ∑ ∇^2 φ_i, the Hessian of the barrier-augmented objective.
Primal-dual: objective_scale = 1 and lmbda the dual variables, giving the condensed modified Hessian ∇^2 f0 + ∑ λ_i C_i.

The objective’s curvature (scaled by objective_scale) and each layer’s contribution (weighted by its slice of lmbda) are summed with MatrixSystem.plus. Same-shape bases combine in closed form (diagonal plus diagonal stays diagonal), and low-rank updates ride on top of any base.

Parameters:

x (npt.NDArray[np.float64]) – Current iterate, of length M, at which the layers’ contributions are evaluated.
point (ObjectivePoint) – The objective’s per-point context, which must be self.obj.at(x); passed in so the per-iterate forward pass is computed once and shared.
objective_scale (float) – Scalar multiplying the objective’s curvature (t for barrier, 1 for primal-dual).
lmbda (npt.NDArray[np.float64]) – Per-constraint weights, of length num_inequality_constraints(), stacked in constraint order across the layers (-1 / f for barrier, the dual variables for primal-dual).

Returns:

system – The assembled Hessian.

Return type:

MatrixSystem

Raises:

IncompatibleStructureError – Propagated from MatrixSystem.plus when two contributions have base shapes that do not compose, rather than silently densifying.

make_phase1(x0)[source]#

Construct a Phase I problem whose solution is a strictly feasible point.

Takes the last layer in ineq as the active layer (the one to make feasible) and the rest as background layers, and dispatches on the active layer’s type:

DirectConstraintLayer: direct form. The active layer, which is also an Objective, becomes the objective, with the background layers and the equality constraint kept as constraints. No augmentation.
SlackConstraintLayer: slack form. The variable is augmented to w_aug = [w; s], the objective minimizes s, the background layers are lifted to w_aug, the active layer is relaxed to f_i(w) ≤ s, and s is bounded above (see _make_phase1_slack_form).

Solver._solve_feasibility drives the Phase I solve.

When equality constraints are present, x0 is first projected onto A w = b (with EqualitySolver), since a feasible-start barrier keeps A w = b but never corrects an off-manifold iterate. Both forms start from the projected point. The slack form’s augmented matrix [A 0] leaves A w = b unchanged, so projecting w suffices.

Parameters:

x0 (npt.NDArray[np.float64]) – Starting iterate, of length M. For the slack form it also sets the initial slack, and it should already satisfy the background layers.

Returns:

phase1_problem (Problem) – The Phase I problem.
x0_phase1 (npt.NDArray[np.float64]) – Starting iterate for phase1_problem: the (projected) x0 for the direct form, or [x0; s0], of length M + 1, for the slack form.

Raises:

ValueError – When ineq is empty; a problem without inequality layers needs no Phase I.
NotImplementedError – When the active layer is neither a SlackConstraintLayer nor a DirectConstraintLayer.
ProblemInfeasibleError – Propagated from EqualitySolver.solve when b is not in the range of A.