Convex Relaxation Methods for Nonconvex Polynomial Optimization Problems

Prof. Dr. André A. Keller
Université des Sciences et Technologies de Lille
Laboratoire d’Informatique Fondamentale de Lille
(LIFL) section SMAC, Cité Scientifique
59650 Villeneuve-d’Ascq, FRANCE
E-mail: andre.keller@univ-lille1.fr
 

Abstract: This presentation introduces to the problem of constructing convex relaxations fornonconvex polynomial optimization problems. Branch-and-bound algorithms are convex relaxation based. The convex envelopes are of primary importance, since they represent theuniformly best convex underestimatorsfornonconvexpolynomials over some region. However, computing convex envelopes is NP-hard, even for simple polynomials. The nuclear norm (i.e., the sum of singular values) heuristic is also used instead the convex envelope of the objective function. The affine matrix rank minimizing problem (RMP) uses the nuclear norm of the rank function.In this case, the nonconvex objective rank function is replaced by its convex envelope (i.e., the nuclear norm). In particular, this important practical problem consists of finding the least complex stochastic model, which is consistent with observations and priors.
The reformulation-linearization technique (RLT) generates LP (linear programming) relaxations of aquadratic problem. RLT operates in two steps: a reformulation step and a linearization (or convexification) step. In the reformulation phase, the constraints (constraints and bounds inequalities) are replaced by new numerous pairwise productsof the constraints (i.e., bound factor product, bound-constraint factor product, and constraint factorproduct inequalities). In the linearization phase, each distinct quadratic term is replaced by a single new RLT variable. This RLT process produces an LP relaxation.
SOS (sum of squares) relaxations can be used to obtain good approximate SDP (semidefinite programming) descriptions of convex envelopes (e.g., computing the convex envelope of quadratic forms over polytopes via a semidefinite program). LMI formulations (linear matrix inequalities) have been proposed to treat efficiently with nonconvex sets. An LMI, equivalent to a system of polynomial inequalities, can be described by a semialgebraic convex set. The feasible sets are spectrahedra with curvedfaces, contrary to the LP case with polyhedra. Successive LMI relaxations of increasing size can be used to achieve the global optimum. Nonlinear inequalities are converted to an LMI form using Schur complements. Optimizing a nonconvex polynomial is equivalent to the LP over a convex set. Engineering applications interests include system analysis, control theory, combinatorial optimization, statistics and structural design. As an illustration, one can mention the truss topology design problem. This problem can be set to an equivalent LMI, by using the Schur lemma for linearization.

Short biography: André A. Keller (Prof.) is at present an associatedresearcher at the Laboratoire d’Informatique Fondamentale de Lille UMR 8022/ Lille Fundamental Computer Science Laboratory, a unit of the French Centre National de la Recherche Scientifique (CNRS) by the Université de Lille 1, Sciences et Technologies. He received a PhD in Economics (Operations Research) from the Université de Paris Panthéon-Sorbonne in 1977. He is a WSEAS Member since 2010 and a Reviewer for the journals Ecological Modelling, Journal of Mathematical Analysis and Applications (Elsevier) and WSEAS Transactions on Information Science and Applications.He taught applied mathematics (optimization techniques) and econometric modeling, microeconomics, theory of games and dynamic macroeconomic analysis. His experience centers are on building and analyzing large scale macro-economic systems, as well as forecasting.
His research interestsinclude: high frequency time-series modeling with application to the foreign exchange market, discrete mathematics (graph theory, combinatorial optimization), stochastic differential games and tournaments, circuit analysis, optimal control under uncertainties. (fuzzy control). His publications consist in writing articles, bookchapters and books. The book chapters are on semi-reduced forms (MartinusNijhoff, 1984), econometrics of technical change (Springer and IISA, 1989), advanced time-series analysis (Woodhead Faulkner, 1989), stochastic differential games (Nova Science, 2009), optimal fuzzy control (InTech, 2009). One book is ‘’Time-Delay Systems with Applications to Economic Dynamics &Control’’(LAP, 2010). One book is ‘’Nonconvex Optimization in Practice: Theory, Algorithms, and Applications’’ (WSEAS Press, forthcoming 2014). One eBook with Bentham Science on ‘’Evolutionary Multiobjective Optimization: Theory and Practice’’ is planned for 2015.