On optimality conditions in optimization problems on solutions of operator equations

We study optimization problems in the presence of connection in the form of operator equations defined in Banach spaces. We prove necessary conditions for optimality of first and second order, for example generalizing the Pontryagin maximal principle for these problems. It is not our purpose to state the most general necessary optimality conditions or to compile a list of all necessary conditions that characterize optimal control in any particular minimization problem. In the present article we describe schemes for obtaining necessary conditions for optimality on solutions of general operator equations defined in Banach spaces, and the scheme discussed here does not require that there be no global functional constraints on the controlling parameters. As an example, in a particular Banach space we prove an optimality condition using the Pontryagin-McShane variation. Bibliography: 20 titles. Translated fromProblemy Matematicheskoi Fiziki, 1998, pp. 55–67.     

Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions

In this paper, we first examine how global optimality of non-convex constrained optimization problems is related to Lagrange multiplier conditions. We then establish Lagrange multiplier conditions for global optimality of general quadratic minimization problems with quadratic constraints. We also obtain necessary global optimality conditions, which are different from the Lagrange multiplier conditions for special classes of quadratic optimization problems. These classes include weighted least squares with ellipsoidal constraints, and quadratic minimization with binary constraints. We discuss examples which demonstrate that our optimality conditions can effectively be used for identifying global minimizers of certain multi-extremal non-convex quadratic optimization problems. The work of Z. Y. Wu was carried out while the author was at the Department of Applied Mathematics, University of New South Wales, Sydney, Australia.     

Global Optimality Conditions for Some Classes of Optimization Problems

We establish new necessary and sufficient optimality conditions for global optimization problems. In particular, we establish tractable optimality conditions for the problems of minimizing a weakly convex or concave function subject to standard constraints, such as box constraints, binary constraints, and simplex constraints. We also derive some new necessary and sufficient optimality conditions for quadratic optimization. Our main theoretical tool for establishing these optimality conditions is abstract convexity.     

Sufficient global optimality conditions for weakly convex minimization problems

In this paper, we present sufficient global optimality conditions for weakly convex minimization problems using abstract convex analysis theory. By introducing (L,X)-subdifferentials of weakly convex functions using a class of quadratic functions, we first obtain some sufficient conditions for global optimization problems with weakly convex objective functions and weakly convex inequality and equality constraints. Some sufficient optimality conditions for problems with additional box constraints and bivalent constraints are then derived.      

An application of matrix computations to classical second-order optimality conditions

For finite dimensional optimization problems with equality and inequality constraints, a weak constant rank condition (WCR) was introduced by Andreani–Martinez–Schuverdt (AMS) (Optimization 5–6:529–542, 2007) to study classical necessary second-order optimality conditions. However, this condition is not easy to check. Using a polynomial and matrix computation tools, we can substitute it by a weak constant rank condition (WCRQ) for an approximated problem and we present a method for checking points that satisfy WCRQ. We extend the result of (Andreani et al. in Optimization 5–6:529–542, 2007), we show that WCR can be replaced by WCRQ and we prove that these two conditions are independent.     

线性约束三次规划问题的全局最优性必要条件和最优化算法

讨论了带线性不等式约束三次规划问题的最优性条件和最优化算法. 首先, 讨论了带有线性不等式约束三次规划问题的 全局最优性必要条件. 然后, 利用全局最优性必要条件, 设计了解线性约束三次规划问题的一个新的局部最优化算法(强局部最优化算法). 再利用辅助函数和所给出的新的局部最优化算法, 设计了带有线性不等式约束三 规划问题的全局最优化算法. 最后, 数值算例说明给出的最优化算法是可行的、有效的.     

Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations

In this paper we present necessary conditions for global optimality for polynomial problems with box or bivalent constraints using separable polynomial relaxations. We achieve this by first deriving a numerically checkable characterization of global optimality for separable polynomial problems with box as well as bivalent constraints. Our necessary optimality conditions can be numerically checked by solving semi-definite programming problems. Then, by employing separable polynomial under-estimators, we establish sufficient conditions for global optimality for classes of polynomial optimization problems with box or bivalent constraints. We construct underestimators using the sum of squares convex (SOS-convex) polynomials of real algebraic geometry. An important feature of SOS-convexity that is generally not shared by the standard convexity is that whether a polynomial is SOS-convex or not can be checked by solving a semidefinite programming problem. We illustrate the versatility of our optimality conditions by simple numerical examples.     

Global minimization of difference of quadratic and convex functions over box or binary constraints

In this paper, we present necessary as well as sufficient conditions for a given feasible point to be a global minimizer of the difference of quadratic and convex functions subject to bounds on the variables. We show that the necessary conditions become necessary and sufficient for global minimizers in the case of a weighted sum of squares minimization problems. We obtain sufficient conditions for global optimality by first constructing quadratic underestimators and then by characterizing global minimizers of the underestimators. We also derive global optimality conditions for the minimization of the difference of quadratic and convex functions over binary constraints. We discuss several numerical examples to illustrate the significance of the optimality conditions. The authors are grateful to the referees for their helpful comments and valuable suggestions which have contributed to the final preparation of the paper.     

Global optimality conditions for quadratic 0-1 optimization problems

In the present work, we intend to derive conditions characterizing globally optimal solutions of quadratic 0-1 programming problems. By specializing the problem of maximizing a convex quadratic function under linear constraints, we find explicit global optimality conditions for quadratic 0-1 programming problems, including necessary and sufficient conditions and some necessary conditions. We also present some global optimality conditions for the problem of minimization of half-products.     

Generalized Benders’ Decomposition for topology optimization problems

