On the weighting method for least squares problems with linear equality constraints

The weighting method for solving a least squares problem with linear equality constraints multiplies the constraints by a large number and appends them to the top of the least squares problem, which is then solved by standard techniques. In this paper we give a new analysis of the method, based on the QR decomposition, that exhibits many features of the algorithm. In particular it suggests a natural criterion for chosing the weighting factor. This work was supported in part by the National Science Foundation under grant CCR 95503126.     

A semismooth Newton method for a class of semilinear optimal control problems with box and volume constraints

In this paper we consider optimal control problems subject to a semilinear elliptic state equation together with the control constraints 0≤u≤1 and ∫u=m. Optimality conditions for this problem are derived and reformulated as a nonlinear, nonsmooth equation which is solved using a semismooth Newton method. A regularization of the nonsmooth equation is necessary to obtain the superlinear convergence of the semismooth Newton method. We prove that the solutions of the regularized problems converge to a solution of the original problem and a path-following technique is used to ensure a constant decrease rate of the residual. We show that, in certain situations, the optimal controls take 0–1 values, which amounts to solving a topology optimization problem with volume constraint.     

An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.     

Solutions to quadratic minimization problems with box and integer constraints

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.     

Separable nonlinear least squares fitting with linear bound constraints and its application in magnetic resonance spectroscopy data quantification

An application in magnetic resonance spectroscopy quantification models a signal as a linear combination of nonlinear functions. It leads to a separable nonlinear least squares fitting problem, with linear bound constraints on some variables. The variable projection (VARPRO) technique can be applied to this problem, but needs to be adapted in several respects. If only the nonlinear variables are subject to constraints, then the Levenberg–Marquardt minimization algorithm that is classically used by the VARPRO method should be replaced with a version that can incorporate those constraints. If some of the linear variables are also constrained, then they cannot be projected out via a closed-form expression as is the case for the classical VARPRO technique. We show how quadratic programming problems can be solved instead, and we provide details on efficient function and approximate Jacobian evaluations for the inequality constrained VARPRO method.     

Spline smoothing under constraints on derivatives

An efficient algorithm for computing a smoothing polynomial splines under inequality constraints on derivatives is introduced where both order and breakpoints ofs can be prescribed arbitrarily. By using the B-spline representation ofs, the original semi-infinite constraints are replaced by stronger finite ones, leading to a least squares problem with linear inequality constraints. Then these constraints are transformed into simple box constraints by an appropriate substitution of variables so that efficient standard techniques for solving such problems can be applied. Moreover, the smoothing term commonly used is replaced by a cheaply computable approximation. All matrix transformations are realized by numerically stable Givens rotations, and the band structure of the problem is exploited as far as possible.     

A reduced gradient method for quadratic programs with quadratic constraints and lp-constrained lp-approximation problems

A dual algorithm is developed for solving a general class of nonlinear programs that properly contains all convex quadratic programs with quadratic constraints and l_p-constrained l_p-approximation problems. The general dual program to be solved has essentially linear constraints but the objective function is nondifferentiable when certain variables equal zero. Modifications to the reduced gradient method for linearly constrained problems are presented that overcome the numerical difficulties associated with the nondifferentiable objective function. These modifications permit ‘blocks’ of variables to move to and away from zero on certain iterations even though the objective function is nondifferentiable at points having a block of variables equal to zero.     

An algorithm for solving the indefinite least squares problem with equality constraints

An algorithm for computing the solution of indefinite least squares problems and of indefinite least squares problems with equality constrained is presented. Such problems arise when solving total least squares problems and in H ^∞-smoothing. The proposed algorithm relies only on stable orthogonal transformations reducing recursively the associated augmented matrix to proper block anti-triangular form. Some numerical results are reported showing the properties of the algorithm.     

On convex quadratic programs with linear complementarity constraints

