Nonconvex Problems of Global Optimization: Linear-Quadratic Control Problems with Quadratic Constraints

In this paper, we study a class of optimization problems,which are of certain interest for control theory. These problemsare of global constrained optimization and may be nonconvex ingeneral. A simple approach to their solution is presented. Aspecial attention is paid to the case when the objective andconstraints functions are quadratic functionals on a Hilbertspace. As an example of an application of the general approach,a methodology is presented by which an optimal controller canbe synthesized for a finite-horizon linear-quadratic controlproblem with quadratic constraints. Both inequality and equalityconstraints are considered. The objective and constraints functionalsmay be nonconvex and may contain both integral and terminal summands.It is shown that, under certain assumptions, the optimal controlexists, is unique, and has feedback structure. Furthermore, theoptimal controller can be computed by the methods of classiclinear-quadratic control theory coupled with those of finitedimensional convex programming.     

Globally convergent decomposition methods for nonconvex optimization problems

In this paper we consider nonlinear optimization problems of a separable form with nonconvex objective and convex constraints. A convexification procedure preserving separability is given in order that primal-dual methods are applicable. A globally convergent algorithm observing computational aspects is given. This algorithm was applied to a real world problem with 1007 variables and 4030 constraints for controlling the heads of a hydroenergy power station.     

DC programming and DCA for enhancing physical layer security via cooperative jamming

The explosive development of computational tools these days is threatening security of cryptographic algorithms, which are regarded as primary traditional methods for ensuring information security. The physical layer security approach is introduced as a method for both improving confidentiality of the secret key distribution in cryptography and enabling the data transmission without relaying on higher-layer encryption. In this paper, the cooperative jamming paradigm - one of the techniques used in the physical layer is studied and the resulting power allocation problem with the aim of maximizing the sum of secrecy rates subject to power constraints is formulated as a nonconvex optimization problem. The objective function is a so-called DC (Difference of Convex functions) function, and some constraints are coupling. We propose a new DC formulation and develop an efficient DCA (DC Algorithm) to deal with this nonconvex program. The DCA introduces the elegant concept of approximating the original nonconvex program by a sequence of convex ones: at each iteration of DCA requires solution of a convex subproblem. The main advantage of the proposed approach is that it leads to strongly convex quadratic subproblems with separate variables in the objective function, which can be tackled by both distributed and centralized methods. One of the major contributions of the paper is to develop a highly efficient distributed algorithm to solve the convex subproblem. We adopt the dual decomposition method that results in computing iteratively the projection of points onto a very simple structural set which can be determined by an inexpensive procedure. The numerical results show the efficiency and the superiority of the new DCA based algorithm compared with existing approaches.     

On concave constraint functions and duality in predominantly black-and-white topology optimization

We study the ‘classical’ discrete, solid-void or black-and-white topology optimization problem, in which minimum compliance is sought, subject to constraints on the available material resource. We assume that this problem is solved using methods that relax the discreteness requirements during intermediate steps, and that the associated programming problems are solved using sequential approximate optimization (SAO) algorithms based on duality. More specifically, we assume that the advantages of the well-known Falk dual are exploited. Such algorithms represent the state-of-the-art in (large-scale) topology optimization when multiple constraints are present; an important example being the method of moving asymptotes (MMA).We depart by noting that the aforementioned SAO algorithms are invariably formulated using strictly convex subproblems. We then numerically illustrate that strictly concave constraint functions, like those present in volumetric penalization, as recently proposed by Bruns and co-workers, may increase the difficulty of the topology optimization problem when strictly convex approximations are used in the SAO algorithm. In turn, volumetric penalization methods are of notable importance, since they seem to hold much promise for generating predominantly solid-void or discrete designs.We then argue that the nonconvex problems we study may in some instances efficiently be solved using dual SAO methods based on nonconvex (strictly concave) approximations which exhibit monotonicity with respect to the design variables.Indeed, for the topology problem resulting from SIMP-like volumetric penalization, we show explicitly that convex approximations are not necessary. Even though the volumetric penalization constraint is strictly concave, the maximum of the resulting dual subproblem still corresponds to the optimum of the original primal approximate subproblem.     

An augmented Lagrangian approach to non-convex SAO using diagonal quadratic approximations

Successful gradient-based sequential approximate optimization (SAO) algorithms in simulation-based optimization typically use convex separable approximations. Convex approximations may however not be very efficient if the true objective function and/or the constraints are concave. Using diagonal quadratic approximations, we show that non-convex approximations may indeed require significantly fewer iterations than their convex counterparts. The nonconvex subproblems are solved using an augmented Lagrangian (AL) strategy, rather than the Falk-dual, which is the norm in SAO based on convex subproblems. The results suggest that transformation of large-scale optimization problems with only a few constraints to a dual form via convexification need sometimes not be required, since this may equally well be done using an AL formulation.     

Test-case generator for nonlinear continuous parameter optimizationtechniques

