Convex Semi-Infinite Programming: Implicit Optimality Criterion Based on the Concept of Immobile Indices

We state a new implicit optimality criterion for convex semi-infinite programming (SIP) problems. This criterion does not require any constraint qualification and is based on concepts of immobile index and immobility order. Given a convex SIP problem with a continuum of constraints, we use an information about its immobile indices to construct a nonlinear programming (NLP) problem of a special form. We prove that a feasible point of the original infinite SIP problem is optimal if and only if it is optimal in the corresponding finite NLP problem. This fact allows us to obtain new efficient optimality conditions for convex SIP problems using known results of the optimality theory of NLP. To construct the NLP problem, we use the DIO algorithm. A comparison of the optimality conditions obtained in the paper with known results is provided.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

Nonlinear robust optimization via sequential convex bilevel programming

In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min–max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curvature of the inequality constraints with respect to the uncertainty is given, we show how to formulate a lower-level concave min–max problem which approximates the robust counterpart in a conservative way. This approximation turns out to be exact in some relevant special cases and can be proven to be less conservative than existing approximation techniques that are based on linearization with respect to the uncertainties. In the second part of the paper, we review existing theory on optimality conditions for nonlinear lower-level concave min–max problems which arise in the context of semi-infinite programming. Regarding the optimality conditions for the concave lower level maximization problems as a constraint of the upper level minimization problem, we end up with a structured mathematical program with complementarity constraints (MPCC). The special hierarchical structure of this MPCC can be exploited in a novel sequential convex bilevel programming algorithm. We discuss the surprisingly strong global and locally quadratic convergence properties of this method, which can in this form neither be obtained with existing SQP methods nor with interior point relaxation techniques for general MPCCs. Finally, we discuss the application fields and implementation details of the new method and demonstrate the performance with a numerical example.     

求解随机凸规划概率约束问题的对偶算法

1引言随机规划中的概率约束问题在工程和管理中有广泛的应用.因为问题中包含非线性的概率约束,它们的求解非常困难.如果目标函数是线性的,问题的求解就比较容易.给出了一个求解随机线性规划概率约束问题的综述.原-对偶算法和切平面算法是比较有效的.在本文中,我们讨论随机凸规划概率约束问题:     

An SQP-type algorithm for nonlinear second-order cone programs

We propose an SQP-type algorithm for solving nonlinear second-order cone programming (NSOCP) problems. At every iteration, the algorithm solves a convex SOCP subproblem in which the constraints involve linear approximations of the constraint functions in the original problem and the objective function is a convex quadratic function. Those subproblems can be transformed into linear SOCP problems, for which efficient interior point solvers are available. We establish global convergence and local quadratic convergence of the algorithm under appropriate assumptions. We report numerical results to examine the effectiveness of the algorithm. This work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

A new reformulation-linearization technique for bilinear programming problems

This paper is concerned with the development of an algorithm for general bilinear programming problems. Such problems find numerous applications in economics and game theory, location theory, nonlinear multi-commodity network flows, dynamic assignment and production, and various risk management problems. The proposed approach develops a new Reformulation-Linearization Technique (RLT) for this problem, and imbeds it within a provably convergent branch-and-bound algorithm. The method first reformulates the problem by constructing a set of nonnegative variable factors using the problem constraints, and suitably multiplies combinations of these factors with the original problem constraints to generate additional valid nonlinear constraints. The resulting nonlinear program is subsequently linearized by defining a new set of variables, one for each nonlinear term. This RLT process yields a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. Various implementation schemes and constraint generation procedures are investigated for the purpose of further tightening the resulting linearization. The lower bound thus produced theoretically dominates, and practically is far tighter, than that obtained by using convex envelopes over hyper-rectangles. In fact, for some special cases, this process is shown to yield an exact linear programming representation. For the associated branch-and-bound algorithm, various admissible branching schemes are discussed, including one in which branching is performed by partitioning the intervals for only one set of variables x or y, whichever are fewer in number. Computational experience is provided to demonstrate the viability of the algorithm. For a large number of test problems from the literature, the initial bounding linear program itself solves the underlying bilinear programming problem.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

