Sequential quadratically constrained quadratic programming norm-relaxed algorithm of strongly sub-feasible directions

In this paper, we present a sequential quadratically constrained quadratic programming (SQCQP) norm-relaxed algorithm of strongly sub-feasible directions for the solution of inequality constrained optimization problems. By introducing a new unified line search and making use of the idea of strongly sub-feasible direction method, the proposed algorithm can well combine the phase of finding a feasible point (by finite iterations) and the phase of a feasible descent norm-relaxed SQCQP algorithm. Moreover, the former phase can preserve the “sub-feasibility” of the current iteration, and control the increase of the objective function. At each iteration, only a consistent convex quadratically constrained quadratic programming problem needs to be solved to obtain a search direction. Without any other correctional directions, the global, superlinear and a certain quadratic convergence (which is between 1-step and 2-step quadratic convergence) properties are proved under reasonable assumptions. Finally, some preliminary numerical results show that the proposed algorithm is also encouraging.     

Global optimization of a class of nonconvex quadratically constrained quadratic programming problems

In this paper we study a class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.     

A Sequential Quadratically Constrained Quadratic Programming Method of Feasible Directions

In this paper, a sequential quadratically constrained quadratic programming method of feasible directions is proposed for the optimization problems with nonlinear inequality constraints. At each iteration of the proposed algorithm, a feasible direction of descent is obtained by solving only one subproblem which consist of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the functions of the discussed problems, and such a subproblem can be formulated as a second-order cone programming which can be solved by interior point methods. To overcome the Maratos effect, an efficient higher-order correction direction is obtained by only one explicit computation formula. The algorithm is proved to be globally convergent and superlinearly convergent under some mild conditions without the strict complementarity. Finally, some preliminary numerical results are reported. Project supported by the National Natural Science Foundation (No. 10261001), Guangxi Science Foundation (Nos. 0236001, 064001), and Guangxi University Key Program for Science and Technology Research (No. 2005ZD02) of China.     

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.     

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.     

A sequential quadratically constrained quadratic programming method for unconstrained minimax problems

In this paper, a sequential quadratically constrained quadratic programming (SQCQP) method for unconstrained minimax problems is presented. At each iteration the SQCQP method solves a subproblem that involves convex quadratic inequality constraints and a convex quadratic objective function. The global convergence of the method is obtained under much weaker conditions without any constraint qualification. Under reasonable assumptions, we prove the strong convergence, superlinearly and quadratic convergence rate.     

A relaxation method for nonconvex quadratically constrained quadratic programs

We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch and bound with linear programming subproblems. When the feasible set is non-convex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.This research was supported in part by National Science Foundation Grant DDM-91-14489.     

Least squares problems with inequality constraints as quadratic constraints

Linear least squares problems with box constraints are commonly solved to find model parameters within bounds based on physical considerations. Common algorithms include Bounded Variable Least Squares (BVLS) and the Matlab function lsqlin. Here, the goal is to find solutions to ill-posed inverse problems that lie within box constraints. To do this, we formulate the box constraints as quadratic constraints, and solve the corresponding unconstrained regularized least squares problem. Using box constraints as quadratic constraints is an efficient approach because the optimization problem has a closed form solution. The effectiveness of the proposed algorithm is investigated through solving three benchmark problems and one from a hydrological application. Results are compared with solutions found by lsqlin, and the quadratically constrained formulation is solved using the L-curve, maximum a posteriori estimation (MAP), and the χ² regularization method. The χ² regularization method with quadratic constraints is the most effective method for solving least squares problems with box constraints.     

A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method; nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.     

A new approach to the weighted peak-constrained least-square error FIR digital filter optimal design problem

This paper deals with the design of linear-phase finite impulse response (FIR) digital filters using weighted peak-constrained least-squares (PCLS) optimization. The PCLS error design problem is formulated as a quadratically constrained quadratic semi-infinite programming problem. An exchange algorithm with a new exchange rule is proposed to solve the problem. The algorithm provides the approximate optimal solution after a finite number of iterations. In particular, the subproblem solved at each iteration is a quadratically constrained quadratic programming. We can rewrite it as a conic optimization problem solvable in polynomial time. For illustration, numerical examples are solved using the proposed algorithm.     

