In this section we introduce the second order problem (SOCP) and quote some basic definitions for the primal-dual interior point approach. The next section contains as on of the main results a proof of the existence of the step length for the long-step method. A number of applications and in each case their reformulation as SOCP is presented in section 3. Subsequently, the various algorithms we have implemented are given in detail and compared on a test set derived from the application problems. We conclude with a summary in the last section.

Second-order cone programming addresses the problem of minimizing a linear objective function over the intersection of an affine set and the direct product of quadratic cones.

where K is a closed convex cone. In addition to (1-1), we suppose is a real matrix and of full rank. Subsequently, the dual problem is

The definition of the quadratic cone is the following:

- quadratic cone
- rotated quadratic cone

Here, is a identity matrix if The existence of the linear transformation not only extends the problem to rotated quadratic cones but also helps to apply the convergence theorem for to . Next, we partition according to the cones, i.e.,

where , and . In order to solve (1-4) with the complementarity conditions, the following definitions are necessary,

- : , and ,
- : , and ,
- : , and , where is in (1-3).

where the centering parameter , the duality measure is

and

In the
original infeasible interior point method, the residuals only
appear in equations after applying Newton's method. It is easy to
verify that the ratio between the new and old residual is
, where is the step length. It is faster than
the rate at which the complementarity gap decreases. This central
path gives the same rate for infeasibility and the complementary
gap. In experiments, we see the latter version needs less
iterations than the previous one.
The well-definedness of (1-5) is not guaranteed. One way to assure that the search direction is well-defined is applying scaling schemes before using Newton's method, then scaling back to the original space. Next, we give the definition of scaling matrices,[1].

- is a symmetric positive definite matrix, and

and

where
The NT direction was proposed by Nesterov and Todd [10]. The paper [10] also shows that the primal-dual IPM maintains its efficiency when the nonnegative constraints in LP are replaced by the homogeneous self-dual cone. More recently, Tsuchiya [13] showed that the long-step algorithm for SOCP using NT direction has log, iteration-complexity, where is the number of cones, which is the best result among several scaling schemes.

The NT direction defines , and , such that

To simplify notations through out this paper, we define the following symbols.