A globally contergent method for nonlinear programming

In this paper a new method for solving the nonlinear programming problem with equality and inequality constraints is presented. With the aid of feasibility functions the feasible region is blown up so that the enlarged region has interior points. Then, under certain assumptions, the solution of the original problem is achieved by constructing a sequence of points which are optimal for the perturbed problems. These are solved by a method of feasible directions for which usable feasible directions can be given in an explicit form.     

Initialization in semidefinite programming via a self-dual skew-symmetric embedding

The formulation of interior point algorithms for semidefinite programming has become an active research area, following the success of the methods for large-scale linear programming. Many interior point methods for linear programming have now been extended to the more general semidefinite case, but the initialization problem remained unsolved.In this paper we show that the initialization strategy of embedding the problem in a self-dual skew-symmetric problem can also be extended to the semidefinite case. This method also provides a solution for the initialization of quadratic programs and it is applicable to more general convex problems with conic formulation.     

Interior Point Algorithms in Linear Optimization

This is a survey of the results concerning the development and study of the interior point algorithms. Some families of the direct and dual algorithms are considered. These algorithms entering the domain of feasible solutions take into account the objective function, which makes it possible to obtain the first feasible solution close to the optimal solution. The main results on the theoretical justification of algorithms are given. Recommendations are proposed concerning the advantages of individual variants of algorithms on the basis of the obtained theoretical results, available experimental studies, and experience of using algorithms in the models of energy engineering. Some numerically efficient version of the polynomial optimization algorithm in the cone of the central path is also presented.     

Improve-and-Branch Algorithm for the Global Optimization of Nonconvex NLP Problems

A new algorithm to solve nonconvex NLP problems is presented. It is based on the solution of two problems. The reformulated problem RP is a suitable reformulation of the original problem and involves convex terms and concave univariate terms. The main problem MP is a nonconvex NLP that outer-approximates the feasible region and underestimate the objective function. MP involves convex terms and terms which are the products of concave univariate functions and new variables. Fixing the variables in the concave terms, a convex NLP that overestimates the feasible region and underestimates the objective function is obtained from the MP. Like most of the deterministic global optimization algorithms, bounds on all the variables in the nonconvex terms must be provided. MP forces the objective value to improve and minimizes the difference of upper and lower bound of all the variables either to zero or to a positive value. In the first case, a feasible solution of the original problem is reached and the objective function is improved. In general terms, the second case corresponds to an infeasible solution of the original problem due to the existence of gaps in some variables. A branching procedure is performed in order to either prove that there is no better solution or reduce the domain, eliminating the local solution of MP that was found. The MP solution indicates a key point to do the branching. A bound reduction technique is implemented to accelerate the convergence speed. Computational results demonstrate that the algorithm compares very favorably to other approaches when applied to test problems and process design problems. It is typically faster and it produces very accurate results.     

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.     

求解退化单调线性互补问题极大互补解的复杂性

本文考虑求解退化单调线性互补问题的一类不可行内点算法，其中嵌入一个恢复算法，给出了用这类算法产生所考虑问题的一个精确极大互补解的复杂性．     

New stopping criteria for detecting infeasibility in conic optimization

Detecting infeasibility in conic optimization and providing certificates for infeasibility pose a bigger challenge than in the linear case due to the lack of strong duality. In this paper we generalize the approximate Farkas lemma of Todd and Ye (Math Program 81:1–22, 1998) from the linear to the general conic setting, and use it to propose stopping criteria for interior point algorithms using self-dual embedding. The new criteria can identify if the solutions have large norm, thus they give an indication of infeasibility. The modified algorithms enjoy the same complexity bounds as the original ones, without assuming that the problem is feasible. Issues about the practical application of the criteria are also discussed. The authors were supported by the Canada Research Chairs program, NSERC Discovery Grant #5-48923 and MITACS.     

A polynomial path-following interior point algorithm for general linear complementarity problems

Linear Complementarity Problems (LCPs) belong to the class of \mathbbNP{\mathbb{NP}} -complete problems. Therefore we cannot expect a polynomial time solution method for LCPs without requiring some special property of the coefficient matrix. Our aim is to construct interior point algorithms which, according to the duality theorem in EP (Existentially Polynomial-time) form, in polynomial time either give a solution of the original problem or detects the lack of property P_*([(k)\tilde]){\mathcal{P}_*(\tilde\kappa)} , with arbitrary large, but apriori fixed [(k)\tilde]{\tilde\kappa}). In the latter case, the algorithms give a polynomial size certificate depending on parameter [(k)\tilde]{\tilde{\kappa}} , the initial interior point and the input size of the LCP). We give the general idea of an EP-modification of interior point algorithms and adapt this modification to long-step path-following interior point algorithms.     