Analytic efficient solution set for multi-criteria quadratic programs

We present active set methods to evaluate the exact analytic efficient solution set for multi-criteria convex quadratic programming problems (MCQP) subject to linear constraints. The idea is based on the observations that a strictly convex programming problem admits a unique solution, and that the efficient solution set for a multi-criteria strictly convex quadratic programming problem with linear equality constraints can be parameterized. The case of bi-criteria quadratic programming (BCQP) is first discussed since many of the underlying ideas can be explained much more clearly in the case of two objectives. In particular we note that the efficient solution set of a BCQP problem is a curve on the surface of a polytope. The extension to problems with more than two objectives is straightforward albeit some slightly more complicated notation. Two numerical examples are given to illustrate the proposed methods.     

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.     

Dual Semidefinite Programs Without Duality Gaps for a Class of Convex Minimax Programs

In this paper, we introduce a new dual program, which is representable as a semidefinite linear programming problem, for a primal convex minimax programming problem, and we show that there is no duality gap between the primal and the dual whenever the functions involved are sum-of-squares convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust sum-of-squares convex programming problems under data uncertainty and to minimax fractional programming problems with sum-of-squares convex polynomials. We obtain these results by first establishing sum-of-squares polynomial representations of non-negativity of a convex max function over a system of sum-of-squares convex constraints. The new class of sum-of-squares convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The sum-of-squares convexity of polynomials can numerically be checked by solving semidefinite programming problems whereas numerically verifying convexity of polynomials is generally very hard.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

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.     

Some Farkas-type results for fractional programming problems with DC functions

For a kind of fractional programming problem that the objective functions are the ratio of two DC (difference of convex) functions with finitely many convex constraints, in this paper, its dual problems are constructed, weak and strong duality assertions are given, and some sufficient and necessary optimality conditions which characterize their optimal solutions are obtained. Some recently obtained Farkas-type results for fractional programming problems that the objective functions are the ratio of a convex function to a concave function with finitely many convex constraints are the special cases of the general results of this paper.     

ℓ1-Minimization with Magnitude Constraints in the Frequency Domain

In this paper, we study the -optimal control problem with additional constraints on the magnitude of the closed-loop frequency response. In particular, we study the case of magnitude constraints at fixed frequency points (a finite number of such constraints can be used to approximate an -norm constraint). In previous work, we have shown that the primal-dual formulation for this problem has no duality gap and both primal and dual problems are equivalent to convex, possibly infinite-dimensional, optimization problems with LMI constraints. Here, we study the effect of approximating the convex magnitude constraints with a finite number of linear constraints and provide a bound on the accuracy of the approximation. The resulting problems are linear programs. In the one-block case, both primal and dual programs are semi-infinite dimensional. The optimal cost can be approximated, arbitrarily well from above and within any predefined accuracy from below, by the solutions of finite-dimensional linear programs. In the multiblock case, the approximate LP problem (as well as the exact LMI problem) is infinite-dimensional in both the variables and the constraints. We show that the standard finite-dimensional approximation method, based on approximating the dual linear programming problem by sequences of finite-support problems, may fail to converge to the optimal cost of the infinite-dimensional problem.     

Optimal coverage of convex regions

The problem of the coverage of convex regions with polygons and quadratic configurations of minimal volume is considered. The regions are presented as inequality constraints of a linear or nonlinear programming problem. It is shown that the problem of the optimal coverage with an arbitrary polygon can be reduced to a convex one of coverage with a multidimensional rectangle. If, however, rotation of the coordinate system is allowed, an additional nonconvex problem must be solved. It is also shown that, to find the minimal covering hypersphere or hyperellipsoid, one has to solve two convex programming problems. Algorithms and examples illustrating the feasibility of the proposed methods are presented.This work was supported by funds for the promotion of research at the Technion under Contract No. 190-515.The authors would like to express their indebtedness to Prof. Aharon Ben-Tal from Technion and to Prof. L. C. W. Dixon of the Hatfield Polytechnic for several valuable suggestions on an earlier draft of this paper.     

