Problems with resource allocation constraints and optimization over the efficient set

The paper studies a nonlinear optimization problem under resource allocation constraints. Using quasi-gradient duality it is shown that the feasible set of the problem is a singleton (in the case of a single resource) or the set of Pareto efficient solutions of an associated vector maximization problem (in the case of $k>1$ resources). As a result, a nonlinear optimization problem under resource allocation constraints reduces to an optimization over the efficient set. The latter problem can further be converted into a quasiconvex maximization over a compact convex subset of $\mathbb{R }^k_+.$ Alternatively, it can be approached as a bilevel program and converted into a monotonic optimization problem in $\mathbb{R }^k_+.$ In either approach the converted problem falls into a common class of global optimization problems for which several practical solution methods exist when the number $k$ of resources is relatively small, as it often occurs.     

Optimality conditions for weak {\psi} -sharp minima in vector optimization problems

In this paper, we develop the characterization of weak ${\psi}$ -sharp minimizer by means of an oriented distance function and investigate the weak ${\psi}$ -sharp minimizer of the composition of two functions. Moreover, we establish sufficient conditions of the weak ${\psi_1}$ -sharp and ${\psi_2}$ -sharp Pareto minimality for vector optimization problem with strictly differentiable and twice strictly differentiable objective function, respectively. Our results extend the corresponding ones in the literature.     

Unified optimization of \hbox {H}_{\infty } index and upper stability bound for singularly perturbed systems

In this paper, unified optimization problem for the upper stability bound \(\varepsilon ^{*}\) and the \(\hbox {H}_{\infty }\) performance index \(\gamma \) based on state feedback is considered for singularly perturbed systems. First, a sufficient condition for the existence of state feedback controller is presented in terms of linear matrix inequalities such that the resulting closed-loop system is asymptotically stable if \(0<\varepsilon <\varepsilon ^{*}\) and also guarantees \(\hbox {H}_{\infty }\) performance index. Furthermore, a new algorithm to optimize these two indices simultaneously is proposed based on Nash game theory which transfers multi-objective problem into a single objective problem as well we determines the objective weights. Then an optimal state feedback controller can be derived. Finally, some numerical examples are provided to demonstrate the effectiveness and correctness of the proposed results.     

Approximation algorithms for k-partitioning problems with partition matroid constraint

The $k$ -partitioning problem with partition matroid constraint is to partition the union of $k$ given sets of size $m$ into $m$ sets such that each set contains exactly one element from each given set. With the objective of minimizing the maximum load, we present an efficient polynomial time approximation scheme (EPTAS) for the case where $k$ is a constant and a full polynomial time approximation scheme (FPTAS) for the case where $m$ is a constant; with the objective of maximizing the minimum load, we present a $\frac{1}{k-1}$ -approximation algorithm for the general case, an EPTAS for the case where $k$ is a constant; with the objective of minimizing the $l_p$ -norm of the load vector, we prove that the layered LPT algorithm (Wu and Yao in Theor Comput Sci 374:41–48, 2007) is an all-norm 2-approximation algorithm.     

Multiple criteria problems over Minkowski balls

Under study are some vector optimization problems over the space of Minkowski balls, i.e., symmetric convex compact subsets in Euclidean space. A typical problem requires to achieve the best result in the presence of conflicting goals; e.g., given the surface area of a symmetric convex body $\mathfrak{x}$ , we try to maximize the volume of $\mathfrak{x}$ and minimize the width of $\mathfrak{x}$ simultaneously.     

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider $N$ -fold $4$ -block decomposable integer programs, which simultaneously generalize $N$ -fold integer programs and two-stage stochastic integer programs with $N$ scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable  $N$ , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843–862,1990), which allows us to use convex continuous optimization as a subroutine.     

The bienergy of unit vector fields

