共查询到20条相似文献,搜索用时 31 毫秒
1.
A. Auslender 《Mathematical Programming》2000,88(1):45-59
In this paper we consider an ordinary convex program with no qualification conditions (such as Slater’s condition) and for
which the optimal set is neither required to be compact, nor to be equal to the sum of a compact set and a linear space. It
is supposed only that the infimum α is finite. A very wide class of convex functions is exhibited for which the optimum is
always attained and α is equal to the supremum of the ordinary dual program. Additional results concerning the existence of
optimal solutions in the non convex case are also given.
Received: February 1, 1999 / Accepted: December 15, 1999?Published online February 23, 2000 相似文献
2.
We prove that strict complementarity, primal and dual nondegeneracy of optimal solutions of convex optimization problems in
conic form are generic properties. In this paper, we say generic to mean that the set of data possessing the desired property
(or properties) has strictly larger Hausdorff dimension than the set of data that does not. Our proof is elementary and it
employs an important result due to Larman [7] on the boundary structure of convex bodies.
Received: September 1997 / Accepted: May 2000?Published online November 17, 2000 相似文献
3.
Robust Optimization (RO) is a modeling methodology, combined with computational tools, to process optimization problems in
which the data are uncertain and is only known to belong to some uncertainty set. The paper surveys the main results of RO
as applied to uncertain linear, conic quadratic and semidefinite programming. For these cases, computationally tractable robust
counterparts of uncertain problems are explicitly obtained, or good approximations of these counterparts are proposed, making
RO a useful tool for real-world applications. We discuss some of these applications, specifically: antenna design, truss topology
design and stability analysis/synthesis in uncertain dynamic systems. We also describe a case study of 90 LPs from the NETLIB
collection. The study reveals that the feasibility properties of the usual solutions of real world LPs can be severely affected
by small perturbations of the data and that the RO methodology can be successfully used to overcome this phenomenon.
Received: May 24, 2000 / Accepted: September 12, 2001?Published online February 14, 2002 相似文献
4.
The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many
closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization
(constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard
constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull
intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived
and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result
on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is
quantified by the angle between the subspaces.
Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999 相似文献
5.
Logarithmic SUMT limits in convex programming 总被引:1,自引:1,他引:0
The limits of a class of primal and dual solution trajectories associated with the Sequential Unconstrained Minimization Technique
(SUMT) are investigated for convex programming problems with non-unique optima. Logarithmic barrier terms are assumed. For
linear programming problems, such limits – of both primal and dual trajectories – are strongly optimal, strictly complementary,
and can be characterized as analytic centers of, loosely speaking, optimality regions. Examples are given, which show that
those results do not hold in general for convex programming problems. If the latter are weakly analytic (Bank et al. [3]),
primal trajectory limits can be characterized in analogy to the linear programming case and without assuming differentiability.
That class of programming problems contains faithfully convex, linear, and convex quadratic programming problems as strict
subsets. In the differential case, dual trajectory limits can be characterized similarly, albeit under different conditions,
one of which suffices for strict complementarity.
Received: November 13, 1997 / Accepted: February 17, 1999?Published online February 22, 2001 相似文献
6.
Martin Gugat 《Mathematical Programming》2000,88(2):255-275
The feasible set of a convex semi–infinite program is described by a possibly infinite system of convex inequality constraints.
We want to obtain an upper bound for the distance of a given point from this set in terms of a constant multiplied by the
value of the maximally violated constraint function in this point. Apart from this Lipschitz case we also consider error bounds
of H?lder type, where the value of the residual of the constraints is raised to a certain power.?We give sufficient conditions
for the validity of such bounds. Our conditions do not require that the Slater condition is valid. For the definition of our
conditions, we consider the projections on enlarged sets corresponding to relaxed constraints. We present a condition in terms
of projection multipliers, a condition in terms of Slater points and a condition in terms of descent directions. For the Lipschitz
case, we give five equivalent characterizations of the validity of a global error bound.?We extend previous results in two
directions: First, we consider infinite systems of inequalities instead of finite systems. The second point is that we do
not assume that the Slater condition holds which has been required in almost all earlier papers.
Received: April 12, 1999 / Accepted: April 5, 2000?Published online July 20, 2000 相似文献
7.
Stephen J. Wright 《Mathematical Programming》2001,90(3):459-473
Techniques for transforming convex quadratic programs (QPs) into monotone linear complementarity problems (LCPs) and vice
versa are well known. We describe a class of LCPs for which a reduced QP formulation – one that has fewer constraints than
the “standard” QP formulation – is available. We mention several instances of this class, including the known case in which
the coefficient matrix in the LCP is symmetric.
Received: May 2000 / Accepted: February 22, 2001?Published online April 12, 2001 相似文献
8.
Model selection for regression on a fixed design 总被引:1,自引:0,他引:1
Yannick Baraud 《Probability Theory and Related Fields》2000,117(4):467-493
We deal with the problem of estimating some unknown regression function involved in a regression framework with deterministic
design points. For this end, we consider some collection of finite dimensional linear spaces (models) and the least-squares
estimator built on a data driven selected model among this collection. This data driven choice is performed via the minimization
of some penalized model selection criterion that generalizes on Mallows' C
p
. We provide non asymptotic risk bounds for the so-defined estimator from which we deduce adaptivity properties. Our results
hold under mild moment conditions on the errors. The statement and the use of a new moment inequality for empirical processes
is at the heart of the techniques involved in our approach.
Received: 2 July 1997 / Revised version: 20 September 1999 / Published online: 6 July 2000 相似文献
9.
This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality
constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods
for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the
iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal
set is ensured when the barrier parameter tends to zero, provided strict complementarity holds.
Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002 相似文献
10.
Entropic proximal decomposition methods for convex programs and variational inequalities 总被引:2,自引:0,他引:2
We consider convex optimization and variational inequality problems with a given separable structure. We propose a new decomposition
method for these problems which combines the recent logarithmic-quadratic proximal theory introduced by the authors with a
decomposition method given by Chen-Teboulle for convex problems with particular structure. The resulting method allows to
produce for the first time provably convergent decomposition schemes based on C
∞ Lagrangians for solving convex structured problems. Under the only assumption that the primal-dual problems have nonempty
solution sets, global convergence of the primal-dual sequences produced by the algorithm is established.
Received: October 6, 1999 / Accepted: February 2001?Published online September 17, 2001 相似文献
11.
The stable admissions polytope– the convex hull of the stable assignments of the university admissions problem – is described by a set of linear inequalities.
It depends on a new characterization of stability and arguments that exploit and extend a graphical approach that has been
fruitful in the analysis of the stable marriage problem.
Received: April 10, 1998 / Accepted: June 3, 1999?Published online January 27, 2000 相似文献
12.
The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular
function and base polyhedron, respectively, and discrete separation theorems are established for L-convex/concave functions
and for M-convex/concave functions as generalizations of Frank’s discrete separation theorem for submodular/supermodular set
functions and Edmonds’ matroid intersection theorem. This paper shows the equivalence between Murota’s L-convex functions
and Favati and Tardella’s submodular integrally convex functions, and also gives alternative proofs of the separation theorems
that provide a geometric insight by relating them to the ordinary separation theorem in convex analysis.
Received: November 27, 1997 / Accepted: December 16, 1999?Published online May 12, 2000 相似文献
13.
Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation
methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming)
Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems
have a linear objective function c
T
x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,”
into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number
of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of
standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method
which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for
a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method
which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations.
Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000 相似文献
14.
Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization
for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically
produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions,
tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational
effort.
We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct,
at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments
performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence
results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the
basic subgradient scheme.
Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999 相似文献
15.
In this paper, we consider the problem of approximating a given matrix with a matrix whose eigenvalues lie in some specific region Ω of the complex plane. More precisely, we consider three types of regions and their intersections: conic sectors, vertical strips, and disks. We refer to this problem as the nearest Ω‐stable matrix problem. This includes as special cases the stable matrices for continuous and discrete time linear time‐invariant systems. In order to achieve this goal, we parameterize this problem using dissipative Hamiltonian matrices and linear matrix inequalities. This leads to a reformulation of the problem with a convex feasible set. By applying a block coordinate descent method on this reformulation, we are able to compute solutions to the approximation problem, which is illustrated on some examples. 相似文献
16.
On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating 总被引:2,自引:0,他引:2
In previous work, the authors provided a foundation for the theory of variable metric proximal point algorithms in Hilbert
space. In that work conditions are developed for global, linear, and super–linear convergence. This paper focuses attention
on two matrix secant updating strategies for the finite dimensional case. These are the Broyden and BFGS updates. The BFGS
update is considered for application in the symmetric case, e.g., convex programming applications, while the Broyden update
can be applied to general monotone operators. Subject to the linear convergence of the iterates and a quadratic growth condition
on the inverse of the operator at the solution, super–linear convergence of the iterates is established for both updates.
These results are applied to show that the Chen–Fukushima variable metric proximal point algorithm is super–linearly convergent
when implemented with the BFGS update.
Received: September 12, 1996 / Accepted: January 7, 2000?Published online March 15, 2000 相似文献
17.
An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints 总被引:12,自引:0,他引:12
Le Thi Hoai An 《Mathematical Programming》2000,87(3):401-426
In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids.
The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the
proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound
scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham
Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting
point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order
to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the
ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can
be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting
procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems.
Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA
and the combined DCA-branch-and-bound algorithm.
Received: April 22, 1999 / Accepted: November 30, 1999?Published online February 23, 2000 相似文献
18.
Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods 总被引:6,自引:0,他引:6
The paper extends prior work by the authors on loqo, an interior point algorithm for nonconvex nonlinear programming. The
specific topics covered include primal versus dual orderings and higher order methods, which attempt to use each factorization
of the Hessian matrix more than once to improve computational efficiency. Results show that unlike linear and convex quadratic
programming, higher order corrections to the central trajectory are not useful for nonconvex nonlinear programming, but that
a variant of Mehrotra’s predictor-corrector algorithm can definitely improve performance.
Received: May 3, 1999 / Accepted: January 24, 2000?Published online March 15, 2000 相似文献
19.
Pierre Maréchal 《Mathematical Programming》2001,89(3):505-516
It is well known that a function f of the real variable x is convex if and only if (x,y)→yf(y
-1
x),y>0 is convex. This is used to derive a recursive proof of the convexity of the multiplicative potential function. In this
paper, we obtain a conjugacy formula which gives rise, as a corollary, to a new rule for generating new convex functions from
old ones. In particular, it allows to extend the aforementioned property to functions of the form (x,y)→g(y)f(g(y)-1
x) and provides a new tool for the study of the multiplicative potential and penalty functions.
Received: June 3, 1999 / Accepted: September 29, 2000?Published online January 17, 2001 相似文献
20.
Universal duality in conic convex optimization 总被引:1,自引:0,他引:1
Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended
real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +∞ and
−∞. In contrast, for optimization problems over nonpolyhedral convex cones, a nonzero duality gap can exist when either the
primal or the dual is feasible.
For a pair of dual conic convex programs, we provide simple conditions on the ``constraint matrices' and cone under which
the duality gap is zero for every choice of linear objective function and constraint right-hand side. We refer to this property as ``universal duality'. Our
conditions possess the following properties: (i) they are necessary and sufficient, in the sense that if (and only if) they
do not hold, the duality gap is nonzero for some linear objective function and constraint right-hand side; (ii) they are metrically
and topologically generic; and (iii) they can be verified by solving a single conic convex program. We relate to universal
duality the fact that the feasible sets of a primal convex program and its dual cannot both be bounded, unless they are both
empty. Finally we illustrate our theory on a class of semidefinite programs that appear in control theory applications.
This work was supported by a fellowship at the University of Maryland, in addition to NSF grants DEMO-9813057, DMI0422931,
CUR0204084, and DoE grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper
are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department
of Energy. 相似文献