A survey of hidden convex optimization
---
paper_title: On the copositive representation of binary and continuous nonconvex quadratic programs

paper_content:

In this paper, we model any nonconvex quadratic program having a mix of binary and continuous variables as a linear program over the dual of the cone of copositive matrices. This result can be viewed as an extension of earlier separate results, which have established the copositive representation of a small collection of NP-hard problems. A simplification, which reduces the dimension of the linear conic program, and an extension to complementarity constraints are established, and computational issues are discussed.
---
paper_title: NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems

paper_content:

We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic polynomials. We also prove that deciding strict convexity, strong convexity, quasiconvexity, and pseudoconvexity of polynomials of even degree four or higher is strongly NP-hard. By contrast, we show that quasiconvexity and pseudoconvexity of odd degree polynomials can be decided in polynomial time.
---
paper_title: On The Reduction of Duality Gap in Box Constrained Nonconvex Quadratic Program

paper_content:

In this paper, we investigate in this paper the reduction of the duality gap between box constrained nonconvex quadratic programming and its semidefinite programming (SDP) relaxation (or Lagrangian dual). Characterizing the zero duality gap by a set of saddle-point-type conditions, we propose a parameterized distance measure δ(θ) between a polyhedral set C and a perturbed nonconvex set Λ(θ) to measure the dissatisfaction degree of the optimality conditions for zero duality gap. An underestimation of the duality gap is then derived which leads to a reduction of the duality gap proportional to δ2(θ*) for the identified best parameter θ*. This reduction of duality gap can be extended to the cases with both box and linear equality constraints. We demonstrate that the computation of δ(θ*) can be reduced to the cell enumeration of hyperplane arrangement in discrete geometry. In particular, we show that the reduction of duality gap can be achieved in polynomial time for a fixed degeneracy degree of the modified ...
---
paper_title: Strong duality in optimization: shifted power reformulation

paper_content:

For a general class of non-convex optimization problems, a class of power reformulation closes the duality gap between the primal problem and its Lagrangian dual, when the order of the power is sufficiently large. In this paper, we first estimate a lower bound of the power above which the attainment of the zero duality gap can be ensured. After introducing a suitable shifting, we further show, surprisingly, that order three is always sufficient to guarantee the zero duality gap. We then extend the proposed shifted power reformulation to discrete optimization.
---
paper_title: Local saddle point and a class of convexification methods for nonconvex optimization problems

paper_content:

A class of general transformation methods are proposed to convert a nonconvex optimization problem to another equivalent problem. It is shown that under certain assumptions the existence of a local saddle point or local convexity of the Lagrangian function of the equivalent problem (EP) can be guaranteed. Numerical experiments are given to demonstrate the main results geometrically.
---
paper_title: Zero duality gap for a class of nonconvex optimization problems

paper_content:

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.
---
paper_title: Towards Strong Duality in Integer Programming

paper_content:

We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint.
---
paper_title: Hidden Convex Minimization

paper_content:

A class of nonconvex minimization problems can be classified as hidden convex minimization problems. A nonconvex minimization problem is called a hidden convex minimization problem if there exists an equivalent transformation such that the equivalent transformation of it is a convex minimization problem. Sufficient conditions that are independent of transformations are derived in this paper for identifying such a class of seemingly nonconvex minimization problems that are equivalent to convex minimization problems. Thus, a global optimality can be achieved for this class of hidden convex optimization problems by using local search methods. The results presented in this paper extend the reach of convex minimization by identifying its equivalent with a nonconvex representation.
---
paper_title: Peeling Off a Nonconvex Cover of an Actual Convex Problem: Hidden Convexity

paper_content:

Convexity is, without a doubt, one of the most desirable features in optimization. Many optimization problems that are nonconvex in their original settings may become convex after performing certain equivalent transformations. This paper studies the conditions for such hidden convexity. More specifically, some transformation-independent sufficient conditions have been derived for identifying hidden convexity. The derived sufficient conditions are readily verifiable for quadratic optimization problems. The global minimizer of a hidden convex programming problem can be identified using a local search algorithm.
---
paper_title: NP-hardness of Linear Multiplicative Programming and Related Problems

paper_content:

The linear multiplicative programming problem minimizes a product of two (positive) variables subject to linear inequality constraints. In this paper, we show NP-hardness of linear multiplicative programming problems and related problems.
---
paper_title: MULTIPLICATIVE PROGRAMMING PROBLEMS

paper_content:

This chapter reviews recent algorithmic developments in multiplicative programming. The multiplicative programming problem is a class of minimization problems containing a product of several convex functions either in its objective or in its constraints. It has various practical applications in such areas as microeconomics, geometric optimization, multicriteria optimization and so on. A product of convex functions is in general not (quasi)convex, and hence the problem can have multiple local minima. However, some types of multiplicative problems can be solved in a practical sense. The types to be discussed in this chapter are minimization of a product of p convex functions over a convex set, minimization of a sum of p convex multiplicative functions, and minimization of a convex function subject to a constraint on a product of p convex functions. If p is less than four or five, it is shown that parametric simplex algorithms or global optimization algorithms work very well for these problems.
---
paper_title: NP-hardness of Linear Multiplicative Programming and Related Problems

paper_content:

The linear multiplicative programming problem minimizes a product of two (positive) variables subject to linear inequality constraints. In this paper, we show NP-hardness of linear multiplicative programming problems and related problems.
---
paper_title: Minimizing the sum of a linear and a linear fractional function applying conic quadratic representation: continuous and discrete problems

paper_content:

This paper tries to minimize the sum of a linear and a linear fractional function over a closed convex set defined by some linear and conic quadratic constraints. At first, we represent some necessary and sufficient conditions for the pseudoconvexity of the problem. For each of the conditions, under some reasonable assumptions, an appropriate second-order cone programming (SOCP) reformulation of the problem is stated and a new applicable solution procedure is proposed. Efficiency of the proposed reformulations is demonstrated by numerical experiments. Secondly, we limit our attention to binary variables and derive a sufficient condition for SOCP representability. Using the experimental results on random instances, we show that the proposed conic reformulation is more efficient in comparison with the well-known linearization technique and it produces more eligible cuts for the branch and bound algorithm.
---
paper_title: Fractional Programming. I, Duality

paper_content:

This paper, which is presented in two parts, is a contribution to the theory of fractional programming, i.e., maximization of quotients subject to constraints. In Part I a duality theory for linear and concave-convex fractional programs is developed and related to recent results by Bector, Craven-Mond, Jagannathan, Sharma-Swarup, et al. Basic duality theorems of linear, quadratic and convex programming are extended. In Part II Dinkelbach's algorithm solving fractional programs is considered. The rate of convergence as well as a priori and a posteriori error estimates are determined. In view of these results the stopping rule of the algorithm is changed. Also the starting rule is modified using duality as introduced in Part I. Furthermore a second algorithm is proposed. In contrast to Dinkelbach's procedure the rate of convergence is still controllable. Error estimates are obtained too.
---
paper_title: A sequential method for a class of pseudoconcave fractional problems

paper_content:

The aim of the paper is to maximize a pseudoconcave function which is the sum of a linear and a linear fractional function subject to linear constraints. Theoretical properties of the problem are first established and then a sequential method based on a simplex-like procedure is suggested. Copyright Springer-Verlag 2008
---
paper_title: A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid

