sergeivolodin / caqm

CAQM: Convexity Analysis of Quadratic Maps arXiv:1810.00896

CAQM: Convexity Analysis of Quadratic Maps

Code for various tasks for quadratic maps.

See the paper Geometry of quadratic maps via convex relaxation, Anatoly Dymarsky, Elena Gryazina, Sergei Volodin, Boris Polyak, 2018, arXiv:1810.00896

Prerequisites

• MATLAB (tested with 9.6-2019a) with Parallel Computing toolbox
• CVX. Tested with Version 2.1, Build 1127 (95903bf)
• Tested on Linux (Debian 10.1) amd64 kernel 4.19.0-6-amd64, Java version 1.8.0_181
• Mathematica 12 for semi-analytical tests and figures 4, 7

Installing

See doc/readme.pdf file

Testing

To test separate functions run in MATLAB from root directory:

>> cd tests
>> runtests('testFunctions')

Result should be like the following:

Totals:
   15 Passed, 0 Failed, 0 Incomplete.
   45.7854 seconds testing time.

Moreover, see tests/testCAQM.m as an example of library usage.

>> cd tests
>> testCAQM

Should give output ending with TEST PASSED. A Youtube video demonstrates how the test normally performs.

For more information see doc/readme.pdf

License

See LICENSE.txt

Files and folders

• / -- main functions (see doc/readme.pdf)
• library/ -- supplementary functions (see doc/library.pdf)
• doc/ -- documentation
• examples/ contains the code which reproduces the results from the Section 7. Examples from the article, both using our library (MATLAB) and using semi-analytical methods (Mathematica)
• examples/figures/ -- MATLAB code for drawing figures from the article:
  • example05_c_minus.m reproduces Fig. 5a
  • example05_c_dot_z_c_t_plot.m reproduces Fig. 5b
  • example06_c_minus.m reproduces Fig. 6a
  • example06_c_dot_z_c_t_plot.m reproduces Fig. 6b
  • homogeneous_procedure_H.m reproduces Fig. 8
• examples/ also contains Mathematica notebooks for reproducing Figures 4 and 7: article_example01_fig4.nb and article_example10_fig7.nb
• examples/maps -- sample quadratic maps
• tests/ -- code for testing the setup

Parameters

The library contains several numerical constants the purpose of which is described on the second page of the supplementary functions document doc/library.pdf.

Further reading

Refer to the documentation in doc/readme.pdf and the article

Copyright (c) 2015-2019 Anatoly Dymarsky, Elena Gryazina, Sergei Volodin, Boris Polyak

caqm's Issues

Make k=1000 default

Make example visible in help

After typing help func_name, the example is not visible for some reason

Choose d rectangular to c_+ in get_c_minus.m

Will speed up the computation

Case Rg=n-2 for R map

1. Found a map for which Rg=n-2 means that the C_- curve ends
2. Can have other cases?

Analytical solution: derive eigenvalues as functions of theta, phi in Mathematica. See if different families of eigenvalues touch or intersect. Also can check if curve lambda_1=lambda_2 intersects with C_-

Add examples with other dimensionality

Random examples in:

1. R⁵ → R⁵ (non-homogeneous)
2. C³ → R⁵ (non-homogeneous)
3. C³ → R⁶ (non-homogeneous)
4. R⁴ → R⁴ (homogeneous)

Possible ways of making the description of the map shorter: low precision or integer matrices

1. Check if algorithms do not fail
2. Try finding C_{_}
3. Try finding z_max

4 Homogeneous example R⁴ → R⁴

A(:, :, 1) = [0 1 0 0; 1 0 0 0; 0 0 0 1; 0 0 1 0];
A(:, :, 2) = [0 0 1 0; 0 2 0 1; 1 0 2 0; 0 1 0 0];
A(:, :, 3) = [0 0 0 1; 0 -1 1 0; 0 1 1 0; 1 0 0 0];
A(:, :, 4) = eye(4);
b = zeros(4);
rng(10);
c_minus = get_c_minus(A, b, [0, 0, 0, 1]', 10);
rng(10);
is_nonconvex = nonconvexity_certificate(A, b, [0, 0, 0, 1]', 10);

display(is_nonconvex);
display(c_minus);

Add homogeneous case analysis to the draft

• New sufficient condition for C_-: see last pages of notes_Volodin.pdf
• New definition of C_- for case b=0

Better optimizer for z(c)

Since in C case a constraint function minimization is used as projection, it can also be used in R case.

Make the projection image more visually appealing

• Make fonts of same size
• Move C_- title to the left

c_minus_continuum.zip

Choose z uniformly from [0, z_max_guess]

Will increase the probability of finding c

Handle complex case in is_nonconvex.m

Add variable arguments