On a continuous approach for the maximum weighted clique problem

This paper is focused on computational study of continuous approach for the maximum weighted clique problem. The problem is formulated as a continuous optimization problem with a nonconvex quadratic constraint given by the difference of two convex functions (d.c. function). The proposed approach consists of two main ingredients: a local search algorithm, which provides us with crucial points; and a procedure which is based on global optimality condition and which allows us to escape from such points. The efficiency of the proposed algorithm is illustrated by computational results.     

Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming

When the follower's optimality conditions are both necessary and sufficient, the nonlinear bilevel program can be solved as a global optimization problem. The complementary slackness condition is usually the complicating constraint in such problems. We show how this constraint can be replaced by an equivalent system of convex and separable quadratic constraints. In this paper, we propose different methods for finding the global minimum of a concave function subject to quadratic separable constraints. The first method is of the branch and bound type, and is based on rectangular partitions to obtain upper and lower bounds. Convergence of the proposed algorithm is also proved. For computational purposes, different procedures that accelerate the convergence of the proposed algorithm are analysed. The second method is based on piecewise linear approximations of the constraint functions. When the constraints are convex, the problem is reduced to global concave minimization subject to linear constraints. In the case of non-convex constraints, we use zero-one integer variables to linearize the constraints. The number of integer variables depends only on the concave parts of the constraint functions.Parts of the present paper were prepared while the second author was visiting Georgia Tech and the University of Florida.     

Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints

In this paper, the nonlinear minimax problems with inequality constraints are discussed, and a sequential quadratic programming (SQP) algorithm with a generalized monotone line search is presented. At each iteration, a feasible direction of descent is obtained by solving a quadratic programming (QP). To avoid the Maratos effect, a high order correction direction is achieved by solving another QP. As a result, the proposed algorithm has global and superlinear convergence. Especially, the global convergence is obtained under a weak Mangasarian–Fromovitz constraint qualification (MFCQ) instead of the linearly independent constraint qualification (LICQ). At last, its numerical effectiveness is demonstrated with test examples.     

An outcome space approach for generalized convex multiplicative programs

This paper addresses the problem of minimizing an arbitrary finite sum of products of two convex functions over a convex set. Nonconvex problems in this form constitute a class of generalized convex multiplicative problems. Convex analysis results allow to reformulate the problem as an indefinite quadratic problem with infinitely many linear constraints. Special properties of the quadratic problem combined with an adequate outer approximation procedure for handling its semi-infinite constrained set enable an efficient constraint enumeration global optimization algorithm for generalized convex multiplicative programs. Computational experiences illustrate the proposed approach.     

A quadratically approximate framework for constrained optimization,global and local convergence

This paper presents a quadratically approximate algorithm framework （QAAF） for solving general constrained optimization problems, which solves, at each iteration, a subproblem with quadratic objective function and quadratic equality together with inequality constraints. The global convergence of the algorithm framework is presented under the Mangasarian-Fromovitz constraint qualification （MFCQ）, and the conditions for superlinear and quadratic convergence of the algorithm framework are given under the MFCQ, the constant rank constraint qualification （CRCQ） as well as the strong second-order sufficiency conditions （SSOSC）. As an incidental result, the definition of an approximate KKT point is brought forward, and the global convergence of a sequence of approximate KKT points is analysed.     

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.     

Projected Hessian algorithm with backtracking interior point technique for linear constrained optimization

In this paper, we propose a new trust-region-projected Hessian algorithm with nonmonotonic backtracking interior point technique for linear constrained optimization. By performing the QR decomposition of an affine scaling equality constraint matrix, the conducted subproblem in the algorithm is changed into the general trust-region subproblem defined by minimizing a quadratic function subject only to an ellipsoidal constraint. By using both the trust-region strategy and the line-search technique, each iteration switches to a backtracking interior point step generated by the trustregion subproblem. The global convergence and fast local convergence rates for the proposed algorithm are established under some reasonable assumptions. A nonmonotonic criterion is used to speed up the convergence in some ill-conditioned cases. Selected from Journal of Shanghai Normal University (Natural Science), 2003, 32(4): 7–13     

A new global optimization method for univariate constrained twice-differentiable NLP problems

