10
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 &...
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$, ...
8
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{...
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
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}})$.
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
Neither. You should delete $d_{u,c}$ from the model whenever $\omega_{u,c} < t_\min$.
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} &= ...
5
Yes, because $\log$ is monotonic, it preserves inequalities. The tightness depends on your other constraints.
4
Edit: I misinterpreted the question as asking about maximization problems which are convex optimization problems.
Here is a whole class of naturally occurring concave optimization problems, i.e., maximizing a convex function or minimizing a concave function, in both cases subject to convex constraints Linear constraints are of course a special case of ...
4
Does this appear in a context in your program such that it can be replaced with a strictly monotonically increasing function of itself? For example, if it is the only term in the objective function, or the only term on the LHS of a LHS >= constant constraint.
If so, this can be handled as a weighted-geometric mean, which actually represents $(x\sqrt{1-x})...
4
If $|P|$ is not too large, you could try an integer programming formulation. Fix an integer $N>1$ (which will control the granularity of the approximation) and let $\Delta=\frac{H^+ - H^-}{N}$. For each $p\in P$ and each $n\in \lbrace 0,\dots, N\rbrace$, introduce variable $t_{p,n}\in [0,1]$. Now add the constraints$$\sum_{n=0}^N t_{p,n} = 1\quad \forall ...
4
If I understood everything correctly this should be false. The following is a counter example.
Let $\epsilon >0$ be small. Choose $K_1=K_2=2$, $c_1 = c_2 = 3$, $K=\epsilon$, $B=\epsilon, A=2\epsilon$, $\beta = \epsilon$ and $C = 4\epsilon^2$.
First consider $\gamma=\gamma'=1$:
Then the first objective becomes:
$$
-(s_1^2+4s_1+s_2^2+4s_2+2\epsilon\alpha) + ...
4
As $x_i\in[0,1]$ we just need to compare the values of the endpoints since $(x_i-c_i)^2$ is minimised at $x_i=c_i$. It is easy to see that $x_i=0$ gives the maximum whenever $c_i\ge1/2$ and $x_i=1$ otherwise.
Thus we can treat $x_i$ as binary variables for the purpose of maximisation (see In an integer program, how I can force a binary variable to equal 1 if ...
Only top voted, non community-wiki answers of a minimum length are eligible
