Computing Weighted Analytic Center for Linear Matrix Inequalities Using Infeasible Newton’s Method

We study the problem of computing weighted analytic center for system of linear matrix inequality constraints. The problem can be solved using the Standard Newton’s method. However, this approach requires that a starting point in the interior point of the feasible region be given or a Phase I problem be solved. We address the problem … Read more

Using the analytic center in the feasibility pump

The feasibility pump (FP) [5,7] has proved to be a successful heuristic for ﬁnding feasible solutions of mixed integer linear problems (MILPs). FP was improved in [1] for ﬁnding better quality solutions. Brieﬂy, FP alternates between two sequences of points: one of feasible so- lutions for the relaxed problem (but not integer), and another of … Read more

On the Volumetric Path

We consider the logarithmic and the volumetric barrier functions used in interior point methods. In the case of the logarithmic barrier function, the analytic center of a level set is the point at which the central path intersects that level set. We prove that this also holds for the volumetric path. For the central path, … Read more

A Path to the Arrow-Debreu Competitive Market Equilibrium

We present polynomial-time interior-point algorithms for solving the Fisher and Arrow-Debreu competitive market equilibrium problems with linear utilities and $n$ players. Both of them have the arithmetic operation complexity bound of $O(n^4\log(1/\epsilon))$ for computing an $\epsilon$-equilibrium solution. If the problem data are rational numbers and their bit-length is $L$, then the bound to generate an … Read more

An analytic center cutting plane approach for conic programming

We analyze the problem of finding a point strictly interior to a bounded, fully dimensional set from a finite dimensional Hilbert space. We generalize the results obtained for the LP, SDP and SOCP cases. The cuts added by our algorithm are central and conic. In our analysis, we find an upper bound for the number … Read more

A matrix generation approach for eigenvalue optimization

We study the extension of a column generation technique to eigenvalue optimization. In our approach we utilize the method of analytic center to obtain the query points at each iteration. A restricted master problem in the primal space is formed corresponding to the relaxed dual problem. At each step of the algorithm, an oracle is … Read more

An interior point cutting plane method for convex feasibility problem with second-order cone inequalities

Convex feasibility problem in general, is a problem of finding a point in a convex set contains a full dimensional ball and is contained in a compact convex set. We assume that the outer set is described by second-order cone inequalities and propose an analytic center cutting plane technique to solve this problem. We discuss … Read more

Using selective orthonormalization to update the analytic center after the addition of multiple cuts

We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope in Euclidean n-space. This is an important issue that arises at every `stage’ in a cutting plane algorithm. If q cuts are to be added, with q no larger than n, … Read more

Characterization of the limit point of the central path in semidefinite programming

In linear programming, the central path is known to converge to the analytic center of the set of optimal solutions. Recently, it has been shown that this is not necessarily true for linear semidefinite programming in the absence of strict complementarity. The present paper deals with the formulation of a convex problem whose solution defines … Read more

Recovery of the Analytic Center in Perturbed Quadratic Regions and Applications

We present results to recover an approximate analytic center when a sectional convex quadratic set is perturbed by a finite number of new quadratic inequalities. This kind of restarting may play an important role in some interior-point algorithms that successively refine the region where is the solution of the original problem. Citation Technical Repor ES … Read more