Metadata-Version: 2.4
Name: ellalgo
Version: 0.10
Summary: Ellipsoid Method in Python
Home-page: https://github.com/luk036/ellalgo
Author: Wai-Shing Luk
Author-email: luk036@gmail.com
License: MIT
Project-URL: Documentation, https://ellalgo.readthedocs.io/en/latest/
Project-URL: Source, https://github.com/luk036/ellalgo
Platform: any
Classifier: Development Status :: 4 - Beta
Classifier: Programming Language :: Python
Requires-Python: >=3.9
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
License-File: LICENSE.txt
Requires-Dist: numpy
Requires-Dist: hypothesis
Provides-Extra: testing
Requires-Dist: setuptools; extra == "testing"
Requires-Dist: hypothesis; extra == "testing"
Requires-Dist: pytest; extra == "testing"
Requires-Dist: pytest-cov; extra == "testing"
Provides-Extra: bench
Requires-Dist: cvxpy; extra == "bench"
Dynamic: license-file

[![Project generated with PyScaffold](https://img.shields.io/badge/-PyScaffold-005CA0?logo=pyscaffold)](https://pyscaffold.org/)
[![Documentation Status](https://readthedocs.org/projects/ellalgo/badge/?version=latest)](https://ellalgo.readthedocs.io/en/latest/?badge=latest)
[![codecov](https://codecov.io/gh/luk036/ellalgo/branch/main/graph/badge.svg?token=6lpjUzPavX)](https://codecov.io/gh/luk036/ellalgo)

<p align="center">
  <img src="./ellipsoid-method-for-convex-optimization.svg"/>
</p>

# 👁️ ellalgo

> Ellipsoid Method in Python

The Ellipsoid Method as a linear programming algorithm was first introduced by L. G. Khachiyan in 1979. It is a polynomial-time algorithm that uses ellipsoids to iteratively reduce the feasible region of a linear program until an optimal solution is found. The method works by starting with an initial ellipsoid that contains the feasible region, and then successively shrinking the ellipsoid until it contains the optimal solution. The algorithm is guaranteed to converge to an optimal solution in a finite number of steps.

The method has a wide range of practical applications in operations research. It can be used to solve linear programming problems, as well as more general convex optimization problems. The method has been applied to a variety of fields, including economics, engineering, and computer science. Some specific applications of the Ellipsoid Method include portfolio optimization, network flow problems, and the design of control systems. The method has also been used to solve problems in combinatorial optimization, such as the traveling salesman problem.

## What is Parallel Cut?

In the context of the Ellipsoid Method, a parallel cut refers to a pair of linear constraints of the form aTx <= b and -aTx <= -b, where a is a vector of coefficients and b is a scalar constant. These constraints are said to be parallel because they have the same normal vector a, but opposite signs. When a parallel cut is encountered during the Ellipsoid Method, both constraints can be used simultaneously to generate a new ellipsoid. This can improve the convergence rate of the method, especially for problems with many parallel constraints.

## Known limitations

- **No sparsity exploitation.** The method treats the problem data as dense, so it cannot take advantage of sparse constraint matrices the way tuned interior-point/LP solvers do.
- **Iteration budget grows ~O(n²).** As dimensionality grows, interior-point methods (e.g. CVXPY/CLARABEL) usually scale better than the ellipsoid method.
- **Interpreted per-iteration overhead.** Each iteration runs in Python, so pure-Python overhead can reverse the ranking against compiled code, especially on small problems.
- **Positive definiteness can be lost silently.** The direct `Ell` representation may lose positive definiteness; mitigate with `Options(check_pd=True)` or use `EllStable`.
- **Stopping threshold.** An absolute stopping threshold should be paired with the stall guard (enabled by default via `Options(stall_guard=True)`) so the loop stops with `SolverStatus.Stalled` at floating-point resolution instead of spinning to `max_iters`.
- **Oracle correctness.** Custom oracles must be verified (see `ellalgo.oracle_checks`: `check_cut_valid`, `check_subgradient`, `check_lmi_witness`).
- **Approximate oracles.** Affine-arithmetic and difference-of-convex oracles carry inherent approximation error/bias.
- **Discrete/quantized design.** Discretizing the design space carries sampling-grid artifacts.

`EllStable` is preferred in compiled code, while `Ell` is preferred for pure-Python prototyping.

## Used by

- [netoptim](https://github.com/luk036/netoptim)
- [corr-solver](https://github.com/luk036/corr-solver)
- [multiplierless](https://github.com/luk036/multiplierless)

## See also

- [Presentation Slides](https://luk036.github.io/cvx)

## 👉 Note

This project has been set up using PyScaffold 4.5. For details and usage
information on PyScaffold see https://pyscaffold.org/.
