# Tag Info

### Do convex quadratic problems always have sparse solutions?

Consider the convex QP $$\min \lbrace \sum_{i=1}^n x_i^2 : x\in \mathbb{R}^n, \sum_{i=1}^n x_i = 1\rbrace.$$ The solution is $$x = (\frac{1}{n},\dots,\frac{1}{n}),$$which is fully dense.
• 39.5k
Accepted

### Why does some solvers can only solve conic optimization problems?

The fundamental algorithm employed by Mosek and SeDuMi is a primal-dual interior-point algorithm based on the work of Nesterov and Todd (NT). See for instance my paper and the references therein. This ...
• 3,206
Accepted

### How to check for convexity of the inequality constraint $−x^2+y−1\ge0$ for a minimization objective function?

I think you are trying to use the following property: $\{x:g(x) \le 0\}$ is convex if $g$ is convex. Note the direction of the inequality. Notice that \begin{align}\{(x,y): -x^2+y-1 \ge 0\}&...

### What is the best open source solver for large scale LP optimization in pyomo?

There is a new open source solver that looks quite promising, HiGHS: https://www.maths.ed.ac.uk/hall/HiGHS/ But as pointed out by others, for mixed-integer programming problems, at the moment, open-...
• 3,188
Accepted

• 32.7k
Accepted

### Convexity/Concavity of Average Number of Jobs in M/M/1 Queue?

Your calculations (factoring and simplification) are incorrect. $L$ is neither convex nor concave as a function of $\lambda$ and $\mu$. This can be concluded by examining the eigenvalues of the ...
• 13.5k

### How to solve this convex problem heuristically?

This is a minimum cost flow problem in the bipartite graph $G=(V,A)$ with $V=N_U \cup N_B$. Add a source node and link it to each vertex $v\in N_U$. On each of these arcs, constrain the flow to be in ...
• 13.5k

### How can I express this max-min in CPLEX?

You can model this as a maxmin problem by introducing an auxiliary variable $\theta$: \begin{align} \max&\quad\theta &\\ \text{s.t.}&\quad\theta \leq \sum_{c=1}^C x_{uc}d_{uc} & \...
• 3,461
Accepted

### Non-symmetric Positive Definite/Semidefinite Matrix in Quadratic Program

Yes, a real PSD matrix $M$ is a symmetric matrix with $$x^TMx\ge 0$$ for any $x$ (see e.g. https://en.wikipedia.org/wiki/Definite_matrix). However, this is not a real restriction. (We have two ...
• 2,806
Accepted

### What is the best open source solver for large scale LP optimization in pyomo?

The Mittlemann benchmarks are an excellent benchmark as ever in particular these two: Benchmark of Barrier LP solvers Large Network-LP Benchmark (commercial vs free) Note that Pyomo doesn't have ...
• 4,037
Accepted

### Inverse of weighted sum of positive definite matrices

This is a convex optimization problem, which can easily be formed (and solved), in CVX, among other convex optimization tools. Let $A = x_1I_1 + x_2I_2 + ... + x_nI_n$, where the $I_i$ are m by m ...
• 13.5k
Accepted

### Determining the optimize lambda in Multi-Objective Optimization

There is no mathematical way to derive (or justify) a value for $\lambda$. The justification has to be made in the context of a specific problem and a specific (reasonably credible) decision maker. ...
• 39.5k

### How to make following constraint a convex one?

The constraint is not convex, and is not transformable to a convex constraint without substantively changing it. The additive linear term $dx$ is irrelevant to convexity. So let's ignore it and look ...
• 13.5k

### What does nonconvex multilinear mean?

Non-convex means not convex, which could mean concave but also neither convex nor concave, such as a bilinear term $xy$.
• 1,702

### Fast way to repeatedly solve many similar LPs/QPs in parallel

The OPTMODEL modeling language in SAS (disclaimer: I work at SAS) supports two features for solving independent optimization (LP or otherwise) problems concurrently: The COFOR loop, which ...
• 32.7k

### Maximize correlation subject to nonconvex correlation constraints

You could add the non-convex constraint $z^Tz = 1$. That would make the objective function and other constraints linear. So this would be a Linear Programming problem, but for a single non-convex ...
• 13.5k
Accepted

### How to find the index of the item, the first time appears?

Here's a formulation if at least one $x_i$ must be $1$: \begin{align} \sum_i y_i &= 1 \tag1\label1\\ y_i &\le x_i &&\text{for all $i$} \tag2\label2\\ y_i &\le 1-x_j &&\text{...
• 32.7k

### Determining the optimize lambda in Multi-Objective Optimization

Another approach could be generating the Pareto Frontier, solving the problem several times for different values of lambda, using a Weighted sum algorithm (see this or this).

### Difference between exploration and exploitation in Simulated Annealing algorithm

I personally see it as follows. In simulated annealing the likelihood of choosing a solution from the neighborhood is quite high at the beginning. This phase could be regarded as exploration as the ...
• 1,652

### Convex Maximization with Linear Constraints

The location-inventory problem by Shen, et al. and Daskin, et al. has a concave minimization objective. It's related to economies of scale (which you list in your PS 2) but not exactly the same.
• 13.1k