共查询到20条相似文献,搜索用时 15 毫秒
1.
Linear programming duality yields efficient algorithms for solving inverse linear programs. We show that special classes of conic programs admit a similar duality and, as a consequence, establish that the corresponding inverse programs are efficiently solvable. We discuss applications of inverse conic programming in portfolio optimization and utility function identification. 相似文献
2.
Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions
of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming
and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory of
lifting to conic integer programming, i.e., integer programs with conic constraints. We show how to derive conic valid inequalities
for a conic integer program from conic inequalities valid for its lower-dimensional restrictions. In order to simplify the
computations, we also discuss sequence-independent lifting for conic integer programs. When the cones are restricted to nonnegative
orthants, conic lifting reduces to the lifting for linear integer programming as one may expect. 相似文献
3.
4.
Qinghong Zhang 《4OR: A Quarterly Journal of Operations Research》2011,9(4):403-416
It is known that the minimal cone for the constraint system of a conic linear programming problem is a key component in obtaining
strong duality without any constraint qualification. For problems in either primal or dual form, the minimal cone can be written
down explicitly in terms of the problem data. However, due to possible lack of closure, explicit expressions for the dual
cone of the minimal cone cannot be obtained in general. In the particular case of semidefinite programming, an explicit expression
for the dual cone of the minimal cone allows for a dual program of polynomial size that satisfies strong duality. In this
paper we develop a recursive procedure to obtain the minimal cone and its dual cone. In particular, for conic problems with
so-called nice cones, we obtain explicit expressions for the cones involved in the dual recursive procedure. As an example
of this approach, the well-known duals that satisfy strong duality for semidefinite programming problems are obtained. The
relation between this approach and a facial reduction algorithm is also discussed. 相似文献
5.
In this we paper we study techniques for generating valid convex constraints for mixed 0-1 conic programs. We show that many of the techniques developed for generating linear cuts for mixed 0-1 linear programs, such as the Gomory cuts, the lift-and-project cuts, and cuts from other hierarchies of tighter relaxations, extend in a straightforward manner to mixed 0-1 conic programs. We also show that simple extensions of these techniques lead to methods for generating convex quadratic cuts. Gomory cuts for mixed 0-1 conic programs have interesting implications for comparing the semidefinite programming and the linear programming relaxations of combinatorial optimization problems, e.g. we show that all the subtour elimination inequalities for the traveling salesman problem are rank-1 Gomory cuts with respect to a single semidefinite constraint. We also include results from our preliminary computational experiments with these cuts.Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514. 相似文献
6.
《Operations Research Letters》2020,48(3):329-335
Farkas’ Lemma is a foundational result in linear programming, with implications in duality, optimality conditions, and stochastic and bilevel programming. Its generalizations are known as theorems of the alternative. There exist theorems of the alternative for integer programming and conic programming. We present theorems of the alternative for conic integer programming. We provide a nested procedure to construct a function that characterizes feasibility over right-hand sides and can determine which statement in a theorem of the alternative holds. 相似文献
7.
Juan Pablo Vielma Iain Dunning Joey Huchette Miles Lubin 《Mathematical Programming Computation》2017,9(3):369-418
In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma et al. (INFORMS J Comput 20: 438–450, 2008) and Hijazi et al. (Comput Optim Appl 52: 537–558, 2012) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by Ben-Tal and Nemirovski (Math Oper Res 26(2): 193–205 2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (Math Programm 103(2): 225–249, 2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulation-based algorithms for MICQP. We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers. 相似文献
8.
The Markowitz Mean Variance model (MMV) and its variants are widely used for portfolio selection. The mean and covariance matrix used in the model originate from probability distributions that need to be determined empirically. It is well known that these parameters are notoriously difficult to estimate. In addition, the model is very sensitive to these parameter estimates. As a result, the performance and composition of MMV portfolios can vary significantly with the specification of the mean and covariance matrix. In order to address this issue we propose a one-period mean-variance model, where the mean and covariance matrix are only assumed to belong to an exogenously specified uncertainty set. The robust mean-variance portfolio selection problem is then written as a conic program that can be solved efficiently with standard solvers. Both second order cone program (SOCP) and semidefinite program (SDP) formulations are discussed. Using numerical experiments with real data we show that the portfolios generated by the proposed robust mean-variance model can be computed efficiently and are not as sensitive to input errors as the classical MMV??s portfolios. 相似文献
9.
Given a self-concordant barrier function for a convex set
, we determine a self-concordant barrier function for the conic hull
of
. As our main result, we derive an “optimal” barrier for
based on the barrier function for
. Important applications of this result include the conic reformulation of a convex problem, and the solution of fractional
programs by interior-point methods. The problem of minimizing a convex-concave fraction over some convex set can be solved
by applying an interior-point method directly to the original nonconvex problem, or by applying an interior-point method to
an equivalent convex reformulation of the original problem. Our main result allows to analyze the second approach showing
that the rate of convergence is of the same order in both cases. 相似文献
10.
Ralf Werner 《Central European Journal of Operations Research》2008,16(2):179-189
It is well known that the robust counterpart introduced by Ben-Tal and Nemirovski (Math Oper Res 23:769–805, 1998) increases
the numerical complexity of the solution compared to the original problem. Kočvara, Nemirovski and Zowe therefore introduced
in Kočvara et al. (Comput Struct 76:431–442, 2000) an approximation algorithm for the special case of robust material optimization,
called cascading. As the title already indicates, we will show that their method can be seen as an adjustment of standard exchange methods
to semi-infinite conic programming. We will see that the adjustment can be motivated by a suitable reformulation of the robust
conic problem.
相似文献
11.
M. J. Todd 《Mathematical Programming》2008,111(1-2):301-313
We observe a curious property of dual versus primal-dual path-following interior-point methods when applied to unbounded linear
or conic programming problems in dual form. While primal-dual methods can be viewed as implicitly following a central path
to detect primal infeasibility and dual unboundedness, dual methods can sometimes implicitly move away from the analytic center of the set of infeasibility/unboundedness detectors.
Dedicated to Clovis Gonzaga on the occassion of his 60th birthday. 相似文献
12.
Yong-Jin Liu Li-Wei Zhang Yin-He Wang 《Journal of Applied Mathematics and Computing》2006,22(1-2):133-148
This paper proposes a smoothing method for symmetric conic linear programming (SCLP). We first characterize the central path conditions for SCLP problems with the help of Chen-Harker-Kanzow-Smale smoothing function. A smoothing-type algorithm is constructed based on this characterization and the global convergence and locally quadratic convergence for the proposed algorithm are demonstrated. 相似文献
13.
Ozden Ustun 《Applied Mathematical Modelling》2012,36(3):974-988
The multi-choice goal programming allows the decision maker to set multi-choice aspiration levels for each goal to avoid underestimation of the decision. In this paper, we propose an alternative multi-choice goal programming formulation based on the conic scalarizing function with three contributions: (1) the alternative formulation allows the decision maker to set multi-choice aspiration levels for each goal to obtain an efficient solution in the global region, (2) the proposed formulation reduces auxiliary constraints and additional variables, and (3) the proposed model guarantees to obtain a properly efficient (in the sense of Benson) point. Finally, to demonstrate the usefulness of the proposed formulation, illustrative examples and test problems are included. 相似文献
14.
Renato D. C. Monteiro Camilo Ortiz Benar F. Svaiter 《Computational Optimization and Applications》2014,57(1):45-69
In this paper, we consider block-decomposition first-order methods for solving large-scale conic semidefinite programming problems given in standard form. Several ingredients are introduced to speed-up the method in its pure form such as: an aggressive choice of stepsize for performing the extragradient step; use of scaled inner products; dynamic update of the scaled inner product for properly balancing the primal and dual relative residuals; and proper choices of the initial primal and dual iterates, as well as the initial parameter for the scaled inner product. Finally, we present computational results showing that our method outperforms the two most competitive codes for large-scale conic semidefinite programs, namely: the boundary-point method introduced by Povh et al. and the Newton-CG augmented Lagrangian method by Zhao et al. 相似文献
15.
Numerical Algorithms - The LP-Newton method solves linear programming (LP) problems by repeatedly projecting a current point onto a certain relevant polytope. In this paper, we extend the... 相似文献
16.
Unified convergence analysis of a second-order method of multipliers for nonlinear conic programming
Science China Mathematics - In this paper, we accomplish the unified convergence analysis of a second-order method of multipliers (i.e., a second-order augmented Lagrangian method) for solving the... 相似文献
17.
18.
The paper considers solving of linear programming problems with p-order conic constraints that are related to a certain class of stochastic optimization models with risk objective or constraints. The proposed approach is based on construction of polyhedral approximations for p-order cones, and then invoking a Benders decomposition scheme that allows for efficient solving of the approximating problems. The conducted case study of portfolio optimization with p-order conic constraints demonstrates that the developed computational techniques compare favorably against a number of benchmark methods, including second-order conic programming methods. 相似文献
19.
Mathematical Programming - In conic linear programming—in contrast to linear programming—the Lagrange dual is not an exact dual: it may not attain its optimal value, or there may be a... 相似文献
20.
Qinghong Zhang 《Optimization Letters》2010,4(3):439-447
In this paper, we present simple proofs for the main results that appear in Nunez (Math Program 91:375–390, 2002) using a
lemma in Freund and Vera (Math Program 86:225–260, 1999) for conic linear programming. Connections between interiors and boundaries
of feasible and infeasible data instances and weak and strong feasibilities of a conic linear programming primal-dual pair
are made. 相似文献