INTERVAL ADJUSTABLE ENTROPY ALGORITHM FOR A CLASS OF UNCONSTRAINED DISCRETE MINIMAX PROBLEMS

In this paper,a class of unconstrained discrete minimax problems is described,in which the objective functions are in C 1.The paper deals with this problem by means of taking the place of maximum entropy function with adjustable entropy function.By constructing an interval extension of adjustable entropy function an d some region deletion test rules,a new interval algorithm is presented.The rele vant properties are proven.The minimax value and the localization of the minimax points of the problem can be obtained by this method. This method can overcome the flow problem in the maximum entropy algorithm.Both theoretical and numerica l results show that the method is reliable and efficient.

A SSLE-TYPE ALGORITHM OF QUASI-STRONGLY SUB-FEASIBLE DIRECTIONS FOR INEQUALITY CONSTRAINED MINIMAX PROBLEMS

In this paper,we discuss the nonlinear minimax problems with inequality constraints.Based on the stationary conditions of the discussed problems,we propose a sequential systems of linear equations(SSLE)-type algorithm of quasi-strongly sub-feasible directions with an arbitrary initial iteration point.By means of the new working set,we develop a new technique for constructing the sub-matrix in the lower right corner of the coefficient matrix of the system of linear equations(SLE).At each iteration,two systems of linear equations(SLEs)with the same uniformly nonsingular coefficient matrix are solved.Under mild conditions,the proposed algorithm possesses global and strong convergence.Finally,some preliminary numerical experiments are reported.

A New Superlinearly Convergent SQP Algorithm for Nonlinear Minimax Problems

In this paper, the nonlinear minimax problems are discussed. By means of the Sequential Quadratic Programming （SQP）, a new descent algorithm for solving the problems is presented. At each iteration of the proposed algorithm, a main search direction is obtained by solving a Quadratic Programming （QP） which always has a solution. In order to avoid the Maratos effect, a correction direction is obtained by updating the main direction with a simple explicit formula. Under mild conditions without the strict complementarity, the global and superlinear convergence of the algorithm can be obtained. Finally, some numerical experiments are reported.

Error Bounds of Two Smoothing Approximations for Semi-infinite Minimax Problems

In the paper we investigate smoothing method for solving semi-infinite minimax problems. Not like most of the literature in semi-infinite minimax problems which are concerned with the continuous time version（i.e., the one dimensional semi-infinite minimax problems）, the primary focus of this paper is on multi- dimensional semi-infinite minimax problems. The global error bounds of two smoothing approximations for the objective function are given and compared. It is proved that the smoothing approximation given in this paper can provide a better error bound than the existing one in literature.

A New Objective Penalty Function Approach for Solving Constrained Minimax Problems

In this paper,a new objective penalty function approach is proposed for solving minimax programming problems with equality and inequality constraints.This new objective penalty function combines the objective penalty and constraint penalty.By the new objective penalty function,a constrained minimax problem is converted to minimizations of a sequence of continuously differentiable functions with a simple box constraint.One can thus apply any efficient gradient minimization methods to solve the minimizations with box constraint at each step of the sequence.Some relationships between the original constrained minimax problem and the corresponding minimization problems with box constraint are established.Based on these results,an algorithm for finding a global solution of the constrained minimax problems is proposed by integrating the particular structure of minimax problems and its global convergence is proved under some conditions.Furthermore,an algorithm is developed for finding a local solution of the constrained minimax problems,with its convergence proved under certain conditions.Preliminary results of numerical experiments with well-known test problems show that satisfactorilyapproximate solutions for some constrained minimax problems can be obtained.

Nonsmooth Equations of K-T Systems for a Constrained Minimax Problem

Using K-T optimality condition of nonsmooth optimization, we establish two equivalent systems of the nonsmooth equations for the constrained minimax problem directly. Then generalized Newton methods are applied to solve these systems of the nonsmooth equations. Thus a new approach to solving the constrained minimax problem is developed.

Solving constrained minimax problem via nonsmooth equations method

A new nonsmooth equations model of constrained minimax problem was de-rived. The generalized Newton method was applied for solving this system of nonsmooth equations system. A new algorithm for solving constrained minimax problem was established. The local superlinear and quadratic convergences of the algorithm were discussed.

Optimality Conditions for Minimax Optimization Problems with an Infinite Number of Constraints and Related Applications

