共查询到20条相似文献,搜索用时 15 毫秒
1.
Krzysztof C. Kiwiel 《Mathematical Programming》2001,90(1):1-25
We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint
in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not
be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and
to the generalized solution set for classical stepsizes t
k
→0, ∑t
k
=∞, and weak or strong convergence of the iterates to a solution for {t
k
}∈ℓ2∖ℓ1 under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an
efficiency estimate of O(ε-2), thus being optimal in the sense of Nemirovskii.
Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001 相似文献
2.
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 相似文献
3.
Paul Tseng 《Mathematical Programming》2000,88(1):183-192
The classes of P-, P
0-, R
0-, semimonotone, strictly semimonotone, column sufficient, and nondegenerate matrices play important roles in studying solution
properties of equations and complementarity problems and convergence/complexity analysis of methods for solving these problems.
It is known that the problem of deciding whether a square matrix with integer/rational entries is a P- (or nondegenerate) matrix is co-NP-complete. We show, through a unified analysis, that analogous decision problems for the other matrix classes are also co-NP-complete.
Received: April 1999 / Accepted: March 1, 2000?Published online May 12, 2000 相似文献
4.
Diego Matessi 《Annals of Global Analysis and Geometry》2006,29(3):197-220
We prove that certain Riemannian manifolds can be isometrically embedded inside Calabi–Yau manifolds. For example, we prove that given any real-analytic one parameter family of Riemannian metrics g
t on a three-dimensional manifold Y with volume form independent of t and with a real-analytic family of nowhere vanishing harmonic one forms θ
t
, then (Y,g
t
) can be realized as a family of special Lagrangian submanifolds of a Calabi–Yau manifold X. We also prove that certain principal torus bundles can be equivariantly and isometrically embedded inside Calabi-Yau manifolds with torus action. We use this to construct examples of n-parameter families of special Lagrangian tori inside n + k-dimensional Calabi–Yau manifolds with torus symmetry. We also compute McLean's metric of 3-dimensional special Lagrangian fibrations with T
2-symmetry.
Mathematics Subject Classification (2000): 53-XX, 53C38.Communicated by N. Hitchin (Oxford) 相似文献
5.
Conditions ensuring the applicability of cutting-plane methods for solving variational inequalities 总被引:1,自引:0,他引:1
Let VIP(F,C) denote the variational inequality problem associated with the mapping F and the closed convex set C. In this paper we introduce weak conditions on the mapping F that allow the development of a convergent cutting-plane framework for solving VIP(F,C). In the process we introduce, in a natural way, new and useful notions of generalized monotonicity for which first order
characterizations are presented.
Received: September 25, 1997 / Accepted: March 2, 1999?Published online July 20, 2000 相似文献
6.
We obtain local estimates of the distance to a set defined by equality constraints under assumptions which are weaker than
those previously used in the literature. Specifically, we assume that the constraints mapping has a Lipschitzian derivative,
and satisfies a certain 2-regularity condition at the point under consideration. This setting directly subsumes the classical
regular case and the twice differentiable 2-regular case, for which error bounds are known, but it is significantly richer
than either of these two cases. When applied to a certain equation-based reformulation of the nonlinear complementarity problem,
our results yield an error bound under an assumption more general than b-regularity. The latter appears to be the weakest assumption under which a local error bound for complementarity problems
was previously available. We also discuss an application of our results to the convergence rate analysis of the exterior penalty
method for solving irregular problems.
Received: February 2000 / Accepted: November 2000?Published online January 17, 2001 相似文献
7.
The local quadratic convergence of the Gauss-Newton method for convex composite optimization f=h∘F is established for any convex function h with the minima set C, extending Burke and Ferris’ results in the case when C is a set of weak sharp minima for h.
Received: July 24, 1998 / Accepted: November 29, 2000?Published online September 3, 2001 相似文献
8.
Given a linear transformation L:?
n
→?
n
and a matrix Q∈?
n
, where ?
n
is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,?
n
+,Q) over the cone ?
n
+ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R
n×n
, we consider the linear transformation L
A
:?
n
→?
n
defined by L
A
(X):=AX+XA
T
and show that the P- and Q-properties for L
A
are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov.
Received: March 1999 / Accepted: November 1999?Published online April 20, 2000 相似文献
9.
In this paper we prove a result on the existence of periodic motions for the periodically forced Liénard differential equation
x
″+f(x)x
′+g(x)=e(t) in a situation where the phase portrait of the associated autonomous equation is similar to that of a centre limited by
an unbounded separatrix. The existence result, which is based on a degree theoretic continuation theorem, enables us to treat
some interesting cases not previously considered in the literature.
Received: April 27, 2000 Published online: December 19, 2001 相似文献
10.
For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n
k-1
F(n,m))=O(mn
k
log(n
2
/m)) time and O(n
2) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn
3) for weighted graphs, but improves the bound ?(mn
3) to O(n
2
F(n,m))=O(min{mn
8/3,m
3/2
n
2}) for unweighted graphs. The bound ?(mn
4) for k=4 improves the previous best randomized bound ?(n
6) (for m=o(n
2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system.
Received: April 1999 / Accepted: February 2000?Published online August 18, 2000 相似文献
11.
We extend an interesting theorem of Yuan [12] for two quadratic forms to three matrices. Let C
1, C
2, C
3 be three symmetric matrices in ℜ
n×n
, if max{x
T
C
1
x,x
T
C
2
x,x
T
C
3
x}≥0 for all x∈ℜ
n
, it is proved that there exist t
i
≥0 (i=1,2,3) such that ∑
i=1
3
t
i
=1 and ∑
i=1
3
t
i
C
i
has at most one negative eigenvalue.
Received February 18, 1997 / Revised version received October 1, 1997? Published online June 11, 1999 相似文献
12.
We study a quasilinear elliptic problem
with nonhomogeneous principal part φ. Under the hypothesis f(x,t)= o(φ(t)t) at t= 0 and ∞, the existence of multiple positive solutions is proved by using the variational arguments in the Orlicz–Sobolev
spaces.
Mathematics Subject Classification (2000) 35J20; 35J25; 35J70; 47J10; 47J30 相似文献
13.
A.B. Levy 《Mathematical Programming》1999,85(2):397-406
n such that x≥0, F(x,u)-v≥0 , and F(x,u)-v T·x=0 where these are vector inequalities. We characterize the local upper Lipschitz continuity of the (possibly set-valued)
solution mapping which assigns solutions x to each parameter pair (v,u). We also characterize when this solution mapping is
locally a single-valued Lipschitzian mapping (so solutions exist, are unique, and depend Lipschitz continuously on the parameters).
These characterizations are automatically sufficient conditions for the more general (and usual) case where v=0. Finally,
we study the differentiability properties of the solution mapping in both the single-valued and set-valued cases, in particular
obtaining a new characterization of B-differentiability in the single-valued case, along with a formula for the B-derivative.
Though these results cover a broad range of stability properties, they are all derived from similar fundamental principles
of variational analysis.
Received March 30, 1998 / Revised version received July 21, 1998
Published online January 20, 1999 相似文献
14.
Philippe Souplet 《Annali di Matematica Pura ed Applicata》2002,181(4):427-436
We prove an a priori estimate and a universal bound for any global solution of the nonlinear degenerate reaction-diffusion
equation u
t
=Δu
m
+u
p
in a bounded domain with zero Dirichlet boundary conditions.
Received: October 1, 2001?Published online: July 9, 2002 相似文献
15.
We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume
that for any submodular function f: ?→R on a distributive lattice ?⊆2
V
with ?,V∈? and f(?)=0 and for any vector x∈R
V
where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|2) times, the descent method finds a sequence of subsets Z
1,Z
2,···,Z
k
of V such that f(Z
1)>f(Z
2)>···>f(Z
k
)=min{f(Y) | Y∈?}, where k is O(|V|2). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient
membership algorithms.
Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001 相似文献
16.
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 相似文献
17.
This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows
exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively,
the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First,
we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a
simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify
several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide
variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy
to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the
QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP.
Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000 相似文献
18.
In a recent paper, the authors have proved results characterizing convexity-preserving maps defined on a subset of a not-necessarily
finite dimensional real vector space as projective maps. The purpose of this note is three-fold. First, we state a theorem
characterizing continuous, injective, convexity-preserving maps from a relatively open, connected subset of an affine subspace
of ℝ
m
into ℝ
n
as projective maps. This result follows from the more general results stated and proved in a coordinate-free manner in the
above paper, and is intended to be more accessible to researchers interested in optimization algorithms. Second, based on
that characterization theorem, we offer a characterization theorem for collinear scalings first introduced by Davidon in 1977
for deriving certain algorithms for nonlinear optimization, and a characterization theorem for projective transformations
used by Karmarkar in 1984 in his linear programming algorithm. These latter two theorems indicate that Davidon’s collinear
scalings and Karmarkar’s projective transformations are the only continuous, injective, convexity-preserving maps possessing
certain features that Davidon and Karmarkar respectively desired in the derivation of their algorithms. The proofs of these
latter two theorems utilize our characterization of continuous, injective, convexity-preserving maps in a way that has implications
to the choice of scalings and transformations in the derivation of optimization algorithms in general. The third purpose of
this note is to point this out.
Received: January 2000 / Accepted: November 2000?Published online January 17, 2001 相似文献
19.
This paper presents a polynomial-time dual simplex algorithm for the generalized circulation problem. An efficient implementation
of this algorithm is given that has a worst-case running time of O(m
2(m+nlogn)logB), where n is the number of nodes, m is the number of arcs and B is the largest integer used to represent the rational gain factors and integral capacities in the network. This running time
is as fast as the running time of any combinatorial algorithm that has been proposed thus far for solving the generalized
circulation problem.
Received: June 1998 / Accepted: June 27, 2001?Published online September 17, 2001 相似文献
20.
The General Routing Problem (GRP) is the problem of finding a minimum cost route for a single vehicle, subject to the condition that the vehicle visits
certain vertices and edges of a network. It contains the Rural Postman Problem, Chinese Postman Problem and Graphical Travelling Salesman Problem as special cases. We describe a cutting plane algorithm for the GRP based on facet-inducing inequalities and show that it
is capable of providing very strong lower bounds and, in most cases, optimal solutions.
Received: November 1998 / Accepted: September 2000?Published online March 22, 2001 相似文献