On KKT points of Celis-Dennis-Tapia subproblem

The Celis-Dennis-Tapia(CDT) problem is a subproblem of the trust region algorithms for the constrained optimization. CDT subproblem is studied in this paper. It is shown that there exists the KKT point such that the Hessian matrix of the Lagrangian is positive semidefinite, if the multipliers at the global solution are not unique. Next the second order optimality conditions are also given, when the Hessian matrix of Lagrange at the solution has one negative eigenvalue. And furthermore, it is proved that all feasible KKT points satisfying that the corresponding Hessian matrices of Lagrange have one negative eigenvalue are the local optimal solutions of the CDT subproblem.     

COMPUTE A CELIS-DENNIS-TAPIA STEP

In this paper,we present an algorithm for the CDT subproblem.This problem stemsfrom computing a trust region step of an algorithm,which was first proposed by Celis,Dennis and Tapia for equality constrained optimization.Our algorithm considers generalcase of the CDT subproblem,convergence of the algorithm is proved.Numerical examplesare also provided.     

A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints

A trust region and affine scaling interior point method (TRAM) is proposed for a general nonlinear minimization with linear inequality constraints [8]. In the proposed approach, a Newton step is derived from the complementarity conditions. Based on this Newton step, a trust region subproblem is formed, and the original objective function is monotonically decreased. Explicit sufficient decrease conditions are proposed for satisfying the first order and second order necessary conditions.?The objective of this paper is to establish global and local convergence properties of the proposed trust region and affine scaling interior point method. It is shown that the proposed explicit decrease conditions are sufficient for satisfy complementarity, dual feasibility and second order necessary conditions respectively. It is also established that a trust region solution is asymptotically in the interior of the proposed trust region subproblem and a properly damped trust region step can achieve quadratic convergence. Received: January 29, 1999 / Accepted: November 22, 1999?Published online February 23, 2000     

Subspace choices for the Celis-Dennis-Tapia problem

Grapiglia et al. (2013) proved subspace properties for the Celis-Dennis-Tapia (CDT) problem. If a subspace with lower dimension is appropriately chosen to satisfy subspace properties, then one can solve the CDT problem in that subspace so that the computational cost can be reduced. We show how to find subspaces that satisfy subspace properties for the CDT problem, by using the eigendecomposition of the Hessian matrix of the objection function. The dimensions of the subspaces are investigated. We also apply the subspace technologies to the trust region subproblem and the quadratic optimization with two quadratic constraints.     

AN ADAPTIVE NONMONOTONIC TRUST REGION METHOD WITH CURVILINEAR SEARCHES

In this paper,an algorithm for unconstrained optimization that employs both trustregion techniques and curvilinear searches is proposed.At every iteration,we solve thetrust region subproblem whose radius is generated adaptively only once.Nonmonotonicbacktracking curvilinear searches are performed when the solution of the subproblem isunacceptable.The global convergence and fast local convergence rate of the proposedalgorithms are established under some reasonable conditions.The results of numericalexperiments are reported to show the effectiveness of the proposed algorithms.     

The convergence of subspace trust region methods

The trust region method is an effective approach for solving optimization problems due to its robustness and strong convergence. However, the subproblem in the trust region method is difficult or time-consuming to solve in practical computation, especially in large-scale problems. In this paper we consider a new class of trust region methods, specifically subspace trust region methods. The subproblem in these methods has an adequate initial trust region radius and can be solved in a simple subspace. It is easier to solve than the original subproblem because the dimension of the subproblem in the subspace is reduced substantially. We investigate the global convergence and convergence rate of these methods.     

A convergence proof for linear mean value cross decomposition

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition that eliminates the need for using the Benders or Dantzig-Wolfe master problem. It is a generalization of the Brown-Robinson method for a finite matrix game and can also be considered as a generalization of the Kornai-Liptak method. It is based on the subproblem phase in cross decomposition, where we iterate between the dual subproblem and the primal subproblem. As input to the dual subproblem we use the average of a part of all dual solutions of the primal subproblem, and as input to the primal subproblem we use the average of a part of all primal solutions of the dual subproblem. In this paper we give a new proof of convergence for this procedure. Previously convergence has only been shown for the application to a special separable case (which covers the Kornai-Liptak method), by showing equivalence to the Brown-Robinson method.     