The paper shows that the global resolution of a general convex quadratic program with complementarity constraints (QPCC), possibly infeasible or unbounded, can be accomplished in finite time. The method constructs a minmax mixed integer formulation by introducing finitely many binary variables, one for each complementarity constraint. Based on the primal-dual relationship of a pair of convex quadratic programs and on a logical Benders scheme, an extreme ray/point generation procedure is developed, which relies on valid satisfiability constraints for the integer program. To improve this scheme, we propose a two-stage approach wherein the first stage solves the mixed integer quadratic program with pre-set upper bounds on the complementarity variables, and the second stage solves the program outside this bounded region by the Benders scheme. We report computational results with our method. We also investigate the addition of a penalty term y ^T Dw to the objective function, where y and w are the complementary variables and D is a nonnegative diagonal matrix. The matrix D can be chosen effectively by solving a semidefinite program, ensuring that the objective function remains convex. The addition of the penalty term can often reduce the overall runtime by at least 50 %. We report preliminary computational testing on a QP relaxation method which can be used to obtain better lower bounds from infeasible points; this method could be incorporated into a branching scheme. By combining the penalty method and the QP relaxation method, more than 90 % of the gap can be closed for some QPCC problems.     

Virtual control regularization of state constrained linear quadratic optimal control problems

A numerical method for linear quadratic optimal control problems with pure state constraints is analyzed. Using the virtual control concept introduced by Cherednichenko et al. (Inverse Probl. 24:1–21, 2008) and Krumbiegel and R?sch (Control Cybern. 37(2):369–392, 2008), the state constrained optimal control problem is embedded into a family of optimal control problems with mixed control-state constraints using a regularization parameter α>0. It is shown that the solutions of the problems with mixed control-state constraints converge to the solution of the state constrained problem in the L ² norm as α tends to zero. The regularized problems can be solved by a semi-smooth Newton method for every α>0 and thus the solution of the original state constrained problem can be approximated arbitrarily close as α approaches zero. Two numerical examples with benchmark problems are provided.     

A Joint Tikhonov Regularization and Augmented Lagrange Approach for Ill-Posed State Constrained Control Problems with Sparse Controls

Abstract

We provide a modified augmented Lagrange method coupled with a Tikhonov regularization for solving ill-posed state constrained elliptic optimal control problems with sparse controls. We consider a linear quadratic optimal control problem without any additional L² regularization terms. The sparsity is guaranteed by an additional L¹ term. Here, the modification of the classical augmented Lagrange method guarantees us uniform boundedness of the multiplier that corresponds to the state constraints. We present a coupling between the regularization parameter introduced by the Tikhonov regularization and the penalty parameter from the augmented Lagrange method, which allows us to prove strong convergence of the controls and their corresponding states. Moreover, convergence results proving the weak convergence of the adjoint state and weak*-convergence of the multiplier are provided. Finally, we demonstrate our method in several numerical examples.     

On safe tractable approximations of chance constraints

A natural way to handle optimization problem with data affected by stochastic uncertainty is to pass to a chance constrained version of the problem, where candidate solutions should satisfy the randomly perturbed constraints with probability at least 1 − ?. While being attractive from modeling viewpoint, chance constrained problems “as they are” are, in general, computationally intractable. In this survey paper, we overview several simulation-based and simulation-free computationally tractable approximations of chance constrained convex programs, primarily, those of chance constrained linear, conic quadratic and semidefinite programming.     

Trust-region problems with linear inequality constraints: exact SDP relaxation,global optimality and robust optimization

The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.     

Perturbation Identities for Regularized Tikhonov Inverses and Weighted Pseudoinverses

We consider the perturbation analysis of two important problems for solving ill-conditioned or rank-deficient linear least squares problems. The Tikhonov regularized problem is a linear least squares problem with a regularization term balancing the size of the residual against the size of the weighted solution. The weight matrix can be a non-square matrix (usually with fewer rows than columns). The minimum-norm problem is the minimization of the size of the weighted solutions given by the set of solutions to the, possibly rank-deficient, linear least squares problem.It is well known that the solution of the Tikhonov problem tends to the minimum-norm solution as the regularization parameter of the Tikhonov problem tends to zero. Using this fact and the generalized singular value decomposition enable us to make a perturbation analysis of the minimum-norm problem with perturbation results for the Tikhonov problem. From the analysis we attain perturbation identities for Tikhonov inverses and weighted pseudoinverses.     

