First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints

In this paper we consider a mathematical program with semidefinite cone complementarity constraints (SDCMPCC). Such a problem is a matrix analogue of the mathematical program with (vector) complementarity constraints (MPCC) and includes MPCC as a special case. We first derive explicit formulas for the proximal and limiting normal cone of the graph of the normal cone to the positive semidefinite cone. Using these formulas and classical nonsmooth first order necessary optimality conditions we derive explicit expressions for the strong-, Mordukhovich- and Clarke- (S-, M- and C-)stationary conditions. Moreover we give constraint qualifications under which a local solution of SDCMPCC is a S-, M- and C-stationary point. Moreover we show that applying these results to MPCC produces new and weaker necessary optimality conditions.     

Lower-Order Penalization Approach to Nonlinear Semidefinite Programming

In this paper, we reformulate a nonlinear semidefinite programming problem into an optimization problem with a matrix equality constraint. We apply a lower-order penalization approach to the reformulated problem. Necessary and sufficient conditions that guarantee the global (local) exactness of the lower-order penalty functions are derived. Convergence results of the optimal values and optimal solutions of the penalty problems to those of the original semidefinite program are established. Since the penalty functions may not be smooth or even locally Lipschitz, we invoke the Ekeland variational principle to derive necessary optimality conditions for the penalty problems. Under certain conditions, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original semidefinite program. Communicated by Y. Zhang This work was supported by a Postdoctoral Fellowship of Hong Kong Polytechnic University and by the Research Grants Council of Hong Kong.     

Approximation of rank function and its application to the nearest low-rank correlation matrix

The rank function rank(.) is neither continuous nor convex which brings much difficulty to the solution of rank minimization problems. In this paper, we provide a unified framework to construct the approximation functions of rank(.), and study their favorable properties. Particularly, with two families of approximation functions, we propose a convex relaxation method for the rank minimization problems with positive semidefinite cone constraints, and illustrate its application by computing the nearest low-rank correlation matrix. Numerical results indicate that this convex relaxation method is comparable with the sequential semismooth Newton method (Li and Qi in SIAM J Optim 21:1641–1666, 2011) and the majorized penalty approach (Gao and Sun, 2010) in terms of the quality of solutions.     

A sequential quadratic penalty method for nonlinear semidefinite programming

In this article, a nonlinear semidefinite program is reformulated into a mathematical program with a matrix equality constraint and a sequential quadratic penalty method is proposed to solve the latter problem. We discuss the differentiability and convexity of the penalty function. Necessary and sufficient conditions for the convergence of optimal values of penalty problems to that of the original semidefinite program are obtained. The convergence of optimal solutions of penalty problems to that of the original semidefinite program is also investigated. We show that any limit point of a sequence of stationary points of penalty problems satisfies the KKT optimality condition of the semidefinite program. Smoothed penalty problems that have the same order of smothness as the original semidefinite program are adopted. Corresponding results such as the convexity of the smoothed penalty function, the convergence of optimal values, optimal solutions and the stationary points of the smoothed penalty problems are obtained.     

Restricted linear constrained minimization of quadratic functionals

In this work, a linearly constrained minimization of a positive semidefinite quadratic functional is examined. We propose two different approaches to this problem. Our results are concerning infinite dimensional real Hilbert spaces, with a singular positive semidefinite operator related to the functional, and considering as constraint a singular operator. The difference between the proposed approaches for the minimization and previous work on this problem is that it is considered for all vectors belonging to the least squares solutions set, or to the vectors perpendicular to the kernel of the related operator or matrix.     

Convex optimization approach to a single quadratically constrained quadratic minimization problem

In this paper, first we show that for rank deficient matrices, the optimal solution of a single equality constrained quadratic minimization problem can be found by relaxing the equality constraint to the inequality one, which makes the problem a convex problem. Then we show that for full rank matrices, an optimal solution can be obtained using semidefinite optimization framework.     

A Dynamical Systems Analysis of Semidefinite Programming with Application to Quadratic Optimization with Pure Quadratic Equality Constraints

This paper considers the problem of minimizing a quadratic cost subject to purely quadratic equality constraints. This problem is tackled by first relating it to a standard semidefinite programming problem. The approach taken leads to a dynamical systems analysis of semidefinite programming and the formulation of a gradient descent flow which can be used to solve semidefinite programming problems. Though the reformulation of the initial problem as a semidefinite pro- gramming problem does not in general lead directly to a solution of the original problem, the initial problem is solved by using a modified flow incorporating a penalty function. Accepted 10 March 1998     

