Homotopy Methods for Convex Optimization

This Python library implements homotopy-based optimization methods designed to solve convex optimization problems, with a particular focus on semidefinite programs, hyperbolic programs, and convex optimization problems involving a single convexity constraint. The repository includes various examples and benchmark comparisons with state-of-the-art solvers.

Features

A homotopy method to solve

• semidefinite programs
• hyperbolic programs
• convex optimization problems with one convex constraint

Table of contents

• Homotopy Optimization
• Features
• Installation
• Examples
  ▹ Semidefinite Programming
  ▹ Hyperbolic Programming
  ▹ Geometric Programming
  ▹ Optimizing over a k-Ellipsoid
• Benchmarks
  ▹ Semidefinite Programming
  ▹ Geometric Programming
• License
• References

Installation

To install the package, you can either clone the repository or download it as a zip file.

1. Clone the repository

git clone https://github.com/andreasklingler/HomotopyOptimization.git
cd HomotopyOptimization

2. Install the required dependecies

The repository requires the following Python libraries:

• numpy
• scipy
• cvxpy (only for the benchmarks)
• sympy (only for the hyperbolic program example)
• matplotlib (for 2D visualizations)

To install the required dependencies, run:

# Install the required dependencies
pip install -r requirements.txt

3. Usage

After installation, you can use the solvers by importing them from the /HomotopyOpt folder in your Python scripts. For example:

from HomotopyOpt.SDPOpt import SDPSolver  # Homotopy SDP solver

solver = SDPSolver(A, B, f, aopt, 1)
solver.solve(N, method="smoothed", tol=1e-6)

Check the /Examples folder for example scripts demonstrating how to use each solver in different optimization scenarios.

Examples

In the following, we illustrate the use of the three solvers on a different examples.

Semidefinite Programming

In /Examples/semidefinite_programming1.py we considers a random semidefinite program in its dual form (see also [1, Section 3.1]).

The following code solves the SDP in two different ways:

# No smoothing
solver0 = SDPSolver(A_init, A_target, f, a0, 0)
solver0.solve(N, method="exact", tol=1e-5)

# First-order smoothing
solver1 = SDPSolver(A_init, A_target, f, a0, 1)
solver1.solve(N, method="smoothed", tol=1e-5)

The variables A_init and A_target are NumPy arrays representing the spectrahedral descriptions of the initial and target feasible sets, respectively. In our case, A_init describes a ball of radius $1$. The vector f defines the linear objective function, and a_0 is the optimizer of the initial problem. The final parameter (either 0, 1, or 2) specifies the degree of smoothing applied. The value N determines the number of homotopy steps to compute, and tol sets the tolerance for the ODE solver used in tracing the homotopy path. The method of the solver can be either smoothed or exact (which is a smoothing of degree 0).

Hyperbolic Programming

In /Examples/hyperbolic_optimization.py we considers a hyperbolic program (see also [1, Section 4.1]).

The following code solves the hyperbolic program over the rigidly convex set represented by symmetric_RZ:

solver = HyperbolicProgramSolver(
    start,           # Initial polynomial
    symmetric_RZ,    # Target polynomial
    2.0,             # Degree of initial polynomial
    r,               # Degree of target polynomial
    f,               # Objective vector
    a0,              # Optimizer of initial problem
    1                # Smoothing degree (0, 1, or 2)
)

# Solve the problem
solver.solve(N, method="smoothed", tol=1e-5)

Here, the initial and target feasible sets are represented via real-zero polynomials: start for the initial set and symmetric_RZ for the target. The solver also requires the degrees of these polynomials.

• f is the linear objective vector.
• a0 is the optimizer of the initial problem.
• The final argument specifies the smoothing degree: 0, 1, or 2.
• N is the number of homotopy steps.
• tol sets the tolerance for the ODE solver.

Note that /Examples/semidefinite_programming2.py considers a random semidefinite program as a hyperbolic optimization problem using the same solver.

Optimization problems over a single convexity constraint

In Examples/optimization_ellipsoid.py and geometric_programming.py, we apply the homotopy solver to convex optimization problems with a single convexity constraint (see [1, Section 3.2] for details).

The following code solves such a problem, where p_start and p_end are convex functions representing the initial and target feasible sets, respectively:

solver = SingleConvexSolver(p_start, p_end, f, a0)
solver.solve(N, tol=1e-5)

In this example:

• f is the linear objective vector.
• a0 is the optimizer of the initial problem.
• p_start and p_end are convex functions defining the initial and target feasible sets.
• N specifies the number of homotopy steps.
• tol sets the tolerance for the ODE solver.

Benchmarks

In Benchmarks/sdp_benchmark.py, the homotopy solver is benchmarked against an interior point solver on random semidefinite programs. In Benchmarks/geometricProg_benchmark.py the homotopy method is benchmarked against an interior point solver on random geometric programs with one convexity constraint.

Licence

This project is licensed under the MIT License - see the LICENSE file for details.

References

1. Andreas Klingler and Tim Netzer, Homotopy Methods for Convex Optimization, arXiv:2403.02095 [math.OC], 2024. https://doi.org/10.48550/arXiv.2403.02095