In this paper, a new global optimization method is proposed for an optimization problem with twice-differentiable objective and constraint functions of a single variable. The method employs a difference of convex underestimator and a convex cut function, where the former is a continuous piecewise concave quadratic function, and the latter is a convex quadratic function. The main objectives of this research are to determine a quadratic concave underestimator that does not need an iterative local optimizer to determine the lower bounding value of the objective function and to determine a convex cut function that effectively detects infeasible regions for nonconvex constraints. The proposed method is proven to have a finite ε-convergence to locate the global optimum point. The numerical experiments indicate that the proposed method competes with another covering method, the index branch-and-bound algorithm, which uses the Lipschitz constant.     

半无限规划离散化问题一个两阶段序列二次规划算法

本文研究了求解半无限规划离散化问题(P)的一个新的算法.利用序列二次规划(SQP)两阶段方法和约束指标集的修正技术,提出了求解(P)的一个两阶段SQP算法.算法结构简单,搜索方向的计算成本较低.在适当的条件下,证明了算法具有全局收敛性.数值试验结果表明算法是有效的.推广了文献[4]中求解(P)的算法.     

An affine scaling trust-region algorithm with interior backtracking technique for solving bound-constrained nonlinear systems

In this paper, we propose a new affine scaling trust-region algorithm in association with nonmonotonic interior backtracking line search technique for solving nonlinear equality systems subject to bounds on variables. The trust-region subproblem is defined by minimizing a squared Euclidean norm of linear model adding the augmented quadratic affine scaling term subject only to an ellipsoidal constraint. By using both trust-region strategy and interior backtracking line search technique, each iterate switches to backtracking step generated by the general trust-region subproblem and satisfies strict interior point feasibility by line search backtracking technique. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

Stabilized Sequential Quadratic Programming

Recently, Wright proposed a stabilized sequential quadratic programming algorithm for inequality constrained optimization. Assuming the Mangasarian-Fromovitz constraint qualification and the existence of a strictly positive multiplier (but possibly dependent constraint gradients), he proved a local quadratic convergence result. In this paper, we establish quadratic convergence in cases where both strict complementarity and the Mangasarian-Fromovitz constraint qualification do not hold. The constraints on the stabilization parameter are relaxed, and linear convergence is demonstrated when the parameter is kept fixed. We show that the analysis of this method can be carried out using recent results for the stability of variational problems.     

A working set SQCQP algorithm with simple nonmonotone penalty parameters

In this paper, we present a new sequential quadratically constrained quadratic programming (SQCQP) algorithm, in which a simple updating strategy of the penalty parameter is adopted. This strategy generates nonmonotone penalty parameters at early iterations and only uses the multiplier corresponding to the bound constraint of the quadratically constrained quadratic programming (QCQP) subproblem instead of the multipliers of the quadratic constraints, which will bring some numerical advantages. Furthermore, by using the working set technique, we remove the constraints of the QCQP subproblem that are locally irrelevant, and thus the computational cost could be reduced. Without assuming the convexity of the objective function or the constraints, the algorithm is proved to be globally, superlinearly and quadratically convergent. Preliminary numerical results show that the proposed algorithm is very promising when compared with the tested SQP algorithms.     

A working set SQCQP algorithm with simple nonmonotone penalty parameters

In this paper, we present a new sequential quadratically constrained quadratic programming (SQCQP) algorithm, in which a simple updating strategy of the penalty parameter is adopted. This strategy generates nonmonotone penalty parameters at early iterations and only uses the multiplier corresponding to the bound constraint of the quadratically constrained quadratic programming (QCQP) subproblem instead of the multipliers of the quadratic constraints, which will bring some numerical advantages. Furthermore, by using the working set technique, we remove the constraints of the QCQP subproblem that are locally irrelevant, and thus the computational cost could be reduced. Without assuming the convexity of the objective function or the constraints, the algorithm is proved to be globally, superlinearly and quadratically convergent. Preliminary numerical results show that the proposed algorithm is very promising when compared with the tested SQP algorithms.     

An Adaptive Dual Parametrization Algorithm for Quadratic Semi-infinite Programming Problems

The so called dual parametrization method for quadratic semi-infinite programming (SIP) problems is developed recently for quadratic SIP problems with a single infinite constraint. A dual parametrization algorithm is also proposed for numerical solution of such problems. In this paper, we consider quadratic SIP problems with positive definite objective and multiple linear infinite constraints. All the infinite constraints are supposed to be continuously dependent on their index variable on a compact set which is defined by a number equality and inequalities. We prove that in the multiple infinite constraint case, the minimu parametrization number, just as in the single infinite constraint case, is less or equal to the dimension of the SIP problem. Furthermore, we propose an adaptive dual parametrization algorithm with convergence result. Compared with the previous dual parametrization algorithm, the adaptive algorithm solves subproblems with much smaller number of constraints. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