On the global optimality of generalized trust region subproblems

Quadratically constrained quadratic programming is an important class of optimization problems. We consider the case with one quadratic constraint. Since both the objective function and its constraint can be neither convex nor concave, it is also known as the ‘generalized trust region subproblem.’ The theory and algorithms for this problem have been well studied under the Slater condition. In this article, we analyse the duality property between the primal problem and its Lagrangian dual problem, and discuss the attainability of the optimal primal solution without the Slater condition. The relations between the Lagrangian dual and semidefinite programming dual is also given.     

Global optimization for a class of fractional programming problems

This paper presents a canonical dual approach to minimizing the sum of a quadratic function and the ratio of two quadratic functions, which is a type of non-convex optimization problem subject to an elliptic constraint. We first relax the fractional structure by introducing a family of parametric subproblems. Under proper conditions on the “problem-defining” matrices associated with the three quadratic functions, we show that the canonical dual of each subproblem becomes a one-dimensional concave maximization problem that exhibits no duality gap. Since the infimum of the optima of the parameterized subproblems leads to a solution to the original problem, we then derive some optimality conditions and existence conditions for finding a global minimizer of the original problem. Some numerical results using the quasi-Newton and line search methods are presented to illustrate our approach.     

Numerical experience with a polyhedral-norm CDT trust-region algorithm

In this paper, we study a modification of the Celis-Dennis-Tapia trust-region subproblem, which is obtained by replacing thel ₂-norm with a polyhedral norm. The polyhedral norm Celis-Dennis-Tapia (CDT) subproblem can be solved using a standard quadratic programming code.We include computational results which compare the performance of the polyhedral-norm CDT trust-region algorithm with the performance of existing codes. The numerical results validate the effectiveness of the approach. These results show that there is not much loss of robustness or speed and suggest that the polyhedral-norm CDT algorithm may be a viable alternative. The topic merits further investigation.The first author was supported in part by the REDI foundation and State of Texas Award, Contract 1059 as Visiting Member of the Center for Research on Parallel Computation, Rice University, Houston, Texas, He thanks Rice University for the congenial scientific atmosphere provided. The second author was supported in part by the National Science Foundation, Cooperative Agreement CCR-88-09615, Air Force Office of Scientific Research Grant 89-0363, and Department of Energy Contract DEFG05-86-ER25017.     

A primal-dual trust region algorithm for nonlinear optimization

This paper concerns general (nonconvex) nonlinear optimization when first and second derivatives of the objective and constraint functions are available. The proposed method is based on finding an approximate solution of a sequence of unconstrained subproblems parameterized by a scalar parameter. The objective function of each unconstrained subproblem is an augmented penalty-barrier function that involves both primal and dual variables. Each subproblem is solved using a second-derivative Newton-type method that employs a combined trust region and line search strategy to ensure global convergence. It is shown that the trust-region step can be computed by factorizing a sequence of systems with diagonally-modified primal-dual structure, where the inertia of these systems can be determined without recourse to a special factorization method. This has the benefit that off-the-shelf linear system software can be used at all times, allowing the straightforward extension to large-scale problems. Numerical results are given for problems in the COPS test collection.Mathematics Subject Classification (2000): 49M37, 65F05, 65K05, 90C30This paper is dedicated to Roger Fletcher on the occasion of his 65th birthday     

An algorithm for solving new trust region subproblem with conic model

The new trust region subproblem with the conic model was proposed in 2005, and was divided into three different cases. The first two cases can be converted into a quadratic model or a convex problem with quadratic constraints, while the third one is a nonconvex problem. In this paper, first we analyze the nonconvex problem, and reduce it to two convex problems. Then we discuss some dual properties of these problems and give an algorithm for solving them. At last, we present an algorithm for solving the new trust region subproblem with the conic model and report some numerical examples to illustrate the efficiency of the algorithm.     

Combining nonmonotone conic trust region and line search techniques for unconstrained optimization