On relations between chance constrained and penalty function problems under discrete distributions

We extend the theory of penalty functions to stochastic programming problems with nonlinear inequality constraints dependent on a random vector with known distribution. We show that the problems with penalty objective, penalty constraints and chance constraints are asymptotically equivalent under discretely distributed random parts. This is a complementary result to Branda (Kybernetika 48(1):105–122, 2012a), Branda and Dupa?ová (Ann Oper Res 193(1):3–19, 2012), and Ermoliev et al. (Ann Oper Res 99:207–225, 2000) where the theorems were restricted to continuous distributions only. We propose bounds on optimal values and convergence of optimal solutions. Moreover, we apply exact penalization under modified calmness property to improve the results.     

An approximation theory of matrix rank minimization and its application to quadratic equations

Matrix rank minimization problems are gaining plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization problem can be approximated to any level of accuracy via continuous optimization (especially, linear and nonlinear semidefinite programming) problems. One of the main results in this paper shows that if the feasible set of the problem has a minimum rank element with the least Frobenius norm, then any accumulation point of solutions to the approximation problem, as the approximation parameter tends to zero, is a minimum rank solution of the original problem. The tractability under certain conditions and convex relaxation of the approximation problem are also discussed. An immediate application of this theory to the system of quadratic equations is presented in this paper. It turns out that the condition for such a system without a nonzero solution can be characterized by a rank minimization problem, and thus the proposed approximation theory can be used to establish some sufficient conditions for the system to possess only zero solution.     

Strong formulations for quadratic optimization with M-matrices and indicator variables

We propose a DC (Difference of two Convex functions) formulation approach for sparse optimization problems having a cardinality or rank constraint. With the largest-k norm, an exact DC representation of the cardinality constraint is provided. We then transform the cardinality-constrained problem into a penalty function form and derive exact penalty parameter values for some optimization problems, especially for quadratic minimization problems which often appear in practice. A DC Algorithm (DCA) is presented, where the dual step at each iteration can be efficiently carried out due to the accessible subgradient of the largest-k norm. Furthermore, we can solve each DCA subproblem in linear time via a soft thresholding operation if there are no additional constraints. The framework is extended to the rank-constrained problem as well as the cardinality- and the rank-minimization problems. Numerical experiments demonstrate the efficiency of the proposed DCA in comparison with existing methods which have other penalty terms.     

Convergence Properties of Dikin’s Affine Scaling Algorithm for Nonconvex Quadratic Minimization

We study convergence properties of Dikin’s affine scaling algorithm applied to nonconvex quadratic minimization. First, we show that the objective function value either diverges or converges Q-linearly to a limit. Using this result, we show that, in the case of box constraints, the iterates converge to a unique point satisfying first-order and weak second-order optimality conditions, assuming the objective function Hessian Q is rank dominant with respect to the principal submatrices that are maximally positive semidefinite. Such Q include matrices that are positive semidefinite or negative semidefinite or nondegenerate or have negative diagonals. Preliminary numerical experience is reported.     

Stochastic nuclear outages semidefinite relaxations

This paper deals with stochastic scheduling of nuclear power plant outages. Focusing on the main constraints of the problem, we propose a stochastic formulation with a discrete distribution for random variables, that leads to a mixed 0/1 quadratically constrained quadratic program. Then we investigate semidefinite relaxations for solving this hard problem. Numerical results on several instances of the problem show the efficiency of this approach, i.e., the gap between the optimal solution and the continuous relaxation is on average equal to 53.35 % whereas the semidefinite relaxation yields an average gap of 2.76 %. A feasible solution is then obtained with a randomized rounding procedure.     

有限维逼近无限维总极值的积分型方法

本文用有限维逼近无限维的方法来讨论函数空间中的总体最优化问题．我们给出了新的最优性条件和用变测度方法求得的有限维解逼近总体最优解的算法．对于有约柬问题，我们用不连续罚函数法把有约束问题化为无约束问题来求解．最后，我们通过一个具有非凸状态约束的最优控制问可题的实例来说明算法的有效性．     

Existence of Exact Penalty for Constrained Optimization Problems in Metric Spaces

In this paper we use the penalty approach in order to study constrained minimization problems in a complete metric space with locally Lipschitzian mixed constraints. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we establish sufficient conditions for the exact penalty property.      