The bienergy of a unit vector field on a Riemannian manifold \((M, g)\) is defined to be the bienergy of the corresponding map \((M, g)\mapsto (T_{1}M, g_{\mathrm{S}})\) , where the unit tangent sphere bundle \(T_{1}M\) is equipped with the restriction of the Sasaki metric \(g_{\mathrm{S}}\) . The constrained variational problem is studied, where variations are confined to unit vector fields, and the corresponding critical point condition characterizes biharmonic unit vector fields. Finally, we completely determine invariant biharmonic unit vector fields in three-dimensional unimodular Lie groups and the generalized Heisenberg groups \(H(1, r), r\ge 2\) .     

On the complexity of finding first-order critical points in constrained nonlinear optimization

The complexity of finding $\epsilon $ -approximate first-order critical points for the general smooth constrained optimization problem is shown to be no worse that $O(\epsilon ^{-2})$ in terms of function and constraints evaluations. This result is obtained by analyzing the worst-case behaviour of a first-order short-step homotopy algorithm consisting of a feasibility phase followed by an optimization phase, and requires minimal assumptions on the objective function. Since a bound of the same order is known to be valid for the unconstrained case, this leads to the conclusion that the presence of possibly nonlinear/nonconvex inequality/equality constraints is irrelevant for this bound to apply.     

Semidefinite relaxations of ordering problems

Ordering problems assign weights to each ordering and ask to find an ordering of maximum weight. We consider problems where the cost function is either linear or quadratic. In the first case, there is a given profit if the element $u$ is before $v$ in the ordering. In the second case, the profit depends on whether $u$ is before $v$ and $r$ is before $s$ . The linear ordering problem is well studied, with exact solution methods based on polyhedral relaxations. The quadratic ordering problem does not seem to have attracted similar attention. We present a systematic investigation of semidefinite optimization based relaxations for the quadratic ordering problem, extending and improving existing approaches. We show the efficiency of our relaxations by providing computational experience on a variety of problem classes.     

The Number of Singular Vector Tuples and Uniqueness of Best Rank-One Approximation of Tensors

In this paper we discuss the notion of singular vector tuples of a complex-valued \(d\) -mode tensor of dimension \(m_1\times \cdots \times m_d\) . We show that a generic tensor has a finite number of singular vector tuples, viewed as points in the corresponding Segre product. We give the formula for the number of singular vector tuples. We show similar results for tensors with partial symmetry. We give analogous results for the homogeneous pencil eigenvalue problem for cubic tensors, i.e., \(m_1=\cdots =m_d\) . We show the uniqueness of best approximations for almost all real tensors in the following cases: rank-one approximation; rank-one approximation for partially symmetric tensors (this approximation is also partially symmetric); rank- \((r_1,\ldots ,r_d)\) approximation for \(d\) -mode tensors.     

On {\epsilon} -solutions for convex optimization problems with uncertainty data

We consider ${\epsilon}$ -solutions (approximate solutions) for a robust convex optimization problem in the face of data uncertainty. Using robust optimization approach (worst-case approach), we establish an optimality theorem and duality theorems for ${\epsilon}$ -solutions for the robust convex optimization problem. Moreover, we give an example illustrating the duality theorems.     

CVaR norm and applications in optimization

This paper introduces the family of CVaR norms in \({\mathbb {R}}^{n}\) , based on the CVaR concept. The CVaR norm is defined in two variations: scaled and non-scaled. The well-known \(L_{1}\) and \(L_{\infty }\) norms are limiting cases of the new family of norms. The D-norm, used in robust optimization, is equivalent to the non-scaled CVaR norm. We present two relatively simple definitions of the CVaR norm: (i) as the average or the sum of some percentage of largest absolute values of components of vector; (ii) as an optimal solution of a CVaR minimization problem suggested by Rockafellar and Uryasev. CVaR norms are piece-wise linear functions on \({\mathbb {R}}^{n}\) and can be used in various applications where the Euclidean norm is typically used. To illustrate, in the computational experiments we consider the problem of projecting a point onto a polyhedral set. The CVaR norm allows formulating this problem as a convex or linear program for any level of conservativeness.     

