Solvers#

Solver#

Solver abstraction: an algorithm that consumes a Problem and produces a Result.

Defines Solver, the abstract base for Cvxium’s algorithms (NewtonSolver, BarrierSolver, PrimalDualSolver, HsdSolver). Each takes a Problem, the mathematical statement, and returns a SolveResult. The base also carries the feasibility machinery the interior-point solvers share: _solve_feasibility finds a strictly feasible starting point, building a Phase I problem with Problem.make_phase1 and solving it through the same solver with _solve_phase1, and _feasible_result lifts a point that needed no Phase I into a full result.

EqualitySolver handles the linear equality constraints A x = b: it projects a point onto the affine set, through an SVD for a dense A or a KKT saddle system for a sparse one, and supplies the equality-aware initial barrier parameter.

class cvxium.solvers.solver.Solver(settings=None)[source]#

Bases: ABC

Abstract algorithm that solves a Problem.

A Solver encapsulates an optimization algorithm (Newton’s method, the barrier method, primal-dual, the homogeneous self-dual method). It is decoupled from the mathematical statement of the problem, which lives on a Problem (objective, inequality layers, and equality constraints).

Concrete subclasses implement a single solve(problem, x0) entry point. The same Problem can be handed to different solvers without modification, and the same solver can be applied to any Problem whose shape it supports; a subclass raises ValueError when handed a Problem it cannot solve.

Parameters:: settings (OptimizationSettings | None) – Algorithm-level settings (tolerances, iteration limits, line-search parameters). None uses the solver’s defaults.

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

Solve problem starting from the initial guess x0.

Parameters:

problem (Problem) – The mathematical problem to solve.
x0 (npt.NDArray[np.float64] | None) – Initial guess of length problem.dimension, or None to let the solver choose a start. The barrier and primal-dual solvers accept None or an infeasible x0 and construct a strictly feasible start with _solve_feasibility; HsdSolver ignores x0 and builds its own; NewtonSolver requires an explicit start and raises ValueError when x0 is None.
on_infeasible (OnInfeasible) – How a feasibility solve responds to an infeasibility certificate: "raise" as soon as it appears, or "continue" to the slack optimum first. Solvers that cannot honor "continue" raise NotImplementedError.

Returns:

result – Solver result, including the final iterate and diagnostic data.

Return type:

SolveResult

Raises:

ValueError – When the solver does not support the shape of problem (for example, a NewtonSolver handed inequality constraints, or a BarrierSolver handed none).
NotImplementedError – When on_infeasible="continue" and the solver cannot honor it (NewtonSolver, PrimalDualSolver and HsdSolver).
ProblemInfeasibleError – When a feasibility solve shows the problem infeasible (ProblemCertifiablyInfeasibleError) or cannot locate a feasible point (ProblemMarginallyFeasibleError).

class cvxium.solvers.solver.EqualitySolver(A=None, b=None, settings=None, constraint=None)[source]#

Bases: FeasibilitySolver

Feasibility solver for linear equality constraints A x = b.

Projects onto the affine set {x : A x = b}: it returns the nearest point to a supplied x0, or the minimum-norm point when none is given. A dense A is handled through its SVD, a sparse A through the KKT saddle system of the constraint layer. The equality data and the cached SVD live on an EqualityConstraintLayer, so several solvers can share one layer and its warm SVD; A, b and svd_A delegate to it. initialize_barrier_parameter serves barrier solvers with equality constraints.

Parameters:

A (npt.NDArray[np.float64] | None) – Equality constraint matrix, of shape (p, M). Give either A and b or constraint: passing constraint together with either of them, or neither form, makes the constructor raise ValueError.
b (npt.NDArray[np.float64] | None) – Equality right-hand side, of length p. A length that does not match A fails an assertion in EqualityConstraintLayer.
settings (OptimizationSettings | None) – Solver settings, read for the trace and verbosity; None uses the defaults.
constraint (EqualityConstraintLayer | None) – A prebuilt equality layer, possibly shared with other solvers.

property A#

Return the equality matrix A, delegated to the constraint layer.

Returns:: A – The matrix, of shape (p, M); dense, or scipy.sparse when the layer holds a sparse matrix.
Return type:: npt.NDArray[np.float64]

property b#

Return the equality right-hand side b, delegated to the constraint layer.

Returns:: b – The right-hand side, of length p.
Return type:: npt.NDArray[np.float64]

property num_eq_constraints#

Return the number of equality constraints.

Returns:: p – The row count of A.
Return type:: int

property num_ineq_constraints#

Return the number of inequality constraints, which is zero.

Returns:: m – Always 0.
Return type:: int

solve(x0=None, **kwargs)[source]#

Solve A x = b, projecting x0 onto the solution set when one is given.

A supplied x0 that already satisfies A x = b (every component of A x0 - b below 1e-10 in absolute value) is returned unchanged. Otherwise the result is the Euclidean projection of x0 onto {x : A x = b}, or the minimum-norm solution when x0 is None. A dense A uses the cached SVD (see Notes); a sparse A goes through _project_via_saddle.

Parameters:

x0 (npt.NDArray[np.float64] | None) – Point to project, of length M, or None.
**kwargs (Any) – Ignored; accepted for the FeasibilitySolver.solve signature.

Returns:

res – A FEASIBLE result with zero iterations, whose solution satisfies the equality.

Return type:

SolveResult

Raises:

ProblemInfeasibleError – When b is not in the range of A. For a dense A the test is relative, :: ‖U_r U_r^T b - b‖ > 1e-8 max(1, ‖b‖), where U_r holds the retained left singular vectors; for a sparse A it is propagated from _project_via_saddle.

Notes

With x0 given, the projection solves

minimize    ‖x - x0‖^2
subject to  A x = b.

The Lagrangian is

L(x, ν) = ‖x - x0‖^2 + ν^T (A x - b),

and setting its gradient in x to zero gives

2 (x - x0) + A^T ν = 0,   so   x = x0 - (1/2) A^T ν.

Substituting gives the dual function

g(ν) = -(1/4) ν^T A A^T ν + ν^T (A x0 - b),

which is maximized where

A A^T ν_star = 2 (A x0 - b).

The solution is then

x_star = x0 - (1/2) A^T ν_star.

A need not have full rank. With the thin SVD A = U diag(s) V^T, (A A^T)^{-1} is applied as

U diag(1 / (s^2 + δ^2)) U^T,

a Tikhonov-damped inverse (numerical_helpers.tikhonov_filter) that drops singular values at or below δ = 1e-12 s_max and damps those just above it, so a redundant row is ignored and a nearly redundant one is not amplified. Without x0, the minimum-norm solution is

x = V diag(s / (s^2 + δ^2)) U^T b.

The damping perturbs each retained mode by a relative δ^2 / (s^2 + δ^2), negligible unless s is near the floor.

Both branches reuse the SVD cached on the layer. Given it, the minimum-norm branch costs O(k (p + M)), with k = min(p, M), and the x0 branch adds two products with A, O(p M).

svd_A()[source]#

Return the thin SVD of A, cached on the constraint layer.

Returns:

U (npt.NDArray[np.float64]) – Left singular vectors, of shape (p, k), with k = min(p, M).
s (npt.NDArray[np.float64]) – Singular values in descending order, of length k.
Vh (npt.NDArray[np.float64]) – Transposed right singular vectors, of shape (k, M).

Raises:

NotImplementedError – When A is sparse. Propagated from EqualityConstraintLayer.svd_A.

initialize_barrier_parameter(gradient, grad_phi, num_ineq, outer_tol, super_init)[source]#

Compute an equality-aware initial barrier parameter t0.

Serves any barrier solver that holds an EqualitySolver; BarrierSolver calls it under its EQUALITY_SCHUR strategy, the default when equality constraints are present.

Following (Boyd and Vandenberghe, 2004, section 11.3.1), it picks the t that best centers x0, the least-squares solution over t and ν of

minimize ‖t ∇f0(x0) + ∇φ(x0) + A^T ν‖,

where φ is the log barrier. Eliminating ν projects onto the null space of A through

P = I - A^T (A A^T)^{-1} A,

