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.     

A penalty function method based on bilevel programming for solving inverse optimal value problems

In this work, we reformulate the inverse optimal value problem equivalently as a corresponding nonlinear bilevel programming (BLP) problem. For the nonlinear BLP problem, the duality gap of the lower level problem is appended to the upper level objective with a penalty, and then a penalized problem is obtained. On the basis of the concept of partial calmness, we prove that the penalty function is exact. Then, an algorithm is proposed and an inverse optimal value problem is resolved to illustrate the algorithm.     

Partial inverse maximum spanning tree in which weight can only be decreased under $$l_p$$-norm

The maximum or minimum spanning tree problem is a classical combinatorial optimization problem. In this paper, we consider the partial inverse maximum spanning tree problem in which the weight function can only be decreased. Given a graph, an acyclic edge set, and an edge weight function, the goal of this problem is to decrease weights as little as possible such that there exists with respect to function containing the given edge set. If the given edge set has at least two edges, we show that this problem is APX-Hard. If the given edge set contains only one edge, we present a polynomial time algorithm.     

An Approximation Scheme for Uncertain Minimax Optimal Control Problems

In this work, we address an uncertain minimax optimal control problem with linear dynamics where the objective functional is the expected value of the supremum of the running cost over a time interval. By taking an independently drawn random sample, the expected value function is approximated by the corresponding sample average function. We study the epi-convergence of the approximated objective functionals as well as the convergence of their global minimizers. Then we define an Euler discretization in time of the sample average problem and prove that the value of the discrete time problem converges to the value of the sample average approximation. In addition, we show that there exists a sequence of discrete problems such that the accumulation points of their minimizers are optimal solutions of the original problem. Finally, we propose a convergent descent method to solve the discrete time problem, and show some preliminary numerical results for two simple examples.     

Approximation algorithms for combinatorial fractional programming problems

We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper, we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time approximation scheme for the fractional 0–1 knapsack problem.     

A Perturbation approach for an inverse quadratic programming problem

We consider an inverse quadratic programming (QP) problem in which the parameters in both the objective function and the constraint set of a given QP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a linear complementarity constrained minimization problem with a positive semidefinite cone constraint. With the help of duality theory, we reformulate this problem as a linear complementarity constrained semismoothly differentiable (SC¹) optimization problem with fewer variables than the original one. We propose a perturbation approach to solve the reformulated problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and its global convergence and local quadratic convergence rate are shown. As the objective function of the problem is a SC¹ function involving the projection operator onto the cone of positively semi-definite symmetric matrices, the analysis requires an implicit function theorem for semismooth functions as well as properties of the projection operator in the symmetric-matrix space. Since an approximate proximal point is required in the inexact Newton method, we also give a Newton method to obtain it. Finally we report our numerical results showing that the proposed approach is quite effective.     

Optimal control of the heat equation in an inhomogeneous body

In this paper we consider a heat flow in an inhomogeneous body without internal source. There exists special initial and boundary conditions in this system and we intend to find a convenient coefficient of heat conduction for this body so that body cool off as much as possible after definite time. We consider this problem in a general form as an optimal control problem which coefficient of heat conduction is optimal function. Then we replace this problem by another in which we seek to minimize a linear form over a subset of the product of two measures space defined by linear equalities. Then we construct an approximately optimal control.     

Least trimmed squares regression,least median squares regression,and mathematical programming

In this paper, we study LTS and LMS regression, two high breakdown regression estimators, from an optimization point of view. We show that LTS regression is a nonlinear optimization problem that can be treated as a concave minimization problem over a polytope. We derive several important properties of the corresponding objective function that can be used to obtain algorithms for the exact solution of LTS regression problems, i.e., to find a global optimum to the problem. Because of today's limited problem-solving capabilities in exact concave minimization, we give an easy-to-implement pivoting algorithm to determine regression parameters corresponding to local optima of the LTS regression problem. For the LMS regression problem, we briefly survey the existing solution methods which are all based on enumeration. We formulate the LMS regression problem as a mixed zero-one linear programming problem which we analyze in depth to obtain theoretical insights required for future algorithmic and computational work.     

An Interval Assignment Problem for Resource Optimization in LTE Networks

In this paper we study the problem of resource allocation in SC-FDMA (Single Carrier Frequency Division Multiple Access) which is adopted as the multiple access scheme for the uplink in the 3GPP-LTE (3rd Generation Partnership Project - Long Term Evolution) standard. The problem can be modeled as an assignment problem where each user can be given a subset of consecutive channels seen as an interval. After introducing the problem, we first prove that it is NP-hard to solve. Then we review some cases where the problem is solvable in polynomial time. An efficient cutting plane algorithm is presented with experimental results.     

