A smoothing projected Newton-type algorithm for semi-infinite programming

This paper presents a smoothing projected Newton-type method for solving the semi-infinite programming (SIP) problem. We first reformulate the KKT system of the SIP problem into a system of constrained nonsmooth equations. Then we solve this system by a smoothing projected Newton-type algorithm. At each iteration only a system of linear equations needs to be solved. The feasibility is ensured via the aggregated constraint under some conditions. Global and local superlinear convergence of this method is established under some standard assumptions. Preliminary numerical results are reported. Qi’s work is supported by the Hong Kong Research Grant Council. Ling’s work was supported by the Zhejiang Provincial National Science Foundation of China (Y606168). Tong’s work was done during her visit to The Hong Kong Polytechnic University. Her work is supported by the NSF of China (60474070) and the Technology Grant of Hunan (06FJ3038). Zhou’s work is supported by Australian Research Council.     

Optimality conditions and Mond–Weir duality for a class of differentiable semi-infinite multiobjective programming problems with vanishing constraints

4OR - In this paper, the class of differentiable semi-infinite multiobjective programming problems with vanishing constraints is considered. Both Karush–Kuhn–Tucker necessary optimality...     

Computer programs for non‐linear programming

In this paper we consider the problem of maximizing a non‐linear or linear objective function subject to non‐linear and/or linear constraints. The approach used is an adaptive random search with some non‐random searches built‐in. The algorithm begins with a given point which is replaced by another point if the latter satisfies each of the constraints and results in a bigger functional value. The process of moving from one point to a better point is repeated many times. The value of each of the coordinates of the next point is determined by one of several ways; for example, a coordinate is sometimes forced to have the same value as the value of the corresponding coordinate of the current feasible point. In this algorithm, a candidate point receives no further computational considerations as soon as it is found to be unfeasible; this makes the algorithm general. Computer programs illustrating the details of the new algorithm are given and computational results of two numerical test problems from the literature are presented. Optimality was reached in each of these two problems.     

A “build-down” scheme for linear programming

We propose a build-down scheme for Karmarkar's algorithm and the simplex method for linear programming. The scheme starts with an optimal basis candidate set including all columns of the constraint matrix, then constructs a dual ellipsoid containing all optimal dual solutions. A pricing rule is developed for checking whether or not a dual hyperplane corresponding to a column intersects the containing ellipsoid. If the dual hyperplane has no intersection with the ellipsoid, its corresponding column will not appear in any of the optimal bases, and can be eliminated from. As these methods iterate, is eventually built-down to a set that contains only the optimal basic columns.     

A reduction method for semi-infinite programming by means of a global stochastic approach†

We describe a reduction algorithm for solving semi-infinite programming problems. The proposed algorithm uses the simulated annealing method equipped with a function stretching as a multi-local procedure, and a penalty technique for the finite optimization process. An exponential penalty merit function is reduced along each search direction to ensure convergence from any starting point. Our preliminary numerical results seem to show that the algorithm is very promising in practice.     

Comment on “Duality theory in fuzzy linear programming problems with fuzzy coefficients”

This note provides a counterexample to illustrate the incorrectness of the proof of Proposition 3.3 that was presented by Wu (Fuzzy Optim Decis Mak 2:61–73, 2003). The original proof of Proposition 3.3 by Wu can only be correct when the extra assumption \(\mu _{\widetilde{y}_i}(0)= 1\) is added. The correct proof of Proposition 3.3 is also presented in this note.     

Optimality conditions and duality for a class of nondifferentiable multiobjective generalized fractional programming problems

This paper studies a class of multiobjective generalized fractional programming problems, where the numerators of objective functions are the sum of differentiable function and convex function, while the denominators are the difference of differentiable function and convex function. Under the assumption of Calmness Constraint Qualification the Kuhn-Tucker type necessary conditions for efficient solution are given, and the Kuhn-Tucker type sufficient conditions for efficient solution are presented under the assumptions of （F, α, ρ, d）-V-convexity. Subsequently, the optimality conditions for two kinds of duality models are formulated and duality theorems are proved.     

Schreier theory for singular extensions of categorical groups and homotopy classification∗ ∗