which gives

t_ls = -∇f0^T P ∇φ / (∇f0^T P ∇f0).

The result is

t0 = min(m / ε, max(super_init, t_ls)),

where the cap m / ε is the value at which the duality-gap bound m / t already meets the outer tolerance ε.

Parameters:

gradient (npt.NDArray[np.float64]) – Objective gradient ∇f0(x0) at the initial iterate, of length M.
grad_phi (npt.NDArray[np.float64]) – Barrier gradient ∇φ(x0) at the initial iterate, of length M.
num_ineq (int) – Number of inequality constraints, m.
outer_tol (float) – Outer duality-gap tolerance, ε.
super_init (float) – Fallback value and lower bound for t0, from the caller’s equality-unaware initializer.

Returns:

t0 – The initial barrier parameter.

Return type:

float

Raises:

NotImplementedError – When A is sparse. Propagated from svd_A.

Notes

(A A^T)^{-1} is applied through the same Tikhonov-damped SVD inverse as solve. The denominator ∇f0^T P ∇f0, a Schur complement, is floored at 1e-16, so a gradient in the row space of A yields a huge t_ls that the cap then bounds. When t_ls is not finite (an extreme scale of A or of the gradients), super_init replaces it, so a non-finite t never reaches the barrier loop.

References

Boyd, Stephen and Vandenberghe, Lieven, Convex Optimization, Cambridge University Press, 2004.

Barrier Method#

Interior-point (barrier) solver over a Cvxium Problem, auto-dispatching.

Defines BarrierSolver, the public interior-point method for inequality-constrained problems, and its private _BarrierAdapter, which bridges a Problem to Cvxium’s shared InteriorPointMethodSolver loop. The solver auto-dispatches on whether the Problem carries an equality layer: problems with only inequalities use the plain barrier method, while problems with equality constraints use the KKT-system barrier method. This module also holds the standalone barrier-parameter initialization helpers shared by the inequality-only and equality paths.

class cvxium.solvers.barrier_solver.BarrierSolver(settings=None)[source]#

Bases: Solver

Interior-point (barrier) method for inequality-constrained problems.

Solves

minimize    f0(x)
subject to  A x = b     (when problem.eq is set)
            fi(x) <= 0  for each layer, i,

auto-dispatching on problem.eq: a Problem with no equality layer is solved by the plain barrier method, and a Problem carrying A x = b by the equality-constrained barrier method.

Parameters:: settings (OptimizationSettings | None) – Algorithm-level settings (tolerances, iteration caps, line-search and barrier-init parameters, etc.) inherited from Solver. When None, the solver uses its default settings.

Notes

The solve proceeds in two stages:

Establish strict feasibility: if x0 is not strictly feasible, call problem.make_phase1(x0) and recursively solve the Phase I Problem with another BarrierSolver. For an equality problem a supplied x0 is first projected onto the equality manifold A x = b.
Run the standard barrier method (centering steps with increasing barrier parameter t) over the original Problem. With equality constraints, each Newton step solves the KKT saddle
```
 _         _   _      _     _        _
| H_ft  A^T | |   Δx   |   |   -∇ft   |
|_ A     0 _| |_  ν   _| = |_    0   _|
```
via the Problem equality’s saddle_system seam.

The Phase I recursion bottoms out because slack-form Phase I produces an augmented Problem whose constructed starting point is strictly feasible by design (verified at construction time inside Problem.make_phase1).

Internally delegates to InteriorPointMethodSolver via a private adapter that composes the Hessian solve from the objective’s and each layer’s structured hessian_contribution.

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

Solve problem via the barrier method, auto-dispatching on equality.

Parameters:

problem (Problem) – The optimization problem; must carry at least one inequality layer (otherwise the barrier method is inapplicable).
x0 (npt.NDArray[np.float64] | None) – Optional starting iterate. May be None or inequality-infeasible; for an equality problem an off-manifold x0 is projected first.
on_infeasible (OnInfeasible) – Policy when the problem is detected infeasible (e.g. "raise" or "continue"), forwarded to the feasibility solve and barrier loop.

Returns:

result – The solve result: an optimization result, or a feasibility result when the problem has no objective.

Return type:

SolveResult

Raises:

ValueError – When problem.ineq is empty (use NewtonSolver instead).
ProblemInfeasibleError – Propagated from the equality projection when b is not in the range of A.
ProblemCertifiablyInfeasibleError – Propagated from the feasibility solve or barrier loop when the problem is certifiably infeasible and on_infeasible="raise".
ProblemMarginallyFeasibleError – Propagated from the feasibility solve when Phase I breaks down without a certificate and on_infeasible="raise".
InteriorPointMethodError – Propagated from the barrier loop when it cannot reach the duality-gap tolerance.

Notes

x0 may be omitted (None) or inequality-infeasible; either way _solve_feasibility constructs a strictly feasible starting iterate from the problem’s own constraint layers (ignoring the objective). For an equality problem a supplied x0 need not lie on the equality manifold. It is projected onto it (least-norm toward x0) before the solve, since the feasible-start barrier maintains A x = b but never corrects an off-manifold iterate.

The barrier loop drives to the duality-gap tolerance (an optimization solve) unless the objective sets a feasibility threshold, in which case it returns as soon as a strictly feasible point is found (objective < 0), so the same solver doubles as a feasibility solver, e.g. for a Phase I problem, where iterating to the optimum is both wasteful and (for the slack form) numerically degenerate as the slack is driven to its minimum.

Primal-Dual Method#

Primal-dual interior-point solver for a Problem with inequality constraints.

Defines PrimalDualSolver, which minimizes f0(w) subject to f_i(w) ≤ 0 and optional equality constraints A w = b by the primal-dual interior-point method (Boyd and Vandenberghe, 2004, section 11.7). Unlike the barrier method (BarrierSolver), it carries the inequality duals λ as explicit state, follows the central path with Newton steps on the perturbed KKT residual rather than nested centering, and sets the barrier parameter adaptively from the surrogate duality gap η = -f^T λ,

t = μ m / η.

After eliminating Δλ, the modified KKT Hessian is

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

which is exactly Problem.build_hessian_system at objective scale 1 with the duals as the weights. Each layer’s hessian_contribution already supplies the atom C_i, so the primal-dual method reuses the structured assembly the barrier method uses.

PrimalDualSolver.solve dispatches on problem.eq:

No equality constraints: a Mehrotra predictor-corrector step per iteration (_run).
Equality constraints: an infeasible-start damped Newton step with a residual line search (_run_equality), which drives A x - b to zero along with the other residuals.

Both paths need a strictly inequality-feasible start. When x0 is omitted or infeasible, Solver._solve_feasibility builds one through Problem.make_phase1, cascading through this same solver. Both paths fall back to adaptive Levenberg-Marquardt damping when the undamped step admits no feasible move.

The module also holds the private pieces the two paths share: _PrimalDualKernel (stacked constraint values and Jacobian products), _StallWatch (stall detection), _clamp_dual_after_update (dual-positivity repair), _PdStepInfo (per-step diagnostics), and _pd_solveresult (result assembly).

References

Boyd, Stephen and Vandenberghe, Lieven, Convex Optimization, Cambridge University Press, 2004.

class cvxium.solvers.primal_dual_solver.PrimalDualSolver(settings=None)[source]#

Bases: Solver

Primal-dual interior-point method for inequality-constrained problems.

Solves

minimize    f0(w)
subject to  f_i(w) ≤ 0,   i = 1, ..., m,
            A w = b       (optional),

It updates the primal iterate and the explicit duals λ (and ν, with equality constraints) jointly by Newton steps on the perturbed KKT residual, following the primal-dual interior-point method (Boyd and Vandenberghe, 2004, section 11.7).

solve dispatches on problem.eq. Without equality constraints it runs a Mehrotra predictor-corrector iteration (_run). With A w = b it runs an infeasible-start iteration (_run_equality) that accepts an x0 off the equality manifold and drives r_pri = A x - b to zero together with the dual and centering residuals. Either way the iterate must be strictly inequality-feasible, f_i(x0) < 0; the feasibility cascade builds such a start when x0 is omitted or infeasible.

