共查询到20条相似文献,搜索用时 656 毫秒
1.
Hong-xia Yin 《应用数学学报(英文版)》2009,25(4):685-696
In the paper we investigate smoothing method for solving semi-infinite minimax problems. Not like most of the literature in semi-infinite minimax problems which are concerned with the continuous time version(i.e., the one dimensional semi-infinite minimax problems), the primary focus of this paper is on multi- dimensional semi-infinite minimax problems. The global error bounds of two smoothing approximations for the objective function are given and compared. It is proved that the smoothing approximation given in this paper can provide a better error bound than the existing one in literature. 相似文献
2.
In this paper we present a homotopy continuation method for finding the Karush-Kuhn-Tucker point of a class of nonlinear non-convex programming problems. Two numerical examples are given to show that this method is effective. It should be pointed out that we extend the results of Lin et al. (see Appl. Math. Comput., 80(1996), 209-224) to a broader class of non-convex programming problems. 相似文献
3.
4.
We study convergence of a semismooth Newton method for generalized semi-infinite programming problems with convex lower level
problems where, using NCP functions, the upper and lower level Karush-Kuhn-Tucker conditions of the optimization problem are
reformulated as a semismooth system of equations. Nonsmoothness is caused by a possible violation of strict complementarity
slackness. We show that the standard regularity condition for convergence of the semismooth Newton method is satisfied under
natural assumptions for semi-infinite programs. In fact, under the Reduction Ansatz in the lower level and strong stability
in the reduced upper level problem this regularity condition is satisfied. In particular, we do not have to assume strict
complementary slackness in the upper level. Numerical examples from, among others, design centering and robust optimization
illustrate the performance of the method.
相似文献
5.
This paper discusses the convergence properties of a smoothing approach for solving the mathematical programs with second-order
cone complementarity constraints (SOCMPCCs). We first introduce B-stationary, C-stationary, M(orduckhovich)-stationary, S-stationary
point, SOCMPCC-linear independence constraint qualification (denoted by SOCMPCC-LICQ), second-order cone upper level strict
complementarity (denoted by SOC-ULSC) condition at a feasible point of a SOCMPCC problem. With the help of the projection
operator over a second-order cone, we construct a smooth optimization problem to approximate the SOCMPCC. We demonstrate that
any accumulation point of the sequence of stationary points to the sequence of smoothing problems, when smoothing parameters
decrease to zero, is a C-stationary point to the SOCMPCC under SOCMPCC-LICQ at the accumulation point. We also prove that
the accumulation point is an M-stationary point if, in addition, the sequence of stationary points satisfy weak second order
necessary conditions for the sequence of smoothing problems, and moreover it is a B-stationary point if, in addition, the
SOC-ULSC condition holds at the accumulation point. 相似文献
6.
In this paper, we analyze the outer approximation property of the algorithm for generalized semi-infinite programming from
Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). A simple bound on the regularization error is found and used to formulate a feasible numerical method for generalized semi-infinite programming with convex lower-level problems. That is, all iterates of the
numerical method are feasible points of the original optimization problem. The new method has the same computational cost
as the original algorithm from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). We also discuss the merits of this approach for the adaptive convexification algorithm, a feasible point method for standard
semi-infinite programming from Floudas and Stein (SIAM J. Optim. 18:1187–1208, 2007). 相似文献
7.
Feng Shan Liwei Zhang Xiantao Xiao 《Journal of Optimization Theory and Applications》2014,163(1):181-199
In this article, we consider a DC (difference of two convex functions) function approach for solving joint chance-constrained programs (JCCP), which was first established by Hong et al. (Oper Res 59:617–630, 2011). They used a DC function to approximate the probability function and constructed a sequential convex approximation method to solve the approximation problem. However, the DC function they used was nondifferentiable. To alleviate this difficulty, we propose a class of smoothing functions to approximate the joint chance-constraint function, based on which smooth optimization problems are constructed to approximate JCCP. We show that the solutions of a sequence of smoothing approximations converge to a Karush–Kuhn–Tucker point of JCCP under a certain asymptotic regime. To implement the proposed method, four examples in the class of smoothing functions are explored. Moreover, the numerical experiments show that our method is comparable and effective. 相似文献
8.
We provide a refined convergence analysis for the SAA (sample average approximation) method applied to stochastic optimization
problems with either single or mixed CVaR (conditional value-at-risk) measures. Under certain regularity conditions, it is
shown that any accumulation point of the weak GKKT (generalized Karush-Kuhn-Tucker) points produced by the SAA method is almost
surely a weak stationary point of the original CVaR or mixed CVaR optimization problems. In addition, it is shown that, as
the sample size increases, the difference of the optimal values between the SAA problems and the original problem tends to
zero with probability approaching one exponentially fast. 相似文献
9.
We develop two implementable algorithms, the first for the solution of finite and the second for the solution of semi-infinite min-max-min problems. A smoothing technique (together with discretization for the semi-infinite case) is used to construct a sequence of approximating finite min-max problems, which are solved with increasing precision. The smoothing and discretization approximations are initially coarse, but are made progressively finer as the number of iterations is increased. This reduces the potential ill-conditioning due to high smoothing precision parameter values and computational cost due to high levels of discretization. The behavior of the algorithms is illustrated with three semi-infinite numerical examples. 相似文献
10.
E. Polak R. S. Womersley H. X. Yin 《Journal of Optimization Theory and Applications》2008,138(2):311-328
We present a new active-set strategy which can be used in conjunction with exponential (entropic) smoothing for solving large-scale
minimax problems arising from the discretization of semi-infinite minimax problems. The main effect of the active-set strategy
is to dramatically reduce the number of gradient calculations needed in the optimization. Discretization of multidimensional
domains gives rise to minimax problems with thousands of component functions. We present an application to minimizing the
sum of squares of the Lagrange polynomials to find good points for polynomial interpolation on the unit sphere in ℝ3. Our numerical results show that the active-set strategy results in a modified Armijo gradient or Gauss-Newton like methods
requiring less than a quarter of the gradients, as compared to the use of these methods without our active-set strategy. Finally,
we show how this strategy can be incorporated in an algorithm for solving semi-infinite minimax problems. 相似文献
11.
《Optimization》2012,61(1):39-50
We extend the convergence analysis of a smoothing method [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg.] to a general class of smoothing functions and show that a weak second-order necessary optimality condition holds at the limit point of a sequence of stationary points found by the smoothing method. We also show that convergence and stability results in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] hold for a relaxation problem suggested by Scholtes [S. Scholtes (2003). Private communications.] using a class of smoothing functions. In addition, the relationship between two technical, yet critical, concepts in [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg; S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] for the convergence analysis of the smoothing and regularization methods is discussed and a counter-example is provided to show that the stability result in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] cannot be extended to a weaker regularization. 相似文献
12.
We study the problem of solving a constrained system of nonlinear equations by a combination of the classical damped Newton
method for (unconstrained) smooth equations and the recent interior point potential reduction methods for linear programs,
linear and nonlinear complementarity problems. In general, constrained equations provide a unified formulation for many mathematical
programming problems, including complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational
inequalities and nonlinear programs. Combining ideas from the damped Newton and interior point methods, we present an iterative
algorithm for solving a constrained system of equations and investigate its convergence properties. Specialization of the
algorithm and its convergence analysis to complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of
variational inequalities are discussed in detail. We also report the computational results of the implementation of the algorithm
for solving several classes of convex programs.
The work of this author was based on research supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739
and the Office of Naval Research under grant N00014-93-1-0228.
The work of this author was based on research supported by the National Science Foundation under grant DMI-9496178 and the
Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340. 相似文献
13.
In this paper a log-exponential smoothing method for mathematical programs with complementarity constraints (MPCC) is analyzed, with some new interesting properties and convergence results provided. It is shown that the stationary points of the resulting smoothed problem converge to the strongly stationary point of MPCC, under the linear independence constraint qualification (LICQ), the weak second-order necessary condition (WSONC), and some reasonable assumption. Moreover, the limit point satisfies the weak second-order necessary condition for MPCC. A notable fact is that the proposed convergence results do not restrict the complementarity constraint functions approach to zero at the same order of magnitude. 相似文献
14.
M. A. Goberna G. A. Lancho M. I. Todorov V. N. Vera de Serio 《Applied Mathematics and Optimization》2011,63(2):239-256
The concept of implicit active constraints at a given point provides useful local information about the solution set of linear
semi-infinite systems and about the optimal set in linear semi-infinite programming provided the set of gradient vectors of
the constraints is bounded, commonly under the additional assumption that there exists some strong Slater point. This paper
shows that the mentioned global boundedness condition can be replaced by a weaker local condition (LUB) based on locally active
constraints (active in a ball of small radius whose center is some nominal point), providing geometric information about the
solution set and Karush-Kuhn-Tucker type conditions for the optimal solution to be strongly unique. The maintaining of the
latter property under sufficiently small perturbations of all the data is also analyzed, giving a characterization of its
stability with respect to these perturbations in terms of the strong Slater condition, the so-called Extended-Nürnberger condition,
and the LUB condition. 相似文献
15.
We study first-order optimality conditions for the class of generalized semi-infinite programming problems (GSIPs). We extend
various well-known constraint qualifications for finite programming problems to GSIPs and analyze the extent to which a corresponding
Karush-Kuhn-Tucker (KKT) condition depends on these extensions. It is shown that in general the KKT condition for GSIPs takes
a weaker form unless a certain constraint qualification is satisfied. In the completely convex case where the objective of
the lower-level problem is concave and the constraint functions are quasiconvex, we show that the KKT condition takes a sharper
form.
The authors thank the anonymous referees for careful reading of the paper and helpful suggestions. The research of the first
author was partially supported by NSERC. 相似文献
16.
《Journal of Computational and Applied Mathematics》2006,196(2):459-473
In this paper, we develop two discretization algorithms with a cutting plane scheme for solving combined semi-infinite and semi-definite programming problems, i.e., a general algorithm when the parameter set is a compact set and a typical algorithm when the parameter set is a box set in the m-dimensional space. We prove that the accumulation point of the sequence points generated by the two algorithms is an optimal solution of the combined semi-infinite and semi-definite programming problem under suitable assumption conditions. Two examples are given to illustrate the effectiveness of the typical algorithm. 相似文献
17.
Angelos Tsoukalas Berç Rustem Efstratios N. Pistikopoulos 《Journal of Global Optimization》2009,44(2):235-250
We propose an algorithm for the global optimization of three problem classes: generalized semi-infinite, continuous coupled
minimax and bi-level problems. We make no convexity assumptions. For each problem class, we construct an oracle that decides
whether a given objective value is achievable or not. If a given value is achievable, the oracle returns a point with a value
better than or equal to the target. A binary search is then performed until the global optimum is obtained with the desired
accuracy. This is achieved by solving a series of appropriate finite minimax and min-max-min problems to global optimality.
We use Laplace’s smoothing technique and a simulated annealing approach for the solution of these problems. We present computational
examples for all three problem classes. 相似文献
18.
Smoothing of data is a problem very important for many applications ranging from 1-D signals (e.g., speech) to 2-D and 3-D signals (e.g., images). Many methods exist in the literature for facing the problem; in the present paper we point our attention on regularization. We shall treat regularization methods in a general framework which is well suited for wavelet analysis; in particular we shall investigate on the relation existing between thresholding methods and regularization. We shall also introduce a new regularization method (Besov regularization), which includes some known regularization and thresholding methods as particular cases. Numerical experiments based on some test problems will be performed in order to compare the performance of some methods of smoothing data. AMS (MOS) Subject Classifications: 65R30, 41A60. 相似文献
19.
We consider a semismooth reformulation of the KKT system arising from the semi-infinite programming (SIP) problem. Based upon
this reformulation, we present a new smoothing Newton-type method for the solution of SIP problem. The main properties of
this method are: (a) it is globally convergent at least to a stationary point of the SIP problem, (b) it is locally superlinearly
convergent under a certain regularity condition, (c) the feasibility is ensured via the aggregated constraint, and (d) it
has to solve just one linear system of equations at each iteration. Preliminary numerical results are reported. 相似文献
20.
In this paper, we consider the stochastic second-order cone complementarity problems (SSOCCP). We first formulate the SSOCCP contained expectation as an optimization problem using the so-called second-order cone complementarity function. We then use sample average approximation method and smoothing technique to obtain the approximation problems for solving this reformulation. In theory, we show that any accumulation point of the global optimal solutions or stationary points of the approximation problems are global optimal solution or stationary point of the original problem under suitable conditions. Finally, some numerical examples are given to explain that the proposed methods are feasible. 相似文献