A Global Optimization Method for Solving Convex Quadratic Bilevel Programming Problems

We use the merit function technique to formulate a linearly constrained bilevel convex quadratic problem as a convex program with an additional convex-d.c. constraint. To solve the latter problem we approximate it by convex programs with an additional convex-concave constraint using an adaptive simplicial subdivision. This approximation leads to a branch-and-bound algorithm for finding a global optimal solution to the bilevel convex quadratic problem. We illustrate our approach with an optimization problem over the equilibrium points of an n-person parametric noncooperative game.     

A non-interior-point smoothing method for variational inequality problem

In this paper, we focus on the variational inequality problem. Based on the Fischer-Burmeister function with smoothing parameters, the variational inequality problem can be reformulated as a system of parameterized smooth equations, a non-interior-point smoothing method is presented for solving the problem. The proposed algorithm not only has no restriction on the initial point, but also has global convergence and local quadratic convergence, moreover, the local quadratic convergence is established without a strict complementarity condition. Preliminary numerical results show that the algorithm is promising.     

An interior affine scaling projective algorithm for nonlinear equality and linear inequality constrained optimization

In this paper, we propose a new nonmonotonic interior point backtracking strategy to modify the reduced projective affine scaling trust region algorithm for solving optimization subject to nonlinear equality and linear inequality constraints. The general full trust region subproblem for solving the nonlinear equality and linear inequality constrained optimization is decomposed to a pair of trust region subproblems in horizontal and vertical subspaces of linearize equality constraints and extended affine scaling equality constraints. The horizontal subproblem in the proposed algorithm is defined by minimizing a quadratic projective reduced Hessian function subject only to an ellipsoidal trust region constraint in a null subspace of the tangential space, while the vertical subproblem is also defined by the least squares subproblem subject only to an ellipsoidal trust region constraint. By introducing the Fletcher's penalty function as the merit function, trust region strategy with interior point backtracking technique will switch to strictly feasible interior point step generated by a component direction of the two trust region subproblems. The global convergence of the proposed algorithm while maintaining fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some high nonlinear function conditioned cases.     

Sequential Semidefinite Program for Maximum Robustness Design of Structures under Load Uncertainty

A robust structural optimization scheme as well as an optimization algorithm are presented based on the robustness function. Under the uncertainties of the external forces based on the info-gap model, the maximization of the robustness function is formulated as an optimization problem with infinitely many constraints. By using the quadratic embedding technique of uncertainty and the S-procedure, we reformulate the problem into a nonlinear semidefinite programming problem. A sequential semidefinite programming method is proposed which has a global convergent property. It is shown through numerical examples that optimum designs of various linear elastic structures can be found without difficulty.The authors are grateful to the Associate Editor and two anonymous referees for handling the paper efficiently as well as for helpful comments and suggestions.     

线性不等式约束的广义非线性互补问题的仿射内点信赖域方法

提供了一种新的非单调内点回代线搜索技术的仿射内点信赖域方法解线性不等式约束的广义非线性互补问题(GCP).基于广义互补问题构成的半光滑方程组的广义Jacobian矩阵,算法使用l2范数作为半光滑方程组的势函数,形成的信赖域子问题为一个带椭球约束的线性化的二次模型.利用广义牛顿方程计算试探迭代步,通过内点映射回代技术确保迭代点是严格内点,保证了算法的整体收敛性.在合理的条件下,证明了信赖域算法在接近最优点时可转化为广义拟牛顿步,进而具有局部超线性收敛速率.非单调技术将克服高度非线性情况加速收敛进展.最后,数值结果表明了算法的有效性.     

A smoothing Newton method for NCPs with the P0-property

In this paper, we first investigate a two-parametric class of smoothing functions which contains the penalized smoothing Fischer-Burmeister function and the penalized smoothing CHKS function as special cases. Then we present a smoothing Newton method for the nonlinear complementarity problem based on the class of smoothing functions. Issues such as line search rule, boundedness of the level set, global and quadratic convergence are studied. In particular, we give a line search rule containing the common used Armijo-type line search rule as a special case. Also without requiring strict complementarity assumption at the P₀-NCP solution or the nonemptyness and boundedness of the solution set, the proposed algorithm is proved to be globally convergent. Preliminary numerical results show the efficiency of the algorithm and provide efficient domains of the two parameters for the complementarity problems.