## Can Mathematica solve matrix-based parametric (convex or semidefinite) constrained optimization problems?

I have gone through Mathematica’s documentation and guides on ConvexOptimization, ParametricConvexOptimization and SemidefiniteOptimization. I am also running the latest version of Mathematica.

The kind of matrix-based, parametric, constrained optimization problems I want to solve is this:

$$$$\min_{X_j, \, L_{jk}} \text{Tr}(A L) \ \text{such that, } X_j \text{ and } L_{jk} \text{ are } 4\times4 \text{ Hermitian matrices} \ G_k \cdot X_j = \delta_{j k}\ L:=\begin{bmatrix}L_{11} &L_{12} &L_{13} \ L_{12} &L_{22} &L_{23} \ L_{13} &L_{23} &L_{33}\end{bmatrix} \succeq \begin{bmatrix} X_1 \ X_2 \ X_3 \end{bmatrix}\begin{bmatrix}X_1 &X_2 &X_3\end{bmatrix}$$$$ where the variables to be optimized over are $$X_j$$ and $$L_{jk}$$ ($$j$$ and $$k$$ run from 1 to 3), which are themselves matrices! The matrices $$G_k$$ and $$A$$ depend on some parameter $$\alpha$$ (and satisfy additional properties).

I have been able to run this kind of optimization in MATLAB, and also a much simpler version of this in Mathematica, where $$j, k=1$$ and the parameter value is fixed, using,

ConvexOptimization[   Tr[\[Rho]0 .      v11], {VectorGreaterEqual[{v11, x1}, "SemidefiniteCone"] &&       Tr[\[Rho]0 . x1] == 0  && Tr[\[Rho]1 . x1] == 1   &&      Element[x1, Matrices[{4, 4}, Complexes, Hermitian]] &&      Element[v11, Matrices[{4, 4}, Complexes, Hermitian]]} , {x1,     v11}]] 

However I simply can not get the full problem to run on Mathematica, using either ConvexOptimization[ ] (at fixed parameter values), ParametricConvexOptimization[ ], SemidefiniteOptimization[ ], or Minimize[ ].

ConvexOptimization[ ] at fixed parameter values for $$j, k = 1, 2$$ shows the warning ConvexOptimization::ctuc: The curvature (convexity or concavity) of the term X1.X2 in the constraint {{L11,L12},{L12,L22}}Underscript[\[VectorGreaterEqual], Subsuperscript[\[ScriptCapitalS], +, \[FilledSquare]]]{{X1.X1,X1.X2},{X1.X2,X2.X2}} could not be determined.

Minimize[ ] shows the error Minimize::vecin: Unable to resolve vector inequalities ...

And ParametricConvexOptimization[ ] and SemidefiniteOptimization[ ] simply return the input as output.

Has anyone got some experience with running such matrix-based optimizations in Mathematica? Thanks for your help.

EDIT 1: For the two-dimensional case ($$j, k=1, 2$$) I tried (with $$A$$ the identity matrix, and at fixed parameter value):

ConvexOptimization[  Tr[Tr[ArrayFlatten[{{L11, L12}, {L12,        L22}}]]], {VectorGreaterEqual[{ArrayFlatten[{{L11, L12}, {L12,          L22}}], ArrayFlatten[{{X1 . X1, X1 . X2}, {X1 . X2,          X2 . X2}}]}, "SemidefiniteCone"] &&  Tr[\[Rho]0 . X1] == 0  &&     Tr[\[Rho]0 . X2] == 0 && Tr[\[Rho]1 . X1] == 1  &&     Tr[\[Rho]1 . X2] == 0  && Tr[\[Rho]2 . X1] == 0  &&     Tr[\[Rho]2 . X2] == 1  &&     Element[X1, Matrices[{4, 4}, Complexes, Hermitian]] &&     Element[X2, Matrices[{4, 4}, Complexes, Hermitian]] &&     Element[L11, Matrices[{4, 4}, Complexes, Hermitian]] &&     Element[L12, Matrices[{4, 4}, Complexes, Hermitian]]  &&     Element[L22, Matrices[{4, 4}, Complexes, Hermitian]] }, {X1, X2,    L11, L12, L22}] 

and for the three-dimensional case ($$j, k = 1, 2, 3$$) with variable parameter value and $$A$$ the identity matrix, I tried

