Diagnosis and Resolution of Infeasibility in the Constraint Method for Solving Multi Objective Linear Programming Problems

In this paper we discuss about infeasibility diagnosis and infeasibility resolution, when the constraint method is used for solving multi objective linear programming problems. We propose an algorithm for resolution of infeasibility, which is a combination of interactive, weighting and constraint methods.Numerical examples are provided to illustrate the techniques developed.

A Combined Homotopy Infeasible Interior-Point Method for Convex Nonlinear Programming

In this paper, on the basis of the logarithmic barrier function and KKT conditions, we propose a combined homotopy infeasible interior-point method （CHIIP） for convex nonlinear programming problems. For any convex nonlinear programming, without strict convexity for the logarithmic barrier function, we get different solutions of the convex programming in different cases by CHIIP method.

Two new predictor-corrector algorithms for second-order cone programming

Based on the ideas of infeasible interior-point methods and predictor-corrector algorithms, two interior-point predictor-corrector algorithms for the second-order cone programming （SOCP） are presented. The two algorithms use the Newton direction and the Euler direction as the predictor directions, respectively. The corrector directions belong to the category of the Alizadeh-Haeberly-Overton （AHO） directions. These algorithms are suitable to the cases of feasible and infeasible interior iterative points. A simpler neighborhood of the central path for the SOCP is proposed, which is the pivotal difference from other interior-point predictor-corrector algorithms. Under some assumptions, the algorithms possess the global, linear, and quadratic convergence. The complexity bound O（rln（εo/ε）） is obtained, where r denotes the number of the second-order cones in the SOCP problem. The numerical results show that the proposed algorithms are effective.

基于全牛顿求解线性互补问题的一种新的不可行内点算法(英文)

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear complementarity problem,which is an extension of Roos about linear optimization. The main iteration of the algorithm consists of a feasibility step and several centrality steps. At last,we prove that the algorithm has O(nlog n/ε) polynomial complexity,which coincides with the best known one for the infeasible interior-point algorithm at present.

A NEW FRAMEWORK OF PRIMAL-DUAL INFEASIBLE INTERIOR-POINT METHOD FOR LINEAR PROGRAMMING

On the basis of the formulations of the logarithmic barrier function and the idea of following the path of minimizers for the logarithmic barrier family of problems the so called "centralpath" for linear programming, we propose a new framework of primal-dual infeasible interiorpoint method for linear programming problems. Without the strict convexity of the logarithmic barrier function, we get the following results: (a) if the homotopy parameterμcan not reach to zero,then the feasible set of these programming problems is empty; (b) if the strictly feasible set is nonempty and the solution set is bounded, then for any initial point x, we can obtain a solution of the problems by this method; (c) if the strictly feasible set is nonempty and the solution set is unbounded, then for any initial point x, we can obtain a (?)-solution; and(d) if the strictly feasible set is nonempty and the solution set is empty, then we can get the curve x(μ), which towards to the generalized solutions.

A Modified Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function

This paper proposes a new full Nesterov-Todd(NT) step infeasible interior-point algorithm for semidefinite programming. Our algorithm uses a specific kernel function, which is adopted by Liu and Sun, to deduce the feasibility step. By using the step, it is remarkable that in each iteration of the algorithm it needs only one full-NT step, and can obtain an iterate approximate to the central path. Moreover, it is proved that the iterative bound corresponds with the known optimal one for semidefinite optimization problems.

A Primal-Dual Infeasible-Interior-Point Algorithm for Multiple Objective Linear Programming Problems

A primal-dual infeasible interior point algorithm for multiple objective linear programming (MOLP) problems was presented. In contrast to the current MOLP algorithm. moving through the interior of polytope but not confining the iterates within the feasible region in our proposed algorithm result in a solution approach that is quite different and less sensitive to problem size, so providing the potential to dramatically improve the practical computation effectiveness.

A New Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function

In this paper, we propose a new infeasible interior-point algorithm with full NesterovTodd (NT) steps for semidefinite programming (SDP). The main iteration consists of a feasibility step and several centrality steps. We used a specific kernel function to induce the feasibility step. The analysis is more simplified. The iteration bound coincides with the currently best known bound for infeasible interior-point methods.

The convergence properties of infeasible inexact proximal alternating linearized minimization

