Spelling suggestions: "subject:"primal"" "subject:"grimal""
51 |
Fast Methods for Bimolecular Charge OptimizationBardhan, Jaydeep P., Lee, J.H., Kuo, Shihhsien, Altman, Michael D., Tidor, Bruce, White, Jacob K. 01 1900 (has links)
We report a Hessian-implicit optimization method to quickly solve the charge optimization problem over protein molecules: given a ligand and its complex with a receptor, determine the ligand charge distribution that minimizes the electrostatic free energy of binding. The new optimization couples boundary element method (BEM) and primal-dual interior point method (PDIPM); initial results suggest that the method scales much better than the previous methods. The quadratic objective function is the electrostatic free energy of binding where the Hessian matrix serves as an operator that maps the charge to the potential. The unknowns are the charge values at the charge points, and they are limited by equality and inequality constraints that model physical considerations, i.e. conservation of charge. In the previous approaches, finite-difference method is used to model the Hessian matrix, which requires significant computational effort to remove grid-based inaccuracies. In the novel approach, BEM is used instead, with precorrected FFT (pFFT) acceleration to compute the potential induced by the charges. This part will be explained in detail by Shihhsien Kuo in another talk. Even though the Hessian matrix can be calculated an order faster than the previous approaches, still it is quite expensive to find it explicitly. Instead, the KKT condition is solved by a PDIPM, and a Krylov based iterative solver is used to find the Newton direction at each step. Hence, only Hessian times a vector is necessary, which can be evaluated quickly using pFFT. The new method with proper preconditioning solves a 500 variable problem nearly 10 times faster than the techniques that must find a Hessian matrix explicitly. Furthermore, the algorithm scales nicely due to the robustness in number of IPM iterations to the size of the problem. The significant reduction in cost allows the analysis of much larger molecular system than those could be solved in a reasonable time using the previous methods. / Singapore-MIT Alliance (SMA)
|
52 |
On Some Properties of Interior Methods for OptimizationSporre, Göran January 2003 (has links)
This thesis consists of four independent papers concerningdifferent aspects of interior methods for optimization. Threeof the papers focus on theoretical aspects while the fourth oneconcerns some computational experiments. The systems of equations solved within an interior methodapplied to a convex quadratic program can be viewed as weightedlinear least-squares problems. In the first paper, it is shownthat the sequence of solutions to such problems is uniformlybounded. Further, boundedness of the solution to weightedlinear least-squares problems for more general classes ofweight matrices than the one in the convex quadraticprogramming application are obtained as a byproduct. In many linesearch interior methods for nonconvex nonlinearprogramming, the iterates can "falsely" converge to theboundary of the region defined by the inequality constraints insuch a way that the search directions do not converge to zero,but the step lengths do. In the sec ond paper, it is shown thatthe multiplier search directions then diverge. Furthermore, thedirection of divergence is characterized in terms of thegradients of the equality constraints along with theasymptotically active inequality constraints. The third paper gives a modification of the analytic centerproblem for the set of optimal solutions in linear semidefiniteprogramming. Unlike the normal analytic center problem, thesolution of the modified problem is the limit point of thecentral path, without any strict complementarity assumption.For the strict complementarity case, the modified problem isshown to coincide with the normal analytic center problem,which is known to give a correct characterization of the limitpoint of the central path in that case. The final paper describes of some computational experimentsconcerning possibilities of reusing previous information whensolving system of equations arising in interior methods forlinear programming. <b>Keywords:</b>Interior method, primal-dual interior method,linear programming, quadratic programming, nonlinearprogramming, semidefinite programming, weighted least-squaresproblems, central path. <b>Mathematics Subject Classification (2000):</b>Primary90C51, 90C22, 65F20, 90C26, 90C05; Secondary 65K05, 90C20,90C25, 90C30.
|
53 |
Computational convex analysis : from continuous deformation to finite convex integrationTrienis, Michael Joseph 05 1900 (has links)
After introducing concepts from convex analysis, we study how to continuously transform one convex
function into another. A natural choice is the arithmetic average, as it is pointwise continuous;
however, this choice fails to average functions with different domains. On the contrary, the proximal
average is not only continuous (in the epi-topology) but can actually average functions with
disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic
average) but also inherits smoothness and differentiability (unlike the arithmetic average).
Then we introduce a computational framework for computer-aided convex analysis. Motivated
by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is
closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope.
As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex
PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit
convex hull algorithm.
Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone
operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions
[5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12,
p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can
be formulated as shortest path problems.
|
54 |
On the nonnegative least squaresSantiago, Claudio Prata 19 August 2009 (has links)
In this document, we study the nonnegative least squares primal-dual method
for solving linear programming problems. In particular, we investigate connections
between this primal-dual method and the classical Hungarian method for the assignment problem.
Firstly, we devise a fast procedure for computing the unrestricted least
squares solution of a bipartite matching problem by exploiting the special
structure of the incidence matrix of a bipartite graph. Moreover, we explain
how to extract a solution for the cardinality matching problem from the
nonnegative least squares solution. We also give an efficient procedure
for solving the cardinality matching problem on general graphs using the
nonnegative least squares approach.
Next we look into some theoretical results concerning the minimization of p-norms,
and separable differentiable convex functions, subject to linear constraints
described by node-arc incidence matrices for graphs.
Our main result is the reduction of the assignment problem to a single
nonnegative least squares problem. This means that the primal-dual
approach can be made to converge in one step for the assignment problem.
This method does not reduce the primal-dual approach to one step for
general linear programming problems, but it appears to give a good
starting dual feasible point for the general problem.
|
55 |
On Some Properties of Interior Methods for OptimizationSporre, Göran January 2003 (has links)
<p>This thesis consists of four independent papers concerningdifferent aspects of interior methods for optimization. Threeof the papers focus on theoretical aspects while the fourth oneconcerns some computational experiments.</p><p>The systems of equations solved within an interior methodapplied to a convex quadratic program can be viewed as weightedlinear least-squares problems. In the first paper, it is shownthat the sequence of solutions to such problems is uniformlybounded. Further, boundedness of the solution to weightedlinear least-squares problems for more general classes ofweight matrices than the one in the convex quadraticprogramming application are obtained as a byproduct.</p><p>In many linesearch interior methods for nonconvex nonlinearprogramming, the iterates can "falsely" converge to theboundary of the region defined by the inequality constraints insuch a way that the search directions do not converge to zero,but the step lengths do. In the sec ond paper, it is shown thatthe multiplier search directions then diverge. Furthermore, thedirection of divergence is characterized in terms of thegradients of the equality constraints along with theasymptotically active inequality constraints.</p><p>The third paper gives a modification of the analytic centerproblem for the set of optimal solutions in linear semidefiniteprogramming. Unlike the normal analytic center problem, thesolution of the modified problem is the limit point of thecentral path, without any strict complementarity assumption.For the strict complementarity case, the modified problem isshown to coincide with the normal analytic center problem,which is known to give a correct characterization of the limitpoint of the central path in that case.</p><p>The final paper describes of some computational experimentsconcerning possibilities of reusing previous information whensolving system of equations arising in interior methods forlinear programming.</p><p><b>Keywords:</b>Interior method, primal-dual interior method,linear programming, quadratic programming, nonlinearprogramming, semidefinite programming, weighted least-squaresproblems, central path.</p><p><b>Mathematics Subject Classification (2000):</b>Primary90C51, 90C22, 65F20, 90C26, 90C05; Secondary 65K05, 90C20,90C25, 90C30.</p>
|
56 |
Computational convex analysis : from continuous deformation to finite convex integrationTrienis, Michael Joseph 05 1900 (has links)
After introducing concepts from convex analysis, we study how to continuously transform one convex
function into another. A natural choice is the arithmetic average, as it is pointwise continuous;
however, this choice fails to average functions with different domains. On the contrary, the proximal
average is not only continuous (in the epi-topology) but can actually average functions with
disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic
average) but also inherits smoothness and differentiability (unlike the arithmetic average).
Then we introduce a computational framework for computer-aided convex analysis. Motivated
by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is
closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope.
As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex
PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit
convex hull algorithm.
Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone
operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions
[5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12,
p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can
be formulated as shortest path problems.
|
57 |
Métodos de pontos interiores/exteriores, de restrições canalizadas progressivas e de suavização arco tangente, em problemas de despacho econômico e ambiental / Interior/exterior point methods, progressive bounded constraints and arctangent smoothing methods in Economic/Environmental dispatch problemsSantos, Mariana Rodrigues Barbosa dos [UNESP] 08 June 2016 (has links)
Submitted by Mariana Rodrigues Barbosa dos Santos null (mariana.rsb@gmail.com) on 2016-08-03T17:28:29Z
No. of bitstreams: 1
Mariana Rodrigues Barbosa dos Santos.pdf: 3047570 bytes, checksum: bd1b89dc57eeef6047e27fce6c4c698d (MD5) / Approved for entry into archive by Ana Paula Grisoto (grisotoana@reitoria.unesp.br) on 2016-08-05T17:13:55Z (GMT) No. of bitstreams: 1
santos_mrb_me_bauru.pdf: 3047570 bytes, checksum: bd1b89dc57eeef6047e27fce6c4c698d (MD5) / Made available in DSpace on 2016-08-05T17:13:55Z (GMT). No. of bitstreams: 1
santos_mrb_me_bauru.pdf: 3047570 bytes, checksum: bd1b89dc57eeef6047e27fce6c4c698d (MD5)
Previous issue date: 2016-06-08 / O problema multiobjetivo de despacho econômico e ambiental envolve a minimização de dois objetivos conflitantes: o custo de geração em uma unidade térmica e a emissão de poluentes. Quando a função objetivo custo de geração inclui os efeitos de pontos de carregamento de válvula, esta torna-se não convexa e, além disso, não diferenciável, pois termos modulares que envolvem a função seno são considerados, impossibilitando que métodos clássicos de otimização sejam diretamente empregados à resolução do problema. Neste trabalho é proposta uma nova metodologia de solução de problemas multiobjetivo que envolve o método de restrições canalizadas progressivas, o método de suavização arco tangente e o método primal-dual previsor-corretor de pontos interiores para a determinação de soluções do problema multiobjetivo de despacho econômico e ambiental. O método de restrições canalizadas progressivas transforma o problema multiobjetivo em um conjunto de subproblemas mono-objetivo, considerando a função custo de geração como função objetivo e a função custo de emissão de poluentes como restrição adicional do problema. O método de suavização arco tangente suaviza os termos modulares da função custo de geração quando são considerados os efeitos de pontos de carregamento de válvula e possibilita a utilização do método primal-dual previsor-corretor de pontos interiores à resolução dos subproblemas mono-objetivo determinados pelo método de restrições canalizadas progressivas. Para a aplicação deste método são consideradas as estratégias de pontos exteriores relacionada à função barreira logarítmica modificada e de correção de inércia, as quais permitem ao método, respectivamente, ser inicializado com pontos exteriores à região viável e determinar uma sequência de pontos que converge para mínimos locais dos subproblemas. A metodologia proposta foi implementada em MATLAB 2011a e aplicada aos problemas testes de despacho econômico e ambiental de três, seis, dez, dezenove e quarenta unidades geradoras. Os resultados obtidos demonstram o bom desempenho desta quando comparados aos resultados da literatura. / The multiobjective problem of economic and environmental order involves the minimization of two conflicting objectives: the cost of generation in a thermal unit and the emission of pollutants. When the generation cost objective function includes the effects of valve loading points, it becomes non-convex, and moreover, not differentiable, as modular terms involving the sine are considered to function, making it impossible classical optimization methods are directly employees to solving the problem. This paper proposes a new multi-objective problem-solving methodology that involves the method of progressive bounded constraints, the arctangent smoothing method and the primal-dual predictor-corrector interior point method for the determination of multi-objective solutions to the problem of economic dispatch and environmental. The method of progressive bounded constraints transforms the multi-objective problem into a set of mono-objective sub-problems, considering the role generation cost as objective function and the cost function of emissions as an additional restriction of the problem. The arctangent smoothing method smoothes modular terms of generation cost function when the valve points load effect are considered and enables the use of the primal-dual method predictor-corrector interior point the resolution of single-purpose subproblems determined by method of progressive bounded constraints. For the application of this method are considered the strategies of external points related to the modified logarithmic barrier function and inertia correction, which allow the method, respectively, be initialized with outside points to the feasible region and determine a sequence of points converging to minimum locations of sub-problems. The proposed methodology was implemented in MATLAB 2011a and applied to economic and environmental problems dispatch tests of three, six, ten, nineteen and forty generating units. The obtained results demonstrated the good performance of this compared to literature results.
|
58 |
Computational convex analysis : from continuous deformation to finite convex integrationTrienis, Michael Joseph 05 1900 (has links)
After introducing concepts from convex analysis, we study how to continuously transform one convex
function into another. A natural choice is the arithmetic average, as it is pointwise continuous;
however, this choice fails to average functions with different domains. On the contrary, the proximal
average is not only continuous (in the epi-topology) but can actually average functions with
disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic
average) but also inherits smoothness and differentiability (unlike the arithmetic average).
Then we introduce a computational framework for computer-aided convex analysis. Motivated
by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is
closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope.
As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex
PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit
convex hull algorithm.
Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone
operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions
[5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12,
p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can
be formulated as shortest path problems. / Graduate Studies, College of (Okanagan) / Graduate
|
59 |
Studies on Optimization Methods for Nonlinear Semidefinite Programming Problems / 非線形半正定値計画問題に対する最適化手法の研究Yamakawa, Yuya 23 March 2015 (has links)
京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19122号 / 情博第568号 / 新制||情||100(附属図書館) / 32073 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 山下 信雄, 教授 太田 快人, 教授 永持 仁 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM
|
60 |
Congestion control in packet switch networksKamga, Morgan 10 December 2008 (has links)
We consider a congestion control problem in computer networks. The problem
is posed as an optimal control problem and reduced to a problem of
finding solutions to delay differential equations. Systems involving time delays
in the dynamics are actually very difficult to model and therefore very
difficult to solve. We consider three approaches in our congestion control
problem: an elastic queue approach leading to an optimal control problem
with a state–dependent delay differential equation; three approaches in flow
models (also leading to systems containing delay differential equations), precisely
the dual control approach, the primal–dual control approach and the
control approach based on queueing delay. The elastic queue approach is not
explored due to the lack of software good enough to solve optimal control
problems involving delay differential equations.
In flow models, we consider the standard case, that is where the feedback
from sources to links is exact and the network behaves perfectly well (without
any unexpected event). We also consider some non–standard cases such as
the case where this feedback contains errors (for example overestimation,
underestimation or noise), and the case where one link breaks in the network.
We numerically solve the delay differential equations obtained and use the
results we get to determine all the considered dynamics in the network.
This is followed by an analysis of the results. We also explore the stability
of some simple cases in the dual control approach, with weaker conditions
on some network parameters, and discuss some fairness conditions in some
simple cases in all the flow model approaches. Non–standard cases are also
solved numerically and the results can be compared with those obtained in
the standard case.
|
Page generated in 0.0734 seconds