共查询到20条相似文献,搜索用时 125 毫秒
1.
In this paper we first establish a Lagrange multiplier condition characterizing a regularized Lagrangian duality for quadratic
minimization problems with finitely many linear equality and quadratic inequality constraints, where the linear constraints
are not relaxed in the regularized Lagrangian dual. In particular, in the case of a quadratic optimization problem with a
single quadratic inequality constraint such as the linearly constrained trust-region problems, we show that the Slater constraint
qualification (SCQ) is necessary and sufficient for the regularized Lagrangian duality in the sense that the regularized duality
holds for each quadratic objective function over the constraints if and only if (SCQ) holds. A new theorem of the alternative
for systems involving both equality constraints and two quadratic inequality constraints plays a key role. We also provide
classes of quadratic programs, including a class of CDT-subproblems with linear equality constraints, where (SCQ) ensures
regularized Lagrangian duality. 相似文献
2.
Jan-J. Rückmann 《Mathematical Programming》1999,86(2):387-415
The paper deals with semi-infinite optimization problems which are defined by finitely many equality constraints and infinitely
many inequality constraints. We generalize the concept of strongly stable stationary points which was introduced by Kojima
for finite problems; it refers to the local existence and uniqueness of a stationary point for each sufficiently small perturbed
problem, where perturbations up to second order are allowed. Under the extended Mangasarian-Fromovitz constraint qualification
we present equivalent conditions for the strong stability of a considered stationary point in terms of first and second derivatives
of the involved functions. In particular, we discuss the case where the reduction approach is not satisfied.
Received June 30, 1995 / Revised version received October 9, 1998?
Published online June 11, 1999 相似文献
3.
Shu Lu 《Mathematical Programming》2011,126(2):365-392
This paper investigates properties of a parametric set defined by finitely many equality and inequality constraints under
the constant rank constraint qualification (CRCQ). We show, under the CRCQ, that the indicator function of this set is prox-regular
with compatible parametrization, that the set-valued map that assigns each parameter to the set defined by that parameter
satisfies a continuity property similar to the Aubin property, and that the Euclidean projector onto this set is a piecewise
smooth function. We also show in the absence of parameters that the CRCQ implies the Mangasarian-Fromovitz constraint qualification
to hold in some alternative expression of the set. 相似文献
4.
This paper studies noncompact feasible sets of a semi-infinite optimization problem which are defined by finitely many equality constraints and infinitely many inequality constraints. The main result is the equivalence of the overall validity of the Extended Mangasarian Fromovitz Constraint Qualification with certain (topological) stability conditions. Furthermore, two perturbation theorems being of independent interest are presented.This work was supported by the Deutsche Forschungsgemeinschaft under grant Gu 304/1-2. 相似文献
5.
Dorit S. Hochbaum 《Annals of Operations Research》2007,153(1):257-296
Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear
problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing
algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space.
We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity,
constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices,
and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms
which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the
complexity of the respective problems.
In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare
the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear
optimization.
An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005. 相似文献
6.
Dorit S. Hochbaum 《4OR: A Quarterly Journal of Operations Research》2005,3(3):171-216
Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear
problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing
algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space.
We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity,
constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices,
and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms
which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the
complexity of the respective problems.
In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare
the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear
optimization.
MSC classification:
90C30, 68Q25 相似文献
7.
In this work we consider a stochastic optimal control problem with either convex control constraints or finitely many equality
and inequality constraints over the final state. Using the variational approach, we are able to obtain first and second order
expansions for the state and cost function, around a local minimum. This fact allows us to prove general first order necessary
condition and, under a geometrical assumption over the constraint set, second order necessary conditions are also established.
We end by giving second order optimality conditions for problems with constraints on expectations of the final state. 相似文献
8.
Over the last few decades several methods have been proposed for handling functional constraints while solving optimization problems using evolutionary algorithms (EAs). However, the presence of equality constraints makes the feasible space very small compared to the entire search space. As a consequence, the handling of equality constraints has long been a difficult issue for evolutionary optimization methods. This paper presents a Hybrid Evolutionary Algorithm (HEA) for solving optimization problems with both equality and inequality constraints. In HEA, we propose a new local search technique with special emphasis on equality constraints. The basic concept of the new technique is to reach a point on the equality constraint from the current position of an individual solution, and then explore on the constraint landscape. We believe this new concept will influence the future research direction for constrained optimization using population based algorithms. The proposed algorithm is tested on a set of standard benchmark problems. The results show that the proposed technique works very well on those benchmark problems. 相似文献
9.
Bin Li Chang Jun Yu Kok Lay Teo Guang Ren Duan 《Journal of Optimization Theory and Applications》2011,151(2):260-291
In this paper, we consider a class of optimal control problems subject to equality terminal state constraints and continuous
state and control inequality constraints. By using the control parametrization technique and a time scaling transformation,
the constrained optimal control problem is approximated by a sequence of optimal parameter selection problems with equality
terminal state constraints and continuous state inequality constraints. Each of these constrained optimal parameter selection
problems can be regarded as an optimization problem subject to equality constraints and continuous inequality constraints.
On this basis, an exact penalty function method is used to devise a computational method to solve these optimization problems
with equality constraints and continuous inequality constraints. The main idea is to augment the exact penalty function constructed
from the equality constraints and continuous inequality constraints to the objective function, forming a new one. This gives
rise to a sequence of unconstrained optimization problems. It is shown that, for sufficiently large penalty parameter value,
any local minimizer of the unconstrained optimization problem is a local minimizer of the optimization problem with equality
constraints and continuous inequality constraints. The convergent properties of the optimal parameter selection problems with
equality constraints and continuous inequality constraints to the original optimal control problem are also discussed. For
illustration, three examples are solved showing the effectiveness and applicability of the approach proposed. 相似文献
10.
In this paper we provide a duality theory for multiobjective optimization problems with convex objective functions and finitely many D.C. constraints. In order to do this, we study first the duality for a scalar convex optimization problem with inequality constraints defined by extended real-valued convex functions. For a family of multiobjective problems associated to the initial one we determine then, by means of the scalar duality results, their multiobjective dual problems. Finally, we consider as a special case the duality for the convex multiobjective optimization problem with convex constraints. 相似文献
11.
S. Rangavajhala A. A. Mullur A. Messac 《Journal of Optimization Theory and Applications》2009,140(2):315-337
Robust design optimization (RDO) problems can generally be formulated by incorporating uncertainty into the corresponding
deterministic problems. In this context, a careful formulation of deterministic equality constraints into the robust domain
is necessary to avoid infeasible designs under uncertain conditions. The challenge of formulating equality constraints is
compounded in multiobjective RDO problems. Modeling the tradeoffs between the mean of the performance and the variation of
the performance for each design objective in a multiobjective RDO problem is itself a complex task. A judicious formulation
of equality constraints adds to this complexity because additional tradeoffs are introduced between constraint satisfaction
under uncertainty and multiobjective performance. Equality constraints under uncertainty in multiobjective problems can therefore
pose a complicated decision making problem. In this paper, we provide a new problem formulation that can be used as an effective
multiobjective decision making tool, with emphasis on equality constraints. We present two numerical examples to illustrate
our theoretical developments. 相似文献
12.
We first establish a relaxed version of Dines theorem associated to quadratic minimization problems with finitely many linear equality and a single (nonconvex) quadratic inequality constraints. The case of unbounded optimal valued is also discussed. Then, we characterize geometrically the strong duality, and some relationships with the conditions employed in Finsler theorem are established. Furthermore, necessary and sufficient optimality conditions with or without the Slater assumption are derived. Our results can be used to situations where none of the results appearing elsewhere are applicable. In addition, a revisited theorem due to Frank and Wolfe along with that due to Eaves is established for asymptotically linear sets. 相似文献
13.
Smoothed penalty algorithms for optimization of nonlinear models 总被引:1,自引:0,他引:1
M. Herty A. Klar A. K. Singh P. Spellucci 《Computational Optimization and Applications》2007,37(2):157-176
We introduce an algorithm for solving nonlinear optimization problems with general equality and box constraints. The proposed
algorithm is based on smoothing of the exact l
1-penalty function and solving the resulting problem by any box-constraint optimization method. We introduce a general algorithm
and present theoretical results for updating the penalty and smoothing parameter. We apply the algorithm to optimization problems
for nonlinear traffic network models and report on numerical results for a variety of network problems and different solvers
for the subproblems. 相似文献
14.
Nikolai P. Osmolovskii 《Journal of Mathematical Analysis and Applications》2018,457(2):1613-1633
One of the first steps towards necessary second-order optimality conditions in problems with constraints was taken by Dubovitskii and Milyutin in 1965. They offered a scheme that was very effective in smooth optimization problems, but seemed to be not suitable for applications in problems with pointwise control constraints. In this article we consider a modification of the Dubovitskii–Milyutin scheme, which allows to derive necessary second-order conditions for a weak local minimum in optimal control problems with a finite number of endpoint constraints of equality and inequality type and with pointwise control constraints of inequality type given by smooth functions. Assuming that the gradients of active control constraints are linearly independent, we provide rather straightforward proof of these conditions for a measurable and essentially bounded optimal control. 相似文献
15.
We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of
a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem
includes the covariance selection problem that can be expressed as an ℓ
1-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated
as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The
method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a
local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem,
the method can terminate in O(n3/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim
19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the
BCGD method can be efficient for large-scale covariance selection problems with constraints. 相似文献
16.
Z. K. Xu 《Journal of Optimization Theory and Applications》1997,94(3):739-746
Recently, Li (Ref. 1) obtained a saddle-point result for a general class of nonconvex optimization problems with inequality constraints, by using a transformation equivalent to taking the pth power of the objective function and the constraints, under several conditions. In this paper, we show that, by an equivalent transformation, using the pth power of the constraints or using the pth power of the objective function and the constraints, the same result can be obtained under much weaker and reasonable conditions. Also, our results can be extended to the problem in which equality and inequality constraints are involved. 相似文献
17.
Frank E. Curtis Nicholas I. M. Gould Daniel P. Robinson Philippe L. Toint 《Mathematical Programming》2017,161(1-2):73-134
We present an interior-point trust-funnel algorithm for solving large-scale nonlinear optimization problems. The method is based on an approach proposed by Gould and Toint (Math Prog 122(1):155–196, 2010) that focused on solving equality constrained problems. Our method is similar in that it achieves global convergence guarantees by combining a trust-region methodology with a funnel mechanism, but has the additional capability of being able to solve problems with both equality and inequality constraints. The prominent features of our algorithm are that (i) the subproblems that define each search direction may be solved with matrix-free methods so that derivative matrices need not be formed or factorized so long as matrix-vector products with them can be performed; (ii) the subproblems may be solved approximately in all iterations; (iii) in certain situations, the computed search directions represent inexact sequential quadratic optimization steps, which may be desirable for fast local convergence; (iv) criticality measures for feasibility and optimality aid in determining whether only a subset of computations need to be performed during a given iteration; and (v) no merit function or filter is needed to ensure global convergence. 相似文献
18.
Francisco Guerra-Vázquez 《Optimization》2017,66(8):1237-1249
AbstractIn this paper, we consider multiobjective semi-infinite optimization problems which are defined in a finite-dimensional space by finitely many objective functions and infinitely many inequality constraints. We present duality results both for the convex and nonconvex case. In particular, we show weak, strong and converse duality with respect to both efficiency and weak efficiency. Moreover, the property of being a locally properly efficient point plays a crucial role in the nonconvex case. 相似文献
19.
Based on an augmented Lagrangian line search function, a sequential quadratically constrained quadratic programming method is proposed for solving nonlinearly constrained optimization problems. Compared to quadratic programming solved in the traditional SQP methods, a convex quadratically constrained quadratic programming is solved here to obtain a search direction, and the Maratos effect does not occur without any other corrections. The “active set” strategy used in this subproblem can avoid recalculating the unnecessary gradients and (approximate) Hessian matrices of the constraints. Under certain assumptions, the proposed method is proved to be globally, superlinearly, and quadratically convergent. As an extension, general problems with inequality and equality constraints as well as nonmonotone line search are also considered. 相似文献
20.
This paper studies how to solve semi-infinite polynomial programming (SIPP) problems by semidefinite relaxation methods. We first recall two SDP relaxation methods for solving polynomial optimization problems with finitely many constraints. Then we propose an exchange algorithm with SDP relaxations to solve SIPP problems with compact index set. At last, we extend the proposed method to SIPP problems with noncompact index set via homogenization. Numerical results show that the algorithm is efficient in practice. 相似文献