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.

Filter by
Sorted by
Tagged with
-3
votes
0answers
37 views

If-else statement in cvx

I have a problem with if-else statement in cvx which causes error. I raised this issue in cvx forum and was highly recommended to ask for assistance in this community. Could you please help to fix it ...
1
vote
1answer
67 views

How to prove this convex-optimization problem?

I am struggling with the following optimization problems. Problem 1 \begin{align}\max_{\alpha, s_1, s_2}&\quad s_1 + s_2 - \gamma (s_1 (K_1 +c_1 + s_1) + s_2 (K_2+ c_2 + s_2) + 2\alpha K) +C\\\...
4
votes
2answers
196 views

How to solve this convex problem heuristically?

I have the following problem $$\max_{X_{i,j},i\in N_{U},j\in N_{B}}\sum_{i=1}^{N_U}\sum_{j=1}^{N_B}R_{i,j}X_{i,j}$$ $$\text{subject to}$$ $$a_{\min}\le\sum_{j=1}^{N_B}X_{i,j}\le a_{\max}, \forall i$$ $...
5
votes
0answers
116 views

Is this a valid strong polynomial algorithm for deciding LP feasibility?

Let $$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
5
votes
0answers
68 views

Polyhedra to Simplex by using convex combination of vertices

Optimization problems over linear constraints (defining a convex polyhedron) can be written as optimization over a simplex in a higher dimension. Let $\mathcal{P}$ be a bounded polyhedron, and the ...
2
votes
0answers
32 views

Optimization of strongly convex functions with approximate evaluations of gradient and Hessian

Suppose I want to find the minimum of a differentiable, strongly convex function $f:\mathbb{R}^n\to\mathbb{R}$ with constant $\mu>0$. That is, for all $x,y\in\mathbb{R}^n$, I have that: $$f(y) \geq ...
2
votes
0answers
58 views

Optimizing with a logistic function

I have a system in which I want to maximize the value of some function $f(x_T, y_T)$. The time evolution of the system is described by some functions: $$ \begin{align} \frac{dx}{dt}&=\alpha \frac{...
4
votes
1answer
59 views

How to evaluate the convexity of an optimal control problem?

Can we consider an optimal control problem, a convex optimization problem like static optimization problems? If it is possible, under what conditions, will this problem be a convex problem? For ...
1
vote
0answers
50 views

How to solve this problem by Lagrange duality?

This is a convex problem and although it can be well solved by CVX, I want to know how it can be solved by the Lagrange duality method. The derivations with regard to $L_k$ and $B_k$ are constants, ...
3
votes
1answer
125 views

Can we get the closed-form solution for this problem?

Can we get the closed-form solution for this problem? \begin{align} \min&\quad\sum_{i=1}^N\frac{K_i}{x_i\log_2(1+\frac{Q_i}{x_i})}\\ {\rm{s.t.}}&\quad\sum_{i=1}^N x_i\le X \end{align} wherein $...
1
vote
0answers
44 views

$\nabla_y\nabla_vf(x^*)\geq0$ for any concave $f$ if and only if $y=-v$

$f:\mathbb R^3\to\mathbb R$ is an arbitrary concave function. $H$ is a plane. $v$ is a given vector on $H$. $x^*=\max_{x\in H} f(x)$ Prove that $\nabla_y\nabla_vf(x^*)\geq 0$ if and only if $y=-v$. I ...
3
votes
0answers
86 views

How can this convex optimization problem be proved?

Consider the following maximization problems: $\max_{x} x -\gamma p(x)$ subject to $x \in \Omega_1$ $\max_{x} x-\gamma (p(x) + q(x) )+K$ subject to $x \in \Omega_2$ where $\Omega_1 $ and $ \Omega_2$...
2
votes
1answer
56 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
29 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 ...
6
votes
1answer
120 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
685 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
120 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
73 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
79 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
63 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
100 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
77 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
120 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
138 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
155 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
112 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
95 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
69 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
145 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
150 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
84 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
350 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
144 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
281 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
235 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
405 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 ...