Algorithm for quadratic semi-assignment problem with partition size coefficients

This paper discusses the problem of assigning $N$ streams of requests (clients) to $M$ related server machines with the objective to minimize the sum of worst-case processing times. The completion time of a batch of requests is measured as a sum of weights of the subset of clients which share a single machine. Such problem can be seen as minimizing the sum of total weights of blocks of $M$ -partition, each multiplied by the cardinality of a block. We prove that this problem can be solved in polynomial time for any fixed $M$ and present an efficient backward induction algorithm.     

Inverse problem of finding n coefficients of lower derivatives in a parabolic equation

We consider the problem of reconstructing the vector function $\vec b(x) = (b_1 ,...,b_n )$ in the term $(\vec b,\nabla u)$ in a linear parabolic equation. This coefficient inverse problem is considered in a bounded domain Ω ? R ⁿ . To find the above-mentioned function $\vec b(x)$ , in addition to initial and boundary conditions we pose an integral observation of the form $\int_0^T {u(x,t)\vec \omega (t)dt = \vec \chi (x)} $ , where $\vec \omega (t) = (\omega _1 (t),...,\omega _n (t))$ is a given weight vector function. We derive sufficient existence and uniqueness conditions for the generalized solution of the inverse problem. We present an example of input data for which the assumptions of the theorems proved in the paper are necessarily satisfied.     

Some Inverse Problems for d-Orthogonal Polynomials

This paper is devoted to the study of the generalized inverse problem of the left product of a d–dimensional vector form by a polynomial. The objective is to find the regularity conditions of the vector linear form ${\mathcal{V}}$ defined by ${\mathcal{U} = \mathcal{RV}}$ , where ${\mathcal{R}}$ is a d × d matrix polynomial. In such a case, the d–OPS {Q _n } _{n ≥ 0} corresponding to ${\mathcal{V}}$ is d–quasi– orthogonal of order l with respect to ${\mathcal{U}}$ . Secondly, we study the inverse problem: Given a d -OPS P _{n n ≥ 0} with respect to ${\mathcal{U}}$ , characterize the parameters ${\{a^{(i)}_{n}\}{^{dl}_{i=1}}}$ such that the sequence $${Q_{n+dl} = P_{n+dl} + \sum _{i=1}^{dl} a_{n+dl}^{(i)}P_{n+dl-i},\quad n\geq 0}$$ , is d–orthogonal with respect to some regular vector linear form ${\mathcal{V}}$ . As an immediate consequence, find the explicit relation between ${\mathcal{U}}$ and ${\mathcal{V}}$ .     

Hadamard well-posedness for a set-valued optimization problem

In this paper, we introduce a kind of Hadamard well-posedness for a set-valued optimization problem. By virtue of a scalarization function, we obtain some relationships between weak ${(\varepsilon, e)}$ -minimizers of the set-valued optimization problem and ${\varepsilon}$ -approximate solutions of a scalar optimization problem. Then, we establish a scalarization theorem of P.K. convergence for sequences of set-valued mappings. Based on these results, we also derive a sufficient condition of Hadamard well-posedness for the set-valued optimization problem.     

Complexity of unconstrained L_2-L_p minimization

We consider the unconstrained $L_q$ - $L_p$ minimization: find a minimizer of $\Vert Ax-b\Vert ^q_q+\lambda \Vert x\Vert ^p_p$ for given $A \in R^{m\times n}$ , $b\in R^m$ and parameters $\lambda >0$ , $p\in [0, 1)$ and $q\ge 1$ . This problem has been studied extensively in many areas. Especially, for the case when $q=2$ , this problem is known as the $L_2-L_p$ minimization problem and has found its applications in variable selection problems and sparse least squares fitting for high dimensional data. Theoretical results show that the minimizers of the $L_q$ - $L_p$ problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function $\Vert \cdot \Vert ^p_p$ . In this paper, we show that the $L_q$ - $L_p$ minimization problem is strongly NP-hard for any $p\in [0,1)$ and $q\ge 1$ , including its smoothed version. On the other hand, we show that, by choosing parameters $(p,\lambda )$ carefully, a minimizer, global or local, will have certain desired sparsity. We believe that these results provide new theoretical insights to the studies and applications of the concave regularized optimization problems.     

