Exponential distribution-based genetic algorithm for solving mixed-integer bilevel programming problems

Two classes of mixed-integer nonlinear bilevel programming problems are discussed. One is that the follower＇s functions are separable with respect to the follower＇s variables, and the other is that the follower＇s functions are convex if the follower＇s variables are not restricted to integers. A genetic algorithm based on an exponential distribution is proposed for the aforementioned problems. First, for each fixed leader＇s variable x, it is proved that the optimal solution y of the follower＇s mixed-integer programming can be obtained by solving associated relaxed problems, and according to the convexity of the functions involved, a simplified branch and bound approach is given to solve the follower＇s programming for the second class of problems. Furthermore, based on an exponential distribution with a parameter λ, a new crossover operator is designed in which the best individuals are used to generate better offspring of crossover. The simulation results illustrate that the proposed algorithm is efficient and robust.

Computation of an Emptiable Minimal Siphon in a Subclass of Petri Nets Using Mixed-Integer Programming

Deadlock resolution strategies based on siphon control are widely investigated.Their computational efficiency largely depends on siphon computation.Mixed-integer programming(MIP)can be utilized for the computation of an emptiable siphon in a Petri net(PN).Based on it,deadlock resolution strategies can be designed without requiring complete siphon enumeration that has exponential complexity.Due to this reason,various MIP methods are proposed for various subclasses of PNs.This work proposes an innovative MIP method to compute an emptiable minimal siphon(EMS)for a subclass of PNs named S^(4)PR.In particular,many particular structural characteristics of EMS in S4 PR are formalized as constraints,which greatly reduces the solution space.Experimental results show that the proposed MIP method has higher computational efficiency.Furthermore,the proposed method allows one to determine the liveness of an ordinary S^(4)PR.

Necessary and Sufficient Conditions in Smooth Programming with Generalized Convexity

Hanson and Mond have grven sets of necessary and sufficient conditions for optimality in constrained optimization by introducing classes of generalized functions, called type Ⅰ functions. Recently, Bector definded univex functions, a new class of functions that unifies several concepts of generalized convexity. In this paper, additional conditions are attached to the Kuhn Tucker conditions giving a set of conditions which are both necessary and sufficient for optimality in constrained optimization, under appropriate constraint qualifications.

A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O（√nL） iteration complexity which is the best result for convex quadratic programming so far.

Global convergent algorithm for the bilevel linear fractional-linear programming based on modified convex simplex method

A global convergent algorithm is proposed to solve bilevel linear fractional-linear programming, which is a special class of bilevel programming. In our algorithm, replacing the lower level problem by its dual gap equaling to zero, the bilevel linear fractional-linear programming is transformed into a traditional sin- gle level programming problem, which can be transformed into a series of linear fractional programming problem. Thus, the modi- fied convex simplex method is used to solve the infinite linear fractional programming to obtain the global convergent solution of the original bilevel linear fractional-linear programming. Finally, an example demonstrates the feasibility of the proposed algorithm.

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.

Fixed-Point Iteration Method for Solving the Convex Quadratic Programming with Mixed Constraints

The present paper is devoted to a novel smoothing function method for convex quadratic programming problem with mixed constrains, which has important application in mechanics and engineering science. The problem is reformulated as a system of non-smooth equations, and then a smoothing function for the system of non-smooth equations is proposed. The condition of convergences of this iteration algorithm is given. Theory analysis and primary numerical results illustrate that this method is feasible and effective.

A New Heuristic for the Convex Quadratic Programming Problem

This paper presents a new heuristic to linearise the convex quadratic programming problem. The usual Karush-Kuhn-Tucker conditions are used but in this case a linear objective function is also formulated from the set of linear equations and complementarity slackness conditions. An unboundedness challenge arises in the proposed formulation and this challenge is alleviated by construction of an additional constraint. The formulated linear programming problem can be solved efficiently by the available simplex or interior point algorithms. There is no restricted base entry in this new formulation. Some computational experiments were carried out and results are provided.

Homotopy Method for Non-convex Programming in Unbonded Set

In the past few years, much and much attention has been paid to the method for solving non-convex programming. Many convergence results are obtained for bounded sets. In this paper, we get global convergence results for non-convex programming in unbounded sets under suitable conditions.

AN IMPROVEMENT ON UNCONSTRAINED CONVEX PROGRAMMING APPROACH TO LINEAR PROGRAMMING