Approximate proximal methods in vector optimization

This paper studies the vector optimization problem of finding weakly efficient points for mappings in a Banach space Y, with respect to the partial order induced by a closed, convex, and pointed cone C ⊂ Y with a nonempty interior. The proximal method in vector optimization is extended to develop an approximate proximal method for this problem by virtue of the approximate proximal point method for finding a root of a maximal monotone operator. In this approximate proximal method, the subproblems consist of finding weakly efficient points for suitable regularizations of the original mapping. We present both an absolute and a relative version, in which the subproblems are solved only approximately. Weak convergence of the generated sequence to a weak efficient point is established. In addition, we also discuss an extension to Bregman-function-based proximal algorithms for finding weakly efficient points for mappings.     

Dual interior point algorithms

For a linear programming problem stated in the canonical form we consider the dual problem and describe a class of interior point algorithms which generate monotonically improving approximations to its solution. We theoretically substantiate the optimization process in the admissible domain under the assumption that the dual problem is nondegenerate. In addition, we describe subsets of algorithms that lead to relative interior points of optimal solutions. These algorithms have linear and superlinear convergence rates. Moreover, we obtain a special subset of algorithms which generate iterative sequences of approximations to a solution of the direct problem, whose convergence rate exceeds that of the sequences of monotonically improving approximations to a solution of the dual problem.     

A simple characterization of solution sets of convex programs

By means of elementary arguments we first show that the gradient of the objective function of a convex program is constant on the solution set of the problem. Furthermore the solution set lies in an affine subspace orthogonal to this constant gradient, and is in fact in the intersection of this affine subspace with the feasible region. As a consequence we give a simple polyhedral characterization of the solution set of a convex quadratic program and that of a monotone linear complementarity problem. For these two problems we can also characterize a priori the boundedness of their solution sets without knowing any solution point. Finally we give an extension to non-smooth convex optimization by showing that the intersection of the subdifferentials of the objective function on the solution set is non-empty and equals the constant subdifferential of the objective function on the relative interior of the optimal solution set. In addition, the solution set lies in the intersection with the feasible region of an affine subspace orthogonal to some subgradient of the objective function at a relative interior point of the optimal solution set.     

Optimization of Algorithmic Parameters using a Meta-Control Approach*

Optimization algorithms usually rely on the setting of parameters, such as barrier coefficients. We have developed a generic meta-control procedure to optimize the behavior of given iterative optimization algorithms. In this procedure, an optimal continuous control problem is defined to compute the parameters of an iterative algorithm as control variables to achieve a desired behavior of the algorithm (e.g., convergence time, memory resources, and quality of solution). The procedure is illustrated with an interior point algorithm to control barrier coefficients for constrained nonlinear optimization. Three numerical examples are included to demonstrate the enhanced performance of this method. This work was primarily done when Z. Zabinsky was visiting Clearsight Systems Inc.     

自对偶嵌入模型解拓展熵规划

本文把拓展熵规划转化为锥最优化问题,再对该锥最优化问题构造一个锥自对偶嵌入模型,证明了锥自对偶嵌入模型的障碍函数满足自协调性,这保证了用某些内点法求解时算法是多项式时间的.这种方法的另一个优点是不需要寻找初始可行解.     

An Interior Point Algorithm for Mixed Complementarity Nonlinear Problems

Nonlinear complementarity and mixed complementarity problems arise in mathematical models describing several applications in Engineering, Economics and different branches of physics. Previously, robust and efficient feasible directions interior point algorithm was presented for nonlinear complementarity problems. In this paper, it is extended to mixed nonlinear complementarity problems. At each iteration, the algorithm finds a feasible direction with respect to the region defined by the inequality conditions, which is also monotonic descent direction for the potential function. Then, an approximate line search along this direction is performed in order to define the next iteration. Global and asymptotic convergence for the algorithm is investigated. The proposed algorithm is tested on several benchmark problems. The results are in good agreement with the asymptotic analysis. Finally, the algorithm is applied to the elastic–plastic torsion problem encountered in the field of Solid Mechanics.     

基于中心路径大邻域上的一类非单调线性互补问题的高阶可行内点算法

