Exact Solutions For Minimax Optimization Problems

Minimax optimization problems are an important category of Mathematical program-mings. Therefore, solving minimax is useful. There are many algorithms for solving min-imax. So far, we have agglomeration algorithm, interval algorithm, Newton-type method, SQP algorithm, filter algorithm and so on. These algorithms are ofen accomplished via dif-ferent iterative methods. Therefore, we want simpler method to solve some simple functions.The purpose of this thesis is to review and discuss Minimax optimization problems and some results, while introducing an available method from the version of extremum condition, this is helpful for solving the minimax problems with constraints in this way. In addition, we discuss and calculate different examples of Minimax Optimization problems, We also give the graphis of the objective functions by Mathematica.This thesis contains five parts.In the second part, we introduce the general form of Minimax Problem and three basic ideas to solve Minimax.Q is a convex closed subsect of Rn, G is a bounded closed subsect of Rm, we want to solve X*:If F(X, Y) is linear, then the above problem is known as linear minimax problem; if Ω≠Rn, it is known as constrained minimax problem.Three basic ideas to solve Minimax:1) Search for the extremal basis Gr: 2) Minimization of the maximum functionφ(X):3) Determination of a saddle point (X*, Y*):In the third part, we introduce two theorems on the Minimax optimization problems.Let fi(x)(i=1,2,…,n) be convex functions. Consider the following Minimax opti-mization problem:whereTheorem1There exists a subgroup I (?) N of cardinality less than or equal to k+1such that the problem has an optimal value of f*. Furthermore, at least one of the solution points to this problem is also the solution of the original problem.Let us have a function f(x) with directional derivatives at every point. A stationary point is a point such that the directional derivative is zero in every direction. Let us define a non-negative stationary point as a point such that the directional derivative is non-negative in every direction.Assume that fi(x) are not necessarily convex.Let fI(x)=max{fi(x)}. Let xS be a non-negative stationary point of fN(x), and let S={i|fi(xS)=fN(xS)}.Theorem2If the gradients of fi(x) at xs exists for i∈S, then there exists a subgroup I c N of cardinality less than or equal to k+1such that xS is a non-negative stationary point of fI(x). In the fourth part, we introduce an available method from the version of extremum condition. In addition, we discuss and calculate different examples of Minimax Optimization problems, We also give the graphis of the objective functions by Mathematica.Consider the minimization of a real function f:where f is defined in some open set in Rn, the objective functions are continously dif-ferentiable, x=(x1, x2,…, xn).Theorem3Let f=max{f1,f2,…, fm}, where the functions fi are continously differ-entiable in some open set in Rn, and let x*be a critical point of f. Suppose that the labeling of the functions is such that for some k. then a necessary condition for f to have a local minimum at x*is that the k+1gradients▽f1(x*),▽f2(x*),…,▽fk+1(x*) have a vanishing nontrivial linear combination with nonnegative coefficients:Moreover, when k=n and the n+1gradients▽fi(x*)(1≤i≤n+1) span Rn, a sufficient condition for f to have a strict minimum at x*is that above equation hold with positive coefficients ciHow to get the exact solution:Any point x*at whichhold is called stationary point of f. Indeed, when k<n the linear dependence expressed by the above condition provides n-k equations that, together with the k equations f1(x*)=f2(x*)=…=fk+i(x*), lead to the stationary points in the critical points, then through the verification we can get the exact solution.Finally, by discussing and calculating the different examples, we can see that solving Minimax optimization problems through the use of extremum condition is available. We should deal with problems case by case, it will make the problems simple and clear by the means of the graphis of the objective functions.