共查询到20条相似文献,搜索用时 15 毫秒
1.
A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical
learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by
second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral
conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that
solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the
branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order
conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are
nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear
cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming.
We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance
capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that
conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer
programs and, hence, improving their solvability.
This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation. 相似文献
2.
This work shows how disjunctive cuts can be generated for a bilevel linear programming problem (BLP) with continuous variables.
First, a brief summary on disjunctive programming and bilevel programming is presented. Then duality theory is used to reformulate
BLP as a disjunctive program and, from there, disjunctive programming results are applied to derive valid cuts. These cuts
tighten the domain of the linear relaxation of BLP. An example is given to illustrate this idea, and a discussion follows
on how these cuts may be incorporated in an algorithm for solving BLP. 相似文献
3.
Global Optimization Issues in Multiparametric Continuous and Mixed-Integer Optimization Problems 总被引:6,自引:3,他引:3
In this paper, a number of theoretical and algorithmic issues concerning the solution of parametric nonconvex programs are presented. In particular, the need for defining a suitable overestimating subproblem is discussed in detail. The multiparametric case is also addressed, and a branch and bound (B&B) algorithm for the solution of parametric nonconvex programs is proposed. 相似文献
4.
5.
Pedro Jiménez Guerra Miguel Angel Melguizo María J. Mu?oz-Bouzo 《Set-Valued Analysis》2007,15(1):47-59
The paper deals with the properties of a conic set-valued function defined on the set of all ideal points of vector programming
problems. The results here about the continuity and derivability of this conic set-valued map, can be used to get information
about the sensitivity of the problem and the stability of the order associated to every ideal point. Furthermore, it is proved
that certain contingent cones are determined by the ideal conic set-valued map.
相似文献
6.
Jongen H. T. Rückmann J. J. Stein O. 《Journal of Optimization Theory and Applications》1997,93(2):321-336
In this paper, we introduce the concepts of (nondegenerate) stationary points and stationary index for disjunctive optimization problems. Two basic theorems from Morse theory, which imply the validity of the (standard) Morse relations, are proved. The first one is a deformation theorem which applies outside the stationary point set. The second one is a cell-attachment theorem which applies at nondegenerate stationary points. The dimension of the cell to be attached equals the stationary index. Here, the stationary index depends on both the restricted Hessian of the Lagrangian and the set of active inequality constraints. In standard optimization problems, the latter contribution vanishes. 相似文献
7.
8.
9.
In earlier proposals, the robust counterpart of conic optimization problems exhibits a lateral increase in complexity, i.e.,
robust linear programming problems (LPs) become second order cone problems (SOCPs), robust SOCPs become semidefinite programming
problems (SDPs), and robust SDPs become NP-hard. We propose a relaxed robust counterpart for general conic optimization problems
that (a) preserves the computational tractability of the nominal problem; specifically the robust conic optimization problem retains
its original structure, i.e., robust LPs remain LPs, robust SOCPs remain SOCPs and robust SDPs remain SDPs, and (b) allows us to provide a guarantee on the probability that the robust solution is feasible when the uncertain coefficients
obey independent and identically distributed normal distributions.
The research of the author was partially supported by the Singapore-MIT alliance.
The research of the author is supported by NUS academic research grant R-314-000-066-122 and the Singapore-MIT alliance. 相似文献
10.
In this paper, we formulate the l
p
-norm optimization problem as a conic optimization problem, derive its duality properties (weak duality, zero duality gap, and primal attainment) using standard conic duality and show how it can be solved in polynomial time applying the framework of interior-point algorithms based on self-concordant barriers. 相似文献
11.
In the conic optimization problems, it is well-known that a positive duality gap may occur, and that solving such a problem is numerically difficult or unstable. For such a case, we propose a facial reduction algorithm to find a primal–dual pair of conic optimization problems having the zero duality gap and the optimal value equal to one of the original primal or dual problems. The conic expansion approach is also known as a method to find such a primal–dual pair, and in this paper we clarify the relationship between our facial reduction algorithm and the conic expansion approach. Our analysis shows that, although they can be regarded as dual to each other, our facial reduction algorithm has ability to produce a finer sequence of faces of the cone including the feasible region. A simple proof of the convergence of our facial reduction algorithm for the conic optimization is presented. We also observe that our facial reduction algorithm has a practical impact by showing numerical experiments for graph partition problems; our facial reduction algorithm in fact enhances the numerical stability in those problems. 相似文献
12.
Romeijn H. E. Zabinsky Z. B. Graesser D. L. Neogi S. 《Journal of Optimization Theory and Applications》1999,101(2):403-427
To reduce the well-known jamming problem in global optimization algorithms, we propose a new generator for the simulated annealing algorithm based on the idea of reflection. Furthermore, we give conditions under which the sequence of points generated by this simulated annealing algorithm converges in probability to the global optimum for mixed-integer/continuous global optimization problems. Finally, we present numerical results on some artificial test problems as well as on a composite structural design problem. 相似文献
13.
In this contribution, a novel approach for the modeling and optimization of discrete-continuous dynamic systems based on a disjunctive problem formulation is proposed. It will be shown that a disjunctive model representation, which constitutes an alternative to mixed-integer model formulations, provides a very flexible and intuitive way to formulate discrete-continuous dynamic optimization problems. Moreover, the structure and properties of the disjunctive process models can be exploited for an efficient and robust numerical solution by applying generalized disjunctive programming techniques. The proposed modeling and optimization approach will be illustrated by means of an optimal control problem that embeds a linear discretecontinuous dynamic system. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
14.
Trust-region methods are powerful optimization methods. The conic model method is a new type of method with more information available at each iteration than standard quadratic-based methods. Can we combine their advantages to form a more powerful method for constrained optimization? In this paper we give a positive answer and present a conic trust-region algorithm for non-linearly constrained optimization problems. The trust-region subproblem of our method is to minimize a conic function subject to the linearized constraints and the trust region bound. The use of conic functions allows the model to interpolate function values and gradient values of the Lagrange function at both the current point and previous iterate point. Since conic functions are the extension of quadratic functions, they approximate general nonlinear functions better than quadratic functions. At the same time, the new algorithm possesses robust global properties. In this paper we establish the global convergence of the new algorithm under standard conditions. 相似文献
15.
We study convex conic optimization problems in which the right-hand side and the cost vectors vary linearly as functions of a scalar parameter. We present a unifying geometric framework that subsumes the concept of the optimal partition in linear programming (LP) and semidefinite programming (SDP) and extends it to conic optimization. Similar to the optimal partition approach to sensitivity analysis in LP and SDP, the range of perturbations for which the optimal partition remains constant can be computed by solving two conic optimization problems. Under a weaker notion of nondegeneracy, this range is simply given by a minimum ratio test. We discuss briefly the properties of the optimal value function under such perturbations. 相似文献
16.
17.
18.
19.
P. Jiménez Guerra M. A. Melguizo M. J. Muñoz-Bouzo 《Journal of Optimization Theory and Applications》2009,142(2):343-354
In the context of vector optimization, several results are stated mainly about the continuity and the derivability of a conic
set-valued map (the polar conic function) having a close relation with the positive efficient points, the ideal points and
other distinguished elements of the efficient line. The contingent cone to the set of the general positive quasiefficient
points at a point x
0 is also related with the frontier of the dual cone of the image at x
0 of the polar conic function.
This work was partially supported by Grant SEJ2006–15401–C04–02 of Spanish Ministerio de Ciencia y Tecnología and Grant S-0505/tic/0230-D3
of Comunidad Autónoma de Madrid. The authors are grateful to the referees for suggestions which led to improving the paper. 相似文献
20.
François Glineur 《Annals of Operations Research》2001,105(1-4):155-184
Geometric optimization1 is an important class of problems that has many applications, especially in engineering design. In this article, we provide new simplified proofs for the well-known associated duality theory, using conic optimization. After introducing suitable convex cones and studying their properties, we model geometric optimization problems with a conic formulation, which allows us to apply the powerful duality theory of conic optimization and derive the duality results valid for geometric optimization. 相似文献