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 ...
- 2,451
11
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\}&...
- 882
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.
- 22.2k
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 ...
- 10.8k
10
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-...
- 2,719
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 ...
- 10.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 ...
- 10.2k
9
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,056
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 ...
- 1,571
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 ...
- 10.8k
8
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 ...
- 10.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,672
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 ...
- 22.2k
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 ...
- 10.8k
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,546
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.
- 12.6k
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) \...
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 ...
- 2,451
6
votes
Disciplined convex programming representation of $x\sqrt{1-x}$
This is possible purely under DCP. As you are interested in the interval $[0,1]$, rewrite your function as $$x\sqrt{1-x}=\exp\left(\ln x+\frac12\ln(1-x)\right),\quad x\in[0,1].$$ Then the following ...
- 5,185
6
votes
Disciplined convex programming representation of $x\sqrt{1-x}$
I don't think you can represent this as a concave function in the (cvxpy-)DCP sense:
import cvxpy as cp
x=cp.Variable()
a=x*cp.sqrt(1-x)
a.curvature
'UNKNOWN'
...
- 543
6
votes
Accepted
Approximation methods for a mixed integer convex optimization problem
Mosek 9.x can natively solve mixed-integer exponential cone problems.
Formulate the problem in YALMIP, specifying the binary variables as binvar, and Mosek as the solver. YALMIP will call Mosek to ...
- 10.8k
6
votes
Difference between exploration and exploitation in Simulated Annealing algorithm
Those two are also called Diversification (Exploration) and Intensification (Exploitation).
In SA, Diversification relates to the larger values of the probability of accepting an inferior neighbor ...
- 2,044
6
votes
Find the farthest point in hypercube to an exterior point
This answers a comment by the OP, to explain why the other answers are correct. It is due to the following standard result.
A concave objective subject to compact convex constraints has a global ...
- 10.8k
6
votes
Should I process the data or add a new constraint to achieve the target?
Neither. You should delete $d_{u,c}$ from the model whenever $\omega_{u,c} < t_\min$.
- 29.7k
6
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 ...
- 10.8k
6
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$.
- 29.7k
6
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 ...
- 10.8k
6
votes
Accepted
How to convexify log(convex) function?
You are maximizing a convex quadratic (the monotonic log is irrelevant) so the maximum is attained at the border, i.e. either $0$ or $\min(1,\sqrt{1-\text{constant}})$.
- 1,672
6
votes
What is a good way to penalise LP relaxation?
You can't quite create a penalty function to enforce integrality and keep your problem linear, at best it would be quadratic (which could indeed be easier to solve sometimes).
The closest thing that ...
- 11.2k
6
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 ...
- 3,477
Only top scored, non community-wiki answers of a minimum length are eligible