A hybrid algorithm for linearly constrained minimax problems

Many real life problems can be stated as a minimax problem, such as economics, finance, management, engineering and other fields, which demonstrate the importance of having reliable methods to tackle minimax problems. In this paper, an algorithm for linearly constrained minimax problems is presented in which we combine the trust-region methods with the line-search methods and curve-search methods. By means of this hybrid technique, it avoids possibly solving the trust-region subproblems many times, and make better use of the advantages of different methods. Under weaker conditions, the global and superlinear convergence are achieved. Numerical experiments show that the new algorithm is robust and efficient.     

Projected quasi-Newton algorithm with trust region for constrained optimization

In Ref. 1, Nocedal and Overton proposed a two-sided projected Hessian updating technique for equality constrained optimization problems. Although local two-step Q-superlinear rate was proved, its global convergence is not assured. In this paper, we suggest a trust-region-type, two-sided, projected quasi-Newton method, which preserves the local two-step superlinear convergence of the original algorithm and also ensures global convergence. The subproblem that we propose is as simple as the one often used when solving unconstrained optimization problems by trust-region strategies and therefore is easy to implement.This research was supported in part by the National Natural Science Foundation of China.     

Simple Sequential Quadratically Constrained Quadratic Programming Feasible Algorithm with Active Identification Sets for Constrained Minimax Problems

In this paper, the nonlinear minimax problems with inequality constraints are discussed. Based on the idea of simple sequential quadratically constrained quadratic programming algorithm for smooth constrained optimization, an alternative algorithm for solving the discussed problems is proposed. Unlike the previous work, at each iteration, a feasible direction of descent called main search direction is obtained by solving only one subprogram which is composed of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the constrained functions. Then a high-order correction direction used to avoid the Maratos effect is computed by updating the main search direction with a system of linear equations. The proposed algorithm possesses global convergence under weak Mangasarian–Fromovitz constraint qualification and superlinear convergence under suitable conditions with the upper-level strict complementarity. At last, some preliminary numerical results are reported.     

半无限极小极大问题的信赖域算法

本文以处理半无限最优化问题的一般技巧,将一类针对有限极小极大问题的信赖域算法推广到半无限极小极大问题。并证明了新建算法的全局收敛性和超线性收敛性。     

Nonmonotone algorithm for minimax optimization problems

Many real life problems can be stated as a minimax optimization problem, such as the problems in economics, finance, management, engineering and other fields. In this paper, we present an algorithm with nonmonotone strategy and second-order correction technique for minimax optimization problems. Using this scheme, the new algorithm can overcome the difficulties of the Maratos effect occurred in the nonsmooth optimization, and the global and superlinear convergence of the algorithm can be achieved accordingly. Numerical experiments indicate some advantages of this scheme.     

A NEW TRUST-REGION ALGORITHM FOR FINITE MINIMAX PROBLEM

In this paper, a new trust region algorithm for minimax optimization problems is proposed, which solves only one quadratic subproblem based on a new approximation model at each iteration. The approach is different from the traditional algorithms that usually require to solve two quadratic subproblems. Moreover, to avoid Maratos effect, the nonmonotone strategy is employed. The analysis shows that, under standard conditions, the algorithm has global and superlinear convergence. Preliminary numerical experiments are conducted to show the efficiency of the new method.     

A New Nonmonotone Linesearch SQP Algorithm for Unconstrained Minimax Problem

In this article, unconstrained minimax problems are discussed, and a sequential quadratic programming (SQP) algorithm with a new nonmonotone linesearch is presented. At each iteration, a search direction of descent is obtained by solving a quadratic programming (QP). To circumvent the Maratos effect, a high-order correction direction is achieved by solving another QP and a new nonmonotone linesearch is performed. Under reasonable conditions, the global convergence and the rate of superlinear convergence are established. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

Global and local convergence of a nonmonotone trust region algorithm for equality constrained optimization

This paper presents a nonmonotone trust region algorithm for equality constrained optimization problems. Under certain conditions, we obtain not only the global convergence in the sense that every limit point is a stationary point but also the one step superlinear convergence rate. Numerical tests are also given to show the efficiency of the proposed algorithm.     

Superlinearly Convergent Exact Penalty Methods with Projected Structured Secant Updates for Constrained Nonlinear Least Squares

We present a superlinearly convergent exact penalty method for solving constrained nonlinear least squares problems, in which the projected exact penalty Hessian is approximated by using a structured secant updating scheme. We give general conditions for the two-step superlinear convergence of the algorithm and prove that the projected structured Broyden–Fletcher–Goldfarb–Shanno (BFGS), Powell-symmetric-Broyden (PSB), and Davidon–Fletcher–Powell (DFP) update formulas satisfy these conditions. Then we extend the results to the projected structured convex Broyden family update formulas. Extensive testing results obtained by an implementation of our algorithms, as compared to the results obtained by several other competent algorithms, demonstrate the efficiency and robustness of the proposed approach.     

关于不等式约束的信赖域算法

对于具有不等式约束的非线性优化问题，本文给出一个依赖域算法，由于算法中依赖区域约束采用向量的∞范数约束的形式，从而使子问题变二次规划，同时使算法变得更实用。在通常假设条件下，证明了算法的整体收敛性和超线性收敛性。