11
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\}&=\{(x,y): -(-x^2+y-1 ) \le 0\} \\
&=\{(x,y): x^2-y+1 \le 0\} \end{align}
If you compute the Hessian of $x^2-y+1$, you will obtain $\begin{bmatrix} 2 &...
11
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.
10
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-source solvers can't compete on performance and reliability with commercial solvers.
9
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 Hessian of $L$ with respect to $\lambda$ and $\mu$. I used MAPLE to compute the Hessian, and then evaluate its eigenvalues at the point $\lambda = 0.5, \mu = 1$. ...
9
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 the range $[a_{min},a_{max}]$. Note that if $a_{min} > |N_B|$ the problem is infeasible.
Likewise with a sink node, that you link to each vertex $v \in N_B$, ...
9
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} & \forall u=1,\dots,U
\end{align}
For future reference, if in contrast you had a minmax objective instead of a maxmin objective, you could apply the same trick:
\begin{...
8
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 at the simple case of $a = b = c = 1$. The Hessian of $\frac{{ax}}{{\ln (b + cy)}}$ at $x = y = 1$ has one positive and one negative eigenvalue. Hence $\frac{{ax}...
8
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 meanings of "real" here). We can form $$M' = \frac{M+M^T}{2}$$ Now $M'$ is symmetric and we have $$x^TM'x = x^TMx$$ for any $x$. So you can make $M$ ...
7
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 algorithm usually takes relatively big steps in the solution space. Later the likelihood decreases and by doing so the algorithm stays within a certain region of ...
7
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.
7
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) \sqrt{1-x} - \sqrt{1-x} = r^{3/2} - r^{1/2},\quad r = 1-x \geq 0.$$
It should now be easy to input into your DCP framework. In MOSEK, it could be represented ...
6
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 code
import cvxpy as cp
x = cp.Variable()
y = cp.exp(cp.log(x) + 0.5 * cp.log(1 - x))
print("x * sqrt(1 - x) curvature:", y.curvature)
gives QUASICONCAVE as ...
6
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'
However, you can represent it using DQCP (disciplined quasiconvex programming):
import cvxpy as cp
x=cp.Variable(pos=True)
a=x*cp.sqrt(1-x)
a.curvature
'QUASICONCAVE'
6
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 exploit its native mixed-integer exponential cone capability.
Here is a mixed-integer example (mixture of binary and continuous):
x = binvar(3,1); % binary
y =...
6
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 solution, while Intensification relates to the smaller values.
Since the probability is dependent to the difference between the objective of the current and ...
6
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 minimum at an extreme of the constraints.
You're maximizing a convex objective, which is equivalent to minimizing the negative of the objective, which is concave. ...
6
Neither. You should delete $d_{u,c}$ from the model whenever $\omega_{u,c} < t_\min$.
6
Maximize an auxiliary variable $z$ subject to the constraints $z\le \sum_{c=1}^C d_{u,c}x_{u,c}\ \forall u$.
6
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}})$.
6
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 comes to mind along the lines of what you propose is to create a feasibility pump objective:
$\min \bar f(x)+\Delta(x,\tilde x)$ s.t. your relaxed constraints, ...
6
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 bindings for most of these locally. If you are just looking for high-level modeling language and are not tied to Python you could use the JuMP modeling language ...
5
Here is an alternative answer.
Clearly, the problem is equivalent to
$$
\begin{array}{rcl}
\frac{1-t}{t} & \leq & y \\
1-x & = & t \\
\end{array}
$$
which in turn is equivalent to
$$
\begin{array}{rcl}
\frac{1}{t} -1 & \leq & y \\
1-x & = & t \\
\end{array}
$$
This is clearly SOCP representable.
...
5
You can model your constraint with the second order cone constraint $$\sqrt{2^2 + (x+y)^2} \le 2-x+y,$$ and a lower bound on $x$.
I found this by first multiplying both sides by $1-x$ to obtain $(1-x)y - x >= 0$. As we have a quadratic inequality with a convex feasible region, this hints to a quadratic or second order cone.
Rewriting this constraint ...
5
Define quadratic functions $g_1(X)$ and $g_2(X)$ such that \begin{align}\mathcal{E}_1 &= \{ X \mid g_1(X) \le 0\}\\\mathcal{E}_2 &= \{ X \mid g_2(X) \le 0\}\end{align}
It follows from the definition that you can find a point in $\mathcal{E}_1 \setminus \mathcal{E}_2$ by solving
$$\begin{align} \min &\quad -g_2(X)\\\text{s.t.} &\quad g_1(X) \...
5
In order to find the best upper bound for variance, for given input values of $u_i$ and $\sigma_i^2$, you should globally maximize variance with respect to the $w_i$, subject to the constraints $w_i \ge 0, \Sigma w_i = 1$.
This can be formulated as a convex QP (Quadratic Programming problem), i.e., maximizing a concave quadratic subject to linear constraints....
5
EDIT: Per comment below by YALMIP deveeloper Johan Lofberg, the bug in YALMIP was a typo, which has now been corrected and available at https://github.com/yalmip/YALMIP/archive/develop.zip . Using this newest develop version of YALMIP, Mosek should now be able to solve the problem.
Edited to reflect YALMIP developer's acknowledgement that there is a bug in ...
5
No, an optimal solution need not exist. Take $f: \mathbb{R} \to \mathbb{R}$ with $f(x) = e^{x}$.
However if you restrict $S$ to be compact instead of just closed, then you are guaranteed a solution. In fact, convexity is not required. For a simple proof, let $f(x_n) \to \inf_{x \in S} f(x)$. $x_n \in S$ has a convergent subsequence by compactness, and let $...
5
Use CVX's entr function.
$\sum_{i=1}^ 4x_i\ln(x_i)$ can be entered as -sum(entr(x))
entr Scalar entropy.
entr(X) returns an array of the same size as X with the unnormalized
entropy function applied to each element:
{ -X.*LOG(X) if X > 0,
entr(X) = { 0 if X == 0,
{ -Inf otherwise.
If X ...
5
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 both sides by the denominator, which males it a linear constraint.
$$\sum_{u=1}^U d_{u,1}L_{u} = \frac{\psi_1}{\psi_2}\sum_{u=1}^U d_{u,2}L_{u}$$
Similarly ...
5
With the natural binary decision variables $x_{s,u}$, $y_{u,g}$, and $z_{s,g}$ you had defined earlier, the problem is to maximize $\sum_u q_u$ subject to
\begin{align}
q_u &= \frac{\sum_s h_{s,u} x_{s,u}}{\sum_s h_{s,u} (1-x_{s,u})} &&\text{for all $u$} \tag1 \\
\sum_g y_{u,g} &= 1 &&\text{for all $u$} \tag2 \\
\sum_g z_{s,g} &= ...
Only top voted, non community-wiki answers of a minimum length are eligible