An Efficient Algorithm for Min-Max Convex Semi-Infinite Programming Problems

In this article, we consider the convex min-max problem with infinite constraints. We propose an exchange method to solve the problem by using efficient inactive constraint dropping rules. There is no need to solve the maximization problem over the metric space, as the algorithm has merely to find some points in the metric space such that a certain criterion is satisfied at each iteration. Under some mild assumptions, the proposed algorithm is shown to terminate in a finite number of iterations and to provide an approximate solution to the original problem. Preliminary numerical results with the algorithm are promising. To our knowledge, this article is the first one conceived to apply explicit exchange methods for solving nonlinear semi-infinite convex min-max problems.     

Convergence of an adaptive Ka?anov FEM for quasi-linear problems

We design an adaptive finite element method to approximate the solutions of quasi-linear elliptic problems. The algorithm is based on a Ka?anov iteration and a mesh adaptation step is performed after each linear solve. The method is thus inexact because we do not solve the discrete nonlinear problems exactly, but rather perform one iteration of a fixed point method (Ka?anov), using the approximation of the previous mesh as an initial guess. The convergence of the method is proved for any reasonable marking strategy and starting from any initial mesh. We conclude with some numerical experiments that illustrate the theory.     

An Exact Solution Method for Reliability Optimization in Complex Systems

Systems reliability plays an important role in systems design, operation and management. Systems reliability can be improved by adding redundant components or increasing the reliability levels of subsystems. Determination of the optimal amount of redundancy and reliability levels among various subsystems under limited resource constraints leads to a mixed-integer nonlinear programming problem. The continuous relaxation of this problem in a complex system is a nonconvex nonseparable optimization problem with certain monotone properties. In this paper, we propose a convexification method to solve this class of continuous relaxation problems. Combined with a branch-and-bound method, our solution scheme provides an efficient way to find an exact optimal solution to integer reliability optimization in complex systems. This research was partially supported by the Research Grants Council of Hong Kong, grants CUHK4056/98E, CUHK4214/01E and 2050252, and the National Natural Science Foundation of China under Grants 79970107 and 10271073.     

Constrained Nonconvex Nonsmooth Optimization via Proximal Bundle Method

In this paper, we consider a constrained nonconvex nonsmooth optimization, in which both objective and constraint functions may not be convex or smooth. With the help of the penalty function, we transform the problem into an unconstrained one and design an algorithm in proximal bundle method in which local convexification of the penalty function is utilized to deal with it. We show that, if adding a special constraint qualification, the penalty function can be an exact one, and the sequence generated by our algorithm converges to the KKT points of the problem under a moderate assumption. Finally, some illustrative examples are given to show the good performance of our algorithm.     

Relaxations and approximations of chance constraints under finite distributions

Optimization problems with constraints involving stochastic parameters that are required to be satisfied with a prespecified probability threshold arise in numerous applications. Such chance constrained optimization problems involve the dual challenges of stochasticity and nonconvexity. In the setting of a finite distribution of the stochastic parameters, an optimization problem with linear chance constraints can be formulated as a mixed integer linear program (MILP). The natural MILP formulation has a weak relaxation bound and is quite difficult to solve. In this paper, we review some recent results on improving the relaxation bounds and constructing approximate solutions for MILP formulations of chance constraints. We also discuss a recently introduced bicriteria approximation algorithm for covering type chance constrained problems. This algorithm uses a relaxation to construct a solution whose (constraint violation) risk level may be larger than the pre-specified threshold, but is within a constant factor of it, and whose objective value is also within a constant factor of the true optimal value. Finally, we present some new results that improve on the bicriteria approximation factors in the finite scenario setting and shed light on the effect of strong relaxations on the approximation ratios.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

Inexact subgradient methods for quasi-convex optimization problems

In this paper, we consider a generic inexact subgradient algorithm to solve a nondifferentiable quasi-convex constrained optimization problem. The inexactness stems from computation errors and noise, which come from practical considerations and applications. Assuming that the computational errors and noise are deterministic and bounded, we study the effect of the inexactness on the subgradient method when the constraint set is compact or the objective function has a set of generalized weak sharp minima. In both cases, using the constant and diminishing stepsize rules, we describe convergence results in both objective values and iterates, and finite convergence to approximate optimality. We also investigate efficiency estimates of iterates and apply the inexact subgradient algorithm to solve the Cobb–Douglas production efficiency problem. The numerical results verify our theoretical analysis and show the high efficiency of our proposed algorithm, especially for the large-scale problems.     

