A dynamic system model for solving convex nonlinear optimization problems

This paper proposes a feedback neural network model for solving convex nonlinear programming (CNLP) problems. Under the condition that the objective function is convex and all constraint functions are strictly convex or that the objective function is strictly convex and the constraint function is convex, the proposed neural network is proved to be stable in the sense of Lyapunov and globally convergent to an exact optimal solution of the original problem. The validity and transient behavior of the neural network are demonstrated by using some examples.     

Simplex-inspired algorithms for solving a class of convex programming problems

We consider a class of convex programming problems whose objective function is given as a linear function plus a convex function whose arguments are linear functions of the decision variables and whose feasible region is a polytope. We show that there exists an optimal solution to this class of problems on a face of the constraint polytope of dimension not more than the number of arguments of the convex function. Based on this result, we develop a method to solve this problem that is inspired by the simplex method for linear programming. It is shown that this method terminates in a finite number of iterations in the special case that the convex function has only a single argument. We then use this insight to develop a second algorithm that solves the problem in a finite number of iterations for an arbitrary number of arguments in the convex function. A computational study illustrates the efficiency of the algorithm and suggests that the average-case performance of these algorithms is a polynomial of low order in the number of decision variables. The work of T. C. Sharkey was supported by a National Science Foundation Graduate Research Fellowship. The work of H. E. Romeijn was supported by the National Science Foundation under Grant No. DMI-0355533.     

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.     

Inverse optimization for linearly constrained convex separable programming problems

In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ₁ and ℓ₂ norms. These inverse optimization problems are either linear programming when ℓ₁ norm is used in the formulation, or convex quadratic separable programming when ℓ₂ norm is used.     

Stability of linearly constrained convex quadratic programs

This paper establishes a simple necessary and sufficient condition for the stability of a linearly constrained convex quadratic program under perturbations of the linear part of the data, including the constraint matrix. It also establishes results on the continuity and differentiability of the optimal objective value of the program as a function of a parameter specifying the magnitude of the perturbation. The results established herein directly generalize well-known results on the stability of linear programs.     

Market price-based convex risk measures: A distribution-free optimization approach

In Cont (2006) [1], a convex risk measure was proposed to measure the impact of uncertainty resulting from the misspecification of derivative models. Evaluation of the risk measures was illustrated on finite families of probability measures. In this paper, we consider the case of infinite families of measures that share common moments, e.g. mean and variance for European-style options. We show that the risk measure can still be efficiently evaluated based on semi-infinite programming. Examples are given that illustrate the benefits of evaluating the risk measure with infinite families of measures and shed light on the limitations of considering only finite families of measures.     

A new global optimization approach for convex multiplicative programming

In this paper, by solving the relaxed quasiconcave programming problem in outcome space, a new global optimization algorithm for convex multiplicative programming is presented. Two kinds of techniques are employed to establish the algorithm. The first one is outer approximation technique which is applied to shrink relaxation area of quasiconcave programming problem and to compute appropriate feasible points and to raise the capacity of bounding. And the other one is branch and bound technique which is used to guarantee global optimization. Some numerical results are presented to demonstrate the effectiveness and feasibility of the proposed algorithm.     

Solving certain singly constrained convex optimization problems in production planning

This paper considers the problem of minimizing a special convex function subject to one linear constraint. Based upon a theorem for lower and upper bounds on the Lagrange multiplier a fully polynomial time approximation scheme is proposed. The efficiency of the algorithm is demonstrated by a computational experiment.     

The relationship between integer and real solutions of constrained convex programming

We prove the following theorem which gives a bound on the proximity of the real and the integer solutions to certain constrained optimization programs.     

A global optimization approach for solving the convex multiplicative programming problem

We consider a convex multiplicative programming problem of the form% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9qq-f0-yqaqVeLsFr0-vr% 0-vr0db8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaGG7bGaam% OzamaaBaaaleaacaaIXaaabeaakiaacIcacaWG4bGaaiykaiabgwSi% xlaadAgadaWgaaWcbaGaaGOmaaqabaGccaGGOaGaamiEaiaacMcaca% GG6aGaamiEaiabgIGiolaadIfacaGG9baaaa!4A08!\[\{ f_1 (x) \cdot f_2 (x):x \in X\} \]where X is a compact convex set of ⁿ and f ₁, f ₂ are convex functions which have nonnegative values over X.Using two additional variables we transform this problem into a problem with a special structure in which the objective function depends only on two of the (n+2) variables. Following a decomposition concept in global optimization we then reduce this problem to a master problem of minimizing a quasi-concave function over a convex set in ² ₂. This master problem can be solved by an outer approximation method which requires performing a sequence of simplex tableau pivoting operations. The proposed algorithm is finite when the functions f _i, (i=1, 2) are affine-linear and X is a polytope and it is convergent for the general convex case.Partly supported by the Deutsche Forschungsgemeinschaft Project CONMIN.     

A convex analysis approach for convex multiplicative programming

Global optimization problems involving the minimization of a product of convex functions on a convex set are addressed in this paper. Elements of convex analysis are used to obtain a suitable representation of the convex multiplicative problem in the outcome space, where its global solution is reduced to the solution of a sequence of quasiconcave minimizations on polytopes. Computational experiments illustrate the performance of the global optimization algorithm proposed.      

