Mathematics Stack Exchange
Mathematics Stack Exchange

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.

Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function. Linear Programming is a special case. Convex Optimization problems as a class are easier to solve numerically than general mathematical optimization problems.

The following problems are all convex minimization problems, or can be transformed into convex minimizations problems via a change of variables:

  • Least squares
  • Linear programming
  • Convex quadratic minimization with linear constraints
  • Quadratic minimization with convex quadratic constraints
  • Conic optimization
  • Geometric programming
  • Second order cone programming
  • Semidefinite programming
  • Entropy maximization with appropriate constraints
7419 questions
2
votes
0 answers

Solution of Cox Lasso dual optimization Problem

In https://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-110.html, page 12-13, the authors derived a dual form of Cox model: Some Definitions In order to define the dual, the optimization problem for the Cox model can be rewritten,assuming the…
floodking
  • 121
2
votes
1 answer

Is this function quasi convex

I have a function $f(x,y) = y(k_1x^2 + k_2x + k_3)$ which describes chemical potential of a species ($y$ is mole fraction and $x$ is temperature) I only want to check quasi convexity over a limited range. k1,k2 and k3 are coefficients of a…
siby
  • 21
2
votes
1 answer

How to prove huber loss as a convex function?

Huber loss is defined by $$\mathcal{H}(u) = \begin{cases} \frac{1}{2}\|u\|_2^2 & \|u\|_2 \leq 1 \\ \|u\|_2- \frac{1}{2} & \|u\|_2 > 1 \end{cases} . $$ From the graph it's evident, but I'm just stuck on the rigorous proof. It happens not to be…
Li haonan
  • 209
2
votes
0 answers

Find subgradient of $f(x)=\max\{f_1(x), f_2(x)\}$

Let $f(x)=\max\{f_1(x), f_2(x)\}$ where $f_1$ and $f_2$ are differentiable convex functions defined on $R^n$. Let $x'$ be such that $f(x')=f_1(x')=f_2(x')$. Show that $g$ is a subgradient of f at $x'$ if and only if $$g=\lambda \nabla…
OlafHolm
  • 55
2
votes
0 answers

Why is the first order condition for $f$ is $f(\mathbf y) \ge f(\mathbf x)+2Re\{\nabla f(\mathbf x)^T(\mathbf y-\mathbf x)\} ? $

Why is the first order condition for $f$ is $f(\mathbf y) \ge f(\mathbf x)+2Re\{\nabla f(\mathbf x)^T(\mathbf y-\mathbf x)\} ? $ According to the first order condition in optimization : $g(\mathbf y) \ge g(\mathbf x)+ \nabla g(\mathbf x)^T(\mathbf…
electronic component
  • 183
2
votes
2 answers

Show $f(x) = \ln\ (\sum_{i=1}^n e^{\langle a_i, x\rangle})$ is convex

Let $a_i \in \mathbb{R}^n, f(x) = \ln\ (\sum_{i=1}^n e^{\langle a_i, x\rangle })$. Show $f(x)$ is convex. I don't really know where to start on this. Is it safe to say $x \in \mathbb{R}^n$ then or is that not necessary for inner products? I'm…
user559412
  • 115
  • 7
2
votes
0 answers

How to find the jacobian of this function?

$\DeclareMathOperator*{\argmin}{arg\,min}$ I want to find the Jacobian of the following function $D:\mathbb{R}^n\rightarrow\mathbb{R}^n$: $$ D(p) = \argmin_{x} \left(C(x) - x \cdot p\right)\ \text{ s.t. } x \in X $$ where $C$ is twice…
spinkus
  • 302
2
votes
1 answer

Exact Line Search

The gradient descent I learnt uses $x^{k+1} = x^k + t\triangledown f(x)$ and we learnt to set $t$ heuristically. Am I right to say that exact line search simply computes the optimal value of $t$ that minimizes the $f(x) ?$ Wouldn't I be able to look…
Kong
  • 884
2
votes
1 answer

Initial solution to a Convex Optimization problem

I am aware that in a convex optimization problem, the initial solution does not matter as the algorithm guarantees convergence to the global minimum/maximum. But what if the initial solution does not satisfy one of the constraints? I.e. it is…
Tomas Jorovic
  • 3,983
  • 3
  • 27
  • 38
2
votes
1 answer

Show that $\frac{\alpha - c^t x}{\sqrt{x^t R x}}$ is quasiconvex

For $\alpha \in \mathbb{R}$ and $x, c \in \mathbb{R}^n$ and $R \in \mathbb{S}_+^n$ (positive semi-definite), let \begin{equation*} f(x) = \frac{\alpha - c^t x}{\sqrt{x^t R x}} \end{equation*} with $\text{dom}f = \{ x | c^t x \geq \alpha\}$ and…
jodag
  • 800
2
votes
0 answers

Nash point and Limit point

I have taken an optimization course but It seems that I don't have its basics so any reference would be appreciated, In the publication , it is stated any limit point satisfies the Nash equilibrium conditions. After reading I knew that Nash…
Mour_Ka
  • 316
2
votes
2 answers

Is optimizing a convex function $f(x,y)$ that has a equality constraint $x+y=1$ a convex optimization problem?

I have a convex function $f(x,y)$, with the equality constraint $x+y=1$. Is this still a convex optimization problem, despite the equality constraint? or is it a nonlinear optimization problem?
Ron
  • 143
2
votes
0 answers

show matrix completion is SDP

I am working on showing a matrix completion problem is a SDP. Specifically, we want to show \begin{array} \underset{minimize}_{ X\in \mathbb{R}^{m \times n}} & \sum_{(i,j) \in \Omega} ( X_{ij} - Z_{ij} )^2 + \lambda \| X \|_{tr} \end{array} is a…
Dave
2
votes
1 answer

What are some applications of entropy maximization and minimum volume covering ellipsoid?

I'm reading Boyd's Convex Optimization textbook. In particular, I'm currently focusing on Chapter 5 (Duality). There is a frequent recurrence of two examples: Minimum volume covering ellipsoid \begin{align*} minimize & \quad log \; det \;…
ashman
  • 952
2
votes
1 answer

Global maxima for concave functions

Let $D$ be a convex set in $\mathbb{R}^n$ and $f: D \to \mathbb{R}$ a concave and $C^1$ function. How do I show that $x^*$ is a global maximum for $f$ if and only if $f^{(1)}(x^*)y \leq 0$ for all $y$ pointing into $D$ at $x^*$ (Here $f^{(1)}$…
df56
  • 21
  • 2
1 2 3
…
24 25