Analysis of a continuous finite element method for H(\mathrm{curl},\mathrm{div})-elliptic interface problem

In this paper, we develop a continuous finite element method for the curlcurl-grad div vector second-order elliptic problem in a three-dimensional polyhedral domain occupied by discontinuous nonhomogeneous anisotropic materials. In spite of the fact that the curlcurl-grad div interface problem is closely related to the elliptic interface problem of vector Laplace operator type, the continuous finite element discretization of the standard variational problem of the former generally fails to give a correct solution even in the case of homogeneous media whenever the physical domain has reentrant corners and edges. To discretize the curlcurl-grad div interface problem by the continuous finite element method, we apply an element-local $L^2$ projector to the curl operator and a pseudo-local $L^2$ projector to the div operator, where the continuous Lagrange linear element enriched by suitable element and face bubbles may be employed. It is shown that the finite element problem retains the same coercivity property as the continuous problem. An error estimate $\mathcal{O }(h^r)$ in an energy norm is obtained between the analytical solution and the continuous finite element solution, where the analytical solution is in $\prod _{l=1}^L (H^r(\Omega _l))^3$ for some $r\in (1/2,1]$ due to the domain boundary reentrant corners and edges (e.g., nonconvex polyhedron) and due to the interfaces between the different material domains in $\Omega =\bigcup _{l=1}^L \Omega _l$ .     

A unified approach for minimizing composite norms

We propose a first-order augmented Lagrangian algorithm (FALC) to solve the composite norm minimization problem $$\begin{aligned} \begin{array}{ll} \min \limits _{X\in \mathbb{R }^{m\times n}}&\mu _1\Vert \sigma (\mathcal{F }(X)-G)\Vert _\alpha +\mu _2\Vert \mathcal{C }(X)-d\Vert _\beta ,\\ \text{ subject} \text{ to}&\mathcal{A }(X)-b\in \mathcal{Q }, \end{array} \end{aligned}$$ where $\sigma (X)$ denotes the vector of singular values of $X \in \mathbb{R }^{m\times n}$ , the matrix norm $\Vert \sigma (X)\Vert _{\alpha }$ denotes either the Frobenius, the nuclear, or the $\ell _2$ -operator norm of $X$ , the vector norm $\Vert .\Vert _{\beta }$ denotes either the $\ell _1$ -norm, $\ell _2$ -norm or the $\ell _{\infty }$ -norm; $\mathcal{Q }$ is a closed convex set and $\mathcal{A }(.)$ , $\mathcal{C }(.)$ , $\mathcal{F }(.)$ are linear operators from $\mathbb{R }^{m\times n}$ to vector spaces of appropriate dimensions. Basis pursuit, matrix completion, robust principal component pursuit (PCP), and stable PCP problems are all special cases of the composite norm minimization problem. Thus, FALC is able to solve all these problems in a unified manner. We show that any limit point of FALC iterate sequence is an optimal solution of the composite norm minimization problem. We also show that for all $\epsilon >0$ , the FALC iterates are $\epsilon $ -feasible and $\epsilon $ -optimal after $\mathcal{O }(\log (\epsilon ^{-1}))$ iterations, which require $\mathcal{O }(\epsilon ^{-1})$ constrained shrinkage operations and Euclidean projection onto the set $\mathcal{Q }$ . Surprisingly, on the problem sets we tested, FALC required only $\mathcal{O }(\log (\epsilon ^{-1}))$ constrained shrinkage, instead of the $\mathcal{O }(\epsilon ^{-1})$ worst case bound, to compute an $\epsilon $ -feasible and $\epsilon $ -optimal solution. To best of our knowledge, FALC is the first algorithm with a known complexity bound that solves the stable PCP problem.