For satate form linear gram as Fang and sao deined and approach which would find an optimal solution by solving an anconstrained convex dual programming.Thedual was construcied by applying an emropic peturbation and a simple Inequality Inz【z-1 for z】0n,In this paper,we suggest than a paperbation functiontake the place of Inx such that the new approdt has good numerical stability andhas all properties of the original

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interiorpoint method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.

Predictor-corrector interior-point algorithm for linearly constrained convex programming

Active set method and gradient projection method are curre nt ly the main approaches for linearly constrained convex programming. Interior-po int method is one of the most effective choices for linear programming. In the p aper a predictor-corrector interior-point algorithm for linearly constrained c onvex programming under the predictor-corrector motivation was proposed. In eac h iteration, the algorithm first performs a predictor-step to reduce the dualit y gap and then a corrector-step to keep the points close to the central traject ory. Computations in the algorithm only require that the initial iterate be nonn egative while feasibility or strict feasibility is not required. It is proved th at the algorithm is equivalent to a level-1 perturbed composite Newton method. Numerical experiments on twenty-six standard test problems are made. The result s show that the proposed algorithm is stable and robust.

NEWTON METHOD FOR SOLVING A CLASS OF SMOOTH CONVEX PROGRAMMING

An algorithm for solving a class of smooth convex programming is given. Using smooth exact multiplier penalty function, a smooth convex programming is minimized to a minimizing strongly convex function on the compact set was reduced. Then the strongly convex function with a Newton method on the given compact set was minimized.

A POTENTIAL REDUCTION ALGORITHM FOR LINEARLY CONSTRAINED CONVEX PROGRAMMING

A potential reduction algorithm is proposed for optimization of a convex function subject to linear constraints.At each step of the algorithm,a system of linear equations is solved to get a search direction and the Armijo's rule is used to determine a stepsize.It is proved that the algorithm is globally convergent.Computational results are reported.

Stochastic level-value approximation for quadratic integer convex programming

We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method to update the sample density functions. We also prove the asymptotic convergence of this algorithm, and report some numerical results to illuminate its effectiveness.

PARALLEL MULTIPLICATIVE ITERATIVE METHODS FOR CONVEX PROGRAMMING

In this paper, we present two parallel multiplicative algorithms for convex programming. If the objective function has compact level sets and has a locally Lipschitz continuous gradient, we discuss convergence of the algorithms. The proofs are essentially based on the results of sequential methods shown by Eggermontt[1].

The Optimality Conditions for Multiobjective Semi-infinite Programming Involving Generalized Unified （C, α, p, d）-convexity

The definition of generalized unified (C, α, ρ, d)-convex function is given. The concepts of generalized unified (C, α, ρ, d)-quasiconvexity, generalized unified (C, α, ρ, d)-pseudoconvexity and generalized unified (C, α, ρ, d)-strictly pseudoconvex functions are presented. The sufficient optimality conditions for multiobjective nonsmooth semi-infinite programming are obtained involving these generalized convexity lastly.

Continuity of the optimal value function and optimal solutions of parametric mixed-integer quadratic programs

To properly describe and solve complex decision problems, research on theoretical properties and solution of mixed-integer quadratic programs is becoming very important. We establish in this paper different Lipschitz-type continuity results about the optimal value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of the linear constraints. The obtained results extend some existing results for continuous quadratic programs, and, more importantly, lay the foundation for further theoretical study and corresponding algorithm analysis on mixed-integer quadratic programs.

Optimality Conditions for Static Programming with Generalized Convexity

The definitions of generalized pseudoconvex,generalized quasiconvex and its stri ctly generalized convexity were presented for the static programming at locally star -shaped set using the concept of right-upper derivative and the concept of sub linear. The sufficient and necessary conditions of the static programming were d erived in terms of a generalized Lemma in this paper. The results obtained are u seful for the further study on the duality of static programming and cover many already known conditions.

Multicut L-Shaped Algorithm for Stochastic Convex Programming with Fuzzy Probability Distribution

Two-stage problem of stochastic convex programming with fuzzy probability distribution is studied in this paper. Multicut L-shaped algorithm is proposed to solve the problem based on the fuzzy cutting and the minimax rule. Theorem of the convergence for the algorithm is proved. Finally, a numerical example about two-stage convex recourse problem shows the essential character and the efficiency.