paper_content:

We consider the nonconvex problem (RQ) of minimizing the ratio of two nonconvex quadratic functions over a possibly degenerate ellipsoid. This formulation is motivated by the so-called regularized total least squares problem (RTLS), which is a special case of the problem’s class we study. We prove that under a certain mild assumption on the problem’s data, problem (RQ) admits an exact semidefinite programming relaxation. We then study a simple iterative procedure which is proven to converge superlinearly to a global solution of (RQ) and show that the dependency of the number of iterations on the optimality tolerance $$\varepsilon$$grows as $$O(\sqrt{\ln \varepsilon^{-1}})$$.
---
paper_title: Finding a global optimal solution for a quadratically constrained fractional quadratic problem with applications to the regularized total least squares

paper_content:

We consider the problem of minimizing a fractional quadratic problem involving the ratio of two indefinite quadratic functions, subject to a two-sided quadratic form constraint. This formulation is motivated by the so-called regularized total least squares (RTLS) problem. A key difficulty with this problem is its nonconvexity, and all current known methods to solve it are guaranteed only to converge to a point satisfying first order necessary optimality conditions. We prove that a global optimal solution to this problem can be found by solving a sequence of very simple convex minimization problems parameterized by a single parameter. As a result, we derive an efficient algorithm that produces an $\epsilon$-global optimal solution in a computational effort of $O(n^3 \log \epsilon^{-1})$. The algorithm is tested on problems arising from the inverse Laplace transform and image deblurring. Comparison to other well-known RTLS solvers illustrates the attractiveness of our new method.
---
paper_title: Parametric Lagrangian dual for the binary quadratic programming problem

paper_content:

Based on a difference between convex decomposition of the Lagrangian function, we propose and study a family of parametric Lagrangian dual for the binary quadratic program. Then we show they improve several lower bounds in recent literature.
---
paper_title: A new semidefinite programming relaxation scheme for a class of quadratic matrix problems

paper_content:

Abstract We consider a special class of quadratic matrix optimization problems which often arise in applications. By exploiting the special structure of these problems, we derive a new semidefinite relaxation which, under mild assumptions, is proven to be tight for a larger number of constraints than could be achieved via a direct approach. We show the potential usefulness of these results when applied to robust least-squares and sphere-packing problems.
---
paper_title: An SDP approach for quadratic fractional problems with a two-sided quadratic constraint

paper_content:

We consider a fractional programming problem (P) which minimizes a ratio of quadratic functions subject to a two-sided quadratic constraint. On one hand, (P) can be solved under some technical conditions by the Dinkelbach iterative method [W. Dinkelbach, On nonlinear fractional programming, Manag. Sci. 13 (1967), pp. 492–498] which has dominated the development of the area for nearly half a century. On the other hand, some special case of (P), typically the one in Beck and Teboulle [A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math. Program. Ser. A 118 (2009), pp. 13–35], could be directly solved via an exact semi-definite reformulation, rather than iteratively. In this paper, by a recent breakthrough of Xia et al. [S-Lemma with equality and its applications. Available at http://arxiv.org/abs/1403.2816] on the S-lemma with equality, we propose to analyse (P) with three cases and show that each of them admits an exact SDP relaxation. As a resu...
---
paper_title: On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint

paper_content:

Strong Lagrangian duality holds for the quadratic programming with a two-sided quadratic constraint. In this paper, we show that the two-sided quadratic constrained quadratic fractional programming, if well scaled, also has zero Lagrangian duality gap. However, this is not always true without scaling. For a special case, the identical regularized total least squares problem, we establish the necessary and sufficient condition under which the Lagrangian duality gap is positive.
---
paper_title: Hidden convexity in some nonconvex quadratically constrained quadratic programming

paper_content:

We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems), we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints, which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent convex programs.
---
paper_title: Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres

paper_content:

In this paper a characterization of the local-nonglobal minimizes of a quadratic function defined on a Euclidean ball or a sphere is given. It is proven that there exists at most one local-nonglobal minimizes and that the Lagrange multiplier that corresponds to this minimizes is the largest solution of a nonlinear scalar equation. An algorithm is proposed for computing the local-nonglobal minimizes.
---
paper_title: Quadratically constrained least squares and quadratic problems

paper_content:

We consider the following problem: Compute a vectorx such that ?Ax?b?2=min, subject to the constraint ?x?2=?. A new approach to this problem based on Gauss quadrature is given. The method is especially well suited when the dimensions ofA are large and the matrix is sparse. ::: ::: It is also possible to extend this technique to a constrained quadratic form: For a symmetric matrixA we consider the minimization ofx T A x?2b T x subject to the constraint ?x?2=?. ::: ::: Some numerical examples are given.
---
paper_title: Second-order-cone constraints for extended trust-region subproblems

paper_content:

The classical trust-region subproblem (TRS) minimizes a nonconvex quadratic objective over the unit ball. In this paper, we consider extensions of TRS having extra constraints. When two parallel cuts are added to TRS, we show that the resulting nonconvex problem has an exact representation as a semidenite program with additional linear and second-order-cone constraints. For the case where an additional ellipsoidal constraint is added to TRS, resulting in the \two trust-region subproblem" (TTRS), we provide a new relaxation including second-order-cone constraints that strengthens the usual SDP relaxation.
---
paper_title: Minimizing the sum of a linear and a linear fractional function applying conic quadratic representation: continuous and discrete problems

paper_content:

This paper tries to minimize the sum of a linear and a linear fractional function over a closed convex set defined by some linear and conic quadratic constraints. At first, we represent some necessary and sufficient conditions for the pseudoconvexity of the problem. For each of the conditions, under some reasonable assumptions, an appropriate second-order cone programming (SOCP) reformulation of the problem is stated and a new applicable solution procedure is proposed. Efficiency of the proposed reformulations is demonstrated by numerical experiments. Secondly, we limit our attention to binary variables and derive a sufficient condition for SOCP representability. Using the experimental results on random instances, we show that the proposed conic reformulation is more efficient in comparison with the well-known linearization technique and it produces more eligible cuts for the branch and bound algorithm.
---
paper_title: Quadratic Assignment Problems

paper_content:

Abstract This paper surveys quadratic assignment problems (QAP). At first several applications of this problem class are described and mathematical formulations of QAPs are given. Then some exact solution methods and good heuristics are outlined. Their computational behaviour is illustrated by numerical results. Further recent results on the asymptotic probabilistic behaviour of QAPs are outlined.
---
paper_title: On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming

paper_content:

We analyze two popular semidefinite programming relaxations for quadratically constrained quadratic programs with matrix variables. These relaxations are based on vector lifting and on matrix lifting; they are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline for how to choose a less expensive semidefinite programming relaxation and still obtain a strong bound. The main technique used to show the equivalence and that allows for the simplified constraints is the recognition of a class of nonchordal sparse patterns that admit a smaller representation of the positive semidefinite constraint.
---
paper_title: Strong Duality for a Trust-Region Type Relaxation of the Quadratic Assignment Problem

paper_content:

