A general method for solving constrained optimization problems

In this paper a general problem of constrained minimization is studied. The minima are determined by searching for the asymptotical values of the solutions of a suitable system of ordinary differential equations.For this system, if the initial point is feasible, then any trajectory is always inside the set of constraints and tends towards a set of critical points. Each critical point that is not a relative minimum is unstable. For formulas of one-step numerical integration, an estimate of the step of integration is given, so that the above mentioned qualitative properties of the system of ordinary differential equations are kept.     

A novel neural network based on NCP function for solving constrained nonconvex optimization problems

This article presents a novel neural network (NN) based on NCP function for solving nonconvex nonlinear optimization (NCNO) problem subject to nonlinear inequality constraints. We first apply the p‐power convexification of the Lagrangian function in the NCNO problem. The proposed NN is a gradient model which is constructed by an NCP function and an unconstrained minimization problem. The main feature of this NN is that its equilibrium point coincides with the optimal solution of the original problem. Under a proper assumption and utilizing a suitable Lyapunov function, it is shown that the proposed NN is Lyapunov stable and convergent to an exact optimal solution of the original problem. Finally, simulation results on two numerical examples and two practical examples are given to show the effectiveness and applicability of the proposed NN. © 2015 Wiley Periodicals, Inc. Complexity 21: 130–141, 2016     

Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality

This paper presents a canonical duality theory for solving a general nonconvex quadratic minimization problem with nonconvex constraints. By using the canonical dual transformation developed by the first author, the nonconvex primal problem can be converted into a canonical dual problem with zero duality gap. A general analytical solution form is obtained. Both global and local extrema of the nonconvex problem can be identified by the triality theory associated with the canonical duality theory. Illustrative applications to quadratic minimization with multiple quadratic constraints, box/integer constraints, and general nonconvex polynomial constraints are discussed, along with insightful connections to classical Lagrangian duality. Criteria for the existence and uniqueness of optimal solutions are presented. Several numerical examples are provided.     

Zero duality gap for a class of nonconvex optimization problems

By an equivalent transformation using thepth power of the objective function and the constraint, a saddle point can be generated for a general class of nonconvex optimization problems. Zero duality gap is thus guaranteed when the primal-dual method is applied to the constructed equivalent form.The author very much appreciates the comments from Prof. Douglas J. White.     

An extragradient algorithm for solving general nonconvex variational inequalities

In this work, we suggest and analyze an extragradient method for solving general nonconvex variational inequalities using the technique of the projection operator. We prove that the convergence of the extragradient method requires only pseudomonotonicity, which is a weaker condition than requiring monotonicity. In this sense, our result can be viewed as an improvement and refinement of the previously known results. Our method of proof is very simple as compared with other techniques.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.     

SDP reformulation for robust optimization problems based on nonconvex QP duality

In a real situation, optimization problems often involve uncertain parameters. Robust optimization is one of distribution-free methodologies based on worst-case analyses for handling such problems. In this paper, we first focus on a special class of uncertain linear programs (LPs). Applying the duality theory for nonconvex quadratic programs (QPs), we reformulate the robust counterpart as a semidefinite program (SDP) and show the equivalence property under mild assumptions. We also apply the same technique to the uncertain second-order cone programs (SOCPs) with “single” (not side-wise) ellipsoidal uncertainty. Then we derive similar results on the reformulation and the equivalence property. In the numerical experiments, we solve some test problems to demonstrate the efficiency of our reformulation approach. Especially, we compare our approach with another recent method based on Hildebrand’s Lorentz positivity.     

Saddle points of general augmented Lagrangians for constrained nonconvex optimization

Local and global saddle point conditions for a general augmented Lagrangian function proposed by Mangasarian are investigated in the paper for inequality and equality constrained nonconvex optimization problems. Under second order sufficiency conditions, it is proved that the augmented Lagrangian admits a local saddle point, but without requiring the strict complementarity condition. The existence of a global saddle point is then obtained under additional assumptions that do not require the compactness of the feasible set and the uniqueness of global solution of the original problem.     

A general regularized gradient-projection method for solving equilibrium and constrained convex minimization problems

In this article, we provide a general iterative method for solving an equilibrium and a constrained convex minimization problem. By using the idea of regularized gradient-projection algorithm (RGPA), we find a common element, which is also a solution of a variational inequality problem. Then the strong convergence theorems are obtained under suitable conditions.     

Applications of Toland's duality theory to nonconvex optimization problems

Through a suitable application of Toland's duality theory to certain nonconvex and nonsmooth problems one obtain an unbounded minimization problem with Fréchet:-differentiable cost function as dual problem and one can establish a gradient projection method for the solution of these problems.     

On zero duality gap in nonconvex quadratic programming problems

We present in this paper new sufficient conditions for verifying zero duality gap in nonconvex quadratically/linearly constrained quadratic programs (QP). Based on saddle point condition and conic duality theorem, we first derive a sufficient condition for the zero duality gap between a quadratically constrained QP and its Lagrangian dual or SDP relaxation. We then use a distance measure to characterize the duality gap for nonconvex QP with linear constraints. We show that this distance can be computed via cell enumeration technique in discrete geometry. Finally, we revisit two sufficient optimality conditions in the literature for two classes of nonconvex QPs and show that these conditions actually imply zero duality gap.     