The experimental results reported in many papers suggest that making an appropriate a priori choice of an evolutionary method for a nonlinear parameter optimization problem remains an open question. It seems that the most promising approach at this stage of research is experimental, involving the design of a scalable test suite of constrained optimization problems, in which many features could be tuned easily. It would then be possible to evaluate the merits and drawbacks of the available methods, as well as to test new methods efficiently. In this paper, we propose such a test-case generator for constrained parameter optimization techniques. This generator is capable of creating various test problems with different characteristics including: 1) problems with different relative sizes of the feasible region in the search space; 2) problems with different numbers and types of constraints; 3) problems with convex or nonconvex evaluation functions, possibly with multiple optima; and 4) problems with highly nonconvex constraints consisting of (possibly) disjoint regions. Such a test-case generator is very useful for analyzing and comparing different constraint-handling techniques     

Nonsmooth DC programming approach to clusterwise linear regression: optimality conditions and algorithms

The clusterwise linear regression problem is formulated as a nonsmooth nonconvex optimization problem using the squared regression error function. The objective function in this problem is represented as a difference of convex functions. Optimality conditions are derived, and an algorithm is designed based on such a representation. An incremental approach is proposed to generate starting solutions. The algorithm is tested on small to large data sets.     

On the influence of local and global stress constraint and filtering radius on the design of hinge-free compliant mechanisms

Distributed compliant mechanisms are components that use elastic strain to obtain a desired kinematic behavior. Compliant mechanisms obtained via topology optimization using the standard approach of minimizing/maximizing the output displacement with a spring at the output port, representing the stiffness of the external medium, usually contain one-node connected hinges. Those hinges are undesired since an ideal compliant mechanism should be a continuous part. This work compares the use of two strategies for stress constrained problems: local and global stress constraints, and analyses their influence in eliminating the one-node connected hinges. Also, the influence of spatial filtering in eliminating the hinges is studied. An Augmented Lagrangian formulation is used to couple the objective function and constraints, and the resulting optimization problem is solved by using an algorithm based on the classical optimality criteria approach. Two compliant mechanisms problems are studied by varying the stress limit and filtering radius. It is observed that a proper combination of filtering radius and stress limit can eliminate one-node connected hinges.     

A new multi-objective programming scheme for topology optimization of compliant mechanisms

This paper presents an alternative method in implementing multi-objective optimization of compliant mechanisms in the field of continuum-type topology optimization. The method is designated as “SIMP-PP” and it achieves multi-objective topology optimization by merging what is already a mature topology optimization method—solid isotropic material with penalization (SIMP) with a variation of the robust multi-objective optimization method—physical programming (PP). By taking advantages of both sides, the combination causes minimal variation in computation algorithm and numerical scheme, yet yields improvements in the multi-objective handling capability of topology optimization. The SIMP-PP multi-objective scheme is introduced into the systematic design of compliant mechanisms. The final optimization problem is formulated mathematically using the aggregate objective function which is derived from the original individual design objectives with PP, subjected to the specified constraints. A sequential convex programming method, the method of moving asymptotes (MMA) is then utilized to process the optimization evolvement based on the design sensitivity analysis. The main findings in this study include distinct advantages of the SIMP-PP method in various aspects such as computation efficiency, adaptability in convex and non-convex multi-criteria environment, and flexibility in problem formulation. Observations are made regarding its performance and the effect of multi-objective optimization on the final topologies. In general, the proposed SIMP-PP method is an appealing multi-objective topology optimization scheme suitable for “real world” problems, and it bridges the gap between standard topological design and multi-criteria optimization. The feasibility of the proposed topology optimization method is exhibited by benchmark examples.     

DC optimization approach to robust controls: the optimal scaling value problem

The optimal scaling problem (OSP) for constant scaling in output feedback control is an inherently difficult nonconvex problem for which in general existing local search algorithms can at best locate a local solution. However, it can be restated as a problem of globally minimizing a convex function under DC constraints, i.e., constraints that can be expressed in terms of differences of convex functions. A particular structure of this DC optimization problem is that it becomes convex when a relatively small number of "complicating" variables are held fixed. We propose alternative branch and bound algorithms for OSP, which exploit this structure by branching upon the complicating variables and use adaptive sub-division strategies to speed-up the convergence to the global solution.     

Using Conical Regularization in Calculating Lagrangian Estimates in Quadratic Optimization Problems

For nonconvex quadratic optimization problems, the authors consider calculation of global extreme value estimates on the basis of Lagrangian relaxation of the original problems. On the boundary of the feasible region of the estimate problem, functions of the problem are discontinuous, ill-conditioned, which imposes certain requirements on the computational algorithms. The paper presents a new approach taking into account these features, based on the use of conical regularizations of convex optimization problems. It makes it possible to construct an equivalent unconditional optimization problem whose objective function is defined on the entire space of problem variables and satisfies the Lipschitz condition.     

Diagonal bundle method with convex and concave updates for large-scale nonconvex and nonsmooth optimization

Nonsmooth optimization is traditionally based on convex analysis and most solution methods rely strongly on the convexity of the problem. In this paper, we propose an efficient diagonal bundle method for nonconvex large-scale nonsmooth optimization. The novelty of the new method is in different usage of metrics depending on the convex or concave behaviour of the objective at the current iteration point. The usage of different metrics gives us a possibility to better deal with the nonconvexity of the problem than the sole—the most commonly used and quite arbitrary—downward shifting of the piecewise linear model does. The convergence of the proposed method is proved for semismooth functions that are not necessarily differentiable nor convex. The numerical experiments have been made using problems with up to one million variables. The results to be presented confirm the usability of the new method.     