Abstract Lagrangian duality underlies many efficient algorithms for convex minimization problems. A key ingredient is strong duality. Lagrangian relaxation also provides lower bounds for non-convex problems, where the quality of the lower bound depends on the duality gap. Quadratically constrained quadratic programs (QQPs) provide important examples of non-convex programs. For the simple case of one quadratic constraint (the trust-region subproblem) strong duality holds. In addition, necessary and sufficient (strengthened) second-order optimality conditions exist. However, these duality results already fail for the two trust-region sub-problem. Surprisingly, there are classes of more complex, non-convex QQPs where strong duality holds. One example is the special case of orthogonality constraints, which arise naturally in relaxations for the quadratic assignment problem (QAP). In this paper we show that strong duality also holds for a relaxation of QAP where the orthogonality constraint is replaced by a semidefinite inequality constraint. Using this strong duality result, and semidefinite duality, we develop new trust-region type necessary and sufficient optimality conditions for these problems. Our proof of strong duality introduces and uses a generalization of the Hoffman–Wielandt inequality.
---
paper_title: Global optimization of a class of nonconvex quadratically constrained quadratic programming problems

paper_content:

In this paper we study a class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.
---
paper_title: S-Lemma with Equality and Its Applications

paper_content:

Let $$f(x)=x^TAx+2a^Tx+c$$f(x)=xTAx+2aTx+c and $$h(x)=x^TBx+2b^Tx+d$$h(x)=xTBx+2bTx+d be two quadratic functions having symmetric matrices $$A$$A and $$B$$B. The S-lemma with equality asks when the unsolvability of the system $$f(x)<0, h(x)=0$$f(x)<0,h(x)=0 implies the existence of a real number $$\mu $$μ such that $$f(x) + \mu h(x)\ge 0, ~\forall x\in \mathbb {R}^n$$f(x)+μh(x)?0,?x?Rn. The problem is much harder than the inequality version which asserts that, under Slater condition, $$f(x)<0, h(x)\le 0$$f(x)<0,h(x)≤0 is unsolvable if and only if $$f(x) + \mu h(x)\ge 0, ~\forall x\in \mathbb {R}^n$$f(x)+μh(x)?0,?x?Rn for some $$\mu \ge 0$$μ?0. In this paper, we show that the S-lemma with equality does not hold only when the matrix $$A$$A has exactly one negative eigenvalue and $$h(x)$$h(x) is a non-constant linear function ($$B=0, b\not =0$$B=0,b?0). As an application, we can globally solve $$\inf \{f(x): h(x)=0\}$$inf{f(x):h(x)=0} as well as the two-sided generalized trust region subproblem $$\inf \{f(x): l\le h(x)\le u\}$$inf{f(x):l≤h(x)≤u} without any condition. Moreover, the convexity of the joint numerical range $$\{(f(x), h_1(x),\ldots , h_p(x)):x\in \mathbb R^n\}$${(f(x),h1(x),?,hp(x)):x?Rn} where $$f$$f is a (possibly non-convex) quadratic function and $$h_1(x),\ldots ,h_p(x)$$h1(x),?,hp(x) are affine functions can be characterized using the newly developed S-lemma with equality.
---
paper_title: SOCP Reformulation for the Generalized Trust Region Subproblem via a Canonical Form of Two Symmetric Matrices

paper_content:

We investigate in this paper the generalized trust region subproblem (GTRS) of minimizing a general quadratic objective function subject to a general quadratic inequality constraint. By applying a simultaneous block diagonalization approach, we obtain a congruent canonical form for the symmetric matrices in both the objective and constraint functions. By exploiting the block separability of the canonical form, we show that all GTRSs with an optimal value bounded from below are second order cone programming (SOCP) representable. Our result generalizes the recent work of Ben-Tal and Hertog (Math. Program. 143(1-2):1-29, 2014), which establishes the SOCP representability of the GTRS under the assumption of the simultaneous diagonalizability of the two matrices in the objective and constraint functions. Compared with the state-of-the-art approach to reformulate the GTRS as a semi-definite programming problem, our SOCP reformulation delivers a much faster solution algorithm. We further extend our method to two variants of the GTRS in which the inequality constraint is replaced by either an equality constraint or an interval constraint. Our methods also enable us to obtain simplified versions of the classical S-lemma, the S-lemma with equality, and the S-lemma with interval bounds.
---
paper_title: Strong duality in nonconvex quadratic optimization with two quadratic constraints

paper_content:

We consider the problem of minimizing an indefinite quadratic function subject to two quadratic inequality constraints. When the problem is defined over the complex plane we show that strong duality holds and obtain necessary and sufficient optimality conditions. We then develop a connection between the image of the real and complex spaces under a quadratic mapping, which together with the results in the complex case lead to a condition that ensures strong duality in the real setting. Preliminary numerical simulations suggest that for random instances of the extended trust region subproblem, the sufficient condition is satisfied with a high probability. Furthermore, we show that the sufficient condition is always satisfied in two classes of nonconvex quadratic problems. Finally, we discuss an application of our results to robust least squares problems.
---
paper_title: Parametric Lagrangian dual for the binary quadratic programming problem

paper_content:

Based on a difference between convex decomposition of the Lagrangian function, we propose and study a family of parametric Lagrangian dual for the binary quadratic program. Then we show they improve several lower bounds in recent literature.
---
paper_title: Convexity of quadratic transformations and its use in control and optimization

paper_content:

Quadratic transformations have the hidden convexity property which allows one to deal with them as if they were convex functions. This phenomenon was encountered in various optimization and control problems, but it was not always recognized as consequence of some general property. We present a theory on convexity and closedness of a 3D quadratic image of ℝn, n≥3, which explains many disjoint known results and provides some new ones.
---
paper_title: Hidden conic quadratic representation of some nonconvex quadratic optimization problems

paper_content:

The problem of minimizing a quadratic objective function subject to one or two quadratic constraints is known to have a hidden convexity property, even when the quadratic forms are indefinite. The equivalent convex problem is a semidefinite one, and the equivalence is based on the celebrated S-lemma. In this paper, we show that when the quadratic forms are simultaneously diagonalizable (SD), it is possible to derive an equivalent convex problem, which is a conic quadratic (CQ) one, and as such is significantly more tractable than a semidefinite problem. The SD condition holds for free for many problems arising in applications, in particular, when deriving robust counterparts of quadratic, or conic quadratic, constraints affected by implementation error. The proof of the hidden CQ property is constructive and does not rely on the S-lemma. This fact may be significant in discovering hidden convexity in some nonquadratic problems.
---
paper_title: On the Solution of the GPS Localization and Circle Fitting Problems

paper_content:

We consider the problem of locating a user's position from a set of noisy pseudoranges to a group of satellites. We consider both the nonlinear least squares formulation of the problem, which is nonconvex and nonsmooth, and the nonlinear squared least squares variant, in which the objective function is smooth, but still nonconvex. We show that the squared least squares problem can be reformulated as a generalized trust region subproblem and as such can be solved efficiently. Conditions for attainment of the optimal solutions of both problems are derived. The nonlinear least squares problem is shown to have tight connections to the well-known geometric circle fitting and orthogonal regression problems. Finally, a fixed point method for the nonlinear least squares formulation is derived and analyzed.
---
paper_title: Strong Duality for Generalized Trust Region Subproblem: S-Lemma with Interval Bounds