Robust nonlinear optimization with conic representable uncertainty set

The robust optimization methodology is known as a popular method dealing with optimization problems with uncertain data and hard constraints. This methodology has been applied so far to various convex conic optimization problems where only their inequality constraints are subject to uncertainty. In this paper, the robust optimization methodology is applied to the general nonlinear programming (NLP) problem involving both uncertain inequality and equality constraints. The uncertainty set is defined by conic representable sets, the proposed uncertainty set is general enough to include many uncertainty sets, which have been used in literature, as special cases. The robust counterpart (RC) of the general NLP problem is approximated under this uncertainty set. It is shown that the resulting approximate RC of the general NLP problem is valid in a small neighborhood of the nominal value. Furthermore a rather general class of programming problems is posed that the robust counterparts of its problems can be derived exactly under the proposed uncertainty set. Our results show the applicability of robust optimization to a wider area of real applications and theoretical problems with more general uncertainty sets than those considered so far. The resulting robust counterparts which are traditional optimization problems make it possible to use existing algorithms of mathematical optimization to solve more complicated and general robust optimization problems.     

Solving Problems with Semidefinite and Related Constraints Using Interior-Point Methods for Nonlinear Programming

 In this paper, we describe how to reformulate a problem that has second-order cone and/or semidefiniteness constraints in order to solve it using a general-purpose interior-point algorithm for nonlinear programming. The resulting problems are smooth and convex, and numerical results from the DIMACS Implementation Challenge problems and SDPLib are provided. Received: March 10, 2001 / Accepted: January 18, 2002 Published online: September 27, 2002 Key Words. semidefinite programming – second-order cone programming – interior-point methods – nonlinear programming Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

Generalized Convex Disjunctive Programming: Nonlinear Convex Hull Relaxation

Generalized Disjunctive Programming (GDP) has been introduced recently as an alternative to mixed-integer programming for representing discrete/continuous optimization problems. The basic idea of GDP consists of representing these problems in terms of sets of disjunctions in the continuous space, and logic propositions in terms of Boolean variables. In this paper we consider GDP problems involving convex nonlinear inequalities in the disjunctions. Based on the work by Stubbs and Mehrotra [21] and Ceria and Soares [6], we propose a convex nonlinear relaxation of the nonlinear convex GDP problem that relies on the convex hull of each of the disjunctions that is obtained by variable disaggregation and reformulation of the inequalities. The proposed nonlinear relaxation is used to formulate the GDP problem as a Mixed-Integer Nonlinear Programming (MINLP) problem that is shown to be tighter than the conventional big-M formulation. A disjunctive branch and bound method is also presented, and numerical results are given for a set of test problems.     

A conic quadratic formulation for a class of convex congestion functions in network flow problems

In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be efficiently formulated by using conic quadratic inequalities. As most of the research on this problem is devoted to heuristic approaches, this study differs in showing that the problem can be solved to optimum by branch-and-bound solvers implementing the second-order cone programming (SOCP) algorithms. Computational experiments on the test problems from the literature show that the continuous relaxation of the formulation gives a tight lower bound and leads to optimal or near optimal integer solutions within reasonable CPU times.     

On the Pironneau-Polak method of centers

The method of centers is a well-known method for solving nonlinear programming problems having inequality constraints. Pironneau and Polak have recently presented a new version of this method. In the new method, the direction of search is obtained, at each iteration, by solving a convex quadratic programming problem. This direction finding subprocedure is essentially insensitive to the dimension of the space on which the problem is defined. Moreover, the method of Pironneau and Polak is known to converge linearly for finite-dimensional convex programs for which the objective function has a positive-definite Hessian near the solution (and for which the functions involved are twice continuously differentiable). In the present paper, the method and a completely implementable version of it are shown to converge linearly for a very general class of finite-dimensional problems; the class is determined by a second-order sufficiency condition and includes both convex and nonconvex problems. The arguments employed here are based on the indirect sufficiency method of Hestenes. Furthermore, the arguments can be modified to prove linear convergence for a certain class of infinite-dimensional convex problems, thus providing an answer to a conjecture made by Pironneau and Polak.