This article considers the non-linear mixed 0–1 optimization problems that appear in topology optimization of load carrying structures. The main objective is to present a Generalized Benders’ Decomposition (GBD) method for solving single and multiple load minimum compliance (maximum stiffness) problems with discrete design variables to global optimality. We present the theoretical aspects of the method, including a proof of finite convergence and conditions for obtaining global optimal solutions. The method is also linked to, and compared with, an Outer-Approximation approach and a mixed 0–1 semi definite programming formulation of the considered problem. Several ways to accelerate the method are suggested and an implementation is described. Finally, a set of truss topology optimization problems are numerically solved to global optimality.     

Solutions to quadratic minimization problems with box and integer constraints

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.     

A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

Second-order conditions in stability analysis for state constrained optimal control

The paper presents an outline of the stability results, for state-constrained optimal control problems, recently obtained in Malanowski (Appl. Math. Optim. 55, 255–271, 2007), Malanowski (Optimization, to be published), Malanowski (SIAM J. Optim., to be published). The pricipal novelty of the results is a weakening of the second-order sufficient optimality conditions, under which the solutions and the Lagrange multipliers are locally Lipschitz continuous functions of the parameter. The conditions are weakened by taking into account strongly active state constraints.     

Some Properties of General Minimization Problems with Constraints

The paper studies the existence of solutions and necessary conditions of optimality for a general minimization problem with constraints. Although we focus mainly on the case where the cost functional is locally Lipschitz, a general Palais–Smale condition is proposed and some of its properties are studied. Applications to an optimal control problem and a Lagrange multiplier rule are also given.     

Duality and optimality conditions for generalized equilibrium problems involving DC functions

We consider a generalized equilibrium problem involving DC functions which is called (GEP). For this problem we establish two new dual formulations based on Toland-Fenchel-Lagrange duality for DC programming problems. The first one allows us to obtain a unified dual analysis for many interesting problems. So, this dual coincides with the dual problem proposed by Martinez-Legaz and Sosa (J Glob Optim 25:311–319, 2006) for equilibrium problems in the sense of Blum and Oettli. Furthermore it is equivalent to Mosco’s dual problem (Mosco in J Math Anal Appl 40:202–206, 1972) when applied to a variational inequality problem. The second dual problem generalizes to our problem another dual scheme that has been recently introduced by Jacinto and Scheimberg (Optimization 57:795–805, 2008) for convex equilibrium problems. Through these schemes, as by products, we obtain new optimality conditions for (GEP) and also, gap functions for (GEP), which cover the ones in Antangerel et al. (J Oper Res 24:353–371, 2007, Pac J Optim 2:667–678, 2006) for variational inequalities and standard convex equilibrium problems. These results, in turn, when applied to DC and convex optimization problems with convex constraints (considered as special cases of (GEP)) lead to Toland-Fenchel-Lagrange duality for DC problems in Dinh et al. (Optimization 1–20, 2008, J Convex Anal 15:235–262, 2008), Fenchel-Lagrange and Lagrange dualities for convex problems as in Antangerel et al. (Pac J Optim 2:667–678, 2006), Bot and Wanka (Nonlinear Anal to appear), Jeyakumar et al. (Applied Mathematics research report AMR04/8, 2004). Besides, as consequences of the main results, we obtain some new optimality conditions for DC and convex problems.     

Karush-Kuhn-Tucker systems: regularity conditions,error bounds and a class of Newton-type methods

 We consider optimality systems of Karush-Kuhn-Tucker (KKT) type, which arise, for example, as primal-dual conditions characterizing solutions of optimization problems or variational inequalities. In particular, we discuss error bounds and Newton-type methods for such systems. An exhaustive comparison of various regularity conditions which arise in this context is given. We obtain a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems, such as quasi-regularity or semistability (equivalently, the R ₀-property). Error bounds are useful, among other things, for identifying active constraints and developing efficient local algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods, as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence conditions of nonsmooth Newton methods and sequential quadratic programming methods. Received: December 10, 2001 / Accepted: July 28, 2002 Published online: February 14, 2003 Key words. KKT system – regularity – error bound – active constraints – Newton method Mathematics Subject Classification (1991): 90C30, 65K05     

A Simply Constrained Optimization Reformulation of KKT Systems Arising from Variational Inequalities

The Karush—Kuhn—Tucker (KKT) conditions can be regarded as optimality conditions for both variational inequalities and constrained optimization problems. In order to overcome some drawbacks of recently proposed reformulations of KKT systems, we propose casting KKT systems as a minimization problem with nonnegativity constraints on some of the variables. We prove that, under fairly mild assumptions, every stationary point of this constrained minimization problem is a solution of the KKT conditions. Based on this reformulation, a new algorithm for the solution of the KKT conditions is suggested and shown to have some strong global and local convergence properties. Accepted 10 December 1997     

双值约束非凸三次规化问题的全局最优性条件

考虑一类带有双值约束的非凸三次优化问题, 给出了该问题的一个全局最优充分必要条件. 结果改进并推广了一些文献中所给出的全局最优性条件, 同时还通过数值例子来说明所给出的全局最优充要条件是易验证的.     

Continuous GRASP with a local active-set method for bound-constrained global optimization

Global optimization seeks a minimum or maximum of a multimodal function over a discrete or continuous domain. In this paper, we propose a hybrid heuristic—based on the CGRASP and GENCAN methods—for finding approximate solutions for continuous global optimization problems subject to box constraints. Experimental results illustrate the relative effectiveness of CGRASP–GENCAN on a set of benchmark multimodal test functions.