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,063
questions
0
votes
0
answers
7
views
Checking for local minimizer on boundary point
My specific question:
For a convex, second-order continuously differentiable function, $f:S_{+}^{n} \to \mathbb{R}$, where $S^{n}_{+}$ denote the set of positive semidefinite matrices, how can we ...
- 632
1
vote
0
answers
45
views
Under which condition $d(y)=\min_x f(x,y)$ is smooth (differentiable, $C^1$)?
Under which condition $d(y)=\min_x f(x,y)$ is smooth (differentiable, $C^1$)?
(1) To determine the smoothness of $d(y)$, I think the following conditions are required:
Differentiability: The function $...
- 105
0
votes
0
answers
17
views
Portfolio optimization with max information ratio. (cvxpy library not giving answer for particular cases)
In portfolio optimisation with maximizing information ratio, our aim is to create a portfolio such that the information ratio of the portfolio and corresponding benchmark is maximized. Information ...
- 113
0
votes
0
answers
29
views
A set C is convex if for any projection onto the set is unique. [duplicate]
In a course on continuous optimization, the professor said that Chebyshev's problem is the following:
Let there be the unique projection onto a set $C$ for every point $x$ in a Hilbert space $X$ over ...
1
vote
0
answers
26
views
Optimization problem that is convex and bounded is said to be unbounded in implementation
I have an optimization problem that is convex and bounded:
\begin{align*}
\text{Minimize}_{\text{wrt} B_{\text{opt}}}\qquad
&\frac{1}{2p\sigma^2}\|Y_{\text{opt}}-X_{\text{opt}}B_{\text{opt}}\|_2^2-...
- 500
0
votes
0
answers
32
views
What is the time complexity of deciding whether a linear program is feasible?
I have a question: What is the time complexity for solving a convex feasibility problem (particularly, this question focuses on the linear feasibility problem)?
Specifically, the feasibility problem ...
- 1
0
votes
2
answers
38
views
Generalisation of convexity
Consider the function $f(\theta,\phi) = \sin \left(\theta+\phi/2\right)+\sin \left(\theta-\phi/2\right)$. Defined on the torus $(x,y) \in [-\pi,\pi]^2$ with periodic boundary conditions.
This function ...
-2
votes
1
answer
34
views
Minimizer of sum of convex combination of convex functions
The accepted answer to this question is very close to yet still missed a bit to what I want to know. It gives an example where the minimizer of $f=f_1+f_2$ is not a convex combination of the ...
- 385
0
votes
0
answers
9
views
Symmetric Trilinear map for proving Newton's method on self-concordance functions
The following claim is used for proving the quadratic convergence phase of Newton's method on self-concordance functions. I have a very long and non-intuitive proof using Lagrange Multipliers. I ...
- 189
-5
votes
0
answers
18
views
Convex or not the following function with matrix [closed]
I have the following function:
$$f(\Delta)=|\Gamma\ast \Delta\ast \Theta\ast \Psi|^{2} $$
where $\Gamma$ is a $1\times N$ complex matrix, $\Delta$ is an $N\times N$ real matrix (diagonal, only in main ...
- 9
0
votes
1
answer
31
views
Vanishing vector field, positive at the origin and negative at infinity
Let $F:\mathbb{R}^n_+\rightarrow\mathbb{R}^n, \ (x_1,x_2,\dots,x_n)\mapsto(F_1(x_1,...,x_n),...,F_n(x_1,...,x_n))$ be a vector field defined over the first quadrant of $\mathbb{R}^n$. That is, $\...
- 323
0
votes
0
answers
25
views
Using the KKT conditions to maximize the likelihood of a multivariate Gaussian sample
Suppose $X_1, \cdots, X_n \sim \mathcal{N}(\mu, \Sigma)$, where $\mu \in \mathbb{R}^d$ and $\Sigma \in S_n^+$. The likelihood of the sample is given by:
$$L(\mu, \Sigma) = \prod_{i=1}^n \frac{(2 \pi)^{...
- 1,267
2
votes
2
answers
50
views
Question about convex optimization with binomial coefficients
I don't have any experience with optimization other than some very basic problems from elementary calculus, but I want to understand a particular claim from Alon and Spencer's The Probabilistic Method....
0
votes
0
answers
17
views
Nonlinear, multi-parametric programming with regularization
I'm considering the following nonlinear, multiparametric problem with regularization term:
$$
x(\theta,\sigma)=\underset{y\in\Omega}{\textrm{argmin}}~f(y,\theta)+\sigma\|y\|_2^2,
$$
where $\Omega \...
- 87
0
votes
0
answers
53
views
Minimizer of the maximum over functions is a convex combination
I have the following problem, related to finding a point in space that minimizes the maximum weighted distance between the point itself and $n$ circles.
Given $a_1, \dots, a_n \in \mathbb{R}$, $ {\bf ...
0
votes
0
answers
30
views
Rate of convergence for a modified projected gradient method
The problem is to find $$\min_x f(x),$$
where
$$ f(x) = g(x) + h(x),$$
and $g$ is convex and $\beta$-smooth, and $h$ is $\alpha$-strongly convex but non-smooth.
I have a modified projected gradient ...
- 11
2
votes
0
answers
38
views
+50
Sufficient conditions for a quadratic program with linear inequality constraints to have unique solution
Consider a quadratic program
$$\min_{x} x^TQx + b^tx$$
such that $Ax\leq c$ pointwise. This is a quadratic program with linear inequality constraints. Under what conditions for the data (matrix $Q$, ...
- 7,094
1
vote
0
answers
36
views
Can certain Convex Optimization Problems be interpreted as Optimal Transport Problems?
The theory of optimal transport considers the problem of transporting utilities distributed acoording to a probability measure $\mu$ on $X$ to "targets" distributed according to a ...
- 1,035
1
vote
1
answer
28
views
Convex conjugate of a differentiable function
Let $f : \mathbb{R}^n \to \mathbb{R}$ be convex and differentiable everywhere. For $y \in \mathbb{R}^n$, define $$f^*(y) := \sup\limits_{x \in \mathbb{R}^n} \lbrace y\cdot x - f(x)\rbrace$$ Define $D =...
1
vote
0
answers
45
views
Simple representation of a positive linear transformation of a semidefinite cone
I am trying to solve a conic optimization problem where one of my length $n$ vector decision variables is the sum of all of the $n$ unique diagonal bands of any $n \times n$ semidefinite matrix. I can ...
3
votes
3
answers
91
views
Lower bound on the sum of square roots of probabilities that are upper and lower bounded
Let $p_i$ with $i=1,\ldots,n$ be probabilities, that is $\sum_i p_i =1$. Moreover each term is bounded according to
$$
\frac{1}{n}-\epsilon \leq p_i \leq \frac{1}{n}+\epsilon
$$
I want to find the ...
- 355
1
vote
2
answers
71
views
For which value of $\mu$, is the region $\lVert x - a \rVert \leq \mu \lVert x-b \rVert$ convex? Give a proof.
I tried taking two points such as $x_1$ and $x_2$ that are in the set (so, by definition, they satisfy the set condition) and tried to show that $z = (\lambda) x_1 + (1 - \lambda) x_2$, also satisfies ...
- 38
0
votes
0
answers
18
views
Fenchel conjugate of a function whose domain is the set of nonnegative real vectors.
Let $-\phi$ be a convex, proper, lower semicontinuous function which has domain $\mathbb{R}^n_+$, i.e., the set of vectors in $\mathbb{R}^n$ with nonnegative entries.
By definition of the convex ...
- 7,094
-2
votes
1
answer
33
views
Convex cones in $\mathbb{R}^n$ - Orthants
I am trying to understand the notion of convex cones. So, here are my questions.
I can understand that the non-negative orthant, $\mathbb{R^n_+}$, defined as $\left\{ (x_1, \ldots, x_n) \in \mathbb{R}^...
2
votes
0
answers
51
views
Doubt in applying Infeasible start Newton method to a really simple example.
I am looking to apply one iteration of the infeasible start Newton method to the example below:
$$ \min f(x,y,z )= x^4/4 + y^2 + z^2 \\
\text{subject to } \,\,\,\,\,\,\,\,\,\,\,\ x + y + z = 2.$$
I ...
- 1,269
0
votes
0
answers
39
views
Second-order-cone programming - Lagrange multiplier and dual cone
In standard nonlinear optimization when we are interested to minimize a given cost function the presence of an inequality constraint g(x)<0 is treated by adding it to the cost function to form the ...
- 233
0
votes
1
answer
52
views
Simple question about infeasible start Newton method for equality constraint problems.
I am reading about infeasible start Newton method for equality constraint problems in the book Convex Optimization, written by Stephen Boyd and Lieven Vandenberghe. The algorithm is stated as follows:
...
- 1,269
0
votes
0
answers
13
views
Does the subgradient and normal align at the maximum of a convex function?
It is well known that a convex function is minimised over a convex set, if and only if there is a subgradient which is inwards normal to the set at that point. i.e the negative subgradient (direction ...
- 9,795
1
vote
1
answer
36
views
Theorem of alternatives for strict inequalities
This is with reference to example 2.21 in Boyd's book on Convex Optimization. I am attaching a screenshot below
Here, I do not understand how we get the conditions on $\mu$ and $\lambda$. To be ...
0
votes
0
answers
18
views
Solving box-constrained quadratic programs?
I am trying to understand and implement algorithms that deal with optimization problems of the kind:
$$\min_x \frac{1}{2} x^{\prime} H x+g^{\prime} x \tag{1}$$
$$\text { s.t.}\ \ A^{\prime} x+b=0$$
$$...
- 1,577
1
vote
2
answers
58
views
$\forall P \succ 0, \langle X,P \rangle = \langle Y,P \rangle$, implies $X=Y$?
For n by n matrices X,Y,P, if $\forall P \succ 0, \langle X,P \rangle = \langle Y,P \rangle$, does $X=Y$?
This question arises from some optimization work I'm doing and in the case of my question $Y=...
- 632
1
vote
1
answer
30
views
Ellipsoid set definitions
In Boyd & Vandenberghe's Convex Optimization, one can find two definitions for the ellipsoid.
$$ \mathcal{E} = \left \{ x \mid (x-x_c)^\mathsf{T}P^{-1}(x-x_c) \leq 1 \right\} $$
and
$$ \mathcal{E} ...
- 151
0
votes
0
answers
20
views
A question about Pareto fronts
Let $C \subseteq \mathbb R_+^2$ be the Pareto front of a pair of nonnegative functions $(f,g)$ (where $f$ is strongly convex and $g$ is convex, for simplicity), i.e,
$$
C := \{f(x(t)),g(x(t)) \mid t \...
- 9,140
0
votes
1
answer
65
views
Show that $f \left( \boldsymbol{x} \right) = -\sqrt[^n]{ {x}_{1} {x}_{2} \ldots {x}_{n} }$ is a convex function , for positive x
I'm having trouble/mistake proving this since when I try to calculate the hessian, the partial derivatives of i,j elements are negative.
This is my current direction and I don't know how to continue:
...
- 1
5
votes
1
answer
85
views
Optimization problem involving the inverse matrix
I have a question related to optimization.
Given natural numbers $n$ and $\ell$, matrices ${\bf K}_1, \dots, {\bf K}_\ell \in \Bbb R^{n \times n}$ and a vector ${\bf y} \in \Bbb R^n$, define $${\bf K} ...
- 101
0
votes
0
answers
16
views
Given the support function of a convex set $C\subseteq \mathbb{R}^{2n}$, compute $\sup \left \{c'y: (x,y) \in C\right\}$ as a function of $x$
Suppose $C \subseteq \mathbb{R}^{2n}$ is a closed, bounded, convex set, with support function $h: \mathbb{R}^{2n} \rightarrow \mathbb{R}$, defined as
$$h(c_1, c_2) := \sup \{c_1'x + c_2'y : (x,y) \in ...
- 1,574
5
votes
1
answer
153
views
Is a piecewise linear function always a sum of concave and convex functions?
If I take a piecewise linear function (piecewise affine) is it true that I can always write it as a sum of concave and convex functions?
My understanding of this page
https://mjo.osborne.economics....
- 159
1
vote
0
answers
45
views
$\nabla f(x)(y-x) \geq 0$ for KKT point x
Let $x\in\mathbb{R}^n$ be a KKT point of the problem $$\min f(x) :\;\text{s.t.}\; h_j(x)\leq0,\;\;\forall j\in\{1,\dots,m\}$$ where $f:\mathbb{R}^n\to\mathbb{R}$ is smooth and all $h_j:\mathbb{R}^n\to\...
- 33
1
vote
0
answers
21
views
Artin's vanishing theorem: a line restricts to a circle in order to calculate critical points
Two different ways of calculating critical points are given from the formulas (I hand wrote them at a class so it's not 100% the formulas but they're close):
$(-1)^{dim} \mathcal{X}(X)$ = # of ...
1
vote
0
answers
53
views
Solving a constrained optimisation problem where the algebra doesn't make sense
I have the following function to maximise with respect to $x$, $p$, and $\eta$:
$\frac{p\eta}{R(x)}[v(x)-\bar\theta R(x)]+(1-\frac{p\eta}{R(x)})p\eta-(1+\lambda)tpx-\lambda R(x) (1)$
subject to the ...
- 23
1
vote
0
answers
36
views
Lemma about $f(x)$ and it's convex conjugate $f^{*}(y)$
Suppose $f:(0,+\infty) \to \mathbb{R}$ is convex function, $f^{*}$ it's convex conjugate. I am trying to prove following lemma.
$\underline{\textbf{Lemma.}}$ For all $\gamma > 0$ and for all $\...
- 1,283
0
votes
0
answers
17
views
Effective computability of non-linear optimization algorithms
We are looking for any results on the effective computability of the optimization algorithms.
In particular, consider probability mass functions on a finite set $X=\{x_1, ... x_n\}$.
We are looking ...
- 1
0
votes
1
answer
38
views
Proving that the probabilities for which the variance of a distribution is greater than some number is convex
From Boyd & Vandenberghe's Convex Optimization, exercise 2.15 (f) and (g) — I am following along with the solutions from here.
2.15 Some sets of probability distributions. Let $x$ be a real-...
1
vote
0
answers
22
views
Adding restrictions together in a linear program
I have a linear program
$\max 3x_1+x_2\quad$ s.t.
$\quad\begin{matrix}
x_1-x_2&\leq& -1\\
-x_1-x_2&\leq& -3 &(*)\\
2x_1+x_2&\leq& 2&(**)\\
x_1,x_2&\geq& 0
\end{...
- 77
0
votes
0
answers
18
views
Calculating the Linear Transformation of a Norm-Bounded Convex Set
I am working on implementing mechanism 1 from this paper. I have limited knowledge on convex optimization and am not sure how to derive an explicit expression for the linear transformation of the unit ...
- 13
0
votes
1
answer
46
views
Gradient descent over a restricted convex domain — how do we guarantee that we stay in the domain if the global minimizer is outside of it?
Let $f:\mathbb R^d \rightarrow \mathbb R$ be a convex function and $A \subset \mathbb R^d$ a convex set. We are interested in finding the minimum of $f$ over $A$. We have the gradient of $f$ and we ...
- 2,342
1
vote
2
answers
76
views
Convexity of general quadratic function [closed]
Let $f(x) := x^T A x + b^T x + c$. If we only know $A \in \mathbb{R}^{n \times n}$, why does convexity of $f$ require that $A + A^T$ be positive semidefinite (PSD) and why does strong convexity ...
- 117
1
vote
0
answers
21
views
Lagrangian function and first order necessary optimality conditions
I am given the following equality constrained convex QP.
$$\min_x \frac{1}{2}x'Hx+g'x$$
$$st. A'x+b=0$$
with $H\succ 0$.
I want to find the Lagrangian function for this problem and the first order ...
5
votes
0
answers
57
views
Proximal operator of squared $\ell_1$-norm
For any $a \in \mathbb R^d$ and $t \ge 0$, let $p_t(a)$ be the unique minimizer of $f_t(x;a) := \|x-a\|_2^2 + t\|x\|_1^2$ over $x \in \mathbb R^d$.
Question. Is there an analytic formula for $p_t(a)$ ?...
- 9,140
0
votes
0
answers
36
views
Two methods for solving bivariate optimization problems — how do they compare?
Consider the unconstrained non-convex optimization problem:
$$\min\limits_{x,y} f(x,y)$$
Suppose that for fixed $x$, the function $y \mapsto f(x,y)$ is convex. In this case, I believe there are two ...
- 1