paper_content:

With the help of the newly developed S-lemma with interval bounds, we show that strong duality holds for the interval bounded generalized trust region subproblem (GTRS) under some mild assumptions, which answers an open problem raised by Pong and Wolkowicz (Comput Optim Appl 58(2), 273–322, 2014).
---
paper_title: A survey of the S-lemma

paper_content:

In this survey we review the many faces of the S-lemma, a result about the correctness of the S-procedure. The basic idea of this widely used method came from control theory but it has important consequences in quadratic and semidefinite optimization, convex geometry, and linear algebra as well. These were all active research areas, but as there was little interaction between researchers in these different areas, their results remained mainly isolated. Here we give a unified analysis of the theory by providing three different proofs for the S-lemma and revealing hidden connections with various areas of mathematics. We prove some new duality results and present applications from control theory, error estimation, and computational geometry.
---
paper_title: Semidefinite Programming Relaxations for the Quadratic Assignment Problem

paper_content:

Semidefinite programming (SDP) relaxations for the quadratic assignment problem (QAP) are derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalent representations of QAP. These relaxations result in the interesting, special, case where only the dual problem of the SDP relaxation has strict interior, i.e., the Slater constraint qualification always fails for the primal problem. Although there is no duality gap in theory, this indicates that the relaxation cannot be solved in a numerically stable way. By exploring the geometrical structure of the relaxation, we are able to find projected SDP relaxations. These new relaxations, and their duals, satisfy the Slater constraint qualification, and so can be solved numerically using primal-dual interior-point methods.
---
paper_title: A Note on Lack of Strong duality for Quadratic Problems with Orthogonal Constraints

paper_content:

Abstract The general quadratically constrained quadratic program (QQP) is an important modelling tool for many diverse problems. The QQP is in general NP hard, and numerically intractable. Lagrangian relaxations often provide good approximate solutions to these hard problems. Such relaxations are equivalent to semidefinite programming relaxations and can be solved efficiently. For several special cases of QQP, the Lagrangian relaxation provides the exact optimal value. This means that there is a zero duality gap and the problem is tractable. It is important to know for which cases this is true, since they can then be used as subproblems to improve Lagrangian relaxation for intractable QQPs. In this paper we study the special QQP with orthogonal (matrix) constraints XX T = I . If C =0, the zero duality gap result holds if the redundant orthogonal constraints X T X = I are added. We show that this is not true in the general case. However, we show how to close the duality gap in the pure linear case by adding variables in addition to constraints.
---
paper_title: On Lagrangian Relaxation of Quadratic Matrix Constraints

paper_content:

Quadratically constrained quadratic programs (QQPs) play an important modeling role for many diverse problems. These problems are in general NP hard and numerically intractable. Lagrangian relaxations often provide good approximate solutions to these hard problems. Such relaxations are equivalent to semidefinite programming relaxations. ::: For several special cases of QQP, e.g., convex programs and trust region subproblems, the Lagrangian relaxation provides the exact optimal value, i.e., there is a zero duality gap. However, this is not true for the general QQP, or even the QQP with two convex constraints, but a nonconvex objective. ::: In this paper we consider a certain QQP where the quadratic constraints correspond to the matrix orthogonality condition XXT=I. For this problem we show that the Lagrangian dual based on relaxing the constraints XXT=I and the seemingly redundant constraints XT X=I has a zero duality gap. This result has natural applications to quadratic assignment and graph partitioning problems, as well as the problem of minimizing the weighted sum of the largest eigenvalues of a matrix. We also show that the technique of relaxing quadratic matrix constraints can be used to obtain a strengthened semidefinite relaxation for the max-cut problem.
---
paper_title: On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming

paper_content:

We analyze two popular semidefinite programming relaxations for quadratically constrained quadratic programs with matrix variables. These relaxations are based on vector lifting and on matrix lifting; they are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline for how to choose a less expensive semidefinite programming relaxation and still obtain a strong bound. The main technique used to show the equivalence and that allows for the simplified constraints is the recognition of a class of nonchordal sparse patterns that admit a smaller representation of the positive semidefinite constraint.
---
paper_title: Nondifferentiable Optimization and Polynomial Problems

paper_content:

Preface. 1. Elements of Convex Analysis, Linear Algebra, and Graph Theory. 2. Subgradient and epsilon-Subgradient Methods. 3. Subgradient-Type Methods with Space Dilation. 4. Elements of Information and Numerical Complexity of Polynomial Extremal Problems. 5. Decomposition Methods Based on Nonsmooth Optimization. 6. Algorithms for Constructing Optimal on Volume Ellipsoids and Semidefinite Programming. 7. The Role of Ellipsoid Method for Complexity Analysis of Combinatorial Problems. 8. Semidefinite Programming Bounds for Extremal Graph Problems. 9. Global Minimization of Polynomial Functions and 17-th Hilbert Problem. References.
---
paper_title: Strong Duality for a Trust-Region Type Relaxation of the Quadratic Assignment Problem

paper_content:

Abstract Lagrangian duality underlies many efficient algorithms for convex minimization problems. A key ingredient is strong duality. Lagrangian relaxation also provides lower bounds for non-convex problems, where the quality of the lower bound depends on the duality gap. Quadratically constrained quadratic programs (QQPs) provide important examples of non-convex programs. For the simple case of one quadratic constraint (the trust-region subproblem) strong duality holds. In addition, necessary and sufficient (strengthened) second-order optimality conditions exist. However, these duality results already fail for the two trust-region sub-problem. Surprisingly, there are classes of more complex, non-convex QQPs where strong duality holds. One example is the special case of orthogonality constraints, which arise naturally in relaxations for the quadratic assignment problem (QAP). In this paper we show that strong duality also holds for a relaxation of QAP where the orthogonality constraint is replaced by a semidefinite inequality constraint. Using this strong duality result, and semidefinite duality, we develop new trust-region type necessary and sufficient optimality conditions for these problems. Our proof of strong duality introduces and uses a generalization of the Hoffman–Wielandt inequality.
---
paper_title: Global optimization of a class of nonconvex quadratically constrained quadratic programming problems

paper_content:

In this paper we study a class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.
---
paper_title: Maxima for graphs and a new proof of a theorem of Turán

paper_content:

Maximum of a square-free quadratic form on a simplex. The following question was suggested by a problem of J. E. MacDonald Jr. (1): Given a graph G with vertices 1, 2, . . . , n. Let S be the simplex in E n given by x i ≥ 0, Σ x i = 1. What is
---
paper_title: Tightening a copositive relaxation for standard quadratic optimization problems

paper_content:

We focus in this paper the problem of improving the semidefinite programming (SDP) relaxations for the standard quadratic optimization problem (standard QP in short) that concerns with minimizing a quadratic form over a simplex. We first analyze the duality gap between the standard QP and one of its SDP relaxations known as "strengthened Shor's relaxation". To estimate the duality gap, we utilize the duality information of the SDP relaxation to construct a graph G ?. The estimation can be then reduced to a two-phase problem of enumerating first all the minimal vertex covers of G ? and solving next a family of second-order cone programming problems. When there is a nonzero duality gap, this duality gap estimation can lead to a strictly tighter lower bound than the strengthened Shor's SDP bound. With the duality gap estimation improving scheme, we develop further a heuristic algorithm for obtaining a good approximate solution for standard QP.
---
paper_title: A Note on Lack of Strong duality for Quadratic Problems with Orthogonal Constraints

