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
1
vote
1 answer

Describing a Dual Cone

1)Does dual cone define just for proper cone or all kinds of cone ? 2)Can someone show me a figure that shows a dual cone of a cone ? In Convex Optimization by Boyd (P.51) said that " $y\in k^*$ iff $-y$ is the normal of hyperplane that supports $k$…
eHH
  • 463
  • 1
  • 4
  • 14
1
vote
1 answer

Is $|| AXB-C ||_F$ convex?

Let $A \in \mathbb R^{n\times n}$, $B \in \mathbb R^{n\times n}$, $C \in \mathbb R^{n\times n}$ be constant matrices. Is the following convex? minimize $|| AXB-C ||_F$ for $X>0$, where $|| \dots ||_F$ denots the frobenius norm.
Lyapunov123
  • 71
1
vote
0 answers

Cauchy point,derivation: whe the constrianed optimizitaion is not used

Sorry for the slightly longer question. Consider the following definition of the Cauchy point $h_{i}^{C}=\alpha_{i}^{C}h_{i}.$ It can be found minimizing a quadratic form $\alpha_{i}^{C}=\arg\min\left\{ f(x_{i})+\nabla…
Tomas
  • 11
1
vote
1 answer

Show that every polytope is bounded

The definition of polytope is the convex hull of a finite set. Thus: $$ \parallel\sum_j\lambda _j x_j\parallel\le\sum_j\lambda_j\parallel x_j\parallel\le\sum_j\lambda_j\max_j \parallel x_j\parallel=M\sum_j\lambda_j=M $$ where $M=\max_j \parallel…
dresden
  • 1,073
  • 2
  • 11
  • 19
1
vote
0 answers

Confusion related to interior point method

I was reading this wiki article related to interior point method. I didn't get when they say that it applied Newton's method to get an update for $(x,\lambda)$. How the expression at the end obtained
user34790
  • 4,192
1
vote
0 answers

Confusion related to fmincon function in matlab

I was reading this help section of matlab's fmincon function that uses interior point algorithm for solving an optimization problem. It says the following optimization problem is replaced by To solve the approximate problem, the algorithm uses one…
user34790
  • 4,192
1
vote
1 answer

Maximize Trace as standard semidefinite optimization

Let $A$ be a symmetric matrix and $X$ a symmetric positive definite matrix, then the following standard semidefinite optimization problem is convex: min $tr (AX)$ subject to $X>0$ Now I wonder if $tr ((-A)X)$ is convex or concave? The reason is the…
Lyapunov123
  • 71
1
vote
1 answer

Minimize Trace for non-symmetric matrix

Let $A$ be a given matrix and $X$ a symmetric positive definite matrix which shall be optimized: min $tr (AX)$ subject to $X>0$ This optimization problem is convex if $A$ is symmetric as it is the standard form of Semidefinite Programming. But is…
Lyapunov123
  • 71
1
vote
0 answers

Is $Q(b)=a^Hb+b^Ha$ ,where $a,b \in \mathbb{C}^{N\times1},b^Hb\leq\epsilon^2$convex or concave?

We assume that $a,b \in \mathbb{C}^{N\times1},b^Hb\leq\epsilon^2$. Is the function $Q(b)=a^Hb+b^Ha$ convex,concave? In other words, which of the following problems is feasible? $\min\ \ a^Hb+b^Ha \\ s.t.\ \ \ b^Hb\leq\epsilon^2$ or $\max\ \…
begforopt
  • 83
1
vote
0 answers

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}\left(z_{i j}^{m}\right) \\ & \text { subject to } y_{i…
ANWESA ROY
  • 11
  • 1
1
vote
0 answers

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 minimization problem $$\min_{x\in\mathbb…
Leontina
  • 11
1
vote
1 answer

Supremum of an inner product constrained to an ellipsoid

I am self-studying Boyd's convex optimization textbook, and I am befuddled by Example 9.1 shown here in screenshot. Specifically, I am confused how he gets that the supremum of $q^{\top} z$ over the ellipsoid is equal to that first term on the…
Ifkaluva
  • 13
  • 2
1
vote
0 answers

simple conditions for a convex optimization problem to be solvable in polynomial time

In a script I am currently reading it is used at some point that the convex funciton $f = \ln (p(\exp (x_1 ), \ldots , \exp( x_n)))$ can be minimized in polynomial time under linear inequality constraints. Here $p$ is a polynomial in $n$ variables…
leon.fuchsler
  • 149
1
vote
0 answers

Lagrange multipliers in global consensus optimization

Consider the following convex optimization problem: $$\text{minimize} ~ \sum_{i=1}^N f_i(x) ~ \text{ s.t. } ~ x \in X,$$ where $X$ is an $m$-dimensional convex set, and $f_i$'s are convex. We can rewrite this as: $$\text{minimize} ~ \sum_{i=1}^N…
smz
  • 283
1
vote
1 answer

Clarifying derivation of Water-filling problem from Convex Optimization

From Boyd & Vandenberghe's Convex Optimization: How did we obtained the highlighted part? I assume it is derived from inequalities above it, but $\lambda_i$ is not in the highlighted part. Also, here we have treated $x \succeq 0$ as one of the…
user1953366
  • 191
  • 7
1 2 3
…
24 25