If G is a categorical group, a G-module is defined to be a braided categorical group (A c) together with an action of G on (A,c). In this work we define the notions of singular extension of G by the G-module (A,c) and of 1-cocycle of G with coefficients in (A,c) and we obtain, first, a bijection between the set of equivalence classes of singular extensions of G by (Ac) and the set of equivalence classes of 1-cocycles. Next, we associate to any G-module (Ac) a Kan fibration of simplicial sets ?: Ner(GAc)) → Ner(G)and then we show that there is a bijection between the set of equivalence classes of singular extensions of G by (A,c) and Γ[Ner(G,A,c/Ner(G)]the set of fibre homotopy classes of cross-sections of the fibration ?.     

Extending the mixed algebraic-analysis Fourier–Motzkin elimination method for classifying linear semi-infinite programmes

Motivated by a recent Basu–Martin–Ryan paper, we obtain a reduced primal-dual pair of a linear semi-infinite programming problem by applying an amended Fourier–Motzkin elimination method to the linear semi-infinite inequality system. The reduced primal-dual pair is equivalent to the original one in terms of consistency, optimal values and asymptotic consistency. Working with this reduced pair and reformulating a linear semi-infinite programme as a linear programme over a convex cone, we reproduce all the theorems that lead to the full eleven possible duality state classification theory. Establishing classification results with the Fourier–Motzkin method means that the two classification theorems for linear semi-infinite programming, 1969 and 1974, have been proved by new and exciting methods. We also show in this paper that the approach to study linear semi-infinite programming using Fourier–Motzkin elimination is not purely algebraic, it is mixed algebraic-analysis.     

A stable primal–dual approach for linear programming under nondegeneracy assumptions

This paper studies a primal–dual interior/exterior-point path-following approach for linear programming that is motivated on using an iterative solver rather than a direct solver for the search direction. We begin with the usual perturbed primal–dual optimality equations. Under nondegeneracy assumptions, this nonlinear system is well-posed, i.e. it has a nonsingular Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. Assuming that a basis matrix (easily factorizable and well-conditioned) can be found, we apply a simple preprocessing step to eliminate both the primal and dual feasibility equations. This results in a single bilinear equation that maintains the well-posedness property. Sparsity is maintained. We then apply either a direct solution method or an iterative solver (within an inexact Newton framework) to solve this equation. Since the linearization is well posed, we use affine scaling and do not maintain nonnegativity once we are close enough to the optimum, i.e. we apply a change to a pure Newton step technique. In addition, we correctly identify some of the primal and dual variables that converge to 0 and delete them (purify step). We test our method with random nondegenerate problems and problems from the Netlib set, and we compare it with the standard Normal Equations NEQ approach. We use a heuristic to find the basis matrix. We show that our method is efficient for large, well-conditioned problems. It is slower than NEQ on ill-conditioned problems, but it yields higher accuracy solutions.     

A linear programming algorithm for curve fitting in the L∞ norm

The L_∞ norm has been widely studied as a criterion for curve fitting problems. This paper presents an algorithm to solve discrete approximation problems in the L_∞ norm. The algorithm is a special-purpose linear programming method using the dual form of the problem, which employs a reduced basis and multiple pivots. Results of the computational experience with a computer code version of the algorithm are presented.     

Average number of iterations of some polynomial interior-point ——Algorithms for linear programming

We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the average number of iterations of these algorithms, coupled with a finite termination technique, is bounded above byO(n ^1.5). The random LP problem is Todd’s probabilistic model with the standard Gauss distribution.     

A combined phase I—phase II scaled potential algorithm for linear programming

We develop an extension of the affinely scaled potential reduction algorithm which simultaneously obtains feasibility and optimality in a standard form linear program, without the addition of any M terms. The method, and its lower-bounding procedure, are particularly simple compared with previous interior algorithms not requiring feasibility.This paper was written while the author was a research fellow at the Center for Operations Reasearch and Econometrics, Université Catholique de Louvain, Louvain-la-Neuve, Belgium.     

Heuristics and reduction methods for multiple constraints 0–1 linear programming problems

This work extends the efficient results relative to the 0–1 knapsack problem to the multiple inequality constraints 0–1 linear programming problems. The two crucial phases for the solving of this type of problems are presented: (i) Two linear expected time complexity greedy algorithms are proposed for the determination of a lower bound on the optimal value by using a cascade of surrogate relaxations of the original problem whose sizes are decreasing step by step. A comparative study with the best known heuristic methods is reported; it concerned the accuracy of the approximate solutions and the practical computational times. (ii) This greedy algorithm is inserted in an efficient reduction framework. Variables and constraints are eliminated by the conjunction of tests applied to Lagrangean and surrogate relaxations of the original problem. A lot of computational results are summarized by considering test problems of the literature.     

Near boundary behavior of primal—dual potential reduction algorithms for linear programming

This paper is concerned with selection of the-parameter in the primal—dual potential reduction algorithm for linear programming. Chosen from [n + , ), the level of determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant, must be set close ton + . This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, we show that this is unnecessary. We find for any iterate that can be sometimes chosen in a wide range [n + , ) while still guaranteeing the currently best convergence rate of O( L) iterations. This finding is encouraging since in practice large values of have resulted in fast convergence rates. Our finding partially complements the recent result of Zhang, Tapia and Dennis (1990) concerning the local convergence rate of the algorithm.Research supported in part by NSF Grant DDM-8922636.     

Saddle point methods,and alogorithms,for non-symmetric linear equations ∗

This paper describes methods for solving non-singular, non-symmetric linear equations whose symmetric part is positive definite. First, the solutions are characterized as saddle points of a convex-concave function. The associated primal and dual variational principles provide quadratic, strictly convex, functions whose minima are the solutions of the original equation and which generalize the energy function for symmetric problems.

Direct iterative methods for finding the saddle point are then developed and analyzed. A globally convergent algorithm for finding the saddle points is described. We show that requiring conjugacy of successive search directions with respect to the symmetric part of the equation is a poor strategy.