It is well known that a large neighborhood interior point algorithm for linear optimization performs much better in implementation than its small neighborhood counterparts. One of the key elements of interior point algorithms is how to update the barrier parameter. The main goal of this paper is to introduce an "adaptive'' long step interior-point algorithm in a large neighborhood of central path using the classical logarithmic barrier function having O(nlog(x0)Ts0ϵ) iteration complexity analogous to the classical long step algorithms. Preliminary encouraging numerical results are reported.
In this paper, the robust counterpart of the linear fractional programming problem under linear inequality constraints with the interval and ellipsoidal uncertainty sets is studied. It is shown that the robust counterpart under interval uncertainty is equivalent to a larger linear fractional program, however under ellipsoidal uncertainty it is equivalent to a linear fractional program with both linear and second order cone constraints. In addition, for each case we have studied the dual problems associated with the robust counterparts. It is shown that in both cases, either interval or ellipsoidal uncertainty, the dual of robust counterpart is equal to the optimistic counterpart of dual problem.
In this paper, we have studied the problem of minimizing the ratio of two indefinite quadratic functions subject to a strictly convex quadratic constraint. First utilizing the relationship between fractional and parametric programming problems due to Dinkelbach, we reformulate the fractional problem as a univariate equation. To find the root of the univariate equation, the generalized Newton method is utilized that requires solving a nonconvex quadratic optimization problem at each iteration. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that this problem can be solved by solving a convex univariate minimization problem. Attainment of the global optimality conditions is discussed. Our preliminary numerical experiments on several randomly generated test problems show that, the new approach is much faster in finding the global optimal solution than the known semidefinite relaxation approach, especially when solving large scale problems.