Complexity of a scheduling problem with controllable processing times

We consider the problem of scheduling a set of independent jobs on a single machine so as to minimize the total weighted completion time, subject to the constraint that the total compression cost is less than or equal to a fixed amount. The complexity of this problem is mentioned as an open problem. In this note we show that the problem is NP-hard.     

Nonconvex and relaxed infinite-horizon optimal control problems

In this paper, we consider the Lagrange problem of optimal control defined on an unbounded time interval in which the traditional convexity hypotheses are not met. Models of this form have been introduced into the economics literature to investigate the exploitation of a renewable resource and to treat various aspects of continuous-time investment. An additional distinguishing feature in the models considered is that we do not assume a priori that the objective functional (described by an improper integral) is finite, and so we are led to consider the weaker notions of overtaking and weakly overtaking optimality. To treat these models, we introduce a relaxed optimal control problem through the introduction of chattering controls. This leads us naturally to consider the relationship between the original problem and the convexified relaxed problem. In particular, we show that the relaxed problem may be viewed as a limiting case for the original problem. We also present several examples demonstrating the applicability of our results.     

The new mysterianism and the thesis of cognitive closure

The paper discusses Colin McGinn’s mysterianist approach to the phenomenon of consciousness. According to McGinn, consciousness is, in and of itself, a fully natural phenomenon, but we humans are just cognitively closed to it, meaning that we cannot in principle understand its nature. I argue that, on a proper conception of the relation between an intellectual problem and its solution, we may well not know what the solution is to a problem we understand, or we may not understand exactly what the problem is, but it is incoherent to suppose that we cannot understand what would count as a solution to a problem we can and do understand. The argument appeals to certain accepted assumption in the logic of questions, developed in the early sixties, mainly by Stahl. I close with a general characterization of mysterianism as such, and formulate a form of mysterianism which is in some sense more optimistic and in another more pessimistic than McGinn’s.     

Control of Cauchy system for an elliptic operator

The control of a Cauchy system for an elliptic operator seems to be globally an open problem. In this paper, we analyze this problem using a regularization method which consists in viewing a singular problem as a limit of a family of well-posed problems. Following this analysis and assuming that the interior of considered convex is non-empty, we obtain a singular optimality system （S.O.S.） for the considered control problem.     

Numerical analysis of an inverse problem for the eikonal equation

We are concerned with the inverse problem for an eikonal equation of determining the speed function using observations of the arrival time on a fixed surface. This is formulated as an optimisation problem for a quadratic functional with the state equation being the eikonal equation coupled to the so-called Soner boundary condition. The state equation is discretised by a suitable finite difference scheme for which we obtain existence, uniqueness and an error bound. We set up an approximate optimisation problem and show that a subsequence of the discrete mimina converges to a solution of the continuous optimisation problem as the mesh size goes to zero. The derivative of the discrete functional is calculated with the help of an adjoint equation which can be solved efficiently by using fast marching techniques. Finally we describe some numerical results.     

Solving Inverse Problems for Hyperbolic Equations via the Regularization Method

In the paper, we first deduce an optimization problem from an inverse problem for a general operator equation and prove that the optimization problem possesses a unique, stable solution that converges to the solution of the original inverse problem, if it exists, as a regularization factor goes to zero. Secondly, we apply the above results to an inverse problem determining the spatially varying coefficients of a second order hyperbolic equation and obtain a necessary condition, which can be used to get an approximate solution to the inverse problem.     

Job selection and sequencing on a single machine in a random environment

We examine a single machine scheduling problem with random processing times and deadline. Given a set of independent jobs having specified initiation costs and terminal revenues, the objective is to select a subset of the jobs and sequence the selected jobs such that the expected profit is maximized. The job selection aspect considered by us marks a clear departure from the pure sequencing focus found in the traditional scheduling literature. In this paper, we assume an exponentially distributed deadline and do not allow preemption. Even under these conditions, the selection and sequencing problem remains quite difficult (unlike its pure sequencing counterpart); we in fact conjecture that the problem is NP-hard. However, we show that the problem can be efficiently solved as long as the cost parameter is agreeable or an approximate solution is acceptable. To this end, we describe several solution properties, present dynamic programming algorithms (one of which exhibits a pseudo-polynomial time worst-case complexity), and propose a fully-polynomial time approximation scheme. In addition, we study a number of special cases which can be solved in polynomial time. Finally, we summarize our work and discuss an extension where the jobs are precedence related.     

Dual decomposition of a single-machine scheduling problem

We design a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0–1 linear program. Also, we show that upon termination of such an ascent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in our application the ascent direction leads to good Lagrangian lower and upper bounds.