排序方式: 共有49条查询结果,搜索用时 15 毫秒
1.
Henry Wolkowicz 《Mathematical Programming》1980,19(1):32-60
The cones of directions of constancy are used to derive: new as well as known optimality conditions; weakest constraint qualifications; and regularization techniques, for the convex programming problem. In addition, the badly behaved set of constraints, i.e. the set of constraints which causes problems in the Kuhn—Tucker theory, is isolated and a computational procedure for checking whether a feasible point is regular or not is presented.This research was supported by the National Research Council of Canada and le Gouvernement du Quebec and is part of the author's Ph.D. Dissertation done at McGill University, Montreal, Que., under the guidance of Professor S. Zlobec. 相似文献
2.
In this paper we study constraint qualifications and duality results for infinite convex programs (P) = inf{f(x): g(x) – S, x C}, whereg = (g
1,g
2) andS = S
1 ×S
2,S
i
are convex cones,i = 1, 2,C is a convex subset of a vector spaceX, andf andg
i
are, respectively, convex andS
i
-convex,i = 1, 2. In particular, we consider the special case whenS
2 is in afinite dimensional space,g
2 is affine andS
2 is polyhedral. We show that a recently introduced simple constraint qualification, and the so-called quasi relative interior constraint qualification both extend to (P), from the special case thatg = g
2 is affine andS = S
2 is polyhedral in a finite dimensional space (the so-called partially finite program). This provides generalized Slater type conditions for (P) which are much weaker than the standard Slater condition. We exhibit the relationship between these two constraint qualifications and show how to replace the affine assumption ong
2 and the finite dimensionality assumption onS
2, by a local compactness assumption. We then introduce the notion of strong quasi relative interior to get parallel results for more general infinite dimensional programs without the local compactness assumption. Our basic tool reduces to guaranteeing the closure of the sum of two closed convex cones. 相似文献
3.
Several new inequalities are obtained for the modulus, the real part, and the imaginary part of a linear combination of the ordered eigenvalues of a square complex matrix. Included are bounds for the condition number, the spread, and the spectral radius. These inequalities involve the trace of a matrix and the trace of its square. Necessary and sufficient conditions for equality are given for each inequality. 相似文献
4.
Henry Wolkowicz 《Journal of Optimization Theory and Applications》1983,40(3):349-378
We present an algorithm which solves a convex program with faithfully convex (not necessarily differentiable) constraints. While finding a feasible starting point, the algorithm reduces the program to an equivalent program for which Slater's condition is satisfied. Included are algorithms for calculating various objects which have recently appeared in the literature. Stability of the algorithm is discussed. 相似文献
5.
We consider a global optimization problem for Lipschitz-continuous functions with an unknown Lipschitz constant. Our approach is based on the well-known DIRECT (DIviding RECTangles) algorithm and motivated by the diagonal partitioning strategy. One of the main advantages of the diagonal partitioning scheme is that the objective function is evaluated at two points at each hyper-rectangle and, therefore, more comprehensive information about the objective function is considered than using the central sampling strategy used in most DIRECT-type algorithms. In this paper, we introduce a new DIRECT-type algorithm, which we call BIRECT (BIsecting RECTangles). In this algorithm, a bisection is used instead of a trisection which is typical for diagonal-based and DIRECT-type algorithms. The bisection is preferable to the trisection because of the shapes of hyper-rectangles, but usual evaluation of the objective function at the center or at the endpoints of the diagonal are not favorable for bisection. In the proposed algorithm the objective function is evaluated at two points on the diagonal equidistant between themselves and the endpoints of a diagonal. This sampling strategy enables reuse of the sampling points in descendant hyper-rectangles. The developed algorithm gives very competitive numerical results compared to the DIRECT algorithm and its well know modifications. 相似文献
6.
We investigate new bounding strategies based on different relaxations of the quadratic assignment problem. In particular, we improve the lower bound found by using an eigenvalue decomposition of the quadratic part and by solving a linear program for the linear part. The improvement is accomplished by applying a steepest ascent algorithm to the sum of the two bounds.Both authors would like to thank the Natural Sciences and Engineering Research Council Canada and the Austrian Government for their support.This author would like to acknowledge partial support from the Department of Combinatorics and Optimization at the University of Waterloo.Research partially supported by Natural Sciences and Engineering Research Council Canada. 相似文献
7.
Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal–dual strictly complementary
optimal solution pair. On the other hand, there exist Semidefinite Programming, SDP, problems which have a nonzero duality
gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if a constraint qualification,
e.g., Slater’s condition (strict feasibility) holds. Measures of strict feasibility, also called distance to infeasibility, have been used in complexity analysis, and, it is known that (near) loss of strict feasibility results in numerical difficulties.
In addition, there exist SDP problems which have a zero duality gap but no strict complementary primal–dual optimal solution.
We refer to these problems as hard instances of SDP. The assumption of strict complementarity is essential for asymptotic superlinear and quadratic rate convergence proofs.
In this paper, we introduce a procedure for generating hard instances of SDP with a specified complementarity nullity (the dimension of the common nullspace of primal–dual optimal pairs). We then show, empirically, that the complementarity
nullity correlates well with the observed local convergence rate and the number of iterations required to obtain optimal solutions
to a specified accuracy, i.e., we show, even when Slater’s condition holds, that the loss of strict complementarity results
in numerical difficulties. We include two new measures of hardness that correlate well with the complementarity nullity. 相似文献
8.
Danilo Elias Oliveira Henry Wolkowicz Yangyang Xu 《Mathematical Programming Computation》2018,10(4):631-658
Semidefinite programming, SDP, relaxations have proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem, QAP, arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the current primal–dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers ADMM in combination with facial reduction, FR, to solve the SDP relaxation. This first order approach allows for: inexpensive iterations, a method of cheaply obtaining low rank solutions; and a trivial way of exploiting the FR for adding cutting plane inequalities. In fact, we solve the doubly nonnegative, DNN, relaxation that includes both the SDP and all the nonnegativity constraints. When compared to current approaches and current best available bounds we obtain robustness, efficiency and improved bounds. 相似文献
9.
We present a new method for regularization of ill-conditioned problems, such as those that arise in image restoration or mathematical processing of medical data. The method extends the traditional trust-region subproblem, TRS, approach that makes use of the L-curve maximum curvature criterion, a strategy recently proposed to find a good regularization parameter. We apply a parameterized trust region approach to estimate the region of maximum curvature of the L-curve and find the regularized solution. This exploits the close connections between various parameters used to solve TRS. A MATLAB code for the algorithm is tested and a comparison to the conjugate gradient least squares, CGLS, approach is given and analysed. 相似文献
10.