ParametricConvexOptimization[  Tr[Tr[ArrayFlatten[{{L11, L12, L13}, {L12, L22, L23}, {L13, L23,        L33}}]]], {VectorGreaterEqual[{ArrayFlatten[{{L11, L12,         L13}, {L12, L22, L23}, {L13, L23, L33}}],      ArrayFlatten[{{X1}, {X2}, {X3}}] .       Transpose[ArrayFlatten[{{X1}, {X2}, {X3}}]]},     "SemidefiniteCone"],  Tr[\[Rho]0 . X1] == 0 ,    Tr[\[Rho]0 . X2] == 0  , Tr[\[Rho]0 . X3] == 0 ,    Tr[\[Rho]1 . X1] == 1 , Tr[\[Rho]1 . X2] == 0  ,    Tr[\[Rho]1 . X3] == 0  , Tr[\[Rho]2 . X1] == 0 ,    Tr[\[Rho]2 . X2] == 1  , Tr[\[Rho]2 . X3] == 0 ,    Tr[\[Rho]3 . X1] == 0 , Tr[\[Rho]3 . X2] == 0  ,    Tr[\[Rho]3 . X3] == 1 }, {Element[X1,     Matrices[{4, 4}, Complexes, Hermitian]],    Element[X2, Matrices[{4, 4}, Complexes, Hermitian]],    Element[X3, Matrices[{4, 4}, Complexes, Hermitian]],    Element[L11, Matrices[{4, 4}, Complexes, Hermitian]],    Element[L12, Matrices[{4, 4}, Complexes, Hermitian]],    Element[L13, Matrices[{4, 4}, Complexes, Hermitian]],    Element[L22, Matrices[{4, 4}, Complexes, Hermitian]],    Element[L23, Matrices[{4, 4}, Complexes, Hermitian]],    Element[L33, Matrices[{4, 4}, Complexes, Hermitian]]}, {\[Alpha]}] 

Here, the $$\rho_{k}$$ matrices are the $$G_k$$ matrices.

## Why use Convex Polygons and not Concave ones in path-finding?

I read in Unity’s path-finding documentation that they use convex polygons because there won’t be any ‘obstruction’ between 2 points. Then they add their vertices as nodes along with starting and ending points and traverse them using A* algorithm to reach the required destination.

However, I do not understand what they mean by "no obstruction between 2 points". I tried to check the differences between concave and convex polygons but only the angle differences come up (in convex the interior angles must be less than 180 degrees)

## Convex hull on set of squares

Imagine a set of two to six squares within 3D-space. The goal is to generate a convex hull around these squares as efficiently as possible.

The following constraints are known:

• Each of the two to six squares consists out of 4 vertices (a vertex being a 3D-vector).
• Each vertex will be part of the convex hull (none of them will be on the "inside").
• During the creation of the convex hull vertices may not be connected to other vertices from within the same square (otherwise the squares would "degenerate").

Is there an especially fast/efficient way to create a convex hull for this very specific geometry?

## Complexity of find histogram bins vs convex hull

For a list of n 2d points, finding the convex hull vertex takes O(n log(n)) time. And O(n) time if it’s sorted lexicon order.

Meanwhile What’s the complexity of finding the histogram bin edges of k bins on both axis ?

Which one is faster ?

## Pack Paths [Concave and Convex]

I would like to design an algorithm to pack closed paths into a rectangle. An example of one of these paths is below:

The rectangle will have a fixed width, but the height will expand to accommodate the paths.

A Simple Approach I Already Tried:

Calculate the smallest rectangle that inscribes the path. (Results were later improved by rotating the path until its width was as small as possible). Pack the paths left to right, and if the remaining width is too small, expand the height and pack on the next row. This approach, however, loses optimizations with concavity. I want optimizations like this to be made:

But with the current approach I get this:

What type of algorithms can be used to optimize both concave and convex shape packing?

## Concentric convex hulls

Given N points in a 2D plane, if we start at a given point and start including points in a set ordered by their distance from the starting point. After including every point, we check if there is a convex hull possible, we move all these points to a visited set and continue. Every time we determine a convex hull, we only move the points to the visited set if the so constructed convex hull contains all the points from the visited set.
How can we do count such convex hulls in as efficient manner as possible?

## Convex Hull of Unit Circles

(Posted this also on Math StackExchange but I’m not sure if it belong there or here).

I know that if we’re trying to get the convex hull of unit circles, we can simply shrink the circles down to their centers and consider the convex hull of their centers, but I’m trying to prove some intermediate steps towards that.