Compared with BarrierSolver (the barrier method on the same Problem), the iteration count tends to vary less with problem conditioning, which suits workflows that value predictable behavior. The per-iteration cost is comparable: the modified Hessian has the same structure as the barrier Hessian, so the same structured Objective and ConstraintLayer assembly and solvers apply.

Parameters:: settings (OptimizationSettings | None) – Algorithm settings; None uses the defaults. The solver reads the outer tolerance, soft tolerance and barrier multiplier μ, the inner iteration cap and stall settings, the Armijo parameters, pd_fraction_to_boundary_min (τ_min), the primal_dual.damping schedule, and the trace.

References

Boyd, Stephen and Vandenberghe, Lieven, Convex Optimization, Cambridge University Press, 2004.

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

Solve a problem by the primal-dual method, dispatching on equality.

A feasibility problem (no objective) goes straight to the feasibility cascade (Solver._solve_feasibility), which runs through this solver; a result from the already-feasible short-circuit is relabeled as a primal-dual result. Otherwise the cascade first finds a strictly inequality-feasible start, ignoring the objective, and the start goes to _run (no equality constraints) or _run_equality. Equality feasibility is not required of x0, since the equality path drives A x - b to zero; this solver therefore keeps the default _validate_x0.

Parameters:

problem (Problem) – The problem to solve; must have at least one inequality layer.
x0 (npt.NDArray[np.float64] | None) – Initial guess, of length M. None or an inequality-infeasible point triggers Phase I.
on_infeasible (OnInfeasible) – Accepted for Solver interface uniformity; only "raise" is supported.

Returns:

result – The solution, multipliers and primal-dual diagnostics.

Return type:

SolveResult

Raises:

NotImplementedError – When on_infeasible is "continue".
ValueError – When problem.ineq is empty; use NewtonSolver for unconstrained or equality-only problems.
ProblemCertifiablyInfeasibleError – Propagated from Solver._solve_feasibility when no strictly feasible start exists, and from _run when the final dual value is positive.
NewtonStepError – Propagated from the step computation when no usable step can be found or an iterate becomes invalid.

Newton’s Method#

Newton’s method for Cvxium problems with no inequality constraints.

Defines NewtonSolver, the Solver for a Problem whose only constraints, if any, are equalities A w = b. It runs Newton’s method with backtracking line search, taking each step from the objective’s structured Hessian, or, with an equality, from the bordered KKT system that the equality layer builds over that Hessian.

The iteration itself is not reimplemented here. The private _ObjectiveNewtonAdapter presents the Objective and the optional EqualityConstraintLayer through the interface of EqualityConstrainedNewtonSolver in optimization, which supplies the centering loop, the line search, and the SolveResult.

class cvxium.solvers.newton_solver.NewtonSolver(settings=None)[source]#

Bases: Solver

Newton’s method for a Problem with no inequality constraints.

Solves either the unconstrained problem

minimize    f0(w)

or, when problem.eq is present, the equality-constrained problem

minimize    f0(w)
subject to  A w = b,

where f0 is problem.obj, using Newton’s method with backtracking line search. The solver dispatches on problem.eq. With no equality, each step comes from the objective’s structured Hessian (hessian_contribution(x).solve). With an equality, it solves the bordered KKT system

| H   A^T | | Δw |   | -∇f0 |
| A    0  | | ν  | = |   0  |

through the SaddleSystem that problem.eq.saddle_system builds over the same Hessian H.

The objective needs an invertible Hessian (QuadraticObjective with positive definite Q is the canonical example); with a singular one, such as a LinearObjective or a rank-deficient QuadraticObjective, the first Newton step fails. With an equality, the initial guess x0 should satisfy A x0 = b: each step keeps A w fixed, so the equality residual at x0 is never corrected, and it is not checked.

Internally delegates to EqualityConstrainedNewtonSolver through a private adapter, which provides the centering loop, the line search, and the SolveResult.

Parameters:: settings (OptimizationSettings | None) – Algorithm settings (tolerances, iteration limits, line-search parameters); None uses the defaults.

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

Solve a problem from an initial guess with Newton’s method.

on_infeasible is accepted for uniformity with the Solver interface. A Newton solve has no feasibility stage, so it cannot honor the "continue" policy.

Parameters:

problem (Problem) – The problem to solve. It must have an objective (none_throws fails on a feasibility-only problem) and no inequality constraint layers.
x0 (npt.NDArray[np.float64] | None) – Initial guess, of length M. Required despite the None default, which exists only to match the Solver signature. With an equality it should satisfy A x0 = b (not checked).
on_infeasible (OnInfeasible) – Infeasibility policy. Only "raise" is supported.

Returns:

result – The solution and the solve’s diagnostics.

Return type:

SolveResult

Raises:

NotImplementedError – When on_infeasible is "continue".
ValueError – When x0 is None, or when problem has any inequality constraint layers (use BarrierSolver or PrimalDualSolver for those).
CenteringStepError – Propagated from centering_step when a Newton step cannot be computed (for example, a singular Hessian; the NewtonStepError is chained as the cause), or when the line search fails or the iteration limit is reached before the iterate meets the acceptable tolerance.

Homogeneous Self-Dual Method#

Homogeneous self-dual interior-point solver for Cvxium’s linear conic programs.

Defines HsdSolver, which solves the linear conic program

minimize c^T x   subject to   A x = b,   x ∈ K,

over a product of symmetric cones K = K_1 × … × K_q (see cone), and the private _HsdEmbedding, which holds the embedded iterate and computes the residuals, Newton steps, step lengths, and infeasibility certificates that the solver’s loop needs.

Following (Andersen, Roos, and Terlaky, 2003), the solver embeds the program in a homogeneous model, adding a scalar τ that homogenizes the equations and a scalar κ complementary to it. The starting point x = s = e_K, y = 0, τ = κ = 1 is built from the cones’ interior points, so no Phase I solve and no strictly feasible x0 are needed. When the iterates converge with τ > 0, x / τ solves the program; when τ collapses while κ stays positive, the iterate yields a certificate of primal infeasibility (b^T y > 0) or of dual infeasibility, that is, unboundedness (c^T x < 0).

Each iteration takes one damped Newton step toward the central path, with a fixed centering parameter and the Nesterov-Todd scaling W of each cone block. The step reduces to a (p + 1) × (p + 1) linear system, where p is the number of equality constraints; each cone assembles its share of the coefficients from its structured W^2 through Cone.accumulate_normal_equations, so W^2 is never formed densely. The embedding also provides the pieces of a Mehrotra predictor-corrector (compute_centering_rhs with affine deltas, and predicted_mu), which the solver loop does not call.

The problem’s objective must be a LinearObjective, and its equality constraints supply (A, b). The cones, not inequality-constraint layers, define K: the problem’s inequality layers are not read. second_order_cone_programs maps second-order cone programs into this form and subclasses _HsdEmbedding with a structured kernel.

References

Andersen, Erling D., Roos, Cornelis and Terlaky, Tamás, On Implementing a Primal-Dual Interior-Point Method for Conic Quadratic Optimization, Mathematical Programming 95, 2003.

class cvxium.solvers.hsd_solver.HsdSolver(cones, settings=None, embedding_class=None)[source]#

Bases: Solver

Homogeneous self-dual interior-point solver for linear conic programs.

Solves

minimize c^T x   subject to   A x = b,   x ∈ K,

where the Problem supplies c (through its LinearObjective) and (A, b) (through its equality constraints, if any), and the solver’s cones define K. Builds the homogeneous embedding (_HsdEmbedding), runs a path-following loop on it, and returns either the recovered solution or an infeasibility or unboundedness certificate. Throughout, n = problem.dimension and p is the number of equality constraints.

Unlike BarrierSolver and PrimalDualSolver, HsdSolver needs no strictly feasible starting point: the embedding starts from the cones’ canonical interior points, so solve ignores x0.

Parameters:

cones (list[Cone]) – The cone blocks of K, in the order their coordinates appear in x. Their dimensions must sum to n, or solve raises ValueError.
settings (OptimizationSettings | None) – Solver settings; None uses the defaults. The solver reads outer.tolerance, outer.tolerance_soft, trace and observability.label. The iteration cap (100) and the centering parameter (0.1) are fixed in solve.
embedding_class (type[_HsdEmbedding] | None) – The embedding class to instantiate; None uses _HsdEmbedding. A subclass can override residuals and kkt_solve with a structure-exploiting kernel, as second_order_cone_programs does.

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

Solve a linear conic program through the homogeneous self-dual embedding.

Builds the embedding, starts it at its canonical interior point, and iterates until the stopping test passes, a Newton step fails, or 100 iterations elapse. Convergence requires three measures, all on the embedded iterate, to fall below outer.tolerance:

the relative primal residual ‖r_p‖ / (1 + ‖b‖),
the relative dual residual ‖r_d‖ / (1 + ‖c‖),
the complementarity gap μ (see _HsdEmbedding.complementarity_gap).

Dividing by τ recovers the solution and the equality and inequality multipliers,

x / τ,   y / τ,   s / τ,

where s is the dual slack. When the loop reaches neither tolerance, the embedding is checked for an infeasibility or unboundedness certificate.

Parameters:

problem (Problem) – The program to solve. Its objective must be a LinearObjective; its equality constraints, if any, give (A, b). Its inequality layers are not read.
x0 (npt.NDArray[np.float64] | None) – Accepted for uniformity with the Solver interface and ignored.
on_infeasible (OnInfeasible) – Accepted for uniformity with the Solver interface. "continue" is not supported. The default "raise" has no effect: an infeasible program yields a result carrying a certificate, not an exception.

Returns:

result – The recovered solution, with solver set to "hsd" and HsdDiagnostics holding the τ, κ and μ histories. The status is INFEASIBLE or UNBOUNDED when a certificate was found, and otherwise OPTIMAL (outer.tolerance reached), ACCEPTABLE (only outer.tolerance_soft reached), or MAX_ITERATIONS (neither reached, including a stop after a failed Newton step).

Return type:

SolveResult

Raises:

NotImplementedError – When on_infeasible is "continue".
ValueError – Propagated from _HsdEmbedding when the cone dimensions do not sum to problem.dimension or the objective is not a LinearObjective, and from the cone and matrix operations on a shape mismatch.

Notes

A Newton step fails when the iterate reaches a cone boundary, where the Nesterov-Todd scaling is undefined (ConeBoundaryError), or when the reduced system is singular (np.linalg.LinAlgError). The loop catches both and stops with ACCEPTABLE when the iterate before the step met outer.tolerance_soft, and with MAX_ITERATIONS otherwise.

Second-Order Cone Programs#

Second-order cone programs, solved by Cvxium’s homogeneous self-dual solver.

Provides solve_second_order_cone_program for the problem

minimize    f^T x
subject to  ‖A_soc x + b_soc‖ ≤ c_soc^T x + d_soc,
            F x = g_eq,
            x ≥ 0.

_solve_socp_via_hsd rewrites it in canonical conic form over the product cone Nonneg(n) × SOC(m + 1), adding a slack block (t, u), and dispatches to HsdSolver. Two specializations keep each iteration cheap. When A_soc = [diag(d) | 0] (detected by _A_soc_diagonal_zero_padded, or supplied as a hint), _make_socp_structured_embedding_class builds an embedding whose residuals and KKT solve exploit that structure, at a cost linear in n for a fixed number p of equality constraints. Otherwise the generic embedding runs, with the slack cone from _make_slack_soc_cone, whose normal-equations contribution has a closed form.

cvxium.solvers.second_order_cone_programs.solve_second_order_cone_program(f, A_soc, b_soc, c_soc, d_soc, F, g_eq, settings=None, A_soc_diag=None)[source]#

Solve a second-order cone program with bound and equality constraints.

Solves

minimize    f^T x
subject to  ‖A_soc x + b_soc‖ ≤ c_soc^T x + d_soc,
            F x = g_eq,
            x ≥ 0,

with the homogeneous self-dual solver HsdSolver (Andersen, Roos, and Terlaky, 2003). The problem is first written in the canonical conic form

minimize c^T z   subject to   A z = b,   z ∈ K = Nonneg(n) × SOC(m + 1),

by adding the slack variables

t = c_soc^T x + d_soc,   u = A_soc x + b_soc,

which form the second-order cone block (t, u), and the m + 1 equality constraints that define them. HsdSolver needs no strictly feasible starting point, and it reports infeasibility or unboundedness through the result’s status and certificate rather than by raising.

Parameters:

f (npt.NDArray[np.float64]) – Linear objective vector, of length n.
A_soc (npt.NDArray[np.float64]) – Matrix in the cone constraint, of shape (m, n).
b_soc (npt.NDArray[np.float64]) – Vector in the cone constraint, of length m.
c_soc (npt.NDArray[np.float64]) – Linear coefficient in the cone constraint, of length n.
d_soc (float) – Scalar in the cone constraint.
F (npt.NDArray[np.float64]) – Equality constraint matrix, of shape (p, n). An empty array means no equality constraints.
g_eq (npt.NDArray[np.float64]) – Equality constraint right-hand side, of length p.
settings (OptimizationSettings | None) – Solver settings; None uses the defaults.
A_soc_diag (npt.NDArray[np.float64] | None) – The diagonal of A_soc, of length m, given as a hint that A_soc is diagonal in its first m columns and zero in the rest, which requires m to be at most n. When given, the solver skips the O(m n) structure check (_A_soc_diagonal_zero_padded) and uses the structured embedding directly, reading nothing from A_soc but its row count. The hint is trusted, not checked: a wrong hint gives a wrong answer.

Returns:

result – The HsdSolver result mapped back to the original variables. solution is the original variable x, with the slack variables stripped, and the objective value is f^T x. equality_multipliers holds the multipliers of the p equality constraints, or None when there are none. inequality_multipliers holds the n multipliers of the bounds on x, followed by the leading entry of the dual vector of the cone block. The status, message, iteration count, diagnostics, and certificate come from HsdSolver unchanged, so a certificate’s witness lives in the embedding’s coordinates rather than those of x.

Return type:

SolveResult

Raises:

ValueError – When f is empty or A_soc has no rows, propagated from the Nonneg and SecondOrderCone constructors.

References

Andersen, Erling D., Roos, Cornelis and Terlaky, Tamás, On Implementing a Primal-Dual Interior-Point Method for Conic Quadratic Optimization, Mathematical Programming 95, 2003.

Settings#

Settings for Cvxium’s solvers: tolerances, iteration limits and observability.

OptimizationSettings is the single object a caller passes to a solver. It groups the knobs by phase:

OuterSettings: the barrier method’s outer loop (tolerances, the barrier multiplier, and the choice of initial barrier parameter via BarrierInitStrategy).
InnerSettings: the Newton centering steps (tolerances, iteration limit, stall detection).
ArmijoSettings: the backtracking line search on the barrier objective.
LineSearchSettings: the feasibility-preserving step search on a constraint layer.
PrimalDualSettings and LevenbergSettings: the primal-dual solvers’ Newton damping.
ObservabilitySettings: verbose logging and the solve label.

The trace field selects where iteration events go; see trace.

This module depends only on diagnostics.trace, and the solvers package initializer holds only a docstring, so constraint layers can import their settings without importing the solver engine.

class cvxium.solvers.settings.LineSearchSettings(beta=0.5, min_step=0.001)[source]#

Bases: object

Settings for the feasibility-preserving step search on a constraint layer.

Used by ConstraintLayer.btls_max_step to find the largest α keeping the layer’s constraints strictly feasible. The default iterative search starts at α = 1 / β, so that the caller’s β α can reach the full unit step, shrinks α by the factor β at each trial, and gives up below min_step.

Fields:

beta (float) – Shrink factor between trials, in (0, 1). Default 0.5.
min_step (float) – Smallest step the iterative search tries before giving up. Default 1e-3.

class cvxium.solvers.settings.BarrierInitStrategy(*values)[source]#

Bases: Enum

Strategy for choosing the initial barrier parameter t0 of the barrier method.