In this paper, we propose a trust region method for unconstrained optimization that can be regarded as a combination of conic model, nonmonotone and line search techniques. Unlike in traditional trust region methods, the subproblem of our algorithm is the conic minimization subproblem; moreover, our algorithm performs a nonmonotone line search to find the next iteration point when a trial step is not accepted, instead of resolving the subproblem. The global and superlinear convergence results for the algorithm are established under reasonable assumptions. Numerical results show that the new method is efficient for unconstrained optimization problems.     

An adaptive trust region method and its convergence

In this paper, a new trust region subproblem is proposed. The trust radius in the new subproblem adjusts itself adaptively. As a result, an adaptive trust region method is constructed based on the new trust region subproblem. The local and global convergence results of the adaptive trust region method are proved. Numerical results indicate that the new method is very efficient.     

A new trust region algorithm for bound constrained minimization

We introduce a new algorithm of trust-region type for minimizing a differentiable function of many variables with box constraints. At each step of the algorithm we use an approximation to the minimizer of a quadratic in a box. We introduce a new method for solving this subproblem, that has finite termination without dual nondegeneracy assumptions. We prove the global convergence of the main algorithm and a result concerning the identification of the active constraints in finite time. We describe an implementation of the method and we present numerical experiments showing the effect of solving the subproblem with different degrees of accuracy.This work was supported by FAPESP (Grants 90-3724-6 and 91-2441-3), CNPq, FINEP, and FAEP-UNICAMP.     

Mean value cross decomposition applied to integer programming problems

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition, that eliminates the need for using the Benders or Dantzig-Wolfe master problems. As input to the dual subproblem the average of a part of all known dual solutions of the primal subproblem is used, and as input to the primal subproblem the average of a part of all known primal solutions of the dual subproblem. In this paper we study the lower bounds on the optimal objective function value of (linear) pure integer programming problems obtainable by the application of mean value cross decomposition, and find that this approach can be used to get lower bounds ranging from the bound obtained by the LP-relaxation to the bound obtained by the Lagrangean dual. We examplify by applying the technique to the clustering problem and give some preliminary computational results.     

Combining trust region and linesearch algorithm for equality constrained optimization

In this paper, a combining trust region and line search algorithm for equality constrained optimization is proposed. At each iteration, we only need to solve the trust region subproblem once, when the trust region trial step can not be accepted, we switch to line search to obtain the next iteration. Hence, the difficulty of repeated solving trust region subproblem in an iterate is avoided. In order to allow the direction of negative curvature, we add second correction step in trust region step and employ nommonotone technique in line search. The global convergence and local superlinearly rate are established under certain assumptions. Some numerical examples are given to illustrate the efficiency of the proposed algorithm.     

A dual approach to primal degeneracy

The Revised Primal Simplex algorithm, in its simplest form, has no defence against degeneracy. Various forms of the perturbation method are usually effective, but most offer no guarantee of avoiding all degeneracy, and can lead to numerical difficulties. This paper presents a method that avoids cycling and circling by taking a dual approach.The degenerate subproblem consists of all the original variables, but only the degenerate transformed constraints. The current primal objective, which may be mixed, is used. This subproblem may be solved using the dual simplex algorithm, starting from the current dual infeasible solution, and with a zero dual objective. If the dual algorithm terminates optimally then the whole problem is optimal (subject to primal feasibility). Otherwise the final solution provides a non-basic direction which improves the value of the mixed primal objective and moves away from the degenerate vertex. A purification algorithm then renders the solution basic and further improves the mixed objective.     

Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem

For optimization problems that are structured both with respect to the constraints and with respect to the variables, it is possible to use primal–dual solution approaches, based on decomposition principles. One can construct a primal subproblem, by fixing some variables, and a dual subproblem, by relaxing some constraints and king their Lagrange multipliers, so that both these problems are much easier to solve than the original problem. We study methods based on these subproblems, that do not include the difficult Benders or Dantzig-Wolfe master problems, namely primal–dual subgradient optimization methods, mean value cross decomposition, and several comtbinations of the different techniques. In this paper, these solution approaches are applied to the well-known uncapacitated facility location problem. Computational tests show that some combination methods yield near-optimal solutions quicker than the classical dual ascent method of Erlenkotter     

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.