Giter VIP home page Giter VIP logo

interrelax's Introduction

InterRelax

InterRelax is a Julia package of solving polynomial optimization problem on the nonnegative orthant:

f* := inf_{x in R^n} {f(x) : x >= 0, gi(x) >= 0, hj(x) = 0}.

We provide a hierarchy of semidefinite relaxations based on Polya's and Handelman's Positivstellensatz for solving this problem. It has the following advantages:

  • The maximal matrix size of each semidefinite relaxation can be arbitrarily chosen. Accordingly, each semidefinite relaxation of maximal matrix size relatively small can be solved efficiently by using interior point methods (Mosek, SDPT3, ...).
  • We guarantee the convergence of the sequence of values returned by this hierarchy to f* under some mild condition. Moreover, the rate of convergence is at least O(eps^-c).

Required softwares

InterRelax has been implemented on a desktop compute with the following softwares:

Before installing InterRelax, you should install TSSOS and PolyPowerModels with the following commands:

Pkg> add https://github.com/wangjie212/TSSOS
Pkg> add https://github.com/tweisser/PolyPowerModels.git

Installation

  • To use InterRelax in Julia, run
Pkg> add https://github.com/maihoanganh/InterRelax.git

Usage

The following examples briefly guide to use InterRelax:

Polynomial optimization on the nonnegative orthant

Consider the following optimization polynomial problem:

using DynamicPolynomials

@polyvar x[1:2] # nonnegative variables

f=x[1]^2+0.5*x[1]*x[2]-0.25*x[2]^2+0.75*x[1]-0.3*x[2] # the objective polynomial to minimize

g=[1.0-sum(x.^2)] # the inequality constraints
h=[(x[1]-1.0)*x[2]] # the equality constraints

k=1 # relaxation order
s=3 # sparsity order

using InterRelax

# get information from the input data f,gi,hj
n,m,l,lmon_g,supp_g,coe_g,lmon_h,supp_h,coe_h,lmon_f,supp_f,coe_f,dg,dh=InterRelax.get_info(x,f,g,h,sparse=false);

# get an approximate optimal value and an approximate optimal solution of the polynomial optimization problem
    opt_val,opt_sol=InterRelax.RelaxDense(n,m,l,
                                          lmon_g,supp_g,coe_g, # information of the inequality constraints
                                          lmon_h,supp_h,coe_h, # information of the equality constraints
                                          lmon_f,supp_f,coe_f, # information of the objective polynomial
                                          dg,dh,k,s,
                                          solver="Mosek", # solver for the semidefinite program
                                          comp_opt_sol=true) # to get an approximate optimal solution

See other examples from .ipynb files in the link.

References

For more details, please refer to:

N. H. A. Mai, V. Magron, J.-B. Lasserre and K-C Toh. Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant. 2022. Forthcoming.

To get the paper's benchmarks, download the zip file in this link and unzip the file.

The following codes are to run the paper's benchmarks in Julia:

using InterRelax

data="/home/mpc-linux-01/dataPOP2" # path of data 
#The path needs to be changed on the user's computer

InterRelax.test()
InterRelax.test_AMGM() #Table 1
InterRelax.test_compare_with_sign_sym() #Table 2
InterRelax.test_dense_POP_arbcons(data) #Table 4
InterRelax.test_compute_stability_number_of_graph(data) #Table 5
InterRelax.test_compute_stability_number_of_graph_ball_constr(data) #Table 6
InterRelax.test_MAXCUT(data) #Table 7
InterRelax.test_PMSV(data) #Table 8
InterRelax.test_compute_stability_number_of_graph_random(data) #Table 9
InterRelax.test_deciding_copositivity(data) #Table 10
InterRelax.test_deciding_nonegativity(data) #Table 11
InterRelax.test_dense_POP_binary_constr_random(data) #Table 12
InterRelax.test_CS_POP_arbcons(data) #Tables 13
InterRelax.test_CertifyNNHousing(data) #Table 15

interrelax's People

Contributors

maihoanganh avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.