An unconstrained convex programming approach to solving convex quadratic programming problems

In this paper, we derive an unconstrained convex programming approach to solving convex quadratic programming problems in standard form. Related duality theory is established by using two simple inequalities. An ?-optimal solution is obtained by solving an unconstrained dual convex program. A dual-to-primal conversion formula is also provided. Some preliminary computational results of using a curved search method is included     

Self-adaptive velocity particle swarm optimization for solving constrained optimization problems

Particle swarm optimization (PSO) is originally developed as an unconstrained optimization technique, therefore lacks an explicit mechanism for handling constraints. When solving constrained optimization problems (COPs) with PSO, the existing research mainly focuses on how to handle constraints, and the impact of constraints on the inherent search mechanism of PSO has been scarcely explored. Motivated by this fact, in this paper we mainly investigate how to utilize the impact of constraints (or the knowledge about the feasible region) to improve the optimization ability of the particles. Based on these investigations, we present a modified PSO, called self-adaptive velocity particle swarm optimization (SAVPSO), for solving COPs. To handle constraints, in SAVPSO we adopt our recently proposed dynamic-objective constraint-handling method (DOCHM), which is essentially a constituent part of the inherent search mechanism of the integrated SAVPSO, i.e., DOCHM + SAVPSO. The performance of the integrated SAVPSO is tested on a well-known benchmark suite and the experimental results show that appropriately utilizing the knowledge about the feasible region can substantially improve the performance of the underlying algorithm in solving COPs.     

Examples of ill-behaved central paths in convex optimization

This paper presents some examples of ill-behaved central paths in convex optimization. Some contain infinitely many fixed length central segments; others manifest oscillations with infinite variation. These central paths can be encountered even for infinitely differentiable data.Mathematics Subject Classification (2000): 90C25, 90C51Research partially supported by CAPES, Brazil.Research partially supported by CAPES and CNPq, Brazil.     

A globalization procedure for solving nonlinear systems of equations

A new globalization procedure for solving a nonlinear system of equationsF(x)=0 is proposed based on the idea of combining Newton step and the steepest descent step WITHIN each iteration. Starting with an arbitrary initial point, the procedure converges either to a solution of the system or to a local minimizer off(x)=1/2F(x) ^T F(x). Each iteration is chosen to be as close to a Newton step as possible and could be the Newton step itself. Asymptotically the Newton step will be taken in each iteration and thus the convergence is quadratic. Numerical experiments yield positive results. Further generalizations of this procedure are also discussed in this paper.     

The CoMirror algorithm for solving nonsmooth constrained convex problems

We introduce a first-order Mirror-Descent (MD) type algorithm for solving nondifferentiable convex problems having a combination of simple constraint set X (ball, simplex, etc.) and an additional functional constraint. The method is tuned to exploit the structure of X by employing an appropriate non-Euclidean distance-like function. Convergence results and efficiency estimates are derived. The performance of the algorithm is demonstrated by solving certain image deblurring problems.     

Infinite-dimensional convex programming with applications to constrained approximation

In this paper, existence and characterization of solutions and duality aspects of infinite-dimensional convex programming problems are examined. Applications of the results to constrained approximation problems are considered. Various duality properties for constrained interpolation problems over convex sets are established under general regularity conditions. The regularity conditions are shown to hold for many constrained interpolation problems. Characterizations of local proximinal sets and the set of best approximations are also given in normed linear spaces.The author is grateful to the referee for helpful suggestions which have contributed to the final preparation of this paper. This research was partially supported by Grant A68930162 from the Australian Research Council.     

Pseudopower expansion of solutions of generalized equations and constrained optimization problems

We show that the solution of a strongly regular generalized equation subject to a scalar perturbation expands in pseudopower series in terms of the perturbation parameter, i.e., the expansion of orderk is the solution of generalized equations expanded to orderk and thus depends itself on the perturbation parameter. In the polyhedral case, this expansion reduces to a usual Taylor expansion. These results are applied to the problem of regular perturbation in constrained optimization. We show that, if the strong regularity condition is satisfied, the property of quadratic growth holds and, at least locally, the solutions of the optimization problem and of the associated optimality system coincide. If, in addition the number of inequality constraints is finite, the solution and the Lagrange multiplier can be expanded in Taylor series. If the data are analytic, the solution and the multiplier are analytic functions of the perturbation parameter.     

A residual method for solving nonlinear operator equations and their application to nonlinear integral equations using symbolic computation

A derivative-free residual method for solving nonlinear operator equations in real Hilbert spaces is discussed. This method uses in a systematic way the residual as search direction, but it does not use first order information. Furthermore a convergence analysis and numerical results of the new method applied to nonlinear integral equations using symbolic computation are presented.     

A multi-iterate method to solve systems of nonlinear equations

We propose an extension of secant methods for nonlinear equations using a population of previous iterates. Contrarily to classical secant methods, where exact interpolation is used, we prefer a least squares approach to calibrate the linear model. We propose an explicit control of the numerical stability of the method.