Wikipedia:Reference desk/Archives/Mathematics/2014 May 28

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 28

Smooth approximation of a hypercube

I'm working on an optimization problem where the solution must fall on the unit hypercube. Is there a simple smooth approximation to this constraint? It must be differentiable, and being twice differentiable would give me more flexibility in solving the problem. The simplest solution I can think of is to use a sphere, then project it to the nearest face and use gradient descent along that face to fine-tune the result. However, if there is a reasonably simple approximation that is more cube-shaped it may get me a good enough result faster because it doesn't cut off the corners of the cube as much. Katie R (talk) 12:20, 28 May 2014 (UTC)

You could use a $p$-norm for large $p$. The unit sphere is $\sum _{i=1}^{n}x_{i}^{2}=1$. If you change that to $\sum _{i=1}^{n}x_{i}^{p}=1$, you'll get a better approximation to the hypercube as $p$ increases; indeed, the limit is the unit hypercube.--80.109.80.78 (talk) 12:35, 28 May 2014 (UTC)

[ec] $\sum _{i=1}^{n}|x_{i}|^{\alpha }=1$ approximates the surface of the cube $\forall i(-1\leq x_{i}\leq 1)$. With higher $\alpha$ the approximation is better but it's less smooth. -- Meni Rosenfeld (talk) 12:37, 28 May 2014 (UTC)

Thanks! That sounds perfect - quick to evaluate, simple derivatives, and it will be easy to work with analytically when I start working on analyzing the convergence of the algorithm. Katie R (talk) 13:08, 28 May 2014 (UTC)

You will have to restrict α to even integers to keep it analytic. —Quondum 17:20, 28 May 2014 (UTC)

The points on the surface of the unit hypercube satify the equation

$\prod _{i}(x_{i}^{2}-1)=0$

The points on the surface of the unit hypersphere satify the equation

$(\sum _{i}x_{i}^{2})-1=0$

So the equation

$(1-p)\prod _{i}(x_{i}^{2}-1)+p((\sum _{i}x_{i}^{2})-1)=0$

is a hypercube for p=0 and a hypersphere for p=1, and for 0<p<1 it is a surface in between. Bo Jacoby (talk) 22:17, 28 May 2014 (UTC).

That's not correct. There are many more points satisfying the first equation than just the surface of the hypercube. It seems to me the last equation is only satisfied by $x=0$ or $y=0$. -- Meni Rosenfeld (talk) 22:35, 28 May 2014 (UTC)

Right - as long as one element has an absolute value of 1, the others are unbounded and can fall anywhere on the plane that face defines. I'm very happy with the unit ball in a p-norm solution. It's very simple, and so are the Jacobian and Hessian, which is important because I may need to evaluate it several thousand times a second. It's also convex which makes it useful for global optimization. Katie R (talk) 02:31, 29 May 2014 (UTC)

We agree that the points on the surface of the unit hypersphere do satify the equation (for p=0) and that inside points do not. It is not a problem that some outside points do. Choose 0≤x₂²≤1 , . . . , 0≤x_n²≤1 and compute x₁² from the linear equation.

$(1-p)(1-x_{1}^{2})\prod _{i=2}^{n}(1-x_{i}^{2})+p(1-x_{1}^{2}-\sum _{i=2}^{n}x_{i}^{2})=0$

It is simpler than the p-norm solution for p>n. Bo Jacoby (talk) 05:35, 29 May 2014 (UTC).

It does matter that points outside the cube satisfy the equation, when you're trying to create a new equation with a convex combination of the two equations. Did you actually try to plot your last equation? I did in the 2D case and got gibberish. And as I said, it is only satisfied for $x=0$ or $y=0$ (fixed above) when $0<p<1$. -- Meni Rosenfeld (talk) 11:41, 29 May 2014 (UTC)

Yes I did actually plot my last equation by this J program:

  'dot; pensize 4' plot(,j.)(,-)(,+)j./%:(,:-.%[:-.0.9&*)?100#0

Explanation: (?100#0) creates 100 random numbers 0≤x²≤1. (,:-.%[:-.0.9&*) appends the corresponding y² values for p=0.1. (-.x) is 1-x. (%) is division. (%:) is square root. (j./x,:y) creates x+iy. (,+) appends x-iy. (,-) appends -(x+iy). (,j.) appends i(x+iy). The program displays 800 dots showing a square with round corners.

Probably you committed an elementary error. Bo Jacoby (talk) 22:10, 29 May 2014 (UTC).

Ok, one issue is that in your original comment you had a sign error. This was corrected in your second comment and gives a more reasonable shape. However, the point remains that there are also points outside the cube that satisfy the equation. -- Meni Rosenfeld (talk) 09:11, 30 May 2014 (UTC)

The equi-p-norm shape is called a superellipse or superellipsoid by the way (or more specifically, a squircle). --catslash (talk) 12:39, 30 May 2014 (UTC)

Looks like squircle is the special case where p=4. Too bad, because I was hoping my high-dimensional version could be called a squircloid. :-P Katie R (talk) 15:54, 30 May 2014 (UTC)

Using only one branch of, say, a hyperbola is not prohibited. It is interesting how reluctance prevented Meni Rosenfeld from catching the idea. Bo Jacoby (talk) 11:32, 1 June 2014 (UTC).

Prohibited for whom? The OP has a specific application. If he tries your equation to test for his required condition, he may end up with false positives. How much of a problem it really is depends on the application. -- Meni Rosenfeld (talk) 20:20, 1 June 2014 (UTC)

My application is to use the function as a constraint that is a good approximation to a hypercube. Using an approximation that requires a hypercube constraint doesn't get me anywhere. Katie R (talk) 12:17, 2 June 2014 (UTC)

The OP gets a parametized family of hyper-surfaces. p=0 gives a hyper-sphere. p=1 gives a hyper-cube. Values in between give hyper-surfaces in between. The hyper-surfaces are infinitely differentiable for p<1. The hyper-surfaces are algebraic of order 4. The solution is straight-forward and not dangerous at all. Bo Jacoby (talk) 21:25, 2 June 2014 (UTC).

Algebra brain-fade.

I'm having trouble with a bit of algebra:

If:

 A = B x

 x = ???

(B is in the range 0..1 and x>1 if that helps at all). 65.111.112.94 (talk) 20:54, 28 May 2014 (UTC)

$x=\log _{B}A={\frac {\log A}{\log B}}$. See Logarithm. -- Meni Rosenfeld (talk) 21:13, 28 May 2014 (UTC)

Logarithm turns multiplications into additions and exponential into multiplications.

So

A = B ^x

becomes

Log(A) = Log(B ^x )

Log(A) = Log(B) * x

So you can easily solve for x. 202.177.218.59 (talk) 01:05, 30 May 2014 (UTC)