paper_content:

Abstract The general quadratically constrained quadratic program (QQP) is an important modelling tool for many diverse problems. The QQP is in general NP hard, and numerically intractable. Lagrangian relaxations often provide good approximate solutions to these hard problems. Such relaxations are equivalent to semidefinite programming relaxations and can be solved efficiently. For several special cases of QQP, the Lagrangian relaxation provides the exact optimal value. This means that there is a zero duality gap and the problem is tractable. It is important to know for which cases this is true, since they can then be used as subproblems to improve Lagrangian relaxation for intractable QQPs. In this paper we study the special QQP with orthogonal (matrix) constraints XX T = I . If C =0, the zero duality gap result holds if the redundant orthogonal constraints X T X = I are added. We show that this is not true in the general case. However, we show how to close the duality gap in the pure linear case by adding variables in addition to constraints.
---
paper_title: On the complexity of quadratic programming with two quadratic constraints

paper_content:

The complexity of quadratic programming problems with two quadratic constraints is an open problem. In this paper we show that when one constraint is a ball constraint and the Hessian of the quadratic function defining the other constraint is positive definite, then, under quite general conditions, the problem can be solved in polynomial time in the real-number model of computation through an approach based on the analysis of the dual space of the Lagrange multipliers. However, the degree of the polynomial is rather large, thus making the result mostly of theoretical interest.
---
paper_title: Convex hull of the orthogonal similarity set with applications in quadratic assignment problems

paper_content:

In this paper, we study thoroughly the convex hull of the orthogonal ::: similarity set and give a new representation. When applied in ::: quadratic assignment problems, it motivates two new lower bounds. ::: The first is equivalent to the projected eigenvalue bound, while the ::: second highly outperforms several well-known lower bounds in ::: literature.
---
paper_title: S-Lemma with Equality and Its Applications

paper_content:

Let $$f(x)=x^TAx+2a^Tx+c$$f(x)=xTAx+2aTx+c and $$h(x)=x^TBx+2b^Tx+d$$h(x)=xTBx+2bTx+d be two quadratic functions having symmetric matrices $$A$$A and $$B$$B. The S-lemma with equality asks when the unsolvability of the system $$f(x)<0, h(x)=0$$f(x)<0,h(x)=0 implies the existence of a real number $$\mu $$μ such that $$f(x) + \mu h(x)\ge 0, ~\forall x\in \mathbb {R}^n$$f(x)+μh(x)?0,?x?Rn. The problem is much harder than the inequality version which asserts that, under Slater condition, $$f(x)<0, h(x)\le 0$$f(x)<0,h(x)≤0 is unsolvable if and only if $$f(x) + \mu h(x)\ge 0, ~\forall x\in \mathbb {R}^n$$f(x)+μh(x)?0,?x?Rn for some $$\mu \ge 0$$μ?0. In this paper, we show that the S-lemma with equality does not hold only when the matrix $$A$$A has exactly one negative eigenvalue and $$h(x)$$h(x) is a non-constant linear function ($$B=0, b\not =0$$B=0,b?0). As an application, we can globally solve $$\inf \{f(x): h(x)=0\}$$inf{f(x):h(x)=0} as well as the two-sided generalized trust region subproblem $$\inf \{f(x): l\le h(x)\le u\}$$inf{f(x):l≤h(x)≤u} without any condition. Moreover, the convexity of the joint numerical range $$\{(f(x), h_1(x),\ldots , h_p(x)):x\in \mathbb R^n\}$${(f(x),h1(x),?,hp(x)):x?Rn} where $$f$$f is a (possibly non-convex) quadratic function and $$h_1(x),\ldots ,h_p(x)$$h1(x),?,hp(x) are affine functions can be characterized using the newly developed S-lemma with equality.
---
paper_title: Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid

paper_content:

Abstract In this paper a duality framework is discussed for the problem of optimizing a nonconvex quadratic function over an ellipsoid. Additional insight is obtained from the observation that this nonconvex problem is in a sense equivalent to a convex problem of the same type, from which known necessary and sufficient conditions for optimality readily follow. Based on the duality results, some existing solution procedures are interpreted as in fact solving the dual. The duality relations are also shown to provide a natural framework for sensitivity analysis.
---
paper_title: Quadratic programs with hollows

paper_content:

Let \(\mathcal {F}\) be a quadratically constrained, possibly nonconvex, bounded set, and let \(\mathcal {E}_1, \ldots , \mathcal {E}_l\) denote ellipsoids contained in \(\mathcal {F}\) with non-intersecting interiors. We prove that minimizing an arbitrary quadratic \(q(\cdot )\) over \(\mathcal {G}:= \mathcal {F}{\setminus } \cup _{k=1}^\ell {{\mathrm{int}}}(\mathcal {E}_k)\) is no more difficult than minimizing \(q(\cdot )\) over \(\mathcal {F}\) in the following sense: if a given semidefinite-programming (SDP) relaxation for \(\min \{ q(x) : x \in \mathcal {F}\}\) is tight, then the addition of l linear constraints derived from \(\mathcal {E}_1, \ldots , \mathcal {E}_l\) yields a tight SDP relaxation for \(\min \{ q(x) : x \in \mathcal {G}\}\). We also prove that the convex hull of \(\{ (x,xx^T) : x \in \mathcal {G}\}\) equals the intersection of the convex hull of \(\{ (x,xx^T) : x \in \mathcal {F}\}\) with the same l linear constraints. Inspired by these results, we resolve a related question in a seemingly unrelated area, mixed-integer nonconvex quadratic programming.
---
paper_title: Polynomial Solvability of Variants of the Trust-Region Subproblem

paper_content:

We consider an optimization problem of the form ::: ::: [EQUATION] ::: ::: where P ⊆ Rn is a polyhedron defined by m inequalities and Q is general and the μh e Rn and the rh quantities are given. In the case |S| = 1, |K| = 0 and m = 0 one obtains the classical trust-region subproblem; a strongly NP-hard problem which has been the focus of much interest because of applications to combinatorial optimization and nonlinear programming. We prove that for each fixed pair |S| and |K| our problem can be solved in polynomial time provided that either (1) |K| > 0 and the number of faces of P that intersect [EQUATION] is polynomially bounded, or (2) |K| = 0 and m is bounded.
---
paper_title: Efficiently solving total least squares with Tikhonov identical regularization

paper_content:

The Tikhonov identical regularized total least squares (TI) is to deal with the ill-conditioned system of linear equations where the data are contaminated by noise. A standard approach for (TI) is to reformulate it as a problem of finding a zero point of some decreasing concave non-smooth univariate function such that the classical bisection search and Dinkelbach’s method can be applied. In this paper, by exploring the hidden convexity of (TI), we reformulate it as a new problem of finding a zero point of a strictly decreasing, smooth and concave univariate function. This allows us to apply the classical Newton’s method to the reformulated problem, which converges globally to the unique root with an asymptotic quadratic convergence rate. Moreover, in every iteration of Newton’s method, no optimization subproblem such as the extended trust-region subproblem is needed to evaluate the new univariate function value as it has an explicit expression. Promising numerical results based on the new algorithm are reported.
---
paper_title: Finding a global optimal solution for a quadratically constrained fractional quadratic problem with applications to the regularized total least squares