A Nonfeasible Gradient Projection Recurrent Neural Network for Equality-Constrained Optimization Problems

In this paper, a recurrent neural network for both convex and nonconvex equality-constrained optimization problems is proposed, which makes use of a cost gradient projection onto the tangent space of the constraints. The proposed neural network constructs a generically nonfeasible trajectory, satisfying the constraints only as t rarr infin. Local convergence results are given that do not assume convexity of the optimization problem to be solved. Global convergence results are established for convex optimization problems. An exponential convergence rate is shown to hold both for the convex case and the nonconvex case. Numerical results indicate that the proposed method is efficient and accurate.     

A global structural optimization technique using an interval method

This paper deals with a global optimization scheme for structural systems that require finite element analysis to evaluate the constraints or the objective function. The paper proposes a strategy for finding the global optimum using an interval method in conjunction with a multipoint function approximation. The highly nonlinear and nonconvex objective and constraint functions are first represented in the design space using linear and adaptive local approximations and these approximations are blended globally with the use of proper weighting functions. The interval method is then employed to trace the global optimum in the approximated function space. The procedure is tested with several examples with known global solutions and it is successfully applied to optimize the fiber-orientation angles of laminated composite plates for minimum deflections. Received December 22, 2000     

Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints

The efficiency of the classic alternating direction method of multipliers has been exhibited by various applications for large-scale separable optimization problems, both for convex objective functions and for nonconvex objective functions. While there are a lot of convergence analysis for the convex case, the nonconvex case is still an open problem and the research for this case is in its infancy. In this paper, we give a partial answer on this problem. Specially, under the assumption that the associated function satisfies the Kurdyka–?ojasiewicz inequality, we prove that the iterative sequence generated by the alternating direction method converges to a critical point of the problem, provided that the penalty parameter is greater than 2L, where L is the Lipschitz constant of the gradient of one of the involved functions. Under some further conditions on the problem's data, we also analyse the convergence rate of the algorithm.     

Nonconvex dynamic spectrum allocation for cognitive radio networks via particle swarm optimization and simulated annealing

Dynamic spectrum access is a promising technique designed to meet the challenge of rapidly growing demands for broadband access in cognitive radio networks. By utilizing the allocated spectrum, cognitive radio devices can provide high throughput and low latency communications. This paper introduces an efficient dynamic spectrum allocation algorithm in cognitive radio networks based on the network utility maximization framework. The objective function in this optimization problem is always nonconvex, which makes the problem difficult to solve. Prior works on network resource optimization always transformed the nonconvex optimization problem into a convex one under some strict assumptions, which do not meet the actual networks. We solve the nonconvex optimization problem directly using an improved particle swarm optimization (PSO) method. Simulated annealing (SA), combined with PSO to form the PSOSA algorithm, overcomes the inherent defects and disadvantages of these two individual components. Simulations show that the proposed solution achieves significant throughput compared with existing approaches, and it is efficient in solving the nonconvex optimization problem.     

On convex transformability and the solution of nonconvex problems via the dual of Falk

In structural optimization, most successful sequential approximate optimization (SAO) algorithms solve a sequence of strictly convex subproblems using the dual of Falk. Previously, we have shown that, under certain conditions, a nonconvex nonlinear (sub)problem may also be solved using the Falk dual. In particular, we have demonstrated this for two nonconvex examples of approximate subproblems that arise in popular and important structural optimization problems. The first is used in the SAO solution of the weight minimization problem, while the topology optimization problem that results from volumetric penalization gives rise to the other. In both cases, the nonconvex subproblems arise naturally in the consideration of the physical problems, so it seems counter productive to discard them in favor of using standard, but less well-suited, strictly convex approximations. Though we have not required that strictly convex transformations exist for these problems in order that they may be solved via a dual approach, we have noted that both of these examples can indeed be transformed into strictly convex forms. In this paper we present both the nonconvex weight minimization problem and the nonconvex topology optimization problem with volumetric penalization as instructive numerical examples to help motivate the use of nonconvex approximations as subproblems in SAO. We then explore the link between convex transformability and the salient criteria which make nonconvex problems amenable to solution via the Falk dual, and we assess the effect of the transformation on the dual problem. However, we consider only a restricted class of problems, namely separable problems that are at least C ¹ continuous, and a restricted class of transformations: those in which the functions that represent the mapping are each continuous, monotonic and univariate.     

Interpolation with multiple norm constraints

This paper considers the problem of finding matrix-valued rational functions that satisfy two-sided residue interpolation conditions subject to norm constraints on their components. It is shown that this problem can be reduced to a finite-dimensional convex optimization problem. As an application, we show that under suitable assumptions on the plant, multiple objective ?₂ and ?_∞ control problems admit finite-dimensional optimal solutions and that such solutions can be computed using finite-dimensional convex programs.