Analytic Center in Python using Scipy and Numpy

The analytic center for a set of inequalities \phi(x)<0 is the minimizing position of \sum -\ln (-\phi(x)) . In particular it is often used with linear inequalities. It gives a reasonable and easily computable for convex constraint function center of the region. The hessian at that point can give you a reasonable ellipse that approximates the region too (both interior and exterior approximation).

I wrote a program for linear inequalities. It is not particularly robust. First I get a feasible point using the LP solver in scipy. Then I give the appropriate gradients and Hessians to a newton conjugate gradient solver in scipy. It does return a reasonable center, but I had to fiddle with some epsilons to avoid logarithms exploding and to avoid the hessian being so big it overwhelms the gradient. Possibly a couple burn in steps of gradient descent might help, or getting a feasible point that isn’t optimal since the optimal points being on the boundary is a huge problem. If the newton solver comes back with only 1 or 2 iterations, it probably failed.

import numpy as np
import scipy.optimize


# Anaytic Center Finding

def analytic_center_fun(x, A, b):
	q = np.dot(A,x)-b + 1e-8
	val = np.sum(np.log(q)) 
	grad = np.sum((1./q).reshape((-1,1)) * A, axis = 0)
	hess = np.sum( (-1./(q*q)).reshape((-1,1,1))  *  A.reshape((-1,-1,1))   *    A.reshape((-1,1,-1)), axis = 0)
	return val, grad, hess

def analytic_center_hess(A, b):
	def hess_fun(x):
		q = b - np.dot(A,x) + 1e-8
		hess = np.sum( (1./(q*q)).reshape((-1,1,1))  *  np.expand_dims(A, axis=2)   *   np.expand_dims(A, axis=1) , axis = 0)
		return hess
	return hess_fun

def analytic_center_grad(A, b):
	def grad_fun(x):
		q = b - np.dot(A,x) + 1e-8
		grad = np.sum((1./q).reshape((-1,1)) * A, axis = 0)
		return grad
	return grad_fun

def analytic_center_val(A, b):
	def val_fun(x):
		q = b - np.dot(A,x) + 1e-8
		val = - np.sum(np.log(q))
		return val
	return val_fun

def get_feasible(A,b):
	#returns a feasible point for Ax < b
	# need to make the inequalities a little tighter so that the logarithms aren't freaking out
	res = scipy.optimize.linprog(-np.random.random(A.shape[1]),A_ub = A, b_ub = b - 1e-5, method='interior-point')
	if res.success == True:
		return res.x
	else:
		print("failure to find feasible point ", res)
		return "FAIL"

def analytic_center(A,b):
	print("Calulating Center")
	x0 = get_feasible(A,b)
	print(x0)
	#xc = scipy.optimiatzew
	#xc, fopt, fcalls, gcalls, hcalls, warn 
	# Had a problem where the hessian is too big at the boundary. Let it stop there
	# The stopping condition is based on delta x rather than grad?
	# Could maybe do some burn in with a couple gradient steps.
	res = scipy.optimize.fmin_ncg(f = analytic_center_val(A,b), x0 = x0, fprime = analytic_center_grad(A,b), fhess = analytic_center_hess(A,b) )
	xc = res
	print(res)
	print(xc)
	return xc

# Make a convenient box where I know where the cneter will be
A = np.array([[1.0 , 0],
			  [-1.0, 0],
			  [0   , 1.0],
			  [0.  , -1.0]])
b = np.array([20,10,1,0])

#analytic_center(np.random.random((100,10)), np.random.random(100))
print(analytic_center_val(A,b)([0.5,0.5]))
print(analytic_center_grad(A,b)([0.5,0.5]))
print(analytic_center_hess(A,b)([0.5,0.5]))

print(analytic_center_val(A,b)([0,0]))
print(analytic_center_grad(A,b)([0,0]))
print(analytic_center_hess(A,b)([0,0]))
sol = analytic_center(A,b)

print(analytic_center_val(A,b)(sol))
print(analytic_center_grad(A,b)(sol))
print(analytic_center_hess(A,b)(sol))

 

Leave a Reply

Your email address will not be published. Required fields are marked *