paper_content:

We consider the problem of minimizing a fractional quadratic problem involving the ratio of two indefinite quadratic functions, subject to a two-sided quadratic form constraint. This formulation is motivated by the so-called regularized total least squares (RTLS) problem. A key difficulty with this problem is its nonconvexity, and all current known methods to solve it are guaranteed only to converge to a point satisfying first order necessary optimality conditions. We prove that a global optimal solution to this problem can be found by solving a sequence of very simple convex minimization problems parameterized by a single parameter. As a result, we derive an efficient algorithm that produces an $\epsilon$-global optimal solution in a computational effort of $O(n^3 \log \epsilon^{-1})$. The algorithm is tested on problems arising from the inverse Laplace transform and image deblurring. Comparison to other well-known RTLS solvers illustrates the attractiveness of our new method.
---
paper_title: On the solution of the Tikhonov regularization of the total least squares problem

paper_content:

Total least squares (TLS) is a method for treating an overdetermined system of linear equations ${\bf A} {\bf x} \approx {\bf b}$, where both the matrix ${\bf A}$ and the vector ${\bf b}$ are contaminated by noise. Tikhonov regularization of the TLS (TRTLS) leads to an optimization problem of minimizing the sum of fractional quadratic and quadratic functions. As such, the problem is nonconvex. We show how to reduce the problem to a single variable minimization of a function ${\mathcal{G}}$ over a closed interval. Computing a value and a derivative of ${\mathcal{G}}$ consists of solving a single trust region subproblem. For the special case of regularization with a squared Euclidean norm we show that ${\mathcal{G}}$ is unimodal and provide an alternative algorithm, which requires only one spectral decomposition. A numerical example is given to illustrate the effectiveness of our method.
---
paper_title: A Linear-Time Algorithm for Trust Region Problems

paper_content:

We consider the fundamental problem of maximizing a general quadratic function over an ellipsoidal domain, also known as the trust region problem. We give the first provable linear-time (in the number of non-zero entries of the input) algorithm for approximately solving this problem. Specifically, our algorithm returns an $\epsilon$-approximate solution in time $\tilde{O}(N/\sqrt{\epsilon})$, where $N$ is the number of non-zero entries in the input. This matches the runtime of Nesterov's accelerated gradient descent, suitable for the special case in which the quadratic function is concave, and the runtime of the Lanczos method which is applicable when the problem is purely quadratic.
---
paper_title: The trust region subproblem with non-intersecting linear constraints

paper_content:

This paper studies an extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with $$m$$ m linear inequality constraints. When $$m=0,\,m = 1$$ m = 0 , m = 1 , or $$m = 2$$ m = 2 and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial time. However, it is also known that, when $$m \ge 2$$ m ? 2 and at least two of the linear constraints intersect within the ball, i.e., some feasible point of the eTRS satisfies both linear constraints at equality, then the same convex relaxation may admit a gap with eTRS. This paper shows that the convex relaxation has no gap for arbitrary $$m$$ m as long as the linear constraints are non-intersecting.
---
paper_title: Convex Relaxations of the Weighted Maxmin Dispersion Problem

paper_content:

Consider the weighted maxmin dispersion problem of locating point(s) in a given region $ \mathcal{X} \subseteq \mathbb{R}^n$ that is/are furthest from a given set of $m$ points. The region is assumed to be convex under componentwise squaring. We show that this problem is NP-hard even when $\mathcal{X}$ is a box and the weights are equal. We then propose a convex relaxation of this problem for finding an approximate solution and derive an approximation bound of $\frac{1-O(\sqrt{\ln({m})\gamma^{*}})}{2}$, where $\gamma^{*}$ depends on $\mathcal{X}$. When $\mathcal{X}$ is a box or a product of low-dimensional spheres, $\gamma^{*}=O(\frac{1}{n})$ and the convex relaxation reduces to a semidefinite program and a second-order cone program.
---
paper_title: On the Ball-Constrained Weighted Maximin Dispersion Problem

paper_content:

The ball-constrained weighted maximin dispersion problem $(P_ball)$ is to find a point in an $n$-dimensional Euclidean ball such that the minimum of the weighted Euclidean distance from given $m$ points is maximized. We propose a new second-order cone programming relaxation for $(P_ball)$. Under the condition $m\le n$, $(P_ball)$ is polynomial-time solvable since the new relaxation is shown to be tight. In general, we prove that $(P_ball)$ is NP-hard. Then, we propose a new randomized approximation algorithm for solving $(P_ball)$, which provides a new approximation bound of $\frac{1-O(\sqrt{\ln(m)/n})}{2}$.
---
paper_title: A semidefinite framework for trust region subproblems with applications to large scale minimization

paper_content:

Primal-dual pairs of semidefinite programs provide a general framework for the theory and algorithms for the trust region subproblem (TRS). This latter problem consists in minimizing a general quadratic function subject to a convex quadratic constraint and, therefore, it is a generalization of the minimum eigenvalue problem. The importance of (TRS) is due to the fact that it provides the step in trust region minimization algorithms. The semidefinite framework is studied as an interesting instance of semidefinite programming as well as a tool for viewing known algorithms and deriving new algorithms for (TRS). In particular, a dual simplex type method is studied that solves (TRS) as a parametric eigenvalue problem. This method uses the Lanczos algorithm for the smallest eigenvalue as a black box. Therefore, the essential cost of the algorithm is the matrix-vector multiplication and, thus, sparsity can be exploited. A primal simplex type method provides steps for the so-called hard case. Extensive numerical tests for large sparse problems are discussed. These tests show that the cost of the algorithm is 1 +ź(n) times the cost of finding a minimum eigenvalue using the Lanczos algorithm, where 0
---
paper_title: A linear-time algorithm for the trust region subproblem based on hidden convexity

paper_content:

We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov’s accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem.
---
paper_title: Quadratic programs with hollows

paper_content:

Let \(\mathcal {F}\) be a quadratically constrained, possibly nonconvex, bounded set, and let \(\mathcal {E}_1, \ldots , \mathcal {E}_l\) denote ellipsoids contained in \(\mathcal {F}\) with non-intersecting interiors. We prove that minimizing an arbitrary quadratic \(q(\cdot )\) over \(\mathcal {G}:= \mathcal {F}{\setminus } \cup _{k=1}^\ell {{\mathrm{int}}}(\mathcal {E}_k)\) is no more difficult than minimizing \(q(\cdot )\) over \(\mathcal {F}\) in the following sense: if a given semidefinite-programming (SDP) relaxation for \(\min \{ q(x) : x \in \mathcal {F}\}\) is tight, then the addition of l linear constraints derived from \(\mathcal {E}_1, \ldots , \mathcal {E}_l\) yields a tight SDP relaxation for \(\min \{ q(x) : x \in \mathcal {G}\}\). We also prove that the convex hull of \(\{ (x,xx^T) : x \in \mathcal {G}\}\) equals the intersection of the convex hull of \(\{ (x,xx^T) : x \in \mathcal {F}\}\) with the same l linear constraints. Inspired by these results, we resolve a related question in a seemingly unrelated area, mixed-integer nonconvex quadratic programming.
---
paper_title: Low-Rank Semidefinite Programming: Theory and Applications