Normality of the maximum principle for nonconvex constrained Bolza problems

We consider a Bolza optimal control problem with state constraints. It is well known that under some technical assumptions every strong local minimizer of this problem satisfies first order necessary optimality conditions in the form of a constrained maximum principle. In general, the maximum principle may be abnormal or even degenerate and so does not provide a sufficient information about optimal controls. In the recent literature some sufficient conditions were proposed to guarantee that at least one maximum principle is nondegenerate, cf. [A.V. Arutyanov, S.M. Aseev, Investigation of the degeneracy phenomenon of the maximum principle for optimal control problems with state constraints, SIAM J. Control Optim. 35 (1997) 930–952; F. Rampazzo, R.B. Vinter, A theorem on existence of neighbouring trajectories satisfying a state constraint, with applications to optimal control, IMA 16 (4) (1999) 335–351; F. Rampazzo, R.B. Vinter, Degenerate optimal control problems with state constraints, SIAM J. Control Optim. 39 (4) (2000) 989–1007]. Our aim is to show that actually conditions of a similar nature guarantee normality of every nondegenerate maximum principle. In particular we allow the initial condition to be fixed and the state constraints to be nonsmooth. To prove normality we use J. Yorke type linearization of control systems and show the existence of a solution to a linearized control system satisfying new state constraints defined, in turn, by linearization of the original set of constraints along an extremal trajectory.     

Projection-iteration methods for solving constrained minimization problems

The problem of minimization of the functionalf(x) on the set in a Hilbert space H is solved by methods that approximatef(x) by a sequence of functionalsf _n(x_n) defined on the sets _n= H _n (H _n H) and then minimize eachf _n(x_n) on _n by gradient projection methods. Several approximations x_n ⁽ⁱ⁾(i=1,2,...,k_n) are constructed for each functional, and the last approximation is accepted as the starting approximation for the next functional. Convergence theorems are proved and error bounds are obtained.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 64, pp. 3–8, 1988.     

A general duality theorem for marginal problems

Summary Given probability spaces (X _i ,A _i ,P _i ),i=1, 2 letM(P ₁,P ₂) denote the set of all probabilities on the product space with marginalsP ₁ andP ₂ and leth be a measurable function on (X ₁×X ₂,A ₁ A ₂). In order to determine supfh dP where the supremum is taken overP inM(P ₁,P ₂), a general duality theorem is proved. Only the perfectness of one of the coordinate spaces is imposed without any further topological or tightness assumptions. An example without any further topological or tightness assumptions. An example is given to show that the assumption of perfectness is essential. Applications to probabilities with given marginals and given supports, stochastic order and probability metrics are included.     

Weak Fenchel and weak Fenchel-Lagrange conjugate duality for nonconvex scalar optimization problems

In this work, by using weak conjugate maps given in (Azimov and Gasimov, in Int J Appl Math 1:171–192, 1999), weak Fenchel conjugate dual problem, ${(D_F^w)}$ , and weak Fenchel Lagrange conjugate dual problem ${(D_{FL}^w)}$ are constructed. Necessary and sufficient conditions for strong duality for the ${(D_F^w)}$ , ${(D_{FL}^w)}$ and primal problem are given. Furthermore, relations among the optimal objective values of dual problem constructed by using Augmented Lagrangian in (Azimov and Gasimov, in Int J Appl Math 1:171–192, 1999), ${(D_F^w)}$ , ${(D_{FL}^w)}$ dual problems and primal problem are examined. Lastly, necessary and sufficient optimality conditions for the primal and the dual problems ${(D_F^w)}$ and ${(D_{FL}^w)}$ are established.     

Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

Nonoccurrence of the Lavrentiev phenomenon for many nonconvex constrained variational problems

In this paper we study nonoccurrence of the Lavrentiev phenomenon for a large class of nonconvex nonautonomous constrained variational problems. A state variable belongs to a convex subset of a Banach space with nonempty interior. Integrands belong to a complete metric space of functions which satisfy a growth condition common in the literature and are Lipschitzian on bounded sets. In our previous work Zaslavski (Ann. Inst. H. Poincare, Anal. non lineare, 2006) we considered a class of nonconstrained variational problems with integrands belonging to a subset and showed that for any such integrand the infimum on the full admissible class is equal to the infimum on a subclass of Lipschitzian functions with the same Lipschitzian constant. In the present paper we show that if an integrand f belongs to , then this property also holds for any integrand which is contained in a certain neighborhood of f in . Using this result we establish nonoccurrence of the Lavrentiev phenomenon for most elements of in the sense of Baire category.      

An algorithm for solving linearly constrained minimax problems

In this study, we propose an algorithm for solving a minimax problem over a polyhedral set defined in terms of a system of linear inequalities. At each iteration a direction is found by solving a quadratic programming problem and then a suitable step size along that direction is taken through an extension of Armijo's approximate line search technique. We show that each accumulation point is a Kuhn-Tucker solution and give a condition that guarantees convergence of the whole sequence of iterations. Through the use of an exact penalty function, the algorithm can be used for solving constrained nonlinear programming. In this case, our algorithm resembles that of Han, but differs from it both in the direction-finding and the line search steps.