14
votes
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.
- 40.1k
13
votes
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,216
12
votes
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\}&...
- 922
12
votes
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,198
12
votes
Accepted
Solver for convex optimization with exponent in the objective function
You are missing some details for the claimed convexity of $f(x)$. I will assume that you meant to say convex on the domain $C+mx+\frac{s}{x+t} \geq 0$ and $x+t \geq 0$. In this case the epigraph of $f(...
- 1,897
11
votes
Accepted
Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only
Rather than solving this directly as MIQCQP, you might consider linearizing the products $y_{ij} x_{ij}$, as shown here, yielding instead an MILP problem.
- 33.6k
11
votes
Accepted
Express equality constraint involving exponentials cones
Q: "How do i write $\text{exp}(a) = b$ using cone programming?"
A You don't.
$\text{exp}(a) = b$ is a nonlinear equality constraint, and is therefore non-convex.
$\text{exp}(a) \le b$ is ...
- 13.8k
10
votes
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,481
10
votes
Accepted
How to solve this linear program with an exponential number of constraints?
For each $k\in\{1,\dots,n\}$, you want the sum of the $k$ smallest $f_i(x)$ to be at least $\sum_{j=1}^k b_j$. Equivalently, you want the sum of the $n-k$ largest $f_i(x)$ to be at most $\sum_{i=1}^n ...
- 33.6k
9
votes
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.8k
9
votes
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.7k
9
votes
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,865
9
votes
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,049
9
votes
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.8k
9
votes
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. ...
- 40.1k
8
votes
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.8k
8
votes
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
8
votes
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 ...
- 33.6k
8
votes
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.8k
8
votes
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{...
- 33.6k
8
votes
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).
7
votes
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,682
7
votes
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.2k
7
votes
Disciplined convex programming representation of $x\sqrt{1-x}$
I think in convex functions and epigraphs, so I hope you don't mind me deriving a DCP representation of the inequality
$$t \geq -x \sqrt{1-x},$$
on $x \in (-∞, 1]$, which I rewrite to
$$t \geq (1-x) \...
- 1,897
7
votes
Accepted
How can I linearise this nonlinear proportional relation constraint?
Based on the comments (thanks @RobPratt), C4 looks like
$$\frac{\sum_{u=1}^U d_{u,1}L_{u}}{\sum_{u=1}^U d_{u,2}L_{u}} = \frac{\psi_1}{\psi_2}$$
with similar constraints for other ratios.
Just multiply ...
- 13.8k
7
votes
How can I express this max-min in CPLEX?
Maximize an auxiliary variable $z$ subject to the constraints $z\le \sum_{c=1}^C d_{u,c}x_{u,c}\ \forall u$.
- 40.1k
7
votes
Accepted
Is $\min \ x^3 \ \mathrm{s.t.}\ x \geq 0$ a convex problem?
An objective function which is convex on only part of its unconstrained domain, but which is convex on the constraint set (i.e.., for any feasible point), can be 'convexified" by modifying the ...
- 13.8k
7
votes
Are there any parallel methods for solving multiple general nonlinear convex optimization problems?
Almost all convex optimization problems can be formulated as a conic optimization problem using only the cone types we can handle in practice. See the Mosek modeling cookbook for details. This often ...
- 3,216
7
votes
Adding CVXPY abs to optimization problem turns out to be non-DCP
I think you want cp.norm1(beta - s), with no need for abs. This is DCP-compliant.
Taking separate norms of ...
- 13.8k
7
votes
How to find the index of the item, the first time appears?
Suppose the index is 1-based and set constant $u_0 = 0$. With binary variables $u_i, y_i, i=1,\dots,n$ and constraints
$$
\begin{align}
u_i &\geq x_i\\
u_i &\geq u_{i-1}\\
u_i &\leq x_i + ...
- 1,206
Only top scored, non community-wiki answers of a minimum length are eligible