In this paper a high-order feasible interior point algorithm for a class of nonmonotonic (P-matrix) linear complementary problem based on large neighborhoods of central path is presented and its iteration complexity is discussed.These algorithms are implicitly associated with a large neighborhood whose size may depend on the dimension of the problems. The complexity of these algorithms bound depends on the size of the neighborhood. It is well known that the complexity of large-step algorithms is greater than that of short- step ones. By using high-order power series (hence the name high-order algorithms), the iteration complexity can be reduced. We show that the upper bound of complexity for our high-order algorithms is equal to that for short-step algorithms.     

Solving the logit-based stochastic user equilibrium problem with elastic demand based on the extended traffic network model

This paper proposes a novel extended traffic network model to solve the logit-based stochastic user equilibrium (SUE) problem with elastic demand. In this model, an extended traffic network is established by properly adding dummy nodes and links to the original traffic network. Based on the extended traffic network, the logit-based SUE problem with elastic demand is transformed to the SUE problem with fixed demand. Such problem is then further converted to a linearly constrained convex programming and addressed by a predictor–corrector interior point algorithm with polynomial complexity. A numerical example is provided to compare the proposed model with the method of successive averages (MSA). The numerical results indicate that the proposed model is more efficient and has a better convergence than the MSA.     

Simulated annealing for constrained global optimization

Hide-and-Seek is a powerful yet simple and easily implemented continuous simulated annealing algorithm for finding the maximum of a continuous function over an arbitrary closed, bounded and full-dimensional body. The function may be nondifferentiable and the feasible region may be nonconvex or even disconnected. The algorithm begins with any feasible interior point. In each iteration it generates a candidate successor point by generating a uniformly distributed point along a direction chosen at random from the current iteration point. In contrast to the discrete case, a single step of this algorithm may generateany point in the feasible region as a candidate point. The candidate point is then accepted as the next iteration point according to the Metropolis criterion parametrized by anadaptive cooling schedule. Again in contrast to discrete simulated annealing, the sequence of iteration points converges in probability to a global optimum regardless of how rapidly the temperatures converge to zero. Empirical comparisons with other algorithms suggest competitive performance by Hide-and-Seek.This material is based on work supported by a NATO Collaborative Research Grant, no. 0119/89.     

An Exact Reformulation Algorithm for Large Nonconvex NLPs Involving Bilinear Terms

Many nonconvex nonlinear programming (NLP) problems of practical interest involve bilinear terms and linear constraints, as well as, potentially, other convex and nonconvex terms and constraints. In such cases, it may be possible to augment the formulation with additional linear constraints (a subset of Reformulation-Linearization Technique constraints) which do not affect the feasible region of the original NLP but tighten that of its convex relaxation to the extent that some bilinear terms may be dropped from the problem formulation. We present an efficient graph-theoretical algorithm for effecting such exact reformulations of large, sparse NLPs. The global solution of the reformulated problem using spatial Branch-and Bound algorithms is usually significantly faster than that of the original NLP. We illustrate this point by applying our algorithm to a set of pooling and blending global optimization problems.     

On finitely convergent iterative methods for the convex feasibility problem

Iterative algorithms for the Convex Feasibility Problem can be modified so that at iterationk the original convex sets are perturbed with a parameter ε_k which tends to zero ask increases. We establish conditions on such algorithms which guarantee existence of a sequence of perturbation parameters which make them finitely convergent when applied to a convex feasibility problem whose feasible set has non empty interior.     

A primal-dual interior point method for optimal zero-forcing beamformer design under per-antenna power constraints

In this paper, we consider an optimal zero-forcing beamformer design problem in multi-user multiple-input multiple-output broadcast channel. The minimum user rate is maximized subject to zero-forcing constraints and power constraint on each base station antenna array element. The natural formulation leads to a nonconvex optimization problem. This problem is shown to be equivalent to a convex optimization problem with linear objective function, linear equality and inequality constraints and quadratic inequality constraints. Here, the indirect elimination method is applied to reduce the convex optimization problem into an equivalent convex optimization problem of lower dimension with only inequality constraints. The primal-dual interior point method is utilized to develop an effective algorithm (in terms of computational efficiency) via solving the modified KKT equations with Newton method. Numerical simulations are carried out. Compared to algorithms based on a trust region interior point method and sequential quadratic programming method, it is observed that the method proposed is much superior in terms of computational efficiency.