The proximal alternating linearized minimization(PALM)method suits well for solving blockstructured optimization problems,which are ubiquitous in real applications.In the cases where subproblems do not have closed-form solutions,e.g.,due to complex constraints,infeasible subsolvers are indispensable,giving rise to an infeasible inexact PALM(PALM-I).Numerous efforts have been devoted to analyzing the feasible PALM,while little attention has been paid to the PALM-I.The usage of the PALM-I thus lacks a theoretical guarantee.The essential difficulty of analysis consists in the objective value nonmonotonicity induced by the infeasibility.We study in the present work the convergence properties of the PALM-I.In particular,we construct a surrogate sequence to surmount the nonmonotonicity issue and devise an implementable inexact criterion.Based upon these,we manage to establish the stationarity of any accumulation point,and moreover,show the iterate convergence and the asymptotic convergence rates under the assumption of the Lojasiewicz property.The prominent advantages of the PALM-I on CPU time are illustrated via numerical experiments on problems arising from quantum physics and 3-dimensional anisotropic frictional contact.

Allocating Fixed Costs with Considering the Return to Scale: A DEA Approach

When the allocated fixed cost is treated as the complement of other costs, conventional data envelopment analysis(DEA) researches have ignored the effect of the return to scale(RTS) in fixed cost allocation problems. This paper first demonstrates why the RTS should be considered in fixed cost allocation problems. Then treating the fixed cost as a complementary input, the authors investigate the relationship between the allocated cost and the variable return to scale(VRS) efficiency based on the super BCC DEA model. However, the infeasibility problem may exist in this situation.To deal with it, the authors propose an algorithm. The authors find that the super BCC efficiency is a monotone non-increasing function of the allocated cost. Based on the relationship, the authors finally propose a fixed cost allocation approach in terms of principles as:(i) The fixed cost proportion allocated to inelastic DMUs should be consistent with their consumed cost proportion, and(ii) the same efficiency satisfaction degree to the rest DMUs. The optimal allocation scheme is unique. A numerical example and a real example of allocating fixed costs among 13 subsidiaries are employed to illustrate the proposed approach.

Constructing orthogonal fractional factorial designs with the same confounding structure

ORTHOGONAL arrays (OAs) have important applications to many fields. A lot of OAs and their construction methods have been introduced in the experimental design literature (for example, Box, Hunter and Dey). These OAs are used for an experimenter to choose in practice.

A necessary and sufficient condition of existence of orthogonal arrays debarring some combinations

Orthogonal arrays (OAs) are used in many fields such as industry, agriculture, medi-cine, quality control of products and other scientific experiments. There are a lot of OAsin the existing experimental design literature. But when an experimenter wants to choosean OA in practice, it still often happens tha any existing OA contains someunsuitable factor-level combinations. For example, in a chemical experiment withtemperature and pressure as its two factors, high temperature and high pressure

A New Class of Infeasible InteriorPoint Algorithm for Linear Complementarity Problem

This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O（n log（n /ε））iterations are required for getting ε-solution of the problem at hand,which coincides with the best-known bound for infeasible interior-point algorithms.

A Modified and Simplified Full Nesterov–Todd Step O(N)Infeasible Interior-Point Method for Second-Order Cone Optimization

We present a modified and simplified version of an infeasible interior-point method for second-order cone optimization published in 2013(Zangiabadi et al.in J Optim Theory Appl,2013).In the earlier version,each iteration consisted of one socalled feasibility step and a few centering steps.Here,each iteration consists of only a feasibility step.Thus,the new algorithm improves the number of iterations and the improvement is due to a lemma which gives an upper bound for the proximity after the feasibility step.The complexity result coincides with the best-known iteration bound for infeasible interior-point methods.

A Path-Following Full Newton-Step Infeasible Interior-Point Algorithm for P∗(κ)-HLCPs Based on a Kernel Function

In this paper,we present a path-following infeasible interior-point method for P∗(κ)horizontal linear complementarity problems(P∗(κ)-HLCPs).The algorithm is based on a simple kernel function for finding the search directions and defining the neighborhood of the central path.The algorithm follows the central path related to some perturbations of the original problem,using the so-called feasibility and centering steps,along with only full such steps.Therefore,it has the advantage that the calculation of the step sizes at each iteration is avoided.The complexity result shows that the full-Newton step infeasible interior-point algorithm based on the simple kernel function enjoys the best-known iteration complexity for P∗(κ)-HLCPs.

Primary Structural and Quantitative Analysis of Infeasible Solution to Job shop Scheduling Problem

In this paper, the structure of infeasible solutions to Job Shop Scheduling Problem (JSSP) is quantitatively analyzed, and a necessary and sufficient condition of the deadlock for JSSP is also given. For a simple JSSP with 2 machines and N jobs, a formula for calculating the infeasible solutions is proposed, which shows that the infeasible solution possesses the majority of search space and only those heuristic algorithms which do not produce infeasible solutions are valid.