Regularization methods for optimization problems with probabilistic constraints

We analyze nonlinear stochastic optimization problems with probabilistic constraints on nonlinear inequalities with random right hand sides. We develop two numerical methods with regularization for their numerical solution. The methods are based on first order optimality conditions and successive inner approximations of the feasible set by progressive generation of p-efficient points. The algorithms yield an optimal solution for problems involving α-concave probability distributions. For arbitrary distributions, the algorithms solve the convex hull problem and provide upper and lower bounds for the optimal value and nearly optimal solutions. The methods are compared numerically to two cutting plane methods.     

On the perturbation of least squares problems with equality constraints

Some new perturbation results are presented for least squares problems with equality constraints, in which relative errors are obtained on perturbed solutions, least squares residuals, and vectors of Lagrange multipliers of the problem, based on the equivalence of the problem to a usual least squares problem and optimal perturbation results for orthogonal projections.     

Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations

In this paper we present necessary conditions for global optimality for polynomial problems with box or bivalent constraints using separable polynomial relaxations. We achieve this by first deriving a numerically checkable characterization of global optimality for separable polynomial problems with box as well as bivalent constraints. Our necessary optimality conditions can be numerically checked by solving semi-definite programming problems. Then, by employing separable polynomial under-estimators, we establish sufficient conditions for global optimality for classes of polynomial optimization problems with box or bivalent constraints. We construct underestimators using the sum of squares convex (SOS-convex) polynomials of real algebraic geometry. An important feature of SOS-convexity that is generally not shared by the standard convexity is that whether a polynomial is SOS-convex or not can be checked by solving a semidefinite programming problem. We illustrate the versatility of our optimality conditions by simple numerical examples.     

Minimal Zero Norm Solutions of Linear Complementarity Problems

In this paper, we study minimal zero norm solutions of the linear complementarity problems, defined as the solutions with smallest cardinality. Minimal zero norm solutions are often desired in some real applications such as bimatrix game and portfolio selection. We first show the uniqueness of the minimal zero norm solution for Z-matrix linear complementarity problems. To find minimal zero norm solutions is equivalent to solve a difficult zero norm minimization problem with linear complementarity constraints. We then propose a p norm regularized minimization model with p in the open interval from zero to one, and show that it can approximate minimal zero norm solutions very well by sequentially decreasing the regularization parameter. We establish a threshold lower bound for any nonzero entry in its local minimizers, that can be used to identify zero entries precisely in computed solutions. We also consider the choice of regularization parameter to get desired sparsity. Based on the theoretical results, we design a sequential smoothing gradient method to solve the model. Numerical results demonstrate that the sequential smoothing gradient method can effectively solve the regularized model and get minimal zero norm solutions of linear complementarity problems.     

The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. The process is repeated with different samples to obtain candidate solutions along with statistical estimates of their optimality gaps.We present a detailed computational study of the application of the SAA method to solve three classes of stochastic routing problems. These stochastic problems involve an extremely large number of scenarios and first-stage integer variables. For each of the three problem classes, we use decomposition and branch-and-cut to solve the approximating problem within the SAA scheme. Our computational results indicate that the proposed method is successful in solving problems with up to 2¹⁶⁹⁴ scenarios to within an estimated 1.0% of optimality. Furthermore, a surprising observation is that the number of optimality cuts required to solve the approximating problem to optimality does not significantly increase with the size of the sample. Therefore, the observed computation times needed to find optimal solutions to the approximating problems grow only linearly with the sample size. As a result, we are able to find provably near-optimal solutions to these difficult stochastic programs using only a moderate amount of computation time.