The first centering step is taken at t = t0, and the outer loop then multiplies t by barrier_multiplier after each step. The right t0 depends on the problem class, so it is configurable per solve through OuterSettings.barrier_init. None there selects BarrierSolver’s default: GRADIENT_BALANCE without equality constraints, EQUALITY_SCHUR with them.

The members:

UNIT: t0 = 1, the base initialize_barrier_parameter. A fixed, neutral start that assumes nothing about the objective’s curvature.
GRADIENT_BALANCE: t0 = ‖∇φ‖ / ‖∇f0‖, balancing the barrier and objective gradients at x0, floored at OuterSettings.min_initial_barrier_parameter. Suited to a start deep in the interior with a large objective gradient, where it removes a heavy line-search damping cost in the first centering. It is adaptive, not conservative: it can put t0 well below 1 or above it. The latter is undesirable for a nonconvex objective whose curvature makes the Newton system indefinite at high t.
EQUALITY_SCHUR: the equality-aware initialization of EqualitySolver.initialize_barrier_parameter (Boyd and Vandenberghe, 2004, section 11.3.1), which folds the equality Jacobian A into the gradient balance through a Schur complement. Requires equality constraints; BarrierSolver raises ValueError when it is requested for a problem without them.
OBJECTIVE_VALUE_GAP: the objective-gap heuristic
```
t0 = m / (μ (f0(x0) - p_star)),
```
where p_star is an under-estimate of the optimal value supplied through OuterSettings.objective_value_estimate, m is the number of inequality constraints and μ is barrier_multiplier (Boyd and Vandenberghe, 2004, section 11.3.1). It skips early centering steps when x0 is already nearly optimal. The result is capped at m / (μ ε), one step from the end, where ε is the outer tolerance, and floored at 1, so at least one centering step runs. It degrades to t0 = 1 when no estimate is given. Use it when a good p_star is cheaply known (a closed-form under-estimate, a relaxation value, or an adjacent point in a sweep).

References

Boyd, Stephen and Vandenberghe, Lieven, Convex Optimization, Cambridge University Press, 2004.

class cvxium.solvers.settings.OuterSettings(tolerance=1e-06, tolerance_soft=0.001, barrier_multiplier=10.0, tolerance_rel=None, min_initial_barrier_parameter=0.001, barrier_init=None, objective_value_estimate=None, max_outer_iterations=30)[source]#

Bases: object

Settings for the outer (barrier) loop of the interior-point method.

Fields:

tolerance (float) – Target tolerance on the surrogate duality gap; the outer loop stops once the gap falls below it. Default 1e-6.
tolerance_soft (float) – Fallback tolerance when tolerance cannot be reached: a gap in [tolerance, tolerance_soft] is acceptable (medium accuracy). This is the hard requirement: when even the best gap found exceeds it, the solve raises. Default 1e-3.
barrier_multiplier (float) – Factor μ by which the barrier parameter grows at each outer iteration. Default 10.0.
tolerance_rel (float | None) – Relative gap tolerance. A solver that honors it declares convergence once the gap is at most
```
max(``tolerance``, ``tolerance_rel`` |f0|),
```
an absolute floor or a fraction of the objective’s scale, whichever is larger. The absolute floor keeps the test meaningful when the optimal value is near zero (for example, a bilinear matrix game with value zero), where a purely relative test would never pass. StationaritySolver uses it as an acceptance criterion. The barrier method keeps its acceptance absolute, since the barrier guarantee is an absolute bound (Boyd and Vandenberghe, 2004, section 11.3), and consults tolerance_rel only for its failure message: when a solve misses tolerance_soft but the relative gap is within tolerance_rel, the raised InteriorPointMethodError notes that the result is probably good enough relative to the objective’s scale. None (the default) disables the relative criterion.
min_initial_barrier_parameter (float) – Lower bound on the initial barrier parameter t0 from the gradient-balance strategy, and on StationaritySolver’s initial barrier parameter. The gradient ratio can be zero in degenerate cases, and t0 = 0 breaks the outer step count, whose log(t0 ε) is then -inf; the floor keeps t0 strictly positive. Keep it small: a large t0 starts the first centering far from the central path, where Newton’s method diverges and the line search collapses. It is deliberately independent of tolerance_soft, which may be raised to a large acceptance scale. Default 1e-3.
barrier_init (BarrierInitStrategy | None) – Strategy for the initial barrier parameter t0 (see BarrierInitStrategy). None (the default) selects GRADIENT_BALANCE without equality constraints and EQUALITY_SCHUR with them. Set it explicitly to override, for example UNIT for a problem class the adaptive ratio does not suit (such as a nonconvex objective whose curvature makes the high-t Newton system indefinite), or to pin a strategy against a future change of default.
objective_value_estimate (float | None) – Under-estimate p_star of the optimal objective value, used by the OBJECTIVE_VALUE_GAP strategy and ignored by the others; with None (the default) that strategy degrades to t0 = 1. It must be an under-estimate: a p_star above the true optimum shrinks the gap and inflates t0 too aggressively.
max_outer_iterations (int) – Maximum number of outer iterations before giving up with SolveStatus.MAX_ITERATIONS. Used by StationaritySolver, whose outer loop runs until a gap test passes and so needs an explicit cap; the barrier method instead computes its step count from the barrier schedule. Default 30.

References

Boyd, Stephen and Vandenberghe, Lieven, Convex Optimization, Cambridge University Press, 2004.

class cvxium.solvers.settings.InnerSettings(tolerance=1e-06, tolerance_soft=0.0001, max_iterations=1000, stall_patience=5, stall_rel_improvement=0.01, newton_decrement_via_gradient=False)[source]#

Bases: object

Settings for the inner (Newton centering) loop of the interior-point method.

Fields:

tolerance (float) – Convergence tolerance on the centering step’s suboptimality, λ^2 / 2 for the squared Newton decrement λ^2. Default 1e-6.
tolerance_soft (float) – Fallback tolerance when tolerance cannot be reached: a centering step that ends with suboptimality below it is accepted. Default 1e-4.
max_iterations (int) – Maximum number of Newton iterations per centering step. Default 1000.
stall_patience (int) – Number of consecutive quadratic-phase iterations without meaningful improvement in suboptimality (see stall_rel_improvement) after which the centering step stops and returns the best iterate it has seen. Guards against the high-t regime, where floating-point cancellation in
```
f_t(x) = t f0(x) - ∑ log(-f_i(x))
```
leaves Newton’s method bouncing at the floating-point floor, below tolerance in exact arithmetic but not in practice. The stop fires only when the best suboptimality is below tolerance_soft; otherwise the loop runs on to max_iterations, where the same soft-tolerance fallback applies. Default 5.
stall_rel_improvement (float) – Smallest relative decrease in suboptimality, against the best so far, that counts as progress and resets the stall counter. Without it, a slow creep toward the floating-point floor would reset the counter every iteration and defeat the stall test, spending the whole max_iterations budget. Genuine quadratic-phase progress is orders of magnitude per step, so a 1% floor never cuts off real convergence. Default 0.01.
newton_decrement_via_gradient (bool) – How to compute the squared Newton decrement, which drives the stopping test and the line search. False (the default) uses the Hessian form Δx^T H Δx through hessian_multiply: a second Hessian-vector product per Newton step, but the true quadratic-model decrement, and more reliable when high precision is needed. True uses the gradient form -∇f_t^T Δx, which agrees at the exact Newton step and can be far cheaper (about 20 times on one large structured objective), but which degrades under inexact solves and ill-conditioning at high t. Prefer True only when high precision is not required.

class cvxium.solvers.settings.ArmijoSettings(alpha=0.01, beta=0.5, min_step=0.001, use_self_concordant_step_cap=False)[source]#

Bases: object

Settings for the Armijo (sufficient-decrease) backtracking line search.

Used by the barrier method’s line search and by the primal-dual solvers’ step search. Distinct from LineSearchSettings, which controls the feasibility-preserving step search on individual constraint layers.

Fields:

alpha (float) – Sufficient-decrease coefficient α. The barrier method accepts a trial step s when the barrier objective decreases by at least α s λ^2, where λ^2 is the squared Newton decrement. Default 0.01.
beta (float) – Shrink factor β applied to the step between trials. Default 0.5.
min_step (float) – Smallest step the search tries before declaring failure. Default 1e-3.
use_self_concordant_step_cap (bool) –

When True, the barrier method’s line search starts from
```
min(1 / (1 + λ), β s_feas)
```
instead of min(1, β s_feas), where s_feas is the maximum feasible step (Boyd and Vandenberghe, 2004, section 9.6.4). Useful on sharply curved barriers, such as second-order cone constraints; harmful on linear and quadratic programs. Default False.

References

Boyd, Stephen and Vandenberghe, Lieven, Convex Optimization, Cambridge University Press, 2004.

class cvxium.solvers.settings.ObservabilitySettings(verbose=False, label=None)[source]#

Bases: object

Settings for solver observability (logging and tracing).

Fields:

verbose (bool) – When True, attach a console handler to the cvxium logger (see _configure_verbose_logging) and show progress at INFO (centering steps) and DEBUG (Newton steps and line search). For finer control, leave it False and configure logging.getLogger("cvxium") directly. Default False.
label (str | None) – Human-readable solver name, reported in the solver field of the start and done trace events of the barrier, primal-dual and homogeneous self-dual solvers (for example, “Starting IPM (<label>)”). With None (the default), each solver uses its class name. This lets a caller replace an uninformative internal adapter name such as _BarrierAdapter with a meaningful one. A name passed explicitly to a BaseInteriorPointMethodSolver takes precedence.

class cvxium.solvers.settings.LevenbergSettings(max_attempts=40, grow=4.0, shrink_good=0.25, shrink_ok=0.5, rho_good=0.75, rho_ok=0.25, drop_to_zero=1e-12)[source]#

Bases: object

Adaptive Levenberg-Marquardt damping schedule for the primal-dual step.

Each iteration tries the undamped step first. Damping engages only when a feasible step cannot otherwise be found, and a ratio test of predicted against actual residual reduction relaxes it back toward zero. See PrimalDualSolver for the full algorithm.

Fields:

max_attempts (int) – Maximum damping increases per iteration; when they are exhausted, the step raises NewtonStepError. Default 40.
grow (float) – Multiplier applied to the damping when a step is rejected. Default 4.0.
shrink_good (float) – Multiplier applied to the damping when the ratio ρ exceeds rho_good. Default 0.25.
shrink_ok (float) – Multiplier applied to the damping when ρ exceeds rho_ok but not rho_good. Default 0.5.
rho_good (float) – Ratio threshold above which the damping shrinks aggressively. Default 0.75.
rho_ok (float) – Ratio threshold above which the damping shrinks gently. Default 0.25.
drop_to_zero (float) – Relative threshold for switching damping off: below drop_to_zero max(1, ‖x‖) the damping snaps to exactly 0, restoring the undamped step. Default 1e-12.

class cvxium.solvers.settings.PrimalDualSettings(damping=<factory>)[source]#

Bases: object

Settings specific to the primal-dual solvers.

Grouped sub-settings, mirroring how OptimizationSettings nests its concerns. It holds the Levenberg damping schedule; further primal-dual settings would join it as sibling groups.

Fields:: damping (LevenbergSettings) – Adaptive Levenberg-Marquardt damping schedule.

class cvxium.solvers.settings.OptimizationSettings(outer=<factory>, inner=<factory>, armijo=<factory>, observability=<factory>, line_search=<factory>, pd_fraction_to_boundary_min=0.99, primal_dual=<factory>, trace=<factory>)[source]#

Bases: object

Algorithm settings shared by Cvxium’s solvers.

Groups the settings of each part of a solve; each solver reads the groups it uses.

Fields:

outer (OuterSettings) – Outer (barrier) loop tolerances and barrier schedule.
inner (InnerSettings) – Inner (Newton) loop tolerances, iteration cap and stall detection.
armijo (ArmijoSettings) – Parameters of the Armijo backtracking line search.
observability (ObservabilitySettings) – Logging and labeling settings, such as verbose.
line_search (LineSearchSettings) – Settings for the feasibility-preserving step search of ConstraintLayer.btls_max_step, distinct from the Armijo line search.
pd_fraction_to_boundary_min (float) – Floor τ_min of the fraction-to-boundary factor that caps each primal-dual step to keep the multipliers positive (see mehrotra_step_cap). The step is
```
s = γ s_max,   γ = max(τ_min, 1 - μ),   μ = η / m,
```
where s_max is the largest step keeping the multipliers nonnegative and μ is the surrogate duality gap per multiplier. Far from the solution (μ ≥ 1 - τ_min) the cap is τ_min s_max. Near it (μ → 0), γ → 1, which keeps the step from pinning at the minimum step when an active multiplier is close to zero while its step keeps pulling it negative (Mehrotra, 1992; Wright, 1997). Default 0.99.
primal_dual (PrimalDualSettings) – Settings specific to the primal-dual solvers (the Levenberg damping schedule); ignored by the barrier method.
trace (Trace) – Sink for structured solver events (Phase I outcome, centering steps, Newton steps, line search, SVD timing). The default LoggingTrace emits each event as a cvxium.* log record in the format IterationHandler reads (USAGE.md, section 7). Subclass Trace to collect events directly, without logging.

References

Mehrotra, Sanjay, On the Implementation of a Primal-Dual Interior Point Method, SIAM Journal on Optimization 2, 1992.

Wright, Stephen J., Primal-Dual Interior-Point Methods, SIAM, 1997.

Subclassing Framework#

Base optimizer classes and settings for Cvxium’s barrier interior-point method.

Defines the class hierarchy that Cvxium’s barrier solvers build on:

Optimizer: the abstract base, holding settings and an optional Phase I solver.
FeasibilitySolver: an optimizer that finds a feasible point; TrivialFeasibilitySolver is the pass-through placeholder.
BaseInteriorPointMethodSolver: the barrier method itself. solve runs the outer loop over the barrier parameter t, tracking the best primal and dual bounds; centering_step runs Newton’s method with backtracking line search; subclasses supply the objective, constraints, Hessian products and Newton step.
InteriorPointMethodSolver and FeasibilityInteriorPointSolver: the optimization and feasibility variants.
UnconstrainedNewtonSolver and EqualityConstrainedNewtonSolver: Newton’s method without inequality constraints, as a single centering step at t = 1.

It also defines the Phase I infeasibility errors and the private helpers that turn centering-step outcomes into SolveResult objects. The solver settings live in settings.

class cvxium.solvers.optimization.Optimizer(phase1_solver=None, settings=None, **kwargs)[source]#

Bases: ABC

Abstract base for Cvxium’s iterative optimizers.

Holds the algorithm settings and an optional Phase I solver, and declares the interface every optimizer shares: the constraint counts and solve.

Parameters:

phase1_solver (FeasibilitySolver | None) – Solver that finds a feasible starting point when the initial guess is not feasible, or None when the optimizer needs none.
settings (OptimizationSettings | None) – Algorithm settings; None uses the defaults. When observability.verbose is set, the constructor attaches a console handler to the cvxium logger.
**kwargs (Any) – Accepted for cooperative construction and ignored.

abstract property num_eq_constraints#

Return the number of equality constraints.

Returns:: p – The number of equality constraints.
Return type:: int

abstract property num_ineq_constraints#

Return the number of inequality constraints.

Returns:: m – The number of inequality constraints.
Return type:: int

abstractmethod solve(x0=None, **kwargs)[source]#

Solve the optimization problem.

Parameters:

x0 (npt.NDArray[np.float64] | None) – Initial guess; None lets the implementation choose or require one.
**kwargs (Any) – Implementation-specific options.

Returns:

result – The solution and the solve’s diagnostics.

Return type:

SolveResult

class cvxium.solvers.optimization.FeasibilitySolver(phase1_solver=None, settings=None, **kwargs)[source]#

Bases: Optimizer

Abstract optimizer that finds a feasible point rather than an optimal one.

Serves as the Phase I solver of an Optimizer. Its solve returns a feasible point, or raises when none is found.

