排序方式: 共有59条查询结果,搜索用时 15 毫秒
1.
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. 相似文献
2.
We have previously shown, by redundant Klee–Minty constructions, that the central path may arbitrarily closely visit every vertex of the Klee–Minty cube. In those constructions, the redundant constraints are far away from the feasible region. In this paper, we provide a construction in which all redundant constraints touch the feasible region. 相似文献
3.
This paper provides an analysis of the polynomiality of primal-dual interior point algorithms for nonlinear complementarity
problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu’s scaled
Lipschitz condition, but is also applicable to mappings that are not monotone. We show that a family of primal-dual affine
scaling algorithms generates an approximate solution (given a precision ε) of the nonlinear complementarity problem in a finite
number of iterations whose order is a polynomial ofn, ln(1/ε) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in Jansen
et al., SIAM Journal on Optimization 7 (1997) 126–140.
Research supported in part by Grant-in-Aids for Encouragement of Young Scientists (06750066) from the Ministry of Education,
Science and Culture, Japan.
Research supported by Dutch Organization for Scientific Research (NWO), grant 611-304-028 相似文献
4.
The primal-dual Dikin-type affine scaling method was originally proposed for linear optimization and then extended to semidefinite optimization. Here, the method is generalized to symmetric conic optimization using the notion of Euclidean Jordan algebras. The method starts with an interior feasible but not necessarily centered primal-dual solution, and it features both centering and reducing the duality gap simultaneously. The method’s iteration complexity bound is analogous to the semidefinite optimization case. Numerical experiments demonstrate that the method is viable and robust when compared to SeDuMi, MOSEK and SDPT3. 相似文献
5.
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. 相似文献
6.
Basis- and partition identification for quadratic programming and linear complementarity problems 总被引:1,自引:0,他引:1
Arjan B. Berkelaar Benjamin Jansen Kees Roos Tamás Terlaky 《Mathematical Programming》1999,86(2):261-282
Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide
maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other
hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification
algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification
algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from
any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski
and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity
problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality
property of basis tableaus.
Received April 9, 1996 / Revised version received April 27, 1998?
Published online May 12, 1999 相似文献
7.
8.
Pietro Belotti Julio C. Góez Imre Pólik Ted K. Ralphs Tamás Terlaky 《Discrete Applied Mathematics》2013,161(16-17):2778-2793
We investigate families of quadrics all of which have the same intersection with two given hyperplanes. The cases when the two hyperplanes are parallel and when they are nonparallel are discussed. We show that these families can be described with only one parameter and describe how the quadrics are transformed as the parameter changes. This research was motivated by an application in mixed integer conic optimization. In that application, we aimed to characterize the convex hull of the union of the intersections of an ellipsoid with two half-spaces arising from the imposition of a linear disjunction. 相似文献
9.
In this paper, we deal with ranking problems arising from various data mining applications where the major task is to train
a rank-prediction model to assign every instance a rank. We first discuss the merits and potential disadvantages of two existing
popular approaches for ranking problems: the ‘Max-Wins’ voting process based on multi-class support vector machines (SVMs)
and the model based on multi-criteria decision making. We then propose a confidence voting process for ranking problems based
on SVMs, which can be viewed as a combination of the SVM approach and the multi-criteria decision making model. Promising
numerical experiments based on the new model are reported.
The research of the last author was supported by the grant #R.PG 0048923 of NESERC, the MITACS project “New Interior Point
Methods and Software for Convex Conic-Linear Optimization and Their Application to Solve VLSI Circuit Layout Problems” and
the Canada Researcher Chair Program. 相似文献
10.