A geometric study of duality gaps, with applications

Lagrangian relaxation is often an efficient tool to solve (large-scale) optimization problems, even nonconvex. However it introduces a duality gap, which should be small for the method to be really efficient. Here we make a geometric study of the duality gap. Given a nonconvex problem, we formulate in a first part a convex problem having the same dual. This formulation involves a convexification in the product of the three spaces containing respectively the variables, the objective and the constraints. We apply our results to several relaxation schemes, especially one called “Lagrangean decomposition” in the combinatorial-optimization community, or “operator splitting” elsewhere. We also study a specific application, highly nonlinear: the unit-commitment problem. Received: June 1997 / Accepted: December 2000?Published online April 12, 2001     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

An accurate a posteriori error estimator for the Steklov eigenvalue problem and its applications

In this paper, a type of accurate a posteriori error estimator is proposed for the Steklov eigenvalue problem based on the complementary approach, which provides an asymptotic exact estimate for the approximate eigenpair. Besides, we design a type of cascadic adaptive finite element method for the Steklov eigenvalue problem based on the proposed a posteriori error estimator. In this new cascadic adaptive scheme, instead of solving the Steklov eigenvalue problem in each adaptive space directly, we only need to do some smoothing steps for linearized boundary value problems on a series of adaptive spaces and solve some Steklov eigenvalue problems on a low dimensional space. Furthermore, the proposed a posteriori error estimator provides the way to refine mesh and control the number of smoothing steps for the cascadic adaptive method. Some numerical examples are presented to validate the efficiency of the algorithm in this paper.

     

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.     

Solving nonlinear principal-agent problems using bilevel programming

While significant progress has been made, analytic research on principal-agent problems that seek closed-form solutions faces limitations due to tractability issues that arise because of the mathematical complexity of the problem. The principal must maximize expected utility subject to the agent’s participation and incentive compatibility constraints. Linearity of performance measures is often assumed and the Linear, Exponential, Normal (LEN) model is often used to deal with this complexity. These assumptions may be too restrictive for researchers to explore the variety of relationships between compensation contracts offered by the principal and the effort of the agent. In this paper we show how to numerically solve principal-agent problems with nonlinear contracts. In our procedure, we deal directly with the agent’s incentive compatibility constraint. We illustrate our solution procedure with numerical examples and use optimization methods to make the problem tractable without using the simplifying assumptions of a LEN model. We also show that using linear contracts to approximate nonlinear contracts leads to solutions that are far from the optimal solutions obtained using nonlinear contracts. A principal-agent problem is a special instance of a bilevel nonlinear programming problem. We show how to solve principal-agent problems by solving bilevel programming problems using the ellipsoid algorithm. The approach we present can give researchers new insights into the relationships between nonlinear compensation schemes and employee effort.     

On the supports of functions

In this paper, finite difference and finite element methods are used with nonlinear SOR to solve the problems of minimizing strict convex functionals. The functionals are discretized by both methods and some numerical quadrature formula. The convergence of such discretization is guaranteed and will be discussed. As for the convergence of the iterative process, it is necessary to vary the relaxation parameter in each iterations. In addition, for the model catenoid problem, boundary grid refinements play an essential role in the proposed nonlinear SOR algorithm. Numerical results which illustrate the importance of the grid refinements will be presented.

     

Two-grid stabilized algorithms for the steady Navier–Stokes equations with damping

This paper presents and studies three two-grid stabilized quadratic equal-order finite element algorithms based on two local Gauss integrations for the steady Navier–Stokes equations with damping. In these algorithms, we first solve a stabilized nonlinear problem on a coarse grid, and then pass the coarse grid solution to a fine grid and solve a stabilized linear problem. Using some nonlinear analysis techniques, we analyze stability of the algorithms and derive optimal order error estimates of the approximate solutions. Theoretical and numerical results show that, when the algorithmic parameters are chosen appropriately, the accuracy of the approximate solutions computed by our two-grid stabilized algorithms is comparable to that of solving a fully stabilized nonlinear problem on the same fine grid; however, our two-grid algorithms save a large amount of CPU time than the one-grid stabilized algorithm.     