This paper is concerned with the study of optimality conditions for minimax optimization problems with an infinite number of constraints,denoted by(MMOP).More precisely,we first establish necessary conditions for optimal solutions to the problem(MMOP)by means of employing some advanced tools of variational analysis and generalized differentiation.Then,sufficient conditions for the existence of such solutions to the problem(MMOP)are investigated with the help of generalized convexity functions defined in terms of the limiting subdifferential of locally Lipschitz functions.Finally,some of the obtained results are applied to formulating optimality conditions for weakly efficient solutions to a related multiobjective optimization problem with an infinite number of constraints,and a necessary optimality condition for a quasiε-solution to problem(MMOP).

Saddle Point Criteria in Nonsmooth Semi-Infinite Minimax Fractional Programming Problems

This paper considers a nonsmooth semi-infinite minimax fractional programming problem（SIMFP） involving locally Lipschitz invex functions. The authors establish necessary optimality conditions for SIMFP. The authors establish the relationship between an optimal solution of SIMFP and saddle point of scalar Lagrange function for SIMFP. Further, the authors study saddle point criteria of a vector Lagrange function defined for SIMFP.

Adjustable entropy method for solving convex inequality problem

To solve the inequality problem, an adjustable entropy method is proposed. An inequality problem can be transformed into a minimax problem which is nondifferentiable; then an adjustable entropy is used to smooth the minimax problem. The solution of inequalities can be approached by using a BFGS algorithm of the standard optimization method. Some properties of the new approximate function are presented and then the global convergence are given according to the algorithm. Two numerical examples illustrate that the proposed method is efficient and is superior to the former ones.

Dynamic System for Solving Saddle Point Problems in Hilbert Spaces and Its Application to Neural Computing

This paper studies the existence and uniqueness of solutions and the stability and convergence of a dynamic system for solving saddle point problems （SPP） in Hilbert spaces. The analysis first converts the SPP into a problem of searching for equilibriums of a dynamic system using a criterion for solutions of the SPP, then shows the existence and uniqueness of the solutions by creating a positive function whose Fréchet derivative is decreasing along any solution. The construction of positively invariant subsets gives the global stability and convergence of this dynamic system, that is, the dynamic system globally converges to some exact solution of the SPP. Finally, the paper also shows that the obtained results can be applied to neural computing for solving SPP.

Primal-dual algorithms for total variation based image restoration under Poisson noise Dedicated to Professor Lin Qun on the Occasion of his 80th Birthday

We consider the problem of restoring images corrupted by Poisson noise. Under the framework of maximum a posteriori estimator, the problem can be converted into a minimization problem where the objective function is composed of a Kullback-Leibler(KL)-divergence term for the Poisson noise and a total variation(TV) regularization term. Due to the logarithm function in the KL-divergence term, the non-differentiability of TV term and the positivity constraint on the images, it is not easy to design stable and efficiency algorithm for the problem. Recently, many researchers proposed to solve the problem by alternating direction method of multipliers(ADMM). Since the approach introduces some auxiliary variables and requires the solution of some linear systems, the iterative procedure can be complicated. Here we formulate the problem as two new constrained minimax problems and solve them by Chambolle-Pock's first order primal-dual approach. The convergence of our approach is guaranteed by their theory. Comparing with ADMM approaches, our approach requires about half of the auxiliary variables and is matrix-inversion free. Numerical results show that our proposed algorithms are efficient and outperform the ADMM approach.

Truncated Smoothing Newton Method for l_∞ Fitting Rotated Cones

In this paper, the rotated cone fitting problem is considered. In case the measured data are generally accurate and it is needed to fit the surface within expected error bound, it is more appropriate to use l∞ norm than 12 norm. l∞ fitting rotated cones need to minimize, under some bound constraints, the maximum function of some nonsmooth functions involving both absolute value and square root functions. Although this is a low dimensional problem, in some practical application, it is needed to fitting large amount of cones repeatedly, moreover, when large amount of measured data are to be fitted to one rotated cone, the number of components in the maximum function is large. So it is necessary to develop efficient solution methods. To solve such optimization problems efficiently, a truncated smoothing Newton method is presented. At first, combining aggregate smoothing technique to the maximum function as well as the absolute value function and a smoothing function to the square root function, a monotonic and uniform smooth approximation to the objective function is constructed. Using the smooth approximation, a smoothing Newton method can be used to solve the problem. Then, to reduce the computation cost, a truncated aggregate smoothing technique is applied to give the truncated smoothing Newton method, such that only a small subset of component functions are aggregated in each iteration point and hence the computation cost is considerably reduced.

A New Algorithm for Unconstrained Min-Max Optimization

We have structured the new differential approximation, Vα-approximation, about the maximum function max{fi(x)}. On the basis of which the kind of minimax algorithms and its convergence are proved. Some numerical examples are tested. The results show that the algorithm is better than Madsen’s algorithm when the problem is singular.