Questions tagged [convex-optimization]
A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.
7,425
questions
0
votes
1
answer
35
views
Prove an inequality for strongly convex function
Let $g:\mathbb R^m\to\mathbb R$ be $\mu$-strongly convex. Let $A\in\mathbb R^{m\times n}$ have full row rank (so $m\le n$). We are interested in the function $f(x)=g(Ax)$, $x\in\mathbb R^n$.
Let $\...
- 658
5
votes
1
answer
84
views
Sublinear function $f$ with $f(x)+f(-x)=0$ for some $x \neq 0$ is linear.
A sublinear function $f$ has the following properties:
$f(x+y) \leq f(x) + f(y)\;\; \forall x,y \in \mathbb R^d$
for any $t > 0, x \in\mathbb R^d, f(tx) = tf(x)$
Now let $f(x_0) + f(-x_0) = 0$ at ...
- 465
0
votes
1
answer
22
views
We define the normal direction of Ω. Now if Ω is convex, why it is equivalent to the following set?
Let $\Omega \subset \mathbb R^n$ be closed and $x^* \in \Omega$. Define the normal directions of
$\Omega$ at $x^*$ is given by $N(x^*) = \{d\in \mathbb R^n|\limsup_{x\to^\Omega x^*} \frac{\langle d, ...
- 23
0
votes
0
answers
10
views
The gradients of a sub-level set of a convex function is the convex hull of the gradients of the associated level set.
This feels like it should be a known result, I am trying to generalize it (if true) to use in some convergence proof of a paper I am currently writing.
Let $f:\mathbb R^n\to\mathbb R^m$ be a ...
- 6,031
1
vote
1
answer
77
views
$f f'' \geq 2(f')^ 2 \implies f$ decreasing
I'm currently doing a project and trying to find the conditions a function needs to have for the problem to have nice properties.
The conditions so far are:
$f(x) > 0$, $\; \forall x \in \text{dom ...
- 147
0
votes
1
answer
68
views
Conditions for $f(x) f(1-x)$ to be concave
Let $f : [0,1] \to [0,1]$. Function $f$ is decreasing and satisfies $f(0) = 1$. Does anyone know any conditions on $f$ that ensure that the function
$$g(x) = f(x) f(1-x)$$
is concave on the interval $[...
- 763
4
votes
2
answers
111
views
Does convergence of gradient to zero imply convergence to optimal value?
Let $f:\mathbb{R}^n\to\mathbb{R}$ be a $C^1(\mathbb{R}^n)$ convex function that has a minimal value $f^\star = \inf_{\mathbb{R}^n} f$. Assume also that $\nabla f$ is $L$-Lipschitz continuous.
Let $(...
- 192
-1
votes
0
answers
16
views
How to solve this nonlinear binary programming problem? [closed]
I am tring to solve the problem of
$$ min\ ||Ax - b||^2_2 $$
$$ subject\ to\ x = \{0,1\}^n $$
The constraint will be satisfied if the factor of the penalty term starts from 0 and gradually turns to a ...
2
votes
0
answers
16
views
Minimize a quadratic form constrained to the vector being non-negative and sum up to one
I want to solve the following optimization problem with respect to $\mathsf{x} = (x_1, \ldots, x_n)^\top$
$$
\min_{\mathbf{x}} \,\, \mathbf{x}^\top A \mathbf{x} \qquad\qquad\text{such that }\,\, x_i \...
- 5,173
0
votes
0
answers
26
views
Does Cutting Plane method always converge in case of Integer Linear Programming?
I learned that the Cutting plane algorithm using Gromory's cut helps in finally reaching an optimum solution in integer linear programming.
But I also observed that in the simplex tableau, if the ...
- 156
3
votes
2
answers
116
views
Why having a global convex upper bound is considered as an advantage for the convex-concave procedure?
I am reading this paper "Variations and extension of the convex–concave procedure" and on page 5/25, second paragraph, the authors state that "Another advantage of CCP is that the over ...
0
votes
1
answer
32
views
Proof of Modified Farkas lemma: $y\ge0,A^Ty=0,y^Tb<0$ or $Ax\le b$ has a solution
The proof of Farka's lemma is known.
An important corollary of Farkas lemma is stated as
Modified Farkas Lemma. Let $A$ be an $m\times n$ matrix with values in $R$ and $b\in R^m$. Then exactly one of ...
- 2,136
2
votes
1
answer
56
views
Help understanding analytic proof of Farkas' lemma
I'm trying to understand the analytic proof of Farkas lemma (presented in a lecture) but I may have noted some steps wrong.
Farkas Lemma. Let $A$ be an $m\times n$ matrix with values in $R$ and $b\in ...
- 2,136
6
votes
1
answer
140
views
Relaxation of $\min_{H} \text{tr}(H^T P H)$
Let $P \in \mathbb{R}^{N \times N}$ be a given symmetric matrix. Specially, $P$ has all zero entries on its diagonal, and all its off-diagonal entries are positive. And I want to minimize
$$\begin{...
- 478
1
vote
1
answer
88
views
"Sandwich" Quadratic majorizer of even convex function
Assume $f : R \to R$ is strictly convex, differentiable, even and $f(0)=0$. Further assume that there exist quadratic functions above f.
I want to prove that for any quadratic function $ax^2 + bx + c \...
- 43
1
vote
1
answer
49
views
Proximity operator
Let $\sigma_C(y)=\sup_{ z \in C} \langle z | y \rangle $. I want to find the proximity operator for the function $q=||.||^2+2\sigma_C$.
My attempt:
To find $$Prox_q(x)=\inf_{ y \in H}(||y||^2+2\...
- 175
0
votes
1
answer
22
views
Relationship between proximal mapping and subgradient
Background: I came across this excerpt on Wikipedia
Can anybody please help in computing exactly how
$$0\in \delta(\lambda f(z))+(z-x)$$
$$\Leftrightarrow 0\in \delta(\lambda f(z)+1/2 \lVert z-x\...
- 481
0
votes
0
answers
14
views
Strongly monotone operator implies coercivity
I read from the book "Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume I" (P. 156) and paper "Finite-dimensional variational inequality and nonlinear ...
- 107
0
votes
1
answer
32
views
Does a convex quadratic program have a unique dual solution?
As shown in Does a convex quadratic program have a unique solution?, a convex quadratic program has a unique primal solution $x$ if $Q$ is PD.
$$\min \; x^T Q x \\ s.t. \ Ax= b : \lambda \\ \ \ \ \ \ \...
- 1
0
votes
1
answer
33
views
Proving concavity of the Lagrange dual function
The Lagrange dual function for an optimization problem of form
$$\min f_0(\boldsymbol x)\quad\text{subject to}\quad f_i(\boldsymbol x)\le0,h_j(\boldsymbol x)=0\quad i=1,2\dots m,j=1,2,\dots p$$
with ...
- 2,136
2
votes
0
answers
34
views
Changing convexity by changing metrics
I was wondering if for a given functional $F$ on some space $X$, is it possible to construct explicit metrics $(X,d_1)$ and $(X,d_2)$ such that $F$ is convex w.r.t $d_1$ while $F$ is non convex w.r.t $...
- 327
0
votes
0
answers
31
views
Gradient descent on a convex function without a minimizer
From what I've seen, most of the proofs of convergence for gradient descent on convex functions assume that there exists at least one minimizer, i.e. for a convex $f: \mathbb{R} \rightarrow \mathbb{R}^...
- 13
2
votes
1
answer
48
views
Tractable formulation of a mixed integer program
Given constant matrices $A_1\in\mathbb{R}^{1\times l}$ and $A_2\in\mathbb{R}^{1\times l}$, and constants $b_i$, $i=1,\dots,n$. Consider the following mixed integer program (MIP) with decision ...
- 39
1
vote
0
answers
27
views
Determining Optimal Policy Probabilities in Off-Policy PPO Using KKT Conditions
I'm working through a paper on Proximal Policy Optimization (PPO) and am trying to understand the derivation of the optimal policy probabilities for the off-policy case as expressed in Equation 16. &...
0
votes
1
answer
20
views
A concrete example with Arrow-Pratt coefficient of absolute risk aversion
Let $u_1$ and $g$ be increasing strictly concave functions from $\mathbb{R}$ to $\mathbb{R}$. Let $u_2:=g\circ u_1$. If we regard $u_1$ and $u_2$ as utility functions of two players, this is saying ...
- 656
1
vote
1
answer
18
views
Maximizer of a function varying smoothly depending on a parameter
Let $f:\mathbb{R}^2\to \mathbb{R}$ be a smooth function such that for all $t$ $f_t:=f(t,\cdot)$ has a unique maximum at $x^*(t)$ (e.g. $f_t$ is a strictly concave function for all $t$).
My question is:...
- 656
0
votes
1
answer
23
views
How to solve $\min(x^2+y^2)$, $x\ge1, y\ge-2$, using the KKT conditions?
I'm trying to understand better optimisation problems and in particular the KKT conditions. To this end, consider the minimisation problem
$\min(x^2+y^2)$ subject to $x\ge1$ and $y\ge -2$.
It's clear ...
- 6,873
0
votes
0
answers
43
views
While we are optimising the Sortino ratio, whether this objective function is convex, concave, or neither.
I am going to formulate an optimization problem for finding a feasible portfolio with the largest value of Sortino ratio. It will defined as follows:
\begin{align*}
\max_{x} \quad & STR(x) = \frac{...
1
vote
0
answers
31
views
Cutting Plane Methods for Convex Optimization
The cutting plane approach in convex optimization is a general recipe for minimizing a convex function. The argument relies on the fact that using the gradient vector we can cut the feasible set into ...
- 688
0
votes
0
answers
16
views
Why does Slater's condition require a point in the *relative* interior of the domain?
Consider a convex optimisation problem in the standard form: $\min f_0(\mathbf x)$ subject to $f_i(\mathbf x)\le 0$ and $A\mathbf x=\mathbf b$, with $f_i$ all convex functions.
When discussing Slater'...
- 6,873
0
votes
0
answers
20
views
Pointwise minimum of quasiconvex function and step function
Suppose I have a quasiconvex function $g:\mathbb{R} \rightarrow \mathbb{R}$ and a step-function $f(x)$ defined as: \begin{align} f(x) = \begin{cases} a \mbox{ if } x\geq \alpha \\ b \mbox{ if } x< \...
- 23
-1
votes
1
answer
61
views
What's the purpose of the KKT condition when first-order optimality condition exists?
Given a convex optimization problem $$\min f(x), x \in D$$ $f, D$ convex.
The first-order optimality condition says $x$ is the minimizer if and only if $\nabla f(x)^T (x-y) \geq 0, \forall y\in D.$ ...
- 8,122
0
votes
0
answers
33
views
Optimization on Manifolds
I am quite new to the concept of optimization on manifolds, however in my research I have stumbled upon a problem which I believe is amenable to this type of analysis.
Specifically, I am concerned ...
- 285
1
vote
0
answers
15
views
How to Solve ADMM Optimization Problem
We are trying to solve the following Optimization Problem
$$
\begin{aligned}
& \min _{\left\{y_{i j}^{m}\right\}} \sum_{i \in I_{m}} f_{i j}^{m}\left(y_{i j}^{m}\right)+\sum_{j \in J} \Phi^{m}\...
- 11
1
vote
0
answers
28
views
Proximal operator of conjugate of Euclidean norm
I am trying to solve the following problem:
Given $\tau \in \mathbb{R}_{++}, \rho \in \mathbb{R}_{++},~y_n \in \mathbb{R}^n,~z_n \in \mathbb{R}^n$.
Derive
$$\text{prox}_{\frac{1}{\tau} g^{*}} (y_n + \...
- 11
2
votes
1
answer
44
views
Image of a two-parameter function over a set
I have the following problem:
Let $B$ be the set $B=\{(x_1 , x_2) \in \mathbb{R}^2\mid x_1^2 + x_2^2 \leq 1\text{ and }x_1 \geq 0\}$.
A function $f:B \rightarrow \mathbb{R}$ is given by
$$
f(x_1 ,x_2 ...
- 21
1
vote
1
answer
50
views
Solving a convex problem with quasiconvexity with CVXPY?
I have a question regarding quasiconvexity and its usage in CVXPY.
I have the following optimization problem.
\begin{equation*}
\begin{aligned}
\min_{x} \quad & \sqrt x\\
\textrm{subject to:} \...
- 21
0
votes
0
answers
17
views
Relation between local Lipschitz continuity constant and Lipschitz smoothness constant of a function.
Using local Lipschitz continuity of $f(\cdot)$:
\begin{align}
f(\mathbf{a}) &\leq f(\mathbf{b})+ L_0 \lVert{\mathbf{a}-\mathbf{b}}\rVert
\end{align}
In the FedProx Paper (https://arxiv.org/pdf/...
0
votes
0
answers
29
views
Theorem for Convex Functions
I need to prove $f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle, \forall x,y \in C \subset \Bbb{R}^n$ where $C$ is a convex set, and $f:C \rightarrow \Bbb{R}$ is a convex function.
I saw someone ...
1
vote
1
answer
51
views
Is $U^{-1}(U(x)+U(y))$ a convex function in general?
Let $U(x)$ be a positive, strictly increasing, strictly convex $C^2$ function in $x$, is it generally true that $U^{-1}(U(x)+U(y))$ is a convex function in $x,y$ ? For $U(x)=e^x$, it is well known ...
- 359
1
vote
1
answer
33
views
How to prove a matrix $M$ has incoherence property?
By incoherence, I am referring to equation 1.18 in the paper The Power of Convex Relaxation: Near-Optimal Matrix Completion
Given a rank 1 matrix $n\times n$ matrix $M = x \mathbf{1}^T$, $x \in \...
- 113
1
vote
1
answer
99
views
Is the density of scale mixtures of Normal-Gamma log-concave?
Consider the following density function (unnormalized)
$$p(y;b)=\int_{0}^{\infty}\dfrac{\exp\left(-\frac{y^2}{2\left(b+\frac 5u\right)}\right)}{\sqrt{b+\frac 5u}} u^{1/2}\exp\left(-\dfrac{2u}{3}\right)...
2
votes
1
answer
38
views
Cannot find the dual function
The picture shows an example of solving the integer problem with a decomposition method. However, what I am trying to ask is about the dual function part instead of the integer part. As you can see, ...
- 21
2
votes
2
answers
57
views
Proving the convexity of $f(x,y) = x^2 + y^2 + |xy|$
I am trying to show that the function $f(x,y) = x^2 + y^2 + |xy|$ is convex. So I can show that both $x^2 + y^2 + xy$ and $x^2 + y^2 - xy$ are convex because their hessian is a diagonally dominant ...
- 25
0
votes
0
answers
23
views
Maximizing a function involving a linear combination of the positive and negative part
Let $u:\mathbb{R}_+ \rightarrow \mathbb{R}$ be a differentiable and strictly concave function satisfying $\lim_{x \to 0^+} u(x)=\infty$ and $\lim_{x \to \infty} u(x)=0$, and let $a,b,c \in \mathbb{R}$ ...
- 404
2
votes
1
answer
45
views
[convex optimization]Does there exist a function h such that its composition with a non-convex function g, h(g(x)), is a convex function?
I have a question regarding convex functions and compositions that I'm hoping someone could provide some insight on.
For a given non-convex function g(x), I'm wondering if it's possible to find ...
- 21
2
votes
1
answer
46
views
The proof for worst-case convergence rate ($\frac{1}{\sqrt{T}}$) of non-smooth convex optimization
In Introductory Lectures on Convex Optimization by Nesterov, Section 3.2.1, they construct a difficult function to show that all the schemes work badly on this function. Say, consider an unconstrained ...
- 21
1
vote
0
answers
37
views
On transferability of solutions to linear programs
I am interested in a sequence of linear programs of the following type, over $x\in\mathbb{R}^k$:
$$
\min c_n^T x\\
x\geq 0\\
Ax = b
$$
for $x\in\mathbb{R}^k$, $n\geq 1$ and some choice of $A, b$ that ...
- 580
1
vote
1
answer
37
views
Why is the relative interior of a set defined in terms of its affine (vs convex) hull?
I'm taking an Intro to Optimization grad course and the notion of the relative interior of a set was introduced as
The relative interior of a convex set $C$, denoted $\text{ri } C$, is the interior ...
- 53
0
votes
1
answer
32
views
An optimisation problem involving a special class of polynomials
I'm currently working on an interesting problem in function approximation thta just came to mind and am seeking insights or methodologies that might aid in approaching it. The problem is as follows:
...
- 1,688