Convergence Properties of Dikin’s Affine Scaling Algorithm for Nonconvex Quadratic Minimization

We study convergence properties of Dikins affine scaling algorithm applied to nonconvex quadratic minimization. First, we show that the objective function value either diverges or converges Q-linearly to a limit. Using this result, we show that, in the case of box constraints, the iterates converge to a unique point satisfying first-order and weak second-order optimality conditions, assuming the objective function Hessian Q is rank dominant with respect to the principal submatrices that are maximally positive semidefinite. Such Q include matrices that are positive semidefinite or negative semidefinite or nondegenerate or have negative diagonals. Preliminary numerical experience is reported.     

Study of a primal-dual algorithm for equality constrained minimization

The paper proposes a primal-dual algorithm for solving an equality constrained minimization problem. The algorithm is a Newton-like method applied to a sequence of perturbed optimality systems that follow naturally from the quadratic penalty approach. This work is first motivated by the fact that a primal-dual formulation of the quadratic penalty provides a better framework than the standard primal form. This is highlighted by strong convergence properties proved under standard assumptions. In particular, it is shown that the usual requirement of solving the penalty problem with a precision of the same size as the perturbation parameter, can be replaced by a much less stringent criterion, while guaranteeing the superlinear convergence property. A second motivation is that the method provides an appropriate regularization for degenerate problems with a rank deficient Jacobian of constraints. The numerical experiments clearly bear this out. Another important feature of our algorithm is that the penalty parameter is allowed to vary during the inner iterations, while it is usually kept constant. This alleviates the numerical problem due to ill-conditioning of the quadratic penalty, leading to an improvement of the numerical performances.     

The effect of calmness on the solution set of systems of nonlinear equations

We address the problem of solving a continuously differentiable nonlinear system of equations under the condition of calmness. This property, also called upper Lipschitz-continuity in the literature, can be described by a local error bound and is being widely used as a regularity condition in optimization. Indeed, it is known to be significantly weaker than classic regularity assumptions that imply that solutions are isolated. We prove that under this condition, the rank of the Jacobian of the function that defines the system of equations must be locally constant on the solution set. In addition, we prove that locally, the solution set must be a differentiable manifold. Our results are illustrated by examples and discussed in terms of their theoretical relevance and algorithmic implications.     

A newton-penalty method for a simplified liquid crystal model

In this paper we are concerned with the computation of a liquid crystal model defined by a simplified Oseen-Frank energy functional and a (sphere) nonlinear constraint. A particular case of this model defines the well known harmonic maps. We design a new iterative method for solving such a minimization problem with the nonlinear constraint. The main ideas are to linearize the nonlinear constraint by Newton’s method and to define a suitable penalty functional associated with the original minimization problem. It is shown that the solution sequence of the new minimization problems with the linear constraints converges to the desired solutions provided that the penalty parameters are chosen by a suitable rule. Numerical results confirm the efficiency of the new method.     

A Unified Approach to the Global Exactness of Penalty and Augmented Lagrangian Functions I: Parametric Exactness

In this two-part study, we develop a unified approach to the analysis of the global exactness of various penalty and augmented Lagrangian functions for constrained optimization problems in finite-dimensional spaces. This approach allows one to verify in a simple and straightforward manner whether a given penalty/augmented Lagrangian function is exact, i.e., whether the problem of unconstrained minimization of this function is equivalent (in some sense) to the original constrained problem, provided the penalty parameter is sufficiently large. Our approach is based on the so-called localization principle that reduces the study of global exactness to a local analysis of a chosen merit function near globally optimal solutions. In turn, such local analysis can be performed with the use of optimality conditions and constraint qualifications. In the first paper, we introduce the concept of global parametric exactness and derive the localization principle in the parametric form. With the use of this version of the localization principle, we recover existing simple, necessary, and sufficient conditions for the global exactness of linear penalty functions and for the existence of augmented Lagrange multipliers of Rockafellar–Wets’ augmented Lagrangian. We also present completely new necessary and sufficient conditions for the global exactness of general nonlinear penalty functions and for the global exactness of a continuously differentiable penalty function for nonlinear second-order cone programming problems. We briefly discuss how one can construct a continuously differentiable exact penalty function for nonlinear semidefinite programming problems as well.     

Enhancing RLT relaxations via a new class of semidefinite cuts

In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.