a) Show that boundary of the convex hull consists of only straight line segments and parts of circles.

b) Show that each circle an appear at most once in the boundary of the convex hull.

(This is from de Berg’s Computational Geometry book.)

I sort of have an intuition of why these are true, but my problem is that whenever I try to come up with a solution, I end up considering lots of cases, and I feel like it’s not rigorous or elegant enough because of so many cases. Is there a neat way to prove these?

(Note: I know that this has been posted before in https://math.stackexchange.com/questions/122867/convex-hull-algorithms, but I’m not satisfied with the answers there, and I’m trying to go for something more rigorous.)

## Find vertices of a convex polytope, constrained by hyperplanes

I am looking for a algorithm that returns the vertices of a polytope if provided with the set of hyperplanes that confine it.

In my special case the polytope is construced by the following constrains on $$\mathbb{R}^d$$

• $$\left\| x \right\|$$ = 1, $$x \in \mathbb{R}^d$$
• $$0 , where $$x_i$$ represents the i-th component of $$x$$

This always generates a convex polytope which is confined by hyperplanes, if I am not mistaken. I would like to have an algorithm that returns a set of points P that are the vertices of the polytope if provided with the set of $$a_i$$‘s and $$b_i$$‘s

There is a special case where there exists no $$x$$ that satifies this condition. Idealy this would be picked up on.

Thank you!

## Convex quadratic approximation to binary linear programming

Munapo (2016, American Journal of Operations Research, http://dx.doi.org/10.4236/ajor.2016.61001) purports to have a proof that binary linear programming is solvable in polynomial time, and hence that P=NP.

Unsurprisingly, it does not really show this.

Its results are based on a convex quadratic approximation to the problem with a penalty term whose weight $$\mathcal{l}$$ needs to be infinitely large for the approximation to recover the true problem.

My questions are the following:

1. Is this an approximation which already existed in the literature (I rather expect it did)?
2. Is this approximation useful in practice? For example, could one solve a mixed integer linear programming problem by homotopy continuation, gradually increasing the weight $$\mathcal{l}$$?

Note: After writing this question I discovered this related question: Time Complexity of Binary Linear Programming . The related question considers a specific binary linear programming problem, but mentions the paper above.

## Generate triangular surface mesh of convex hull spanned by 8 points in 3D-Space

I am looking for a numerically efficient algorithm to get a triangular surface mesh of the convex hull given by 8 points in three-dimensional space.

For context, the use case is the following:

I have a numerical Simulation calculating the time evolution of a field with three components on a lattice. Say we have lattice coordinates $$(i,j,k)$$, then every lattice point $$(i,j,k)$$ has a field vector $$(\phi_1, \phi_2 , \phi_3)$$ attached.

For relevant physics, I need to now take unit cells on my lattice, so the 8 corners of a little cube of my lattice. I take the field vectors $$(\phi_1, \phi_2 , \phi_3)$$ of every corner of my unit cell and then interpret their convex hull as a closed volume in $$\phi$$-space, with $$\phi$$-space being the 3D space given by the $$(\phi_1,\phi_2,\phi_3)$$ coordinates.

I am now interested if the volume spanned by these 8 points in $$\phi$$-space does the following things:

1. If it contains the origin, $$(0 ,0 ,0 )$$

2. If a Ray traveling from the origin in $$(-1,0,0)$$-direction pierces my given volume

The idea to evaluate both 1.) and 2.) at the same time is to decompose the surface of the convex hull into triangles. For a triangle in 3-Dimensional space, it is easy to evaluate whether it is pierced by my given Ray in $$(-1,0,0)$$ direction. I can then count how many triangles are pierced. If exactly two triangles are pierced (because of convexity), I know the cell satisfies condition 2.). If exactly one triangle is pierced, I know the origin has to lie inside my volume, that is condition 1.) is satisfied. Lastly, when no triangles are pierced, none of the above apply.

I think this approach is probably relatively fast. Speed is critical, because I have approximately $$10^6 … 10^9$$ cells to evaluate per sweep across my lattice.

I’d be interested in any other approaches as well, though.

Update: So, I think possibly a 3D-Gift-Wrapping algorithm would atleast produce the required result, because it creates the convex hull by consecutively finding triangles on the surface? I will have to try that out tomorrow.

Can I do better than that in terms of efficiency?