paper_content:

Finding low-rank solutions of semidefinite programs is important in many applications. For example, semidefinite programs that arise as relaxations of polynomial optimization problems are exact relaxations when the semidefinite program has a rank-1 solution. Unfortunately, computing a minimum-rank solution of a semidefinite program is an NP-hard problem. In this paper we review the theory of low-rank semidefinite programming, presenting theorems that guarantee the existence of a low-rank solution, heuristics for computing low-rank solutions, and algorithms for finding low-rank approximate solutions. Then we present applications of the theory to trust-region problems and signal processing.
---
paper_title: Max-Min Fairness Linear Transceiver Design Problem for a Multi-User SIMO Interference Channel is Polynomial Time Solvable

paper_content:

Consider the linear transceiver design problem for a multi-user single-input multi-output (SIMO) interference channel. Assuming perfect channel knowledge, we formulate this problem as one of maximizing the minimum signal to interference plus noise ratio (SINR) among all the users, subject to individual power constraints at each transmitter. We prove in this letter that the max-min fairness linear transceiver design problem for the SIMO interference channel can be solved to global optimality in polynomial time. We further propose a low-complexity inexact cyclic coordinate ascent algorithm (ICCAA) to solve this problem. Numerical simulations show the proposed algorithm can efficiently find the global optimal solution of the considered problem.
---
paper_title: Quadratic matrix programming

paper_content:

We introduce and study a special class of nonconvex quadratic problems in which the objective and constraint functions have the form $f(\boldmath $X$)={Tr}(\boldmath $X$^T \boldmath $A$ \boldmath $X$) + 2 Tr(\boldmath $B$^T \boldmath $X$) +c, \boldmath $X$ \in {\real R}^{n \times r}$. The latter formulation is termed quadratic matrix programming (QMP) of order $r$. We construct a specially devised semidefinite relaxation (SDR) and dual for the QMP problem and show that under some mild conditions strong duality holds for QMP problems with at most $r$ constraints. Using a result on the equivalence of two characterizations of the nonnegativity property of quadratic functions of the above form, we are able to compare the constructed SDR and dual problems to other known SDRs and dual formulations of the problem. An application to robust least squares problems is discussed.
---
paper_title: A new semidefinite programming relaxation scheme for a class of quadratic matrix problems

paper_content:

Abstract We consider a special class of quadratic matrix optimization problems which often arise in applications. By exploiting the special structure of these problems, we derive a new semidefinite relaxation which, under mild assumptions, is proven to be tight for a larger number of constraints than could be achieved via a direct approach. We show the potential usefulness of these results when applied to robust least-squares and sphere-packing problems.
---
paper_title: On the complexity of quadratic programming with two quadratic constraints

paper_content:

The complexity of quadratic programming problems with two quadratic constraints is an open problem. In this paper we show that when one constraint is a ball constraint and the Hessian of the quadratic function defining the other constraint is positive definite, then, under quite general conditions, the problem can be solved in polynomial time in the real-number model of computation through an approach based on the analysis of the dual space of the Lagrange multipliers. However, the degree of the polynomial is rather large, thus making the result mostly of theoretical interest.
---
paper_title: Convexity Properties Associated with Nonconvex Quadratic Matrix Functions and Applications to Quadratic Programming ∗

paper_content:

We establish several convexity results which are concerned with nonconvex quadratic matrix (QM) functions: strong duality of quadratic matrix programming problems, convexity of the image of mappings comprised of several QM functions and existence of a corresponding S-lemma. As a consequence of our results, we prove that a class of quadratic problems involving several functions with similar matrix terms has a zero duality gap. We present applications to robust optimization, to solution of linear systems immune to implementation errors and to the problem of computing the Chebyshev center of an intersection of balls.
---
paper_title: On a self-consistent-field-like iteration for maximizing the sum of the Rayleigh quotients

paper_content:

In this paper, we consider efficient methods for maximizing x^@?Bxx^@?Wx+x^@?Dx over the unit sphere, where B,D are symmetric matrices, and W is symmetric and positive definite. This problem can arise in the downlink of a multi-user MIMO system and in the sparse Fisher discriminant analysis in pattern recognition. It is already known that the problem of finding a global maximizer is closely associated with a nonlinear extreme eigenvalue problem. Rather than resorting to some general optimization methods, we introduce a self-consistent-field-like (SCF-like) iteration for directly solving the resulting nonlinear eigenvalue problem. The SCF iteration is widely used for solving the nonlinear eigenvalue problems arising in electronic structure calculations. One attractive feature of the SCF for our problem is that once it converges, the limit point not only satisfies the necessary local optimality conditions automatically, but also, and most importantly, satisfies a global optimality condition, which generally is not achievable in some optimization-based methods. The global convergence and local quadratic convergence rate are proved for certain situations. For the general case, we then discuss a trust-region SCF iteration for stabilizing the SCF iteration, which is of good global convergence behavior. Our preliminary numerical experiments show that these algorithms are more efficient than some optimization-based methods.
---
paper_title: The Legendre–Fenchel Conjugate of the Product of Two Positive Definite Quadratic Forms

paper_content:

It is well known that the Legendre-Fenchel conjugate of a positive definite quadratic form can be explicitly expressed as another positive definite quadratic form and that the conjugate of the sum of several positive definite quadratic forms can be expressed via inf-convolution. However, the Legendre-Fenchel conjugate of the product of two positive definite quadratic forms is not clear at present. Hiriart-Urruty posted it as an open question in the field of nonlinear analysis and optimization [Question 11 in SIAM Rev., 49 (2007), pp. 255-273]. From a convex analysis point of view, it is interesting and important to address such a question. The purpose of this paper is to answer this question and to provide a formula for the conjugate of the product of two positive definite quadratic forms. We prove that the computation of the conjugate can be implemented via finding a root of a certain univariate polynomial equation, and we also identify the situations in which the conjugate can be explicitly expressed as a single function without involving any parameter. Some other issues, including the convexity condition for the product function, are also investigated as well. Our analysis shows that the relationship between the matrices of quadratic forms plays a vital role in determining whether the conjugate can be explicitly expressed or not.
---
paper_title: Polynomial Solvability of Variants of the Trust-Region Subproblem

paper_content:

We consider an optimization problem of the form ::: ::: [EQUATION] ::: ::: where P ⊆ Rn is a polyhedron defined by m inequalities and Q is general and the μh e Rn and the rh quantities are given. In the case |S| = 1, |K| = 0 and m = 0 one obtains the classical trust-region subproblem; a strongly NP-hard problem which has been the focus of much interest because of applications to combinatorial optimization and nonlinear programming. We prove that for each fixed pair |S| and |K| our problem can be solved in polynomial time provided that either (1) |K| > 0 and the number of faces of P that intersect [EQUATION] is polynomially bounded, or (2) |K| = 0 and m is bounded.
---
paper_title: Efficiently solving total least squares with Tikhonov identical regularization

paper_content:

The Tikhonov identical regularized total least squares (TI) is to deal with the ill-conditioned system of linear equations where the data are contaminated by noise. A standard approach for (TI) is to reformulate it as a problem of finding a zero point of some decreasing concave non-smooth univariate function such that the classical bisection search and Dinkelbach’s method can be applied. In this paper, by exploring the hidden convexity of (TI), we reformulate it as a new problem of finding a zero point of a strictly decreasing, smooth and concave univariate function. This allows us to apply the classical Newton’s method to the reformulated problem, which converges globally to the unique root with an asymptotic quadratic convergence rate. Moreover, in every iteration of Newton’s method, no optimization subproblem such as the extended trust-region subproblem is needed to evaluate the new univariate function value as it has an explicit expression. Promising numerical results based on the new algorithm are reported.
---
paper_title: Potpourri of Conjectures and Open Questions in Nonlinear Analysis and Optimization ∗

paper_content:

We present a collection of fourteen conjectures and open problems in the fields of nonlinear analysis and optimization. These problems can be classified into three groups: problems of pure mathematical interest, problems motivated by scientific computing and applications, and problems whose solutions are known but for which we would like to know better proofs. For each problem we provide a succinct presentation, a list of appropriate references, and a view of the state of the art of the subject.
---
paper_title: Solving Generalized CDT Problems via Two-Parameter Eigenvalues

paper_content:

We consider solving a nonconvex quadratic minimization problem with two quadratic constraints, one of which being convex. This problem is a generalization of the Celis--Denis--Tapia (CDT) problem and thus we refer to it as GCDT (Generalized CDT). The CDT problem has been widely studied, but no polynomial-time algorithm was known until Bienstock's recent work. His algorithm solves the CDT problem in polynomial time with respect to the number of bits in data and $\log\epsilon^{-1}$ by admitting an $\epsilon$ error in the constraints. The algorithm, however, appears to be difficult to implement. In this paper, we present another algorithm for GCDT, which is guaranteed to find a global solution for almost all GCDT instances (and slightly perturbed ones in some exceptionally rare cases), in exact arithmetic (including eigenvalue computation). Our algorithm is based on the approach proposed by Iwata, Nakatsukasa, and Takeda (2015) for computing the signed distance between overlapping ellipsoids. Our algorithm computes all the Lagrange multipliers of GCDT by solving a two-parameter linear eigenvalue problem, obtains the corresponding KKT points, and finds a global solution as the KKT point with the smallest objective value. In practice, in finite precision arithmetic, our algorithm requires $O(n^6\log\log u^{-1})$ computational time, where $n$ is the number of variables and $u$ is the unit roundoff. Although we derive our algorithm under the unrealistic assumption that exact eigenvalues can be computed, numerical experiments illustrate that our algorithm performs well in finite precision arithmetic.
---
paper_title: On the solution of the Tikhonov regularization of the total least squares problem

paper_content:

Total least squares (TLS) is a method for treating an overdetermined system of linear equations ${\bf A} {\bf x} \approx {\bf b}$, where both the matrix ${\bf A}$ and the vector ${\bf b}$ are contaminated by noise. Tikhonov regularization of the TLS (TRTLS) leads to an optimization problem of minimizing the sum of fractional quadratic and quadratic functions. As such, the problem is nonconvex. We show how to reduce the problem to a single variable minimization of a function ${\mathcal{G}}$ over a closed interval. Computing a value and a derivative of ${\mathcal{G}}$ consists of solving a single trust region subproblem. For the special case of regularization with a squared Euclidean norm we show that ${\mathcal{G}}$ is unimodal and provide an alternative algorithm, which requires only one spectral decomposition. A numerical example is given to illustrate the effectiveness of our method.
---
paper_title: Quadratic matrix programming

paper_content:

We introduce and study a special class of nonconvex quadratic problems in which the objective and constraint functions have the form $f(\boldmath $X$)={Tr}(\boldmath $X$^T \boldmath $A$ \boldmath $X$) + 2 Tr(\boldmath $B$^T \boldmath $X$) +c, \boldmath $X$ \in {\real R}^{n \times r}$. The latter formulation is termed quadratic matrix programming (QMP) of order $r$. We construct a specially devised semidefinite relaxation (SDR) and dual for the QMP problem and show that under some mild conditions strong duality holds for QMP problems with at most $r$ constraints. Using a result on the equivalence of two characterizations of the nonnegativity property of quadratic functions of the above form, we are able to compare the constructed SDR and dual problems to other known SDRs and dual formulations of the problem. An application to robust least squares problems is discussed.
---
paper_title: Trust Region Subproblem with a Fixed Number of Additional Linear Inequality Constraints has Polynomial Complexity

paper_content:

The trust region subproblem with a fixed number m additional linear inequality constraints, denoted by (Tm), have drawn much attention recently. The question as to whether Problem (Tm) is in Class P or Class NP remains open. So far, the only affirmative general result is that (T1) has an exact SOCP/SDP reformulation and thus is polynomially solvable. By adopting an early result of Mart´onez on local non-global minimum of the trust region subproblem, we can inductively reduce any instance in (Tm) to a sequence of trust region subproblems (T0). Although the total number of (T0) to be solved takes an exponential order of m, the reduction scheme still provides an argument that the class (Tm) has polynomial complexity for each fixed m. In contrast, we show by a simple example that, solving the class of extended trust region subproblems which contains more linear inequality constraints than the problem dimension; or the class of instances consisting of an arbitrarily number of linear constraints, namely S1=1 (Tm), is NP-hard. When m is small such as m = 1,2, our inductive algorithm should be more efficient than the SOCP/SDP reformulation since at most 2 or 5 subproblems of (T0), respectively, are to be handled. In the end of the paper, we improve a very recent dimension condition by Jeyakumar and Li under which (Tm) admits an exact SDP relaxation. Examples show that such an improvement can be strict indeed.
---
paper_title: A generalized solution of the orthogonal procrustes problem

paper_content:

A solutionT of the least-squares problemAT=B +E, givenA andB so that trace (E′E)= minimum andT′T=I is presented. It is compared with a less general solution of the same problem which was given by Green [5]. The present solution, in contrast to Green's, is applicable to matricesA andB which are of less than full column rank. Some technical suggestions for the numerical computation ofT and an illustrative example are given.
---
paper_title: A note on polynomial solvability of the CDT problem

paper_content:

We describe a simple polynomial-time algorithm for the CDT problem that relies on a construction of Barvinok.
---
paper_title: On Local Convexity of Quadratic Transformations

paper_content:

In this paper, we improve Polyak's local convexity result for quadratic transformations. Extension and open problems are also presented.
---

Title: A Survey of Hidden Convex Optimization

Section 1: Introduction
Description 1: Present the overview of convex programming, its challenges, and the concept of hidden convex optimization. Summarize the structure of the paper.

Section 2: Nonlinear transformation
Description 2: Describe various nonlinear transformation techniques used to convert nonconvex problems into convex problems.

Section 3: Lagrangian dual and its variation
Description 3: Discuss how strong Lagrangian duality can be achieved for nonconvex problems and explore variations of Lagrangian duality.

Section 4: Tight primal relaxation
Description 4: Explain how primal relaxation approaches can reveal hidden convexity in nonconvex optimization problems.

Section 5: Open problems
Description 5: Identify and elaborate on open research problems that remain in the field of hidden convex optimization.