Questions tagged [convex-optimization]
Convex minimization, a subfield of optimization, studies the problem of minimizing convex functions over convex sets. The convexity property can make optimization in some sense "easier" than the general case - for example, any local minimum must be a global minimum.
26
questions
2
votes
1answer
45 views
Quasi-convex function must be “partially monotonic”?
$f(x)$ is quasi-convex,
$$x^*\in\arg\min_{x\in C}f(x).$$
How to prove that, for any $a\in C$, $f(x) $ is weakly monotonic in the direction of $(x^*-a)$?
Is this simple result a part of an ancient ...
3
votes
0answers
27 views
Linear functions in Lenstra's algorithm
I had asked this question at MathOverflow and was pointed here.
I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
5
votes
1answer
110 views
Convexity of the variance of a mixture distribution
$X$ is a random variable that is sampled from the mixture of uniform distributions. In other words:
$$X \sim \sum_{i=1}^N w_i \cdot \mathbb{U}(x_i, x_{i+1}),$$
where $\mathbb{U}(x_i, x_{i+1})$ denotes ...
7
votes
2answers
611 views
Difference between exploration and exploitation in Simulated Annealing algorithm
In evolutionary algorithms, two main abilities maintained which are Exploration and Exploitation.
In Exploration the algorithm searching for new solutions in new regions, while Exploitation means ...
3
votes
2answers
97 views
Can we use reinforcement learning and convex optimization to solve an optimization problem?
For an optimization problem, there are multiple-type variables should be optimized. Can we use the convex optimization method to solve a subproblem of partial variables, and then, with the obtained ...
2
votes
1answer
53 views
Relationship between extreme points and optimal solutions of SDPs
Consider this to be our SDP problem:
Minimize $\langle C, X \rangle$ such that
$\langle A_i, X \rangle \ge b_i$ for all $i \in [m]$ and
$X \succcurlyeq 0$.
For SDPs, is there a relationship between ...
4
votes
1answer
65 views
Conditions required for strong duality to hold for SDPs
According to Wikipedia, strong duality holds when "the primal optimal objective and the dual optimal objective are equal."
What are the necessary conditions for strong duality to hold in ...
2
votes
0answers
62 views
Can every convex problem use Lagrangian dual method?
If not all constraints satisfy equalities, does Lagrangian dual method make sense to a convex problem?
2
votes
1answer
91 views
Is a convex or MILP (without big-M) formulation possible for this problem
Assume we are given a directed acyclic graph (DAG) $G(V, A)$, where $|V| = n, |A| = m$, and the graph contains a source node $\mathbf{s}$ (i.e. every node in $V \backslash \mathbf{s}$ is connected by ...
1
vote
0answers
75 views
Question on quadratically constrained quadratic program
If the constrained optimization problem is a quadratically constrained quadratic program of the form \begin{align}\min&\quad x^HQx-a(x+x^H)+b|z^Hx|^2\\\text{s.t.}&\quad\|x\|^2\le1\end{align} ...
3
votes
2answers
112 views
DCP representation of a convex quotient of affine functions
I am trying to represent the following inequality:
$$\frac{x}{1-x} \leq y \qquad\mathrm{with}\qquad 0<x<1$$
The function on the left is convex (its second derivative is always positive over ...
6
votes
2answers
136 views
Find a point inside non-empty difference of ellipsoids
Given two ellipsoids \begin{align}\mathcal{E}_1 &= \{ X \mid X^\top A_1 X + 2B_1^\top X + C_1 \leq 0\}\\\mathcal{E}_2 &= \{ X \mid X^\top A_2 X + 2 B_2^\top X + C_2 \leq 0\}\end{align} are ...
4
votes
1answer
57 views
How to check for convexity of the inequality constraint $āx^2+yā1\ge0$ for a minimization objective function?
I checked the Hessian which is $\begin{bmatrix}-2&0\\0&0\end{bmatrix}$ which is negative semidefinite but according to the sketch of the function it is convex. What am I missing?
3
votes
1answer
136 views
Approximation methods for a mixed integer convex optimization problem
I have a convex objective function, e.g., minimizing the negative entropy function. My constraints are also linear. The only issue is that I also have binary variables.
I am currently aware of AIMMS'...
5
votes
1answer
104 views
Which solver solves PSD constrained convex non-linear problem
I have a problem with a vector variable $w \in \mathbb{R}^n$ and a symmetric matrix variable $V \in \mathbb{R^{n \times n}}$. I am solving a problem which is roughly like:
\begin{align}
\begin{array}{...
4
votes
1answer
80 views
Minimize a convex function over a sphere
Problem description
Let $\mathcal{C} = \{X \in \mathbb{R}^n \mid g(X) \leq 0\}$ with $g(X)$ a convex function. Suppose I need to solve the feasibility problem, for a given $r>0$
$$ \exists ^?X \...
3
votes
0answers
58 views
Strong Duality and Slater Condition
I am studying the Duality Chapter of Convex Optimization by Boyd. Is it possible that strong duality holds for non-convex optimization? If yes, is there any specific condition? And, what is the ...
6
votes
2answers
134 views
Existence of Optimal Solution
Assume we are solving $\min\{f(x) \ | \ x \in S \}$.
If $f: \mathbb{R}^n \mapsto \mathbb{R}$ is a proper closed convex function, and $S$ is a non-empty closed convex set, does this imply that the ...
4
votes
1answer
148 views
Cutting-planes application procedure for a specific problem
Sort of following up with this question. I reformulated another model to make it convex and possibly solve it with some cut generation method. I would like to double-check whether I am doing it ...
7
votes
1answer
79 views
Ridge Regression lagrange duality
In every machine learning book we see that it is roughly mentioned that the ridge regression:
$$p_1^* = \min\limits_{\beta} \ \left( \mathrm{RSS} + \lambda\sum_{j=1}^p \beta_j^2 \right)$$
is ...
6
votes
0answers
50 views
Semi-definite Programming, non standard notation
The usual way to define a semi-definite program (SDP), e.g., as given in Boyd and Vandenberghe's convex optimization book, is:
$$
\begin{array}{cl}
\min & c^\top x \\
\mathrm{s.t.} & 0 \succeq ...
5
votes
0answers
182 views
Convexity of the projection of a convex set
Question:
A set $S \subset \mathbb{R}^m \times \mathbb{R}^n$ is convex. Using the fact that affine maps preserves convexity prove that $S(y) = \{x \in \mathbb{R}^m\mid (x,y)\in S \}$ and $\hat{S} = ...
8
votes
2answers
133 views
Convex Optimization: Separation of Cones
I am trying to solve Exercise 2.39 at Boyd and Vandenberghe's Convex Optimization book. In one source, the answer is given as:
2.39 Separation of cones. Let $K$ and $\tilde K$ be two convex cones ...
8
votes
4answers
255 views
Disciplined convex programming representation of $x\sqrt{1-x}$
Anyone have an idea for a disciplined convex programming (DCP) representation of the concave function $x\sqrt{1-x}$, which is defined over the domain $[0,1]$?
The Taylor series about $x=0$ is $$x - \...
8
votes
1answer
232 views
Convexity/Concavity of Average Number of Jobs in M/M/1 Queue?
I am working on a problem involving the average number of jobs $L$ in an M/M/1 queue with arrival rate $\lambda$, service rate $\mu$. For traffic intensity $\rho = \frac{\lambda}{\mu}$,
$$
L = \frac{\...
12
votes
2answers
278 views
Convex Maximization with Linear Constraints
I am doing active research in convex maximization w.r.t. linear constraints. There are many cases which can be efficiently approximately solved, e.g., convex quadratic maximization, log-sum-exp ...