Numerical treatment of singularly perturbed two point boundary value problems using initial-value method

In this paper, we describe an initial-value method for linear and nonlinear singularly perturbed boundary value problems in the interval [p,q]. For linear problems, the required approximate solution is obtained by solving the reduced problem and one initial-value problems directly deduced from the given problem. For nonlinear problems the original second-order nonlinear problem is linearized by using quasilinearization method. Then this linear problem is solved as previous method. The present method has been implemented on several linear and non-linear examples which approximate the exact solution. We also present the approximate and exact solutions graphically.     

An adaptive algorithm for the Thomas–Fermi equation

A free boundary value problem is introduced to approximate the original Thomas–Fermi equation. The unknown truncated free boundary is determined iteratively. We transform the free boundary value problem to a nonlinear boundary value problem defined on [0,1]. We present an adaptive algorithm to solve the problem by means of the moving mesh finite element method. Comparison of our numerical results with those obtained by other approaches shows high accuracy of our method.     

A Simple Semi-Implicit Scheme for Partial Differential Equations with Obstacle Constraints

We develop a simple and efficient numerical scheme to solve a class of obstacle problems encountered in various applications. Mathematically, obstacle problems are usually formulated using nonlinear partial differential equations (PDE). To construct a computationally efficient scheme, we introduce a time derivative term and convert the PDE into a time-dependent problem. But due to its nonlinearity, the time step is in general chosen to satisfy a very restrictive stability condition. To relax such a time step constraint when solving a time dependent evolution equation, we decompose the nonlinear obstacle constraint in the PDE into a linear part and a nonlinear part and apply the semi-implicit technique. We take the linear part implicitly while treating the nonlinear part explicitly. Our method can be easily applied to solve the fractional obstacle problem and min curvature flow problem. The article will analyze the convergence of our proposed algorithm. Numerical experiments are given to demonstrate the efficiency of our algorithm.     

Computing equilibria of Cournot oligopoly models with mixed-integer quantities

We consider Cournot oligopoly models in which some variables represent indivisible quantities. These models can be addressed by computing equilibria of Nash equilibrium problems in which the players solve mixed-integer nonlinear problems. In the literature there are no methods to compute equilibria of this type of Nash games. We propose a Jacobi-type method for computing solutions of Nash equilibrium problems with mixed-integer variables. This algorithm is a generalization of a recently proposed method for the solution of discrete so-called “2-groups partitionable” Nash equilibrium problems. We prove that our algorithm converges in a finite number of iterations to approximate equilibria under reasonable conditions. Moreover, we give conditions for the existence of approximate equilibria. Finally, we give numerical results to show the effectiveness of the proposed method.     

A technique for speeding up the solution of the Lagrangean dual

We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, thek-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems,K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.     

Mixed-integer minimax dynamic optimization for structure identification of glycerol metabolic network

Cell metabolism is a dynamic regulation process, in which its network structure and/or regulatory mechanisms can change constantly over time due to internal and external perturbations. This paper models glycerol metabolism in continuous fermentation as a nonlinear mixed-integer dynamic system by defining the time-varying metabolic network structure as an integer-valued function. To identify the dynamic network structure and kinetic parameters, we establish a mixed-integer minimax dynamic optimization problem with concentration robustness as its objective functional. By direct multiple shooting strategy and a decomposition approach consisting of convexification, relaxation and rounding strategy, the optimization problem is transformed into a large-scale approximate multistage parameter optimization problem. It is then solved using a competitive particle swarm optimization algorithm. We also show that the relaxation problem yields the best lower bound for the optimization problem, and its solution can be arbitrarily approximated by the solution obtained from rounding strategy. Numerical results indicate that the proposed mixed-integer dynamic system can better describe cellular self-regulation and response to intermediate metabolite inhibitions in continuous fermentation of glycerol. These numerical results show that the proposed numerical methods are effective in solving the large-scale mixed-integer dynamic optimization problems.