An SQP approach with line search for a system of nonlinear equations

In this paper, a line search sequential quadratic programming (SQP) approach to a system of nonlinear equations (SNE) is taken. In this method, the system of nonlinear equations is transformed into a constrained nonlinear programming problem at each step, which is then solved using SQP algorithms with a line search strategy. Furthermore, at each step, some equations, which are satisfied at the current point, are treated as constraints and the others act as objective functions. In essence, constrained optimization strategies are utilized to cope with the system of nonlinear equations.     

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 active set strategy for solving optimization problems with up to 200,000,000 nonlinear constraints

Numerical test results are presented for solving smooth nonlinear programming problems with a large number of constraints, but a moderate number of variables. The active set method proceeds from a given bound for the maximum number of expected active constraints at an optimal solution, which must be less than the total number of constraints. A quadratic programming subproblem is generated with a reduced number of linear constraints from the so-called working set, which is internally changed from one iterate to the next. Only for active constraints, i.e., a certain subset of the working set, new gradient values must be computed. The line search is adapted to avoid too many active constraints which do not fit into the working set. The active set strategy is an extension of an algorithm described earlier by the author together with a rigorous convergence proof. Numerical results for some simple academic test problems show that nonlinear programs with up to 200,000,000 nonlinear constraints are efficiently solved on a standard PC.     

Dynamic Programming Method for Constrained Discrete-Time Optimal Control

A dynamic programming method is presented for solving constrained, discrete-time, optimal control problems. The method is based on an efficient algorithm for solving the subproblems of sequential quadratic programming. By using an interior-point method to accommodate inequality constraints, a modification of an existing algorithm for equality constrained problems can be used iteratively to solve the subproblems. Two test problems and two application problems are presented. The application examples include a rest-to-rest maneuver of a flexible structure and a constrained brachistochrone problem.     

A branch and bound network approach to the canonical constrained entropy problem

In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved.     

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

Adaptive Algorithm for Constrained Least-Squares Problems

This paper is concerned with the implementation and testing of an algorithm for solving constrained least-squares problems. The algorithm is an adaptation to the least-squares case of sequential quadratic programming (SQP) trust-region methods for solving general constrained optimization problems. At each iteration, our local quadratic subproblem includes the use of the Gauss–Newton approximation but also encompasses a structured secant approximation along with tests of when to use this approximation. This method has been tested on a selection of standard problems. The results indicate that, for least-squares problems, the approach taken here is a viable alternative to standard general optimization methods such as the Byrd–Omojokun trust-region method and the Powell damped BFGS line search method.     

并行求解约束优化问题的QP-free型算法

针对约束块可分的最优化问题,引入序列线性方程组方法和有效集策略,提出了一个求解约束块可分优化问题的QP-free型并行变量分配（PVD）算法.算法中用三个系数具有对称结构的线性方程组来代替PVD算法中的二次规划问题以求解线搜索方向,避免了约束不相容,减小了计算量.并且算法不要求约束是凸的.最后证明了QP-free型PVD算法的全局收敛性.     

Efficient Sequential Quadratic Programming Implementations for Equality-Constrained Discrete-Time Optimal Control

Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N ³. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction.     

A New Quadratic Semi-infinite Programming Algorithm Based on Dual Parametrization

The so called dual parameterization method for quadratic semi-infinite programming (SIP) problems is developed recently. A dual parameterization algorithm is also proposed for numerical solution of such problems. In this paper, we present and improved adaptive algorithm for quadratic SIP problems with positive definite objective and multiple linear infinite constraints. In each iteration of the new algorithm, only a quadratic programming problem with a limited dimension and a limited number of constraints is required to be solved. Furthermore, convergence result is given. The efficiency of the new algorithm is shown by solving a number of numerical examples.