Parameters:

phase1_solver (FeasibilitySolver | None) – Phase I solver of its own, or None.
settings (OptimizationSettings | None) – Algorithm settings; None uses the defaults.
**kwargs (Any) – Accepted for cooperative construction and ignored.

abstractmethod solve(x0=None, **kwargs)[source]#

Find a feasible point.

Parameters:

x0 (npt.NDArray[np.float64] | None) – Initial guess; None lets the implementation choose or require one.
**kwargs (Any) – Implementation-specific options.

Returns:

result – The result, whose solution is the feasible point found.

Return type:

SolveResult

class cvxium.solvers.optimization.TrivialFeasibilitySolver(settings=None)[source]#

Bases: FeasibilitySolver

Pass-through feasibility solver for which every point is feasible.

A placeholder Phase I solver for an optimizer whose feasibility is established elsewhere: BarrierSolver’s internal adapter uses it, since BarrierSolver finds a feasible point before constructing the adapter.

Parameters:: settings (OptimizationSettings | None) – Algorithm settings; None uses the defaults.

property num_eq_constraints#

Return zero, the number of equality constraints.

Returns:: p – Always 0.
Return type:: int

property num_ineq_constraints#

Return zero, the number of inequality constraints.

Returns:: m – Always 0.
Return type:: int

solve(x0=None, **kwargs)[source]#

Return the initial guess unchanged, as a feasible point.

Parameters:

x0 (npt.NDArray[np.float64] | None) – The point to return. Required despite the None default.
**kwargs (Any) – Ignored.

Returns:

result – A result with solution x0, status FEASIBLE and zero iterations.

Return type:

SolveResult

Raises:

ValueError – When x0 is None.

class cvxium.solvers.optimization.InteriorPointMethodSolver(phase1_solver=None, settings=None, name=None, **kwargs)[source]#

Bases: BaseInteriorPointMethodSolver

Barrier interior-point solver for optimization problems.

A BaseInteriorPointMethodSolver whose is_feasible always returns False: outside feasibility mode the solver runs to the optimum rather than stopping at a feasible point.

Parameters:

phase1_solver (FeasibilitySolver | None) – Solver that finds a strictly feasible start; required by solve.
settings (OptimizationSettings | None) – Algorithm settings; None uses the defaults.
name (str | None) – Identifier for log messages; None uses the label or the class name.
**kwargs (Any) – Accepted for cooperative construction and ignored.

is_feasible(x)[source]#

Return False, so the solver never stops at a merely feasible point.

Parameters:: x (npt.NDArray[np.float64]) – The point to test; ignored.
Returns:: feasible – Always False.
Return type:: bool

solve(x0=None, **kwargs)[source]#

Solve the problem with the barrier method.

Solves

minimize    f0(x)
subject to  f_i(x) ≤ 0,   i = 1, ..., m,
            A x = b.

See BaseInteriorPointMethodSolver.solve.

Parameters:

x0 (npt.NDArray[np.float64] | None) – Initial guess. When it is not strictly feasible, the Phase I solver finds a start that is.
**kwargs (Any) – Forwarded to BaseInteriorPointMethodSolver.solve.

Returns:

result – The solution and the solve’s diagnostics.

Return type:

SolveResult

Raises:

ValueError – Propagated from BaseInteriorPointMethodSolver.solve when there is no Phase I solver.
InteriorPointMethodError – Propagated from BaseInteriorPointMethodSolver.solve when the best bounds miss outer.tolerance_soft or no centering step completes.

class cvxium.solvers.optimization.FeasibilityInteriorPointSolver(phase1_solver=None, settings=None, **kwargs)[source]#

Bases: BaseInteriorPointMethodSolver, FeasibilitySolver

Base class for a feasibility solver built on the barrier method.

A feasibility solver can stop as soon as it finds a feasible point, rather than solving its Phase I problem to optimality. That early stop happens in BaseInteriorPointMethodSolver’s feasibility mode, which a subclass enables by overriding _feasibility_threshold to return a value and is_feasible to recognize a feasible point; this class adds neither.

Parameters:

phase1_solver (FeasibilitySolver | None) – Solver that finds a start strictly feasible for the constraints this solver keeps; required by solve.
settings (OptimizationSettings | None) – Algorithm settings; None uses the defaults.
**kwargs (Any) – Passed to BaseInteriorPointMethodSolver (for example, name).

solve(x0=None, **kwargs)[source]#

Find a point satisfying every constraint, with the barrier method.

Finds x with

A x = b,   f_i(x) ≤ 0 for i = 1, ..., m,   f_j(x) ≤ 0 for j = 1, ..., n,

given a start the Phase I solver makes strictly feasible for the first group.

Parameters:

x0 (npt.NDArray[np.float64] | None) – Initial guess. A guess feasible for some of the constraints lets the Phase I solver focus on the rest.
**kwargs (Any) – Forwarded to BaseInteriorPointMethodSolver.solve.

Returns:

result – The result, whose solution is a feasible point.

Return type:

SolveResult

Raises:

ProblemCertifiablyInfeasibleError – Propagated from BaseInteriorPointMethodSolver.solve in feasibility mode, when the dual certifies that no feasible point exists.
ProblemMarginallyFeasibleError – Propagated from BaseInteriorPointMethodSolver.solve in feasibility mode, when no feasible point is found and infeasibility cannot be certified.
InteriorPointMethodError – Propagated from BaseInteriorPointMethodSolver.solve when a centering step fails before reaching an acceptable gap.

Notes

Given x0 with A x0 = b and f_i(x0) < 0 for every i, the typical formulation solves

minimize    s
subject to  A x = b,
            f_i(x) ≤ 0,   i = 1, ..., m,
            f_j(x) ≤ s,   j = 1, ..., n.

If the optimal s is positive, the problem is infeasible, and the Lagrange multipliers certify it. Otherwise the solution x is feasible for every constraint. The problem need not be solved to high precision: any feasible (x, s) with s < 0 is enough to stop.

class cvxium.solvers.optimization.UnconstrainedNewtonSolver(settings=None, **kwargs)[source]#

Bases: BaseInteriorPointMethodSolver

Newton’s method for problems with no equality or inequality constraints.

Without inequality constraints the barrier parameter plays no role, so the outer barrier loop is skipped and Newton’s method is applied directly to f0, which is one centering step at t = 1.

A subclass implements newton_step (solve H Δx = -∇f0 and return Δx), evaluate_objective, gradient and hessian_vector_product.

Parameters:

settings (OptimizationSettings | None) – Algorithm settings; None uses the defaults.
**kwargs (Any) – Passed to BaseInteriorPointMethodSolver (for example, name).

property num_eq_constraints#

Return zero, the number of equality constraints.

Returns:: p – Always 0.
Return type:: int

property num_ineq_constraints#

Return zero, the number of inequality constraints.

Returns:: m – Always 0.
Return type:: int

solve(x0=None, **kwargs)[source]#

Minimize the objective with Newton’s method.

Skips the barrier loop and runs a single centering step at t = 1.

Parameters:

x0 (npt.NDArray[np.float64] | None) – Initial guess. Required despite the None default.
**kwargs (Any) – Ignored.

Returns:

result – The solution, with solver name "newton".

Return type:

SolveResult

Raises:

ValueError – When x0 is None.
CenteringStepError – Propagated from centering_step when a Newton step cannot be computed, the line search fails, or Newton’s method does not reach an acceptable tolerance.

is_feasible(x)[source]#

Return True, since every point is feasible without constraints.

Parameters:: x (npt.NDArray[np.float64]) – The point to test; ignored.
Returns:: feasible – Always True.
Return type:: bool

constraints(x)[source]#

Return the empty vector of inequality constraint values.

Parameters:: x (npt.NDArray[np.float64]) – The point; ignored.
Returns:: f – An empty array.
Return type:: npt.NDArray[np.float64]

grad_constraints(x)[source]#

Return the empty inequality constraint Jacobian.

Parameters:: x (npt.NDArray[np.float64]) – The point, used only for its length M.
Returns:: G – An empty array of shape (0, M).
Return type:: npt.NDArray[np.float64]

btls_keep_feasible(x, delta_x)[source]#

Return inf, since no constraint limits the step.

Parameters:

x (npt.NDArray[np.float64]) – The current iterate; ignored.
delta_x (npt.NDArray[np.float64]) – The search direction; ignored.

Returns:

btls_s – Always inf.

Return type:

float

abstractmethod newton_step(x)[source]#

Compute the Newton step for the objective.

Implementations solve H(x) Δx = -∇f0(x), exploiting the Hessian’s structure.

Parameters:: x (npt.NDArray[np.float64]) – The current iterate.
Returns:: delta_x – The Newton step.
Return type:: npt.NDArray[np.float64]
Raises:: NewtonStepError – Implementations raise when the system cannot be solved.

abstractmethod hessian_vector_product(x, y)[source]#

Multiply a vector by the objective Hessian H(x).

Parameters:

x (npt.NDArray[np.float64]) – The point at which the Hessian is evaluated.
y (npt.NDArray[np.float64]) – The vector to multiply.

Returns:

Hy – The product H(x) y.

Return type:

npt.NDArray[np.float64]

calculate_newton_step(x, t)[source]#

Compute the Newton step through newton_step, ignoring t.

Parameters:

x (npt.NDArray[np.float64]) – The current iterate.
t (float) – The barrier parameter; unused, since there is no barrier.

Returns:

delta_x (npt.NDArray[np.float64]) – The Newton step.
nu (npt.NDArray[np.float64]) – An empty array, since there are no equality constraints.

Raises:

NewtonStepError – Propagated from newton_step.

hessian_multiply(x, t, y)[source]#

Multiply a vector by the objective Hessian, ignoring t.

Parameters:

x (npt.NDArray[np.float64]) – The point at which the Hessian is evaluated.
t (float) – The barrier parameter; unused, since there is no barrier.
y (npt.NDArray[np.float64]) – The vector to multiply.

Returns:

Hy – The product H(x) y.

Return type:

npt.NDArray[np.float64]

evaluate_dual(lmbda, nu, x_star)[source]#

Return the objective value at the solution, which the dual equals here.

Without constraints the Lagrangian is the objective itself, so at a minimizer the dual value equals the primal value. Exact only at the optimum: at an approximate solution the returned value is not a lower bound.

Parameters:

lmbda (npt.NDArray[np.float64]) – The inequality multipliers; ignored (empty).
nu (npt.NDArray[np.float64]) – The equality multipliers; ignored (empty).
x_star (npt.NDArray[np.float64]) – The solution.

Returns:

g – The objective value f0(x_star).

Return type:

float

class cvxium.solvers.optimization.EqualityConstrainedNewtonSolver(settings=None, **kwargs)[source]#

Bases: BaseInteriorPointMethodSolver

Newton’s method for problems with equality constraints A x = b only.

Without inequality constraints the barrier parameter plays no role, so the outer barrier loop is skipped and Newton’s method is applied directly to the equality-constrained problem, each step solving the KKT system rather than the Hessian system alone.

A subclass implements A (of shape (p, M)), b (of length p), newton_step (solve the KKT system and return Δx and ν), evaluate_objective, gradient and hessian_vector_product.

Parameters:

settings (OptimizationSettings | None) – Algorithm settings; None uses the defaults.
**kwargs (Any) – Passed to BaseInteriorPointMethodSolver (for example, name).

abstract property A#

Return the equality constraint matrix A.

Returns:: A – The equality matrix, of shape (p, M).
Return type:: npt.NDArray[np.float64]

abstract property b#

Return the equality right-hand side b.

Returns:: b – The right-hand side, of length p.
Return type:: npt.NDArray[np.float64]

property num_eq_constraints#

Return the number of equality constraints, the length of b.

Returns:: p – The number of equality constraints.
Return type:: int

property num_ineq_constraints#

Return zero, the number of inequality constraints.

Returns:: m – Always 0.
Return type:: int

solve(x0=None, **kwargs)[source]#

Minimize the objective subject to A x = b with Newton’s method.

Skips the barrier loop and runs a single centering step at t = 1. Each Newton step satisfies A Δx = 0, so the iterates keep the equality residual of x0.

Parameters:

x0 (npt.NDArray[np.float64] | None) – Initial guess, which should satisfy A x0 = b (not checked). Required despite the None default.
**kwargs (Any) – Ignored.

Returns:

result – The solution, with solver name "newton" and the equality multipliers.

Return type:

SolveResult

Raises:

ValueError – When x0 is None.
CenteringStepError – Propagated from centering_step when a Newton step cannot be computed, the line search fails, or Newton’s method does not reach an acceptable tolerance.

is_feasible(x)[source]#

Return True, since there are no inequality constraints to violate.

Parameters:: x (npt.NDArray[np.float64]) – The point to test; ignored.
Returns:: feasible – Always True.
Return type:: bool

constraints(x)[source]#

Return the empty vector of inequality constraint values.

Parameters:: x (npt.NDArray[np.float64]) – The point; ignored.
Returns:: f – An empty array.
Return type:: npt.NDArray[np.float64]

grad_constraints(x)[source]#

Return the empty inequality constraint Jacobian.

Parameters:: x (npt.NDArray[np.float64]) – The point, used only for its length M.
Returns:: G – An empty array of shape (0, M).
Return type:: npt.NDArray[np.float64]

btls_keep_feasible(x, delta_x)[source]#

Return inf, since no inequality constraint limits the step.

Parameters:

x (npt.NDArray[np.float64]) – The current iterate; ignored.
delta_x (npt.NDArray[np.float64]) – The search direction; ignored.

Returns:

btls_s – Always inf.

Return type:

float

abstractmethod newton_step(x)[source]#

Solve the KKT system for the Newton step and the equality multiplier.

Implementations solve

| H(x)   A^T | | Δx |   | -∇f0(x) |
|  A      0  | | ν  | = |    0    |

exploiting the problem’s structure.

Parameters:

x (npt.NDArray[np.float64]) – The current iterate.

Returns:

delta_x (npt.NDArray[np.float64]) – The Newton step, of length M.
nu (npt.NDArray[np.float64]) – The equality multipliers, of length p.

Raises:

NewtonStepError – Implementations raise when the system cannot be solved.

abstractmethod hessian_vector_product(x, y)[source]#

Multiply a vector by the objective Hessian H(x).

Parameters:

x (npt.NDArray[np.float64]) – The point at which the Hessian is evaluated.
y (npt.NDArray[np.float64]) – The vector to multiply.

Returns:

Hy – The product H(x) y.

Return type:

npt.NDArray[np.float64]

calculate_newton_step(x, t)[source]#

Compute the Newton step through newton_step, ignoring t.

Parameters:

x (npt.NDArray[np.float64]) – The current iterate.
t (float) – The barrier parameter; unused, since there is no barrier (t = 1).

Returns:

delta_x (npt.NDArray[np.float64]) – The Newton step.
nu (npt.NDArray[np.float64]) – The equality multipliers.

Raises:

NewtonStepError – Propagated from newton_step.

hessian_multiply(x, t, y)[source]#

Multiply a vector by the objective Hessian, ignoring t.

Parameters:

x (npt.NDArray[np.float64]) – The point at which the Hessian is evaluated.
t (float) – The barrier parameter; unused, since there is no barrier (t = 1).
y (npt.NDArray[np.float64]) – The vector to multiply.

Returns:

Hy – The product H(x) y.

Return type:

npt.NDArray[np.float64]

evaluate_dual(lmbda, nu, x_star)[source]#

Return the objective value at the solution, which the dual equals here.

With only linear equality constraints, strong duality holds, and at a feasible minimizer with its multipliers the Lagrangian equals the objective, so the dual value equals the primal value. Exact only at the optimum: at an approximate solution the returned value is not a lower bound.

Parameters:

lmbda (npt.NDArray[np.float64]) – The inequality multipliers; ignored (empty).
nu (npt.NDArray[np.float64]) – The equality multipliers; ignored.
x_star (npt.NDArray[np.float64]) – The solution.

Returns:

g – The objective value f0(x_star).

Return type:

float