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)

1
vote
0answers
75 views
+50

Maximize the largest eigenvalue of a Hermitian matrix constrained by quadratic polynomials

I am looking for a method to maximize under $\mathbf{y}$ the largest eigenvalue of the following Hermitian matrix \begin{equation} S = \left [ \begin{array}{ccc} \mathbf{y}^{H}S_{11}\mathbf{y} ...
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
37 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
87 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 $$ ...
0
votes
1answer
21 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
15 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
25 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 ...
1
vote
0answers
15 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 ...
2
votes
0answers
17 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 ...
0
votes
0answers
20 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 ...
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)$. $$ ...
2
votes
0answers
21 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 ...
0
votes
2answers
20 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 ...
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} ...
1
vote
2answers
41 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
1answer
15 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
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 ...
-1
votes
0answers
18 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
1answer
61 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
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
4answers
32 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 ...
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
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
28 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
22 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
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 ...
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: ...
3
votes
0answers
26 views

Box Optimization: find best boxes for multiple products

I have a company that sells all kind of products and we have many issues with boxes. We are going to buy wholesale volumes, so we need to get the sizes right. We are trying to develop an algorythm ...
0
votes
0answers
17 views

Stuck on polynomial equation in optimization problem

I've been trying to solve an optimization problem, but I am completely stock on one step. I had the following Langrangian: $$\nabla\mathcal{L}(x,\lambda)= e\frac{\sum_{t\in I}e^t \Delta P(t)( x^t ...
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 ...
-3
votes
0answers
29 views

Convex optimization problem [closed]

Can anybody tell me how to convert this to quadratic programming format...?? objective is:- minimize {sum ( $(x(i)-x(j))^2 + (y(i)-y(j))^2$ ) for $j>i$; constraints:- $x(i)+r(i) \leq (1/2)w$; ...
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
2answers
25 views

Finding the critical points of $f(x,y) = x y^2 - x^2 y + x y$

Trying to find the critical points of $f(x,y) = y^2x - yx^2 + xy$. I took partial derivative with respect to x, so $F_x = y^2 - 2xy + y$ $F_x = y(y - 2x + 1)$ Then with respect to y, $F_y = 2xy - ...
0
votes
0answers
25 views

Variational optimization problem with several constraints

I am looking for solutions, approaches or hints to solve this variational optimization problem: Let $f:\mathbb{R}\rightarrow [0,\infty)$ be such that $\int f(x)\,dx=1$ and $\int x\,f(x)\,dx=0$ and ...
-1
votes
1answer
40 views

Find the largest range of values of the step size α for which the algorithm is globally convergent

Consider a fixed-step-size gradient algorithm applied to the following function f. $$ f(x)=1+2x_1+3(x_1^2+x_2^2 )+4x_1 x_2$$ Find the range of values of the step size α for which the fixed step ...
0
votes
1answer
12 views

Question about separability of convex envelopes

Given a function $f(\boldsymbol{x})$ defined on the hypercube $\boldsymbol{x} \in [0,1]^n$. Suppose $f(\boldsymbol{x})$ can be expressed as $f(\boldsymbol{x})=c(\boldsymbol{x})+g(\boldsymbol{x})$, ...
1
vote
1answer
29 views

Recovering the optimal primal solution from dual solution

I'm having trouble finding the optimal primal solution of a particular problem from its dual solution. Primal: $\texttt{Maximize} \ \ 10 x_1 + 24 x_2 + 20 x_3 + 20 x_4 + 25 x_5$ Subject to $x_1 + ...
0
votes
0answers
43 views

The limit of an argmax function

Consider the function $$f(x,n)=x(A-cn)\frac{1-x^{n}}{1-x^{n+1}},$$ where $n\in\{1,2,...\}$, $x\in\mathbb{R}_{\geq0}$, and $A>c>0$. Let $n^{*}(x)=\mbox{argmax}_{n}f(x,n)$ denote the $n$ that ...
1
vote
0answers
16 views

Linear Integer Optimzation Problem (scheduling problem)

Does any of you know how to get this done?
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
10 views

optima; value of a function

Suppose we have the following function $$Err(f) = \frac{1}{2}E|Y-f(X)| = P(Y=1,f(X)=-1) + P(Y=-1,f(X)=1),$$ where $Y, f(X) \in \{-1, 1\}$. How can find the optimal value of the above function, Err? I ...
0
votes
2answers
42 views

Minimize a non-convex function subject to linear dynamics constraint

I want to solve the following problem: $$\min\limits_{\bf u} \frac{\bf c^T {\bf x} (T_f)}{\| \bf c\|\|{\bf x} (T_f)\|}$$ subject to $$\dot{\bf x} (t) = A {\bf x}(t) + B {\bf u}(t)$$ $$x(0) = x_0$$ ...
0
votes
0answers
8 views

Calculating minimum optimization of wall panel leftovers in excel

6,4,2,8,8,3,8,9 Group the following values based on the constraints listed below. Each value can only be used once. There is no limit to the amount of values in a group. The sum of each group must ...
0
votes
1answer
52 views

If g(x) is the maximum value of f(t)

Let f be continuous on [a,b] and define a function g(x) on [a,b] as follows g(a)=f(a) and for a $\lt\ $x $\le\ $b then g(x) be the maximum value of f(t) on [a,x]. Prove that g(x) is continuous of ...
0
votes
6answers
228 views

I am trying to maximize an exponential function [closed]

I am looking for the value of $x$ that will maximize $y$ in the following equation $$ y=e^{-(x-a)^2/b} $$ where $a$ and $b$ are constants. Any help is appreciated