Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

0
votes
1answer
39 views

Given the set of all polygons with m sides and perimeter 1, why is there an element with maximal area?

The set of all polygons with $m$ sides and perimeter $1$ has an element with maximal area. I read this fact in a book, and the reference was in German. Does anyone here know? I know how to ...
3
votes
1answer
31 views

How can I project a matrix on the set of symmetric positive definite matrices with trace 1?

Given a square matrix $A \in \mathbb{R}^{n \times n}$, I need to compute $$ \min_{X \in \Omega} \lVert A - X\rVert^2$$ where $\Omega = \{X \in \mathbb{R}^{n \times n} |\, tr(X) = 1, X \text{ is ...
0
votes
0answers
54 views

Matrix norm optimization problem : $\min_{\textit{ }x} \| A x B \|_4$, $x$ in the “unit” circle

Bonjour, Let $A$, $B$, $C$ and $D$ complex matrices. Is there a way to find a matrix $x$ (edit: non trivial) as: $\min_{\textit{ }x} \| A x B \|_4^4$ Or, more complicated, $x$ as $\min_{\textit{ ...
0
votes
1answer
38 views

Given $R \in \mathbb R$, choose $a,b,c$ from discrete set so that $a^{-1} + b^{-1} + c^{-1} \approx R^{-1}$

I am working with the following equation (parallel resistors): $\frac{1}{R_g} = \frac{1}{R_1} + \frac{1}{R_2} + \frac{1}{R_3}$ The values of $R_1, R_2$ and $ R_3$ are discrete - lets say 256 steps ...
0
votes
0answers
14 views

Dual norm of quasi norms

The dual norm $\Omega^*$ of the norm $\Omega$ is defined for any vector $\mathbf{z} \in \mathrm{R}^N$ by \begin{equation} \Omega^*:= \underset{\mathbf{x} \in \mathrm{R}^N}{max } \quad \mathbf{z}^{T} ...
1
vote
0answers
16 views

Optimal $A\in \Sigma$ that maximizes an objective

Let $([0,1],\Sigma, \lambda)$ be a probability space. For any given $B\in \Sigma$, $K\in [0,1]$ and $f\in L^2(\lambda)$ with $f(x)\in[0,1]$ for all $x $, $$\max_{A\in \Sigma}\int_A f(x) d\lambda(x)- ...
-1
votes
0answers
40 views

calculus optimization help

Minimum Cost A storage box with a square base must have a volume of 80 cubic centimeters. The top and bottom cost 0.20cents per square centimeter and the sides cost 0.10cents per square centimeter. ...
2
votes
1answer
25 views

Where can I find an algorithm to compute $\min_{x \in \Delta_n} \langle g , x - y \rangle_1 + c\lvert x - y\rvert_1^2$?

I wish to compute the minimizer of $$ \min_{x \in \Delta_n} \langle g , x - y \rangle + \frac{c}{2}\lvert x - y\rvert_1^2$$ where the subindex $1$ indicates that the norm is the $1$-norm and ...
0
votes
0answers
39 views

Non-convex function with global minimum [duplicate]

I am working on a complicated objective function which I suppose is not convex. But when I use a global optimization tool that can find all its local minimums, it will always converge to the same ...
0
votes
1answer
26 views

Convex optimization problem: linear equality and inequality constraints

When linear equality constraints can be converted in an inequality constraints for a strongly convex optimization problem? I mean, I got the same solution for both the following problem: 1) $\min_x ...
0
votes
2answers
35 views

Is there a name for this modified newton's method?

I know that Newton's method has the following formula: $$f_{t+1} (x)= f_{t}(x)-f'(x)/f''(x)$$ The source code at the end of the post seems to use the following construction instead: $$f_{t+1} (x)= ...
2
votes
0answers
22 views

Some maximization over stochastic matrix

I am writing some applied assignment which leads me to the following problem. I will be very grateful if anyone can provide a solution or even some thoughts. Thanks a lot! Consider a (row-)stochastic ...
4
votes
1answer
2k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
0
votes
1answer
16 views

Discrete optimization of weighted sum under constraint

Let $\lambda_1, \dots, \lambda_n \geq 0$, $\;\;c_1, \dots, c_n \in \mathbb{R}$ and $\;\;\gamma >0 $. We are looking for the maximum of function $f$ with $$ f(x) = x_1\lambda_1 + \dots + ...
0
votes
1answer
22 views

Prove that $w/w_0$ (no idle over minimum possible) $\le 2-1/n$ for any set of tasks on an n processor system

$w/w_0 $ $\le 2-1/n$ I've noticed this problem in a couple of discrete math and algorithm analysis textbooks. Many of them prove it for n=2, but I want to prove it for all n. The idea is that we ...
0
votes
0answers
21 views

Optimality Conditions and Optimal Solution to minimize f(x)

just wanted to check my working for a homework problem. Any help would be much appreciated. Write the set of optimality conditions and state the optimal solution for the following mathematical ...
1
vote
1answer
38 views

Why is Mergesort $O(n)$ rather than $O(n\log{n})$?

Assume we want a divide-and-conquer algorithm that finds the max and min of a set $S$ with $n = 2^k$ elements, e.g. mergesort. The recurrence for time complexity is $T(n)=2*T(n/2) +2$, for $n>2$, ...
1
vote
1answer
28 views

Question about optimization

I have a question about maximization/minimization problems. I have noticed that for almost all the practice problems that I have had that ask to find the sum of numbers and minimize product or ...
3
votes
3answers
91 views

Why do lagrange multipliers have the form $\nabla G$

I was studying some multivariable Calculus and we were covering the topic of Lagrange multipliers. I didn't understand exactly why the equations take the form: $$ \nabla f = \lambda \nabla G $$ ...
1
vote
0answers
17 views

Maximizing the frobenius norm subject to constraints $\underset{\mathbf{S}}{\text{maximize }} \|\mathbf{S}\|_F^2$

IF $\mathbf{X=AS}$ where $\mathbf{X} \in R_+^{n \times m}$, $\mathbf{A} \in R_+^{n \times r}$ are known variable and $\mathbf{S} \in R_+^{r \times m}$ is unknown variable, How to solve the below ...
0
votes
0answers
16 views

Are there Karnaugh maps over other algebras?

Karnaugh maps are a useful way to minimize or factorize polynomial expressions in Boolean algebra by considering the smallest combinations of logical "subcomponents" of an expression, whose sum is ...
0
votes
0answers
22 views

connections between polar set, polar cone?

Given a set $S$, its polar cone http://en.wikipedia.org/wiki/Dual_cone_and_polar_cone and its polar set http://en.wikipedia.org/wiki/Polar_set are defined. Could some please tell me the ...
0
votes
0answers
28 views

How can I minimize a quadratic on the unit simplex?

How can I compute $$ \min_{x \in \Delta_n} \frac{1}{2}\lVert Bx\rVert^2 + x^tAy$$ with $x \in \mathbb{R}^n, y \in \mathbb{R}^m, A_{m \times n}$, $B_{n \times n}$ where $\Delta_n$ is the unit simplex ...
2
votes
0answers
24 views

How to maximize the minimal amount not payable with the exchange of at most two coins?

Background I've been thinking about payments which you can do using at most two coins. This includes three possible cases: You pay by giving one coin of the value you owe (for example, if you have ...
0
votes
0answers
18 views

KKT Sufficient condition when optimal solution is intuitively at the boundary

My optimization problem is: $\operatorname{arg\,max}_P \sqrt P$ subject to $P \le \upsilon_\tau$ where $P \in \mathbb{R}^+$ and $\upsilon_\tau \in \mathbb{R}^+$ Intuitively, because $\sqrt P$ is ...
4
votes
1answer
46 views

Lagrange's multiplier not working

Given the function $f(x,y):=xy+x-y$. Let $D:=\{(x,y)\in\mathbb{R}^2:x^2+y^2\leq25\wedge x \geq 0\}$. Find the absolute maximum and minimum of $f$ on $D$. My working is as follows: $\begin{array} ...
3
votes
4answers
513 views

The median minimizes the sum of absolute deviations

Suppose we have a set $S$ of real numbers. Show that $$\sum_{s\in S}|s-x| $$ is minimal if $x$ is equal to the median. This is a sample exam question of one of the exams that I need to take and I ...
1
vote
1answer
39 views

How to maximize $a^2 + \delta^2(s-a)^2$ by inspection?

I need to maximize: $a^2 + \delta^2(s-a)^2$ where: $\delta\in(0,1)$ and $0\le a \le s$. The solution in my text simply states: Since $\delta^2 < 1$ , the maximum occurs when $a=s$. I ...
0
votes
0answers
8 views

optimization of formulas involving binomial coefficients

I encountered such a problem. We need to find the min value and max value of $f(x,y)$. $x$ and $y$ are integers $\in[0,n]\times[0,n]$ and $(x,y)\neq (0,0)$ or $(n,n)$. $$ ...
-1
votes
0answers
19 views

Help understanding the specification of constraints for cvxopt

This is an example from the cvxopt documentation and I am trying to understand how the L2 constraints are specified to the solver. The problem is specified as: ...
0
votes
2answers
774 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
1
vote
2answers
43 views

maximizing a coordinate of $x^T A^T A x \leq r^2$

Given a vector $\mathbf{x} \in \mathbb{R}^n$, a scalar $r\gt 0$ and an invertible matrix $\mathbf{A} \in \mathbb{R}^{n\times n}$, I'd like to maximize one of the components $x_\alpha$ constrained by ...
0
votes
2answers
22 views

Optimization - Maximizing Profit

I have been struggling with the problem below for quite some time now and no one can seem to figure it out, so I am asking it here. The question is as follows: You own an apartment complex with 50 ...
0
votes
0answers
19 views

How can I solve $\min \{ \langle A(x),y\rangle + f(y) \text{ s.t. } y \in S^n, \operatorname{tr}(y) =1, y \geq 0\}$?

I'm trying to solve the problem $$\min \{ \langle A(x),y\rangle + f(y) \mid y \in S^m, \operatorname{tr}(y) =1, y \geq 0\}$$ where $x \in \mathbb{R}^n$, $y \in S^M$, that is, it's a symmetric $m$ by ...
0
votes
1answer
43 views

How to solve $3y\cos(\theta) - 2x\sin(\theta) = 5 \sin(\theta)\cos(\theta)$?

How to solve $3y\cos(\theta) - 2x\sin(\theta) = 5 \sin(\theta)\cos(\theta)$? I am optimizing a function where I need to solve the above equation for $\theta$. What is the best way to do this? I ...
0
votes
1answer
62 views

Maximise $y$ with respect to $x$ for $y=\prod_{k=1}^{\infty}(1-x^{-k})$

$$y=\prod_{k=1}^{\infty}(1-x^{-k})$$ I want to maximise this function. So far I have: $$\ln(y)=\sum_{k=1}^{\infty}\ln(1-x^{-k})$$ ...
0
votes
1answer
42 views

Can this optimization problem be solved analytically?

Can the following be solved analytically? minimize $$ \ V(x) = |x_1-2| + |x_2-2| \ \ ; \ \ [x_1,x_2] \in R^2$$ subject to: $$ h_1(x) = x_1-x_2^2 \ge 0 $$ $$ h_2(x) = x_1^2+x_2^2-1 = 0 $$ I ...
0
votes
1answer
950 views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
0
votes
4answers
37 views

Distance to origin from curve

Hello all I am trying to redo a problem I had and I am stumped for some reasons. I just want to find the maximum and minimal distance from the curve $$7x^2-6xy+7y^2-6=0$$ to the origin. But I want to ...
0
votes
1answer
13 views

Understanding the Derivation of Dual Geometric Programming Problem

Enthusiastic CS major interested in Optimization Theory here. Pardon me for overlooking something obvious. I'm referring to this nice tutorial/ebook: http://faculty.uml.edu/cbyrne/optfirst0.pdf In ...
2
votes
0answers
81 views

Find the minimum value of $P=\frac{\sqrt{3(2x^2+2x+1)}}{3}+\frac{1}{\sqrt{2x^2+(3-\sqrt{3})x+3}}+\frac{1}{\sqrt{2x^2+(3+\sqrt{3})x+3}}$ [duplicate]

Let $x$ be a real number. Find the minimum value of $$P=\frac{\sqrt{3(2x^2+2x+1)}}{3}+\frac{1}{\sqrt{2x^2+(3-\sqrt{3})x+3}}+\frac{1}{\sqrt{2x^2+(3+\sqrt{3})x+3}}$$ This is a problem from 2015 ...
0
votes
0answers
9 views

Maximum of an expression over two sets.

Assume we have an expression, say $G$, and we want to maximize it over a set $E$. Also let $F$ and $F^{'}$ be two disjoint sets with $E = F \cup F^{'}$. How are the following optimization problems ...
0
votes
0answers
30 views

Polynomial optimization and AM-GM inequality

I want to maximize the function $f(\mathbf{x},\mathbf{y}) = \sum \limits_{k=1}^{K}p_k(\mathbf{x})q_k(\mathbf{y})$, where $0 < p_k(\mathbf{x}) \leq \delta_k$ and $0 < q_k(\mathbf{y}) \leq ...
0
votes
0answers
25 views

Trace minimization when some matrix is unknown

The problem is as follows: $\displaystyle\min_{V}$ trace($V^TH^T\Phi HV$)$\\$ s.t. $V^TV=I_d$ in the case when $H$ is not known. When $H$ is known, the solution is given by the eigenvectors ...
1
vote
1answer
418 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
1
vote
1answer
19 views

Semidefiniteness of the Hessian and optimization

This question is for sure a duplicate, but different users seem to give different answers. The question is: suppose you find that the Hessian matrix for a function $f(\textbf{x})$ is semidefinite ...
1
vote
1answer
26 views

Displaying images on Matlab.

I'm working on image denoising problem and I have develop an optimization algorithm in Matlab for this prupose. The images are in a 256 grey level scale so mathematically what I have is a map from ...
1
vote
1answer
22 views

Finding a solution to matrix equation occurring inside an optimization problem

As a part of an optimization problem (while equating the derivative of the cost function to 0), I'm getting the following expression. $$-2XX^TC + 2XX^TACC^T + \gamma GA = 0,$$ where, $X, C, G$ are ...
0
votes
0answers
16 views

Minimizing a function known to have a unique local and global minimum

Quasi-convex functions are a class of functions known to have a unique local and global minimum, which can minimized over convex sets using numerical methods with convergence guarantees. A function is ...
0
votes
0answers
6 views

Distinct Maximizers over a convex set

Let $u,u'\in\mathbb{R}^n$ be linearly independent and $B(x)$ be a smooth convex set (perhaps an $\epsilon$-ball) containing some point $x\in\